# Question
Title: Find perfect matching whose weight is minimal, in polynomial time
Given a bipartite graph $G=(A,B,E)$ and a weight function $w: E \rightarrow\mathbb{R}^+$, I'd like to find a perfect matching $M\subseteq E$ with min. weight. I'm assuming $|A| \leq |B|$, and WLOG $G$ is a complete graph (else give weight $\infty$ to non-existing edges).

Giving a variable $x\_{i,j}$ for each $a\_i\in A$ and $b\_j\in B$, I wrote the following IP:

$$ \min{\Sigma\_{i,j} w(a\_i,b\_j)\cdot x\_{i,j}} $$

$\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,$**subject to** $\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\, \Sigma\_{j} x\_{i,j}=1$ (for each $a\_i\in A$)

$\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,$$\\,\\,\\, \Sigma\_{i} x\_{i,j}\leq 1$ (for each $b\_j\in B$)

$\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,$$\\,\\,\\, x\_{i,j}\in \\{ 0,1 \\}$

Assuming I have the IP solution, it's obvious how to construct a min weight matching.

The only problem is that solving an IP problem is NP-Hard. Thus, I wrote the following (very similar) LP:

$$ \min{\Sigma\_{i,j} w(a\_i,b\_j)\cdot x\_{i,j}} $$

$\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,$**subject to** $\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\, \Sigma\_{j} x\_{i,j}=1$ (for each $a\_i\in A$)

$\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,$$\\,\\,\\, \Sigma\_{i} x\_{i,j}\leq 1$ (for each $b\_j\in B$)

$\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,\\,$$\\,\\,\\, x\_{i,j}\geq 0$

I've seen a proof that the IP solution value equals the LP solution value, but I'd like to find something else, I'm looking for a way to round a LP solution such that it'd be an IP solution, with the same min value!

I thought about starting from any $A$-vertex $a\_i$ that doesn't have a edge with $x\_{i,j}=1$. Assume $(a\_i,b\_j$ is the minimal weight edge for $a\_i$, go to $b\_j$ and check if $(a\_i,b\_j)$ is the min weihgt for $b\_j$ too. If it is, give $x\_{i,j}\leftarrow 1$ and the rest of $x\_{i,j^{'}}$ and $x\_{i^{'},j}$ value $0$. One problem is that I have no control over what this might affect on other vertices, meaning some other equations may not be equal $1$ now. The second problem is that if it's not the min weight for $b\_j$ - so I'll have to keep going on and on, but I know that sooner or later I'll either find a pair whose min weight edge is the same or go into a cycle and that'd be a contradiction. But either way, the first problem I said already makes this useless.

Any ways to improve this method? Or perhaps other suggestions?

Thanks!

# Answer
Yes, there is a polynomial-time algorithm for your problem. There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods. In particular, we can solve your problem by a reduction to the assignment problem, i.e., to computing a maximum weight matching in a weighted bipartite graph.

Suppose we have a bipartite graph with weights on the edge, and we want to find a perfect matching whose total weight is as large as possible. Call this the maximum-weight perfect-matching problem. You can solve this problem as follows. Pick a large constant $C$ (sufficiently large); replace the weight $w$ on each edge with $w+C$ (i.e., add $C$ to each edge weight). Now find the maximum weight matching in the resulting graph using the Hungarian algorithm or any other algorithm for maximum weight matching. (Here the key fact we are using is that a maximum weight matching can be found in polynomial time.)

I claim that the resulting matching will be a perfect matching, if one exists. Why? Well, if a perfect matching exists, then its weight will be $Cn+\delta$, where $n$ is the number of edges in a perfect matching and $\delta$ is something bounded (it's the sum of $n$ weights from the original graph). The weight of any non-perfect matching will be at most $C(n-1)+\delta'$, where $\delta$ is something bounded (it's the sum of at most $n-1$ weights from the original graph). Suppose $C$ is at least $2n$ times the largest of the absolute values of the weights of the original graph. Then $Cn+\delta$ will always be larger than $C(n-1)+\delta'$, or in other words, any perfect matching will have greater total weight than any non-perfect matching. It follows that the Hungarian algorithm on this modified graph will find the maximum-weight perfect matching in the modified graph, and this corresponds to the maximum-weight perfect matching in the original graph (since we added the same constant to the weight of every edge).

So, there is a polynomial-time algorithm to find the perfect matching whose total weight is maximized. Given this, we can solve your problem (find the perfect matching whose total weight is minimized) by simply negating all of the edge weights.
> 7 votes

---
Tags: graphs, optimization, bipartite-matching, matching, integer-programming
---


# Question
Title: How can I evaluate an algorithm for a NP-Hard problem?
I have written a program to calculate the number of stable partition in a graph. ( That is: find which partition of the nodes does not have edges between nodes of the same block. )

The professor, asked me a way to evaluate the performance of my algorithm (not the program), but my algorithm is simply a brute force of all the possible cases, and I don't think you can do any better without heuristics, therefore I think the questions makes no sense (at least to me).

Am I wrong?

# Answer
> 4 votes
There are plenty of ways to go about dealing with NP-hard problems.

Even if you know the asymptotic upper bounds on worst-case runtime (more you usually don't get), you don't have information about

* the *typical* case and
* the precision of your bound.

In the absence of exact analyses, all you can do is run the algorithm on a representative sample of inputs and compare it to others.

To be clear, even though your algorithm has bad $O$-runtime (in the worst case) it does not always take this long to finish. Go find out!

Conducting meaningful runtime experiments is not trivial, and often done horribly wrong in the literature. I can recommend (the affordable) *A Guide to Experimental Algorithmics* by C.C. McGeoch (2012) for an introduction.

# Answer
> 6 votes
It doesn't matter for what the algorithm is for, that is, you can analyze an algorithm for an easy problem (e.g. sorting) just like you would analyze an algorithm for a hard problem (e.g. 3-SAT). So the question *does* make sense.

Think about how your brute force method works. If you try all partitions of nodes, how many possible partitions are there? This is the way your analysis should work. Given that the problem is NP-hard, one should not expect a polynomial time algorithm though, but that's fine.

# Answer
> 0 votes
Maybe your professor is asking you to implement and run your algorithm and evaluate the time it takes in different sizes of instances. As is brute force, maybe you can't go away to more than 20 vertices, but is still a good excercise.

---
Tags: graphs, algorithm-analysis, performance
---


# Question
Title: How can Weighted MaxSAT be in $FP^{NP}$ when dealing with large weights?
Weighted MaxSAT is in $\mathrm{FP^{NP}}$, see \[1\] Theorem 17.4, i.e. Weighted MaxSAT can be solved with at most a polynomial number of calls to a SAT oracle.

The proof in \[1\] makes use of binary search with a search space from weight $0$ to the sum of all weights. But I am struggling with the fact that the weights could very large. For example: Let $\\{c\_1, ..., c\_m\\}$ be a set of clauses where some clause $c\_i$ has weight $w\_i = 2^{2^{m}}$. Then binary search will take $log\_2(2^{2^{m}}) = 2^m$ steps in the worst case, which is exponential in the input length $m$.

What am I missing?

Reference: \[1\] Papadimitriou - Computational Complexity (1994)

# Answer
The input length is not $m$. To represent an integer of $2^{2^m}$, one needs $\log\_2{2^{2^m}}=2^m$ bits. Hence an algorithm taking $2^m$ steps is considered linear in the input length, which is $2^m$.

A number like $2^{2^m}$ can be represented by just giving $m$, but it is usually assumed that numbers are given in binary. And the result that MAX-SAT is in $FP^{NP}$ only holds when that encoding is used.
> 3 votes

---
Tags: complexity-theory, np-hard
---


# Question
Title: Efficient way to calculate sum in sliding window?
Assume you have a grid as below:

The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the window should not cross the boundaries of the grid.)

For each such position I want to calculate the sum of the cells in the window. I'd like to be able to do this with different sizes of windows as well. More specifically, given some range for the possible widths and possible heights of windows, I want to calculate and store all the sums over the cells in the window, for all positions of the window, and for all possible width/height combinations.

As an example: if the possible widths are 2 and 3 and the possible heights are 4, 5 and 6, then there are 6 combinations: $2 \times 4$, $2 \times 5$, $2 \times 6$ $3 \times 4$, $3 \times 5$, $3 \times 6$ and for each such sliding window size, I want to store the sums over cells in the sliding window for all possible positions of the sliding window.

What would be an efficient way to do this?

Cheers

# Answer
> 5 votes
One possible way would be to store the sum of all the submatrices of the form $((0,0),(i,j))$. You can compute each of these sums in $O(1)$ time per entry (by using the previous entries).

If you then want to know the sum of the submatrix $((x,y),(i,j))$, you can compute this in $O(1)$ from the stored sums using inclusion-exclusion. If we let $S$ denote such a sum, then

$$S((x,y),(i,j))=S((0,0),(i,j))-S((0,0),(x,j))-S((0,0),(i,y))+S((0,0),(x,y))$$

---
Tags: algorithms, efficiency, arrays
---


# Question
Title: What is the difference between assignment, valuation and name binding?
I read that Name binding assigns some value (data/code/expression) to an identifier. Assignment and valuation seem to do the same thing. It is confusing. Can I just tell that free variable is one, which was not assigned a value whereas bound variable has its value assigned?

# Answer
> 8 votes
Binding has to do with giving names to things (or values) in a given well delimited context. Assignment is about storing things (or values) in some location (a variable). Another assignment can replace a previous value with a new one. Valuation consist in binding all the identifiers of a formal text with something (with a value). In mathematics these identifiers are often called variables, which causes a confusion with the concept of variable (i.e. memory storage) in computer science.

## Trying to give more intuitive details

Name binding attaches a meaning to identifiers within some part (called scope) of the concerned mathematical or programming text. This meaning can indeed be seen as a value in some domain when the text is interpreted.

For example, if you declare `foo` as an integer variable, the value attached to `foo` within the scope is an integer variable. An integer variable may be seen informally a a container that can carry an integer value, which may be changed. You can also see it as the address of a place in memory where the content may be stored.

But if you declare `foo` as the integer 25, then whithin the scope, any use of `foo` is identical to a use of 25. If you declare foo as an integer constant, it cannot change and thus its value must be specified.

Binding is attaching a name to some value that does not change within the scope of the name. An example is a legal documents stating that "`for the purpose of this document, Mr. Brown, and the Smith family shall be called the beneficiary.`" The scope is the legal document. And everywhere in the document, the use of the word `beneficiary` means Mr. Brown, and the Smith family. You can see it as a definition of a local terminology. It has to do with giving names to things. Binding is about speaking, reading or writing. It is not about executing or moving values around: that corresponds to assignment.

A variable may be seen as a chunk of memory that can contain a value, When you have a variable, you can change the value contained in this variable contains with an assignment. If `foo` is bound to (or denotes) a variable in the current scope, you can assign a value to `foo`, i.e. to the variable denoted by `foo`, or read the value contained in that variable. And you can change that value with a new assignment.

So binding is an operation that tells what is the meaning of names in the text of the program or of the mathematical discourse. It is static, in the sense that the text does not change. But assignment is a programming concept that consist is storing a value in a variable, i.e. a container, which is usually a place in memory. It is a dynamic concept related to how (representations of) values are stored in memory, which changes as the program progresses.

Note that a variable may exist independently of any name to which it could be bound. This is the case for an element of an array, to take a simple example.

In various contexts, one may consider expressions or texts that use names that have not been defined. For example you can write $(a^2-b^2)/(a-b)$ which is an arithmetic expression. Then you may valuate the variables by associating an environment (you may read approximately a scope) where the variables $a$ and $b$ are bound to some values, for example 3 and 12, and be interested in the value taken by the exression. A valuation is such an association of a set of names, each with a specific value. The name valuation is used more in formal mathematics, while assigment is a programming concept.

---
Tags: terminology, programming-languages, variable-binding
---


title: Not Hamiltonian is in NP Class?

text:
# Question
Title: Not Hamiltonian is in NP Class?
I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest.

From this book and other study in complexity theory, I have seen the following statement:

> The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is an open question whether the following problem belongs to NP: given a graph G, is it true that G is not Hamiltonian?

However, I was wondering if this this problem was NP-Complete. Could someone let me know if the following statement true?

> Determining a that a Graph is not Hamiltonian is in NP-Class.

I read another book on this book on end of page 306, the authors wrote this is NP-Hard. anyone could clarify me?

# Answer
> 4 votes
The statement

> Determining a that a Graph is not Hamiltonian is in NP-Class.

is neither true nor false. It doesn't have a truth value, since there's a type mismatch. Similarly, the statement

> The color red is in NP.

is neither true nor false.

Here is something which is true. Let $L$ be the language of all Hamiltonian graphs. That is, $x \in L$ if $x$ encodes a Hamiltonian graph. (We fix the encoding once and for all.) The language $L$ is in NP since to prove that $x \in L$, one just needs to present a Hamiltonian circuit (a proof whose size is polynomial in the input size), and this proof can be verified in polynomial time.

Furthermore, $L$ is NP-complete. The book you're consulting probably has a proof. Therefore, if $L$ were in coNP, then NP=coNP, which is believed to be false. So it is probably the case that $L$ is not in coNP. But we don't know for sure.

The language $L'$ of non-Hamiltonian graphs is the complement of $L$ (modulo boring technicalities arising from the fact that not every string encodes a graph). Since $L$ is NP, $L'$ is in coNP. We can also see it directly: to prove that $x \notin L'$, one just needs to present a Hamiltonian circuit.

Furthermore, $L'$ is coNP-complete, since $L$ is NP-complete. Again, it is probably the case that $L'$ is not in coNP, since otherwise NP=coNP, which is believed to be false.

---
Tags: complexity-theory, graphs, np-complete, np-hard, decision-problem
---


title: Reduction to $n\log n$ time problem

text:
# Question
Title: Reduction to $n\log n$ time problem
If a problem $A$ is poly-time reducible to a problem $B$ ($A \<\_\mathrm{p} B$), and $B$ can be solved in time $O(n\log n)$, can $A$ also be solved in time $O(n\log n)$?

# Answer
> 7 votes
You can't guarantee that $A$ can also be solved in time $O(n\log n)$ because the reduction from $A$ to $B$ might require more time than that (for example, $n^3$ steps).

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


title: Logic and Functional programming

text:
# Question
Title: Logic and Functional programming
I have a subject *Introduction to logic and functional programming* but the course is not provided in detail. This is the provided course.

> Introduction to declarative programming paradigms. The functional style of programming, paradigms of development of functional programs, use of higher order functional and pattern matching. Introduction to lambda calculus. Interpreters for functional languages and abstract machines for lazy and eager lambda calculi, Types, type- checking and their relationship to logic. Logic as a system for declarative programming. The use of pattern-matching and programming of higher order functions within a logic programming framework. Introduction to symbolic processing. The use of resolution and theorem-proving techniques in logic programming. The relationship between logic programming and functional programming.

I want to ask that, I have the *SICP* book. Will it be enough for the preparation of course?

For example: I don't know what topic can be under *The functional style of programming, paradigms of development of functional programs*.

Please guide me if anyone can in a proper direction. I cannot ask teachers as there are none for this subject.

# Answer
> 1 votes
My suggestion is in preparation for this course, to try and read some beginners guides on pure functional programming language. Having some practical experience actually doing some functional programming before learning the theory could be beneficial.

I learned functional programming with F# which might not be the best idea, since it is a hybrid language and allows you to do a lot of imperative programming in between.

My suggestion is to get into either SML or Haskell and try to translate some imperative programs into functional programming to get an idea of how it feels to work with it.

Logic programming is a whole other beast and I think it is probably best to go the other way around with this, since it is really difficult to understand the programs without some basic knowledge of Data Logic.

---
Tags: reference-request, functional-programming, education, logic-programming
---


# Question
Title: Collecting and combining data from iterative DFS on read-only trees
I am iterating over a tree through an API. This API provides a list of nodes sorted in post order DFS. I need to gather data for each node in the tree, combine that data with the parent's data (according to some heuristic not just a simple arithmetic accumulation). Another way to look at this, is that each node in the tree gathers data about its children and combines it to make its own data. Its parent, in turn, will use this data and combine it with its children.

There is no way to annotate the tree with the intermediate data. (No write permissions) Somehow, I need to associate each node of the tree with some data. One approach would be to use a map of some sort. The issue is that these N nodes do not have ids from 0 to N, so the map could introduce a O(Nlog(N)) complexity in an algorithm that should just be O(N).

Intuitively and by running a few examples, I can up with the pseudo code below.

```
StackOfData stack
for each node in post ordered list
  data=initialize()
  # Sibling order does not matter,
  # all we care is popping the stack once for each child
  for each child of node
    childData = stack.pop()
    data = combine(data,childData)
  end

  mydata = node.extractData()
  data = combine(data, mydata)
  stack.push(data)
end

```

I am not so much looking for alternate ways of solving this problem. I am solely trying here to fill an academic void.

My question is : Is there some theoretical proof to substantiate the above pseudo-code?

Thanks for the help.

# Answer
You can build a "shadow tree": a tree *you* build up, where each node of your node has a pointer to the corresponding node in the API's tree. Basically, you do a deep copy of the API's tree. Now you'll have write permission to your copy, so you can now augment/annotate each node with any additional information you want. At this point you can do the linear-time bottom-up traversal to annotate all the nodes and aggregate the data.

The total running time will be linear in the size of the original tree ($O(N)$, not $O(N \log N)$).
> 0 votes

---
Tags: algorithms, trees, stacks
---


title: SAT for arithmetic

text:
# Question
Title: SAT for arithmetic
Given two integers $X$ and $Y$, each can be encoded in binary $X=(x\_4 x\_3 x\_2 x\_1)$ and $Y=(y\_4 y\_3 y\_2 y\_1)$, how do I encode each one of the constraints

$$|X-Y|\geq n \quad\text{and}\quad|X-Y|= n$$ when $n$ is a given natural number (say, 10) as a boolean formula over $x\_1,\dots, x\_4, y\_1, \dots, y\_4$?

# Answer
Here is the general approach to this type of question.

1. You write a boolean combinatorial circuit to express the constraint. In other words, you write a circuit $C$ that takes as input the values of your variables (e.g., $X$, $Y$) and outputs true or false. Your circuit $C$ should be designed to output true if the inputs satisfy all of your constraints, or false if they don't. Your circuit can use standard boolean gates, e.g., AND, OR, NOT, XOR, and so on.
2. You use the Tseitin transform to convert this to an instance of SAT. (Basically, this is using the standard reduction from CircuitSAT to SAT that's implicit in Cook's theorem.)
3. You feed the SAT formula to a SAT solver, and ask it to find for you a set of inputs that satisfies the formula you got in step 2 (i.e., that satisfies all your constraints).

Alternatively, some SAT front-ends and SMT solvers will help do these steps for you, which saves some effort. For instance, STP lets you express your constraints directly as arbitrary expressions containing AND, OR, NOT, XOR, etc. (so it does steps 2 and 3 for you). It also has some convenient syntactic support for constraints that use integer arithmetic, so it will make step 1 easier for you as well. Another example of such a solver is Z3.
> 4 votes

---
Tags: satisfiability, arithmetic, sat-solvers
---


title: Morgenstern proof for FFT lower bound

text:
# Question
Title: Morgenstern proof for FFT lower bound
I looked at my notes from a class about fast forier transform , and the professor proved in class theorem thanks to Morgenstern , first he defined linear algorithm as a algorithm that inly uses multiplications by scalar and addtions, that he stated Morgenstern's theorem the following way

> Every linear algorithm that computes DFT (Discrete Fourier Transform) , in which the scalar are bounded in their absolute value by $C$ , takes at least $\Omega\_C(n\log{n})$ addition operations.

I haven't understood his proof , if someone can give me guidlines to the proof I'll be more than happy :) \[right now my proof of the theorem looks like a mess\]

p.s.: In class he said we will write in each step the coeffiecents of the linear function that was just computed , then he defined a "computation advancment function" , I didn't understand his definition of this function , it was definied something like $\phi(k)=$ maximum determinant of n$\times$n matrices that were computed untill the k'th step \[I probably copied wrong\]

# Answer
> 5 votes
Morgenstern first defines the notion of a linear algorithm. A linear algorithm gets as input $x\_1,\ldots,x\_n$ and its goal is to compute some $y\_1,\ldots,y\_m$, each of which is a (specific) linear combination of $x\_i$s. The algorithm proceeds in steps, starting with step $n+1$. At step $t$, the algorithm computes $x\_t = \lambda\_t x\_i + \mu\_t x\_j$ for some $i,j \< t$. At the end of the computation, for each $i$, $y\_i = x\_j$ for some $j$.

For example, here is an algorithm computing the unnormalized DFT on 2 variables: $$ x\_3 \gets x\_1 + x\_2 \\ x\_4 \gets x\_1 - x\_2 $$ Similarly, the unnormalized two dimensional DFT on $2^2$ variables is computed by: $$ x\_5 \gets x\_1 + x\_2 \\ x\_6 \gets x\_1 - x\_2 \\ x\_7 \gets x\_3 + x\_4 \\ x\_8 \gets x\_3 - x\_4 \\ x\_9 \gets x\_5 + x\_7 \\ x\_{10} \gets x\_5 - x\_7 \\ x\_{11} \gets x\_6 + x\_8 \\ x\_{12} \gets x\_6 - x\_8 $$

We can view each $x\_t$ as an $n$-dimensional vector which gives the linear combination of $x\_1,\ldots,x\_n$ producing $x\_t$; call this vector $v\_t$. The vectors $v\_1,\ldots,v\_n$ are just the $n$ basis vectors.

Morgenstern defines the quantity $\Delta\_t$, which is the maximum magnitude of the determinant of any square submatrix of the matrix $V\_t$ whose rows are $v\_1,\ldots,v\_t$.

**Lemma.** Let $c \geq 1/2$. If $|\lambda\_s|,|\mu\_s| \leq c$ for all $s$ then $\Delta\_{n+t} \leq (2c)^t$.

**Proof.** The proof is by induction on $t$. When $t = 0$, this is easy to verify directly since $V\_n$ is just the identity matrix. Consider now any $t \> 0$. Every square submatrix of $V\_t$ is either a square submatrix of $V\_{t-1}$, in which case its determinant is at most $(2c)^{t-1} \leq (2c)^t$ by induction, or it involves the new row $v\_t = \lambda\_t v\_i + \mu\_t v\_j$. In the latter case, we can write the square submatrix $A$ as $A = \lambda\_t B + \mu\_t C$, where $B,C$ are square submatrices of $V\_{t-1}$ (replace the relevant part of $v\_t$ by the corresponding parts of $v\_i$ and $v\_j$). Since the determinant is a linear function of any of its rows, $\det(A) = \lambda\_t \det(B) + \mu\_t(C)$. By induction, $|\det(B)|,|\det(C)| \leq (2c)^{t-1}$, and so $$|\det(A)| \leq |\lambda\_t| |\det(B)| + |\mu\_t| |\det(C)| \leq c(2c)^{t-1} + c(2c)^{t-1} = (2c)^t.$$

**Corollary.** Computing the DFT on $n$ variables using a linear algorithm with bounded coefficients requires $\Omega(n\log n)$ steps.

**Proof.** The determinant of the DFT matrix is $n^{n/2}$. Hence any linear algorithm computing the DFT in $t$ steps satisfies $\Delta\_t \geq n^{n/2}$. If the bound on the coefficients is $c$, then the lemma shows that $(2c)^t \geq n^{n/2}$ and so $t = \Omega(n\log n)$.

**Remark.** Strassen has shown that any algebraic algorithm (algorithm involving $+,-,\cdot,/$) for computing the DFT can be transformed to a linear algorithm using the same number of steps.

# Answer
> 0 votes
Morganstern's original paper is here:

Jacques Morgenstern. Note on a lower bound on the linear complexity of the fast Fourier transform. J. ACM, 20(2):305–306, April 1973.

---
Tags: lower-bounds, fourier-transform
---


# Question
Title: How to find the Branch factor of 8 Puzzle
I would like to know how to find the average *branching factor* for 8 puzzle.While referring *Artificial Intelligence* by George F Luger it says that:

> Suppose,for example we wish to establish the branching factor of the 8-puzzle.We calculate the total number of possible moves: 2 from each corner for a total of 8 corner moves,3 from center of each side for a total of 12, and 4 from the center of the grid for a grand total of 24.This divided by 9,the different possible locations of the blank, gives an average branching factor of 2.67.

Why do we have to divide by 9(possible locations of the blank space) to get the average branching factor.I'm confused with how the blank space affects the branching factor?

# Answer
The average branching factor is defined as :

*On average, how many moves can you do, from a given position.*

For some positions (corners 4x), you have 2 moves. For other positions (sides 4x), you have 3 moves. Lastly, for some position (centers 1x), you have 4 moves.

So, a weighted average gives you $$4 \cdot 2 + 4 \cdot 3 + 1 \cdot 4 \over 4 + 4 + 1$$

The blank space affects the branching factor of a given position by limiting the number of moves you can make.
> 4 votes

# Answer
The relevance of the blank space is that a move is encoded by the transition of the blank space. So for example, if the blank space is in the center we have 4 possible moves:

---

This is what the author is talking about when he says

> "2 from each **corner** for a total of 8 corner moves."

The blank space is what's in the corner. Here's one of the 4 possible corner positions:

As you can see, when the blank space is in the corner there are two possible transitions.

Continuing,

> "3 from **center of each side** for a total of 12"

There are 4 centers of a side and each has 3 possible transitions.

I hope this combined with Jeffrey's weighted average explanation answers the question.
> 5 votes

---
Tags: algorithm-analysis, combinatorics, search-algorithms, branch-and-bound
---


# Question
Title: Finding a maximal independent set in parallel
On a graph $G(V,E)$, we do the following process:

* Initially, all nodes in $V$ are uncolored.
* While there are uncolored nodes in $V$, each uncolored node does the following:
    + Selects a random real number and sends it to all its neighbours;
    + Compares its number to the number of its neighbours; if its own number is strictly smallest, then the neighbour paints itself red and notifies all its neighbours.
    + If a neighbour became red, then this node paints itself black.

For example:

* Suppose the graph is a path: a-b-c-d-e.
* Suppose the numbers in the first step are: 1-2-0-3-4.
* Nodes a and c are painted red; nodes b and d are painted black.
* In the second step, only node e remains uncolored; it is trivially minimal so it paints itself red.

MY QUESTION IS: what is the average number of steps that this process takes before all nodes are colored?

My current calculation leads me to an $O(1)$ estimate, which seems too good to be true. Here is the calculation:

Consider a node $v$ with $d$ neighbours. The probability that $v$ will be the smallest among its neighbours is $1/(d+1)$. If this happens, then $v$ and all its neighbours will be colored. So the expected number of vertices colored each step is $(d+1)/(d+1)=1$ *per node*. Hence the total expected number of vertices colored each step is $O(n)$, so in $O(1)$ time all nodes will be colored.

If this analysis is wrong (which is probably the case), then what is the actual number of steps?

EDIT: As noted by @JukkaSuomela, the algorithm described above is due to Metivier et al, 2011 and is explained and analyzed in these lecture notes. They prove that the run time is $O(\log n)$.

But, I am still not convinced that this analysis is tight. In all graphs I checked, it seems that the algorithm completes in $O(1)$ expected time.

My question is now: what is a worst-case graph in which this algorithm indeed requires $O(\log n)$ steps in average?

# Answer
There is a minor mistake, the probability of $v$ being minimal is $1/(d+1)$. That doesn't change anything, but it is still worth pointing out.

The problem is that the events you are summing aren't disjoint. Consider two vertices that aren't adjacent but have a common neighbour. If both vertices end up being minimal amongst their neighbours, then the common neighbour gets counted as being coloured twice.

We need to examine what happens in a vertex more closely. Let's compute the probability (and thus expectation of the indicator variabele) of a single vertex getting coloured.

Assume for the sake of analysis that the graph is $d$-regular and contains no triangles or squares. We will compute the chance that a given vertex $v$ does *not* get coloured. There are $d+1$ possibilities: the $v$ might be the smallest amongst it neighbours, $v$ might be the second smallest, third smallest, and so on... We are not interested in the case that it is the smallest, since then it gets coloured.

If $v$ is the second smallest, there is one vertex that is smaller. The probability of this vertex being smallest amongst its neighbours is $\frac{1}{d}$ (and thus $v$ getting coloured). The probability of the remaining neighbours being smallest amongst their neighbours is 0 (since $v$ is smaller). The total probability (of $v$ *not* getting coloured) from this case is $\frac{1}{d+1}\cdot\frac{d-1}{d}$.

If $v$ is third smallest, there are two smaller vertices. The probability from this case is $\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$.

Continuing on like this, we find that the probability that $v$ does *not* get coloured is $\frac{1}{d+1}\Sigma\_{i=1}^d (\frac{d-1}{d})^i$. The probability of a given vertex getting coloured is thus $1-\frac{1}{d+1}\Sigma\_{i=1}^d (\frac{d-1}{d})^i$. As $d\to \infty$, the probability becomes $\frac{1}{e}\approx 0.368$.

Hence the probability that a given vertex gets coloured is a constant, so the expected number of vertices that gets coloured in the first step is indeed $O(n)$.

That does not make the algorithm $O(1)$. Assuming the probability stays constant (which is not entirely justified considering nodes get coloured and no longer participate in the algorithm, the graph does not remain $d$-regular), in the $k$-th step there will be (in expectation) ${(\frac{1}{e})}^kn$ uncoloured nodes. The decay is exponential, so the algorithm takes $O(\log n)$ steps.

Perhaps somebody else will be able to offer a more precise analysis, but from my argumentation it seems likely the algorithm is $O(\log n)$.
> 3 votes

---
Tags: algorithm-analysis, graphs, distributed-systems, parallel-computing, randomized-algorithms
---


# Question
Title: Applications of Lamport's Distributed Mutual Exclusion algorithm
I'm trying to understand the relevance of the Lamport distributed mutual exclusion algorithm (or any of its variants), where a group of processes cooperate to gain exclusive access to a resource without relying on a centralized coordinator.

How can this be useful in practice? For instance, if the resource is something like a printer, or a shared file system, it can enforce mutual exclusion on its own, so there is no need for a distributed algorithm. I can't think of an example where this wouldn't be the case. What am I missing?

# Answer
Lamport introduced his distributed mutual exclusion algorithm as an example in

> Lamport, Leslie: Time, Clocks and the Ordering of Events in a Distributed System, *Communications of the ACM*, 21(7):558-565, 1978.

The link leads to Lamport's personal page, where he has an annotated bibliography of all his work, with PDFs of every paper that has an electronic version.

The paper in question is the one that introduced Lamport timestamps and Lamport clocks. Here's what Lamport has to say about the distributed mutual exclusion algorithm:

> It didn't take me long to realize that an algorithm for totally ordering events could be used to implement any distributed system. A distributed system can be described as a particular sequential state machine that is implemented with a network of processors. The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system. So, I wrote this paper, which is about how to implement an arbitrary distributed state machine. As an illustration, I used the simplest example of a distributed system I could think of--a distributed mutual exclusion algorithm.

The relevance is not that you would use it to protect some kind of centralized resource. The relevance is rather to show that when you are implementing a distributed state machine, you can actually get all the participants to agree about something, so you don't *need* centralized resources.
> 5 votes

---
Tags: algorithms, distributed-systems
---


# Question
Title: Finding the lightest simple path in trees with integer weights
A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest paths where the length of the path is equal to sum of all edges weights.

I know that in a tree there is only one simple path between every pair of nodes. So, even if you try every pair of nodes finding the path between then, you would have an $O(n^3)$ algorithm.

A better way is to find for every node the cost to every other node in a single visit. This lowers the algorithm to $O(n^2)$.

Is there any algorithm that runs in linear time?

# Answer
> 1 votes
Order the tree, so we can speak about a node and its subtrees. Now evaluate the tree recursively. In each node keep track of two values: (1) the value of the optimal path below the node (starting and ending somewhere below in the subtrees), and (2) the value of the optimal path below that additionally ends in the node itself.

# Answer
> 1 votes
Since trees are *acyclic* graphs, we can find longest and shortest (simple) paths, with or without negative weight with the same basic algorithmic idea, changing only which path to prefer.

Hence, this recursive solution for finding the diameter of trees carries over with minor changes.

---
Tags: algorithms, algorithm-analysis, search-algorithms, trees, shortest-path
---


title: Use of Big-Oh in Worst case

text:
# Question
Title: Use of Big-Oh in Worst case
If it is given that a program has a worst case running time of $O(n)$, then is it still okay to define the running time as being $O(n^2)$. By definition, this seems corrects since Big-Oh is essentially an upper bound.

But, since we already established a worst case running time, can this still be correct.

# Answer
> 2 votes
Yes, if a program runs in time $O(n)$, then it also runs in time $O(n^2)$. However, usually we try to give the best possible bound, to prevent readers from being misled. You can signify that the bound is tight using big theta: the worst-case running time of the program is $\Theta(n)$.

---
Tags: asymptotics
---


# Question
Title: Binary Indexed Trees: Why does i & -i work?
I already read this related question on the intuition behind binary indexed trees, and while the answer explains how the tree structure works, it does not really explain how this correlates back to the array representation where the next node is accessed based on the current nodes index according to $i \mathrel{\\&} -i$.

I know physically that $i \mathrel{\\&} -i$ gives you the highest power of 2 that divides $i$, essentially the least significant set of bits, but I don't see why adding or subtracting this to/from the current index allows you to jump around to get to the wanted node.

Linking this back to the tree representation,

```
      4
   /     \
  2       6
 / \     / \
1   3   5   7

```

I see how the left parent of a node with index N is $(N - 2^h)$ and the right parent is $(N + 2^h)$ where h is the height of the subtree from N down (including N), and this seems to be related to why the $i \mathrel{\\&} -i$ works.

However, what about the cases like finding the previous node of 5, which according to $5 - 5\mathrel{\\&}-5$ is 4? The formula $N - 2^h$ also seems to work except there is no direct link between 4 and 5. How do you prove that it works in these cases too?

# Answer
Assuming that your tree is storing cumulative sums, one query you would like to make is "what is the cumulative sum to index n". Suppose the tree is as shown in the OP, and n is 5. The answer to the question would be found by adding the sum in node 4 and the sum in node 5. This is because each node is storing the cumulative sum of itself plus its left subtree (if any). Thus, node 4 has the cumulative sum of indices 1-4 and node 5 has the cumulative sum of index 5 (just itself). Because of the way the tree is built, you basically need to visit one node for each 1 bit in the binary representation of your index.

So the algorithm to compute the cumulative sum is to start at the given index, in this case 5. Note that 5 is 101 in binary. Add its sum to the total. Then, to get to the next node needed, we want to remove the least significant bit (we want to get from 101 to 100). The least significant bit of `i` is `i & -i`. To remove the least significant bit, `i -= (i & -i)`. That gets us to node 4. We add node 4's sum to the total. Then we remove the next significant bit, leaving 0 which means we are at the end.

If the tree were bigger, and the starting index were 50 (which is 110010 in binary), we'd have to visit node 50 (110010), node 48 (110000), and node 32 (100000). In this example, node 32 contains the sums of 1-32, node 48 has the sums of 33-48, and node 50 has the sums of 49-50.
> 4 votes

# Answer
I have recently written a detailed post about Binary Indexed Tree.

You can have a look at it here.

I hope it will help.
> 0 votes

---
Tags: data-structures, binary-trees, correctness-proof, arithmetic
---


# Question
Title: Mathematical optimization on a noisy function
Let $f:\mathbb{R}^d \to \mathbb{R}$ be a function that is fairly nice (e.g., continuous, differentiable, not too many local maxima, maybe concave, etc.). I want to find a maxima of $f$: a value $x \in \mathbb{R}^d$ that makes $f(x)$ as large as possible.

If I had a procedure to evaluate $f$ precisely on any input of my choice, I could use standard mathematical optimization techniques: hill-climbing, gradient descent (well, gradient ascent), etc. However, in my application I don't have a way to evaluate $f(x)$ exactly. Instead, I have a way to estimate the value of $f(x)$.

In particular, given any $x$ and any $\varepsilon$, I have an oracle that will output an estimate of $f(x)$, and whose expected error is approximately $\varepsilon$. The running time of this oracle invocation is proportional to $1/\varepsilon^2$. (It is implemented by a kind of simulation; the accuracy of the simulation increases with the square root of the number of trials, and I can choose how many trials to run, so I can choose the desired accuracy.) So this gives me a way to get an estimate of any accuracy I desire, but the more accurate I want the estimate to be, the longer it will take me.

Given this noisy oracle for $f$, are there any techniques for computing a maxima of $f$ as efficiently as possible? (Or, more precisely, finding an approximate maxima.) Are there variants of hill-climbing, gradient descent, etc., that work within this model?

Of course, I could fix a very small value of $\varepsilon$ and apply hill-climbing or gradient descent with this oracle, keeping the same $\varepsilon$ throughout. However, this might be unnecessarily inefficient: we might not need such a precise estimate near the beginning, whereas precision near the end when you are zeroing in on the solution is more important. So is there any way to take advantage of my ability to control the accuracy of my estimate dynamically, to make the optimization process more efficient? Has this kind of problem been studied before?

# Answer
> 4 votes
One could replace the exact function $f(x,p)$ by the noisy function $f(x+\Delta x, p + \Delta p)$, where $p$ is an artificial parameter used to describe the noise dependency such that $\Delta x$ and $\Delta p$ contain the noise.

* Some techniques used in stochastic optimization and robust optimization might be applicable.
* Because $\frac{\partial f}{\partial x}\approx 0$ near the maxima, $\Delta x$ is less dangerous than $\Delta p$.
* Sometimes $\frac{\partial f}{\partial x}(\tilde{x}, \tilde{p})$ can be approximated accurately while evaluating $f(\tilde{x}, \tilde{p})$. Often, this is only true in theory, because it is not implemented, and some parts would require special care.
* The desired "smallness" of $\Delta p$ (and $\Delta x$) is an "end user" decision. One can offer heuristics to control it, but a runtime proportional to $1/\epsilon^2$ is too slow for fully automatic accuracy handling.
* The given noise vs runtime tradeoff is what sets this problem apart from better studied problems. Problems were the noise is just unavoidable are more common and better studied.

---
Tags: optimization, approximation
---


# Question
Title: Data structure to hold and retrieve points in a plane
**Definition 1:** Point $(x,y)$ is controlling point $(x',y')$ if and only if $x \< x'$ and $y \< y'$.

**Definition 2:** Point $(x,y)$ is controlled by point $(x',y')$ if and only if $x' \< x $ and $ y' \< y$.

I'm trying to come up with data structure to support the following operations:

* $\mathrm{Add}(x,y)$ - Adds a point $(x,y)$ to the system in $\mathcal{O}(\log n)$ complexity where $n$ is the number of points in the system.
* $\mathrm{Remove}(x,y)$ - Removes a point $(x,y)$ from the system in $\mathcal{O}(\log n)$ complexity where $n$ is the number of points in the system.
* $\mathrm{Score}(x,y)$ - Returns the number of points $(x,y)$ controls - number of points that $(x,y)$ is controlled by. Worst case complexity $\mathcal{O}(\log n)$ .

---

I've tried to solve it using multiple AVL trees, but could not come up with elegant enough solution.

This question appeared on my exams few days ago. The question should have relatively straightforward as it was worth $15/100$ points. I tried to solve this by several AVL trees but couldn't come up with elegant enough solution.

Hints are welcome.

# Answer
**Solution outline:**

We will maintain two AVL trees.

* Tree\_X: will hold points sorted by their X coordinate.
* Tree\_Y: will hold points sorted by their Y coordinate.

Each node within both trees will hold the following additional data:

1. Number of leaves in left sub-tree.
2. Number of leaves in right sub-tree.

For a point $(x,y)$ we will define regions $A$ ,$B$, $C$, $D$:

* Point $(x',y')$ is in $A$ if $x' \< x$ and $y' \> y$.
* Point $(x',y')$ is in $B$ if $x' \> x$ and $y' \> y$.
* Point $(x',y')$ is in $C$ if $x' \< x$ and $y' \< y$.
* Point $(x',y')$ is in $D$ if $x' \> x$ and $y' \< y$.

Now it is clear that Score(x,y) = |C|-|B|. However $|A|+|C|$, $|B|+|D|$, $|A|+|B|$, $|C|+|D|$ could be easily retrieved from our two AVL trees, as we will soon see. And notice that $\frac {(|A| + |C| + |C| + |D|) - (|A| + |B| + |B| + |D|)}{2} = |C|-|B|$

**Implementation of required operations:**

* Add(x,y) - We will add point (x,y) to both of our AVL trees. Since the additional data we are storing is affected only on the insertion path and since the insertion occurs in (logn), the total cost of Add(x,y) is O(logn).
* Remove(x,y) - We will remove point (x,y) from both of our AVL trees. Since the additional data we are storing is affected only on the removal path and since the removal occurs in (logn), the total cost of Remove(x,y) is O(logn).
* Score(x,y) - I will show how to calculate $|B|+|D|$ as others done in similar way and same complexity costs. It is clear that $|B|+|D|$ is the number of points which satisfy $x' \> x$. To calculate this number we will:

1. Find x in AVL\_X. Complexity O(logn).
    2. Go upwards in Tree\_X until the root and on each turn right we will sum the number of elements in left sub-tree of the son. Complexity O(logn).

Total cost of Remove(x,y) is O(logn).
> 2 votes

---
Tags: data-structures, space-partitioning
---


# Question
Title: Polynomial Identity Testing Evaluating a polynomial on a circuit
Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C\_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of bits required for the intermediate calculations is too high i.e How can we guarantee that the evaluation does not require more than polynomial bits (polynomial in the size of the circuit) ?

# Answer
> 2 votes
If you're working over $\mathbb{Z}/p\mathbb{Z}$, you don't have to do anything: the intermediate results can't get larger than $p$.

If you're working over $\mathbb{Z}$, the standard trick is to pick a random $k$-bit prime $p$ and then reduce everything modulo $p$, so you are effectively working over $\mathbb{Z}/p\mathbb{Z}$. One can show that the probability of getting a wrong answer using this method is exponentially small in $k$ (using the prime number theorem).

If you're working over $\mathbb{Q}$, you can reduce this to working over $\mathbb{Z}$ by clearing all fractions.

---
Tags: complexity-theory, polynomial-time, circuits
---


# Question
Title: Which type of computer programs could be called intelligent agents?
I know some computer programs can be modeled as intelligent agents, for example a chess program which plays against a human. The environment is the chess board stored in the memory and actuators are commands to move a piece. Another intelligent program may react to the user commands.

My question is could any computer program be regarded as an intelligent agent? for example a media player, or a simple calculator?

If no, which characteristics a program should possess to be called an intelligent agent?

# Answer
> 3 votes
This is (obviously) up for debate. If you speak about agents, one common definition of agents is:

* **autonomy**: agents operate without the direct intervention of humans or others, and have some kind of control over their actions and internal state; social ability: agents interact with other agents (and possibly humans) via some kind of agent-communication language \[Genesereth and Ketchpel, 1994\];
* **reactivity**: agents perceive their environment, (which may be the physical world, a user via a graphical user interface, a collection of other agents, the INTERNET, or perhaps all of these combined), and respond in a timely fashion to changes that occur in it;
* **pro-activeness**: agents do not simply act in response to their environment, they are able to exhibit goal-directed behaviour by taking the initiative.

There is also the BDI model using the concepts *belief*, *desire* and *intention* for intelligent agents.

If you go further away from "agents" (this term has a specific meaning in computer science as it's also part of a software engineering paradigm) to "what makes a piece of code intelligent?" You'll see that every research area will give you a different answer. Artificial intelligence distinguishes between **hard** and **soft** AI. Neuroinformatics takes its answers from cognitive science, importing the definitions that biopsychology and neuro science give about cognition and what makes a being "intelligent". A philosopher will also have a different definition.

These definitions all have some common ground but in the end there is no ultimate definition everybody can agree on.

# Answer
> 1 votes
A media player or calculator is in no way intelligent. They are stupid deterministic programs. To call software intelligent you will need at least some sort of learning, planning, prediction or something similar that reminds of intelligent behaviour.
But in the end many software developers claim that their products are intelligent when they are not.

---
Tags: artificial-intelligence
---


title: Branch predictor question

text:
# Question
Title: Branch predictor question
If the branch predictor is placed in the fetch stage then how does it know that the current instruction is actually a branch before trying to predict its outcome? Is some (very little) decoding already done in the fetch stage before going to the actual decode stage?

# Answer
There is no decoding done in the fetch stage. The fetch stage relies on the Branch Target Buffer (BTB) to tell it which instruction addresses have had taken branches in the past.

The BTB is a small highly associative structure. It performs two functions. First it tells you which instructions are and are not branches. If the current program counter (PC) is in the BTB then the instruction pointed to by the PC is a branch, and the BTB will tell us the target of that branch and the branch predictor will give us a guess about whether the branch is taken or not taken.

If the current program counter in *not* in the BTB then either (a) the current instruction is not a branch or (b) we have never seen this instruction before (and don't know whether or not it is a branch, but we'll assume it is not or (c) the current instruction is a branch, but we've never seen the branch taken, so we've never put it in the BTB.

This last function (branches that are never taken are never put in the BTB) makes the BTB actually a very effective branch predictor. Branches that have never been taken are unlikely to be taken in the future, and the BTB predicts this correctly. Branches that have been taken at least once in the recent pass are slightly more likely than not to be taken in the future, and the BTB reflects this as well.

The BTB effect was rarely taken into account in academic branch predictor research done at the end of the 1990s (nor is it taken into account in the statistics in most textbooks). For most programs on most architectures the BTB actually filters out a significant number of branches (on the order of 25%) because they are never taken or rarely taken. For those 25% of branches you essentially get a 99% accurate branch prediction for free. The "real" branch predictor needs focus, then, only on the other 75% of branches.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: The logic behind one's complement addition
For my computer science class I need to finish a project where I desperately need to understand logic of one's complement and two's complement. I already know how to construct these and also how hardware adder works when dealing with two's complement. The thing that is bothering me and I need help with is the logic behind one's complement addition. Why do we have to add the bit we would carry over (and discard when using two's complement coding) to the sum to get the correct result? I don't understand why binary addition behaves like this when adding one's complement and why is that last adding of carry over bit so crucial. I need to understand the logic behind it. Thanks

# Answer
A binary number in one's complement is represented by $\bar{N} = (2^{n} - 1) - N$.
So when you subtract *N* from *M* you get: $$ S = M - N = M + \bar{N} = M + (2^{n} - 1 - N) = (M - N) + 2^{n} - 1 $$ And when you do the so called *end-around carry* operation you effectively add $-2^{n}+1$ to the intermediate result because you take away the MSB and add 1. So you get:
$$SUM = S -2^{n}+1= (M - N) + 2^{n} - 1 - 2^{n}+ 1 = M - N$$ This is correct again.

In two's complement ($2^{n} - N$) you have: $$S = -M + N = \bar{M} + N = (2^{n} - M) + N = 2^{n} - (N - M)$$ Discarding the MSB does $- 2^{n}$ and gives you: $$SUM = S -2^{n} = 2^{n} - (N - M) - 2^{n} = N - M$$

Done you are.
> 4 votes

---
Tags: arithmetic
---


# Question
Title: What is a continuous environment for an agent?
I know the environment of an intelligent agent is divided to discrete and continuous. But I think they are relevant to sensors and actuators of the agent itself. Moreover, environment may have many mutable factors,(some continuous, some discrete).

For example for an agent which is an expert system (computer program) to play the role of a physician, what is the environment, is it continuous or discrete?

Please give some examples of continuous environments.

# Answer
Continuous has its usual definition: a variable that "looks like the real numbers" in the sense that, for any value $x$ that the variable could take and any positive constant $\delta$, there's another value $y$ that the variable could take that's within distance $\delta$ of $x$. So, for example, the environment of your physician expert system will include things like the patient's temperature and blood pressure, which are both continuous, but it will also include discrete things such as what medicines they're currently taking and substances they're allergic to. There are also awkward cases such as how much pain they feel, which you might imagine to be continuous but is typically expressed on a discrete scale of 0 to 10. (I guess it's on a discrete scale partly because it's completely subjective and partly because nobody could distinguish between 3.298364 and 3.298365.)

However, note that your agent is most likely running on a digital computer. Because of this, any inputs it receives will have been rounded to some level of precision, making everything discrete in the end.
> 2 votes

---
Tags: artificial-intelligence
---


# Question
Title: How should I design a hash table where all the keys are permutations?
I need to create a hash table to store values for (possibly all) permutations of `123456789`, which is exactly 362 880 keys.

Given that I know how all the keys look up front, it seems I that there should be an optimal hashing function, and an optimal size of the table to store the values in.

Is this true? If so, how can I create the *perfect* hashing function? And also, how can I determine the optimal size for the hash table?

**update:** I'm looking to store all of the possible permutations, where each will be stored only once, which means the table should in the end contain exactly all 362 880 keys (since I have a hard limit on my algorithm for which I need to optimize my worst case scenario.)

# Answer
> 9 votes
Simply compute the *index* of the permutation into the sorted list of all permutations and use that as your hash key. This can be achieved with a relatively simple algorithm: https://stackoverflow.com/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of

Once you have that index, you can make a table with exactly 9! slots - you have a perfect hash over your input domain.

For example, for n=3, the hash function produces

```
123 -> 0
132 -> 1
213 -> 2
231 -> 3
312 -> 4
321 -> 5

```

# Answer
> 4 votes
Since you have only 362,880 possible keys, you can uniquely represent every key with just 19 bits. (Where a really naïve representation of the key might take 9\*4 = 36 bits).

I can't see a way to have this help you with hashing.

The size of the hash table is determined by how many keys you need to store, not by the size of the space of possible keys.

The size of the output of the hash function is determined by the size of the hash table.

*Perfect* hashing is a technical term meaning that every key maps to a different hash bucket. It is only possible to construct a perfect hash if you know the exact elements you are going to be storing before you start.

I guess if you really are going to store all possible permutations then you can make a table of 362,880 bits, map each permutation to a unique key in the range \[0, 362,879\], and then use the key as an index into the table, but that's hardly perfect or optimal if you usually only need to store a few thousand permutations.

# Answer
> 1 votes
If you want to optimize for memory usage, use an array instead of a hash table.

For example, suppose I'd like to store the following keys/values: {123456789: "alpha", 123456798: "beta", 123456879: "gamma", 987654321: "omega"}

We could instead store these in an array: \[123456789, 123456798, 123456879, ..., 987654321\]

To do this, you'll need a function that will take a permutation, and return a unique number between 0 and 362879 inclusive. This unique number is your array index.

Whether this is a better solution depends on what your optimisation goals are:

* lookup performance
* memory usage
* programmer time/effort
* iteration performance

Lookup performance might be better, or it might be worse. This depends on how fast your permutation-\>index function runs.

Memory usage will be better than a hash table -- there's no extra padding space, no hash collisions, and the keys don't need to be stored in the data structure.

Programmer time/effort will be worse than a hash table.

Iteration performance \[ie, how quickly it can visit all entries in the hash table\] will be greatly improved. However, since you're looking for a hash table, this is likely irrelevant.

---
Tags: data-structures, hash, hash-tables, permutations
---


# Question
Title: AVL tree with fixed height and as few elements as possible
I have been reading about AVL trees, at the moment I'm trying to figure out how to determine the height of a tree and how to draw an AVL tree of some height with minimum number of elements.

In a tutorial I found that this: would be a AVL tree of height 7

And this AVL tree with the height 4

This is really confusing by the look I would guess that both of them are of height 4. I'm fairly new to data structures, I could not find a simple documentation/tutorial regarding this most of what i found was about Insertion/Deletion with AVL trees.

So is the top tree of height 7 if not how would I draw it with the minimal number of elements. I understand the each sub tree would have to be balanced.

# Answer
> 4 votes
Generally tree height is defined as the length of the longest path from the root to a leaf. Therefore you're right that the two trees have the same height, but they actually have height 3.

As far as your second question, about how to draw the smallest possible AVL tree of a given height $n$, the trick is to think inductively. Construct a new tree of height $n$ by joining the smallest possible AVL trees of height $n-1$ and height $n-2$ as subtrees of a new common root. Using the definition of AVL trees, it's a straightforward exercise to see that (1) this new tree is a valid AVL tree and (2) it's the smallest possible AVL tree of height $n$.

To get the height 7 tree in particular, find the base case minimal AVL trees of heights 0 and 1, and repeat the above construction 6 times.

# Answer
> 1 votes
What you want is to produce maximally unbalanced AVL trees of a given height, also called Fibonacci trees (because they have Fn+2-1 nodes, where n is the height of the tree, and Fn is the n-th Fibonacci number).

I worked on that, and asked and answered a question on stackoverflow, accepting another answer. Have a look, you may find what you are looking for.

And of course, the top tree is of height 4, not 7. BTW, your last sentence is not correct: every subtree should be **un**balanced.

To build a Fibonacci tree of height 7, you may start from your bottom picture, which is a Fibonacci tree of height 4, consisting of two Fibonacci subtrees, the left one of height 3, and the right one of height 2. Take the left subtree, put it to the right of the current tree, and link both to a new root node. You will obtain a Fibonacci tree of height 5. Just repeat the same recipe 2 more times, and you are done.

Please note: I'm using the more intuitive convention that calls the height of the tree the number of nodes on the longest path from root to leaf. I'm not alone in this for sure. I find it a bit disturbing to say that an empty tree has height -1.

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


# Question
Title: will this be decidable or partially decidable?
$A=\\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\\}$

Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is possible. Then deciding whether cardinality is greater than 3 should be decidable. But the material that i have been studying says it is partially decidable. Which one is right?

# Answer
> 3 votes
The language is clearly not decidable; use Rice's theorem. See e.g. our reference question.

We can certainly simulate $M$ on every input by dovetailing and count accepted inputs; if $|L(M)| \geq 3$ our counter hits three after finite time and we accept, otherwise we loop. Therefore, $A$ is semi-decidable.

# Answer
> 0 votes
You can make a reduction from the HALTING problem({,w| is a turing machine that halts on w}), using pseudocode:

```
def R(<M>,w):
    def F(x):
        M(w) //run M on w, if it loops we are rejecting everything
        return x in ('1','2','3')
    return F

```

For every x in HALTING problem, there is some y in A, such that f(x) = y.

---
Tags: computability, turing-machines, semi-decidability
---


title: Red Black Tree clarification

text:
# Question
Title: Red Black Tree clarification
I am quite new to Red-Black trees, and therefore I am having a bit of difficult time trying to understand them.

One of the properties of the Red-Black tree is that every red vertex must have two black children, meaning one cannot have two consecutive red vertices.

Can someone explain to me why this is an essential property? What are the benefits of having such a property?

# Answer
If you check the proof height-balancedness of red-black trees, you'll see that we essentially analyse the *black-height* $h\_b$ of the tree which, by another important invariant, is the number of black nodes from the root to *any* leaf.

The property you cite then gives us the right half of

$\qquad\displaystyle h\_b(T) \leq h(T) \leq 2h\_b(T)$,

which allows us to carry over bounds on black-height to usual height.
> 2 votes

# Answer
The properties of a red black tree allow insertion, deletion and search in $O(log(n))$. I guess you can find a prove online somewhere.

When an element is inserted or deleted. A fix-up is done, it involves rotations in a tree, so the properties still hold. This ensures the tree is **quite**balanced at all times and search is **quite** fast at all times.
> 1 votes

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


title: Algorithm to generate all planar graphs

text:
# Question
Title: Algorithm to generate all planar graphs
Is there an algorithm which provides a sequence of all simple planar graphs, unique by graph isomorphism? For instance: first all planar graphs with 1 node, then all planar graphs with 2 nodes, etc.

Note: It is okay if it generates only graphs with a minimal node degree of 1 or 2.

# Answer
House of Graphs is a good resource. From the database, you can download all planar graphs up to 11 vertices.

For generating planar graphs even with some additional properties (e.g. connectivity), have a look at plantri by Brinkmann and McKay.
> 2 votes

# Answer
One approach would be to enumerate all graphs of a given size, then test each one to see if it is planar and filter out the non-planar ones. This might work acceptably if you only want very small graphs.

Brendan McKay has a collection that enumerates all non-isomorphic planar graphs of size up to 11, which you could download and use directly. There are about 16 million different planar graphs of size up to 11, so if you're lucky you might not need to consider anything larger and that collection will be adequate.
> 4 votes

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


# Question
Title: How can I academically say that 'one computer is slower than the other'?
I'm writing a research paper and I have to basically say that one microcontroller is slower than an other microprocessor. However, I'm worried that simply saying that it's 'slower' wouldn't be appropriate in a research paper.

Am I right? Is it OK to just say that one processor is 'slower', or do I need to say something else? What else could I say? The best I have come up with is that one has 'less computational power' than the other or that the microcontroller has 'low computational power'. Unfortunately, these expressions don't seem to be too popular when searching online.

So, what would be a better and academically correct way of saying this?

# Answer
Let me see if I can clear up a few potential misconceptions here.

Sometimes people think that when they write a research paper they have to use fancy language: it's not enough to just say what they mean, but rather, it has to be written in academic code with more complex-sounding language. Or, they think that using bigger words will make them sound more authoritative. This is not the case. If anything, it leads to papers that are overly pompous and unnecessarily hard to read.

Instead, I suggest you figure out what you mean, and then write that. Don't worry too much about how to say it (whether the word you are using is OK in a research paper). Do worry about being precise: figure out exactly what you mean, and then be precise in your wording.

You have a good intuition. Your hesitation about just saying one processor is slower than another is valid. (But not because you can't say one thing is slower than another in a research paper.) The issue I see with that wording is that it is not very precise. There are many things that 'slower' could mean.

What exactly do you mean by 'slower'? Slower in what way? And how do you know? What evidence do you have? Can you quantify it? How would you measure 'slowness' in a quantitative, defensible way?

Once you can answer those questions, then you can figure out how to write something more convincing in your paper. For instance, "processor X is 20% slower on the SpecCPU benchmark than processor Y" is more precise than "processor X is slower than processor Y", and backs up the claim with evidence.

But first you need to figure out precisely what you mean by 'slower', and why it matters to your argument, and then you can figure out how to be more precise in what you write and what evidence you can provide to back up your statement.

You won't always need to write with this level of care and precision. Sometimes, when you are just providing intuition or background, the specifics don't matter so much, and then you can just say that X is slower than Y. But if that statement plays a key role in your paper -- maybe it is a key part of the motivation for your paper, or it is a key part of the reasoning that underpins the design of your system -- then you should try to be as precise as you can, and provide evidence for the statement.
> 38 votes

# Answer
Claiming that a microprocessor has a "speed" is very, very difficult nowadays.

You can look at the clock rate, which is mostly a meaningless number nowadays. Especially since microprocessors don't have *one* clock rate anymore, but run at varying speeds depending on many circumstances. You can look at the number of cores, which is also meaningless if we don't know how many cores the application can use. You can look at the computer architecture, and rely on claims of the manufacturers of speed. The computer's memory can have different speeds. If it doesn't have enough memory, the operating system starts swapping memory which takes time.

If you said "this microprocessor is slower", without some reasoning why it is slower for the application you are interested in, I would be dubious and think you might not know what you are talking about. If you said "it has less computational power" I'd think you are trying to bluff your way through the paper. If you called it "less performant" as was suggested, all doubts on my side would be gone.

Write down in your paper which microprocessor models you are comparing (they all have exact names so anyone interested can look up the details anyway), give all the relevant specs (architecture, clock speed, number of cores, amount of L1, L2 and L3 cache), and explain why one is slower for the purpose you are discussing, based on this data.
> 2 votes

# Answer
You probably need to take a set of programs, compiled and run on the various platforms and cite a "speedup" number for one versus the other for each program. You could give a simplistic MIPS number (throughput in millions of instructions per second) for one processor versus another, but that only makes sense if they are executing the same instructions (I presume that they are not). You could cite latency until the program completes.

Processor comparisons is a well known marketing game. You really don't have a well defined ordering unless you have a broad comparison that says the same thing across many comparisons.
> 0 votes

# Answer
This is an answer the question you asked instead of the question you really care about, but it seemed like a fun exercise: How would one attempt to rigorously "prove" (as far as possible) that one computer is slower than another?

I thought of one way: You write a virtual machine that simulates the "slow" processor and run it on the "fast" processor. If you can argue that any operation done by the "slow" processor takes at least as long as the same operation done by the virtual machine on the fast processor, then you have proven that it is slower. Because even if there is some program A that takes longer to run on the "fast" processor directly, we can always run A on the virtual machine on the "fast" processor. So for any program, the "fast" processor can run it faster by choosing the better option of either running it natively or on the VM.

Of course, proving the "if you can argue..." part would be impossibly complicated for a full modern machine. But perhaps it is possible to argue by benchmarking each primitive operation (like each machine instruction) in both cases. (Issues like different cache sizes would probably make this futile.) Another issue is that in practice, knowing whether a program will run faster on one processor or the other may be undecidable, but you have still theoretically shown that one processor is faster than the other.
> 0 votes

# Answer
You can really just be straight out with it. You're over doing this, slow is the right word for it. However, a more formal context would be good.

As an example:

> X evidence supports that Y processes at a slower speed compared to Z
> 0 votes

# Answer
"less performant" is a great way to say this, if the exact performance figures aren't affecting your results. For example, you might write something like:

> Table X shows that this implementation runs in real-time on the Xeon processor used for benchmarking. If a less performant processor were to be used, such as an ARM Cortex M microcontroller popular in battery-powered embedded systems, then additional optimizations should be investigated.

The term "less performant" neatly wraps up all the factors affecting you: clock speed, architectural efficiency, cache sizes, memory latency, etc.
> -5 votes

---
Tags: terminology, computer-architecture
---


# Question
Title: What is the exact definition of a dictionary in the concept of linear algebra and computer science?
I am reading this paper for my master thesis and trying to understand every concept in it. The following sentence confuses me as to what is the exact definition of a dictionary in this concept except for the fact that it holds the atoms as its columns?

> Recall we refer to the columns of the matrix $A$ as *atoms* that are later used as building blocks in the construction of $b$. Such a matrix that holds the atoms as its columnsis referred to as a dictionary\[...\].

# Answer
> 1 votes
Yes, as it says, a "dictionary" is just the word they're using for a matrix with entries of a particular type that's used for a particular purpose. They're drfining the term "dictionary" in the text you quote.

---
Tags: terminology, image-processing, linear-algebra
---


# Question
Title: Should one learn proofs for the correctness of algorithms? Why?
I'm reading *Introduction to Algorithms* and would like to know if learning the proofs is worthwhile.

# Answer
> 4 votes
That's up to you. Reading correctness proofs for algorithms is useful since:

1. The proofs explain why the algorithms work. If you need to modify these algorithms, you'd better know how they work. Such an understanding is very useful even just for coding algorithms, and certainly for debugging them.
2. The proofs are good examples of mathematical proofs. The mathematical notion of proof is one of the most important contributions of mathematics to the world, and is a way of knowing which you could find useful in life, even without using it yourself.
3. If you continue in academia, say get a graduate degree, you might have to write such proofs in the future.

However, it is my understanding that most programmers don't come up with new algorithms, or even code classical ones. If this is your case, you can probably skip the proofs, indeed the entire course, if it were not made compulsory by your university (if any).

---
Tags: algorithms
---


# Question
Title: Is it Polynomial to decide whether any product of input numbers satisfies a boolean expression?
I have an input number c of n bits and its prime factorization. I want to find a divisor of c with certain fixed bits "f". For example:

```
INPUT:
c=1100011 (99) (n=7)
prime factorization = 11,11,1011 (3,3,11)
f=0??1?0?

OUTPUT:
o=0001001 (9)

```

Unfortunately, it's no use to check all divisors, because according to http://en.wikipedia.org/wiki/Divisor there may be up to O(sqrt(2^n)) divisors, which is exponential.

# Answer
> 3 votes
Here is one special case that is solvable a bit more efficiently than brute force. Suppose all of the fixed bits are consecutive and in the least significant bits. For instance, we are given the desired value for the low $k$ bits. Then this problem amounts to asking whether there is a divisor $d$ of $c$ such that $d \equiv f \pmod{2^k}$.

In other words, if $T$ is the multiset of prime factors of $c$, we are looking for a submultiset $S \subseteq T$ such that

$$\prod\_{x \in S} x \equiv f \pmod{2^k},$$

where $f,k,T$ are given. Let me sketch an algorithm for this special case.

How can we find a solution to this equation without enumerating all $2^{|T|}$ submultisets? One way is to take discrete logs and reduce this to a subset sum problem. In particular, the multiplicative group $(\mathbb{Z}/2^k\mathbb{Z})^\*$ is isomorphic to $(\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})$. Let $\varphi$ be an isomorphism that maps $(\mathbb{Z}/2^k\mathbb{Z})^\* \to (\mathbb{Z}/2\mathbb{Z}) \times (\mathbb{Z}/2^{k-2}\mathbb{Z})$. Then, we search for a $S$ such that

$$\sum\_{x \in S} \varphi(x) = \varphi(f).$$

So, if we can compute $\varphi$ efficiently, this basically reduces to a subset sum problem modulo $2^{k-2}$. And it turns out that $\varphi$ *can* be computed efficiently using Hensel lifting (basically, you find the discrete log of $x$ modulo 8, then modulo 16, then modulo 32, and so on; at each step there are only two possibilities for the discrete log, so you try them both). So, you compute $T^\* = \\{\varphi(x) : x \in T\\}$ and $f^\* = \varphi(f)$ and then try to find a submultiset $S^\* \subseteq T^\*$ such that

$$\sum\_{y \in S^\*} y = f^\*.$$

This is a subset sum problem modulo $2^{k-2}$ (if you allow me to handwave over the $\mathbb{Z}/2\mathbb{Z}$ part of the range of $\varphi$).

And finally, there are algorithms for the subset sum problem that are more efficient than brute force trial-and-error of all subsets. This then gives you an algorithm for your original problem, in the special case where all the fixed bits are consecutive and in the least least significant bits.

---

This connection also suggests that your problem is probably not in P. In particular, it appears that we can show that your problem is at least as hard as subset sum, which is known to be NP-hard. Therefore, it looks like your problem will be NP-hard, too.

---
Tags: np-complete, decision-problem, polynomial-time
---


# Question
Title: Examples for directed graphs with super polynomial cover time
The cover time of a graph is the expected number of steps in a random walk on the graph until we visit all the nodes.

For undirected graphs the cover time is upperbounded by $O(n^3)$. What about directed graphs? I'm looking for examples of super-polynomial cover time.

Is there an example for such graph with $O(2^{\sqrt n})$ cover time?

# Answer
Yes, it's not too hard to construct such a graph. Consider a path $v\_1 \to v\_2 \to v\_3 \to \dots \to v\_n$ containing $n$ vertices. Now add a new "dead-end vertex" $w$, and add edges $v\_1 \to w$, $v\_2 \to w$, $v\_3 \to w$, etc.

If you do a random walk starting at $v\_1$, the probability that you reach $v\_n$ is $1/2^{n-1}$, as you have to get lucky and move in the right direction at each of the vertices $v\_1,\dots,v\_{n-1}$ to avoid getting stuck at the dead end. Therefore, the cover time will be $\Omega(2^n)$.

---

Notice how things would change if we converted this into an undirected graph. In an undirected graph $w$ would no longer be a dead end: if we hit $w$, we're not stuck (we still have a chance to get back to where we want to be, by backtracking our steps). In the directed graph, $w$ is a dead end: once you hit $w$, you're done and you have no hope of making it to where you want to be.
> 4 votes

---
Tags: graphs, random-walks
---


# Question
Title: P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q
My problem: Define two sets P and Q of words (that is, two problems) such that: P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q

# Answer
Hint: Following the OP's suggestion, let $P$ be the set of all TMs halting on every input, and let $Q$ be the set of all TMs halting on the empty input. It is known that $Q$ is undecidable and semidecidable (indeed, $\Sigma\_1^P$-complete) and that $P$ is undecidable and not semidecidable (indeed, $\Pi\_2^P$-complete). Moreover, $P \subseteq Q$ since if $T \in P$ then $T$ halts on every input, and in particular $T$ halts on the empty input, so that $T \in Q$.
> 2 votes

---
Tags: undecidability, semi-decidability
---


# Question
Title: Is a stack overflow detected by hardware or software?
Is it the task of the software (operating system) to detect stack overflows or is a stack overflow detected in hardware, causing an exception in the CPU?

# Answer
It can be software, or hardware, or both, or none.

There are two kinds of overflows: overflow when growing the stack (when entering a function), and overflow when accessing an array on the stack. Overflows when growing the stack can be detected by making a bounds check on function entry, to verify that there is enough room (and either signal an error or grow the stack if there isn't). Overflows when accessing an array on the stack are only an issue in low-level languages that don't verify array bounds; the solution there is to verify array bounds.

These software approaches have the advantage that they work fully reliably: you can be sure that any stack overflow will be detected. Their downside is that they increase the code size and the execution time. Hardware can help by providing a method to detect most overflows at no cost as long as no overflow occurs. On an architecture with an MMU¹, the runtime environment can arrange to map the stack on a page boundary, with the next page remaining unmapped.

```
+---------------+---------------+---------------+---------------+
| stack                         | unmapped      | other stuff   |
|    ----> direction of growth  |               |               |
+---------------+---------------+---------------+---------------+
^               ^               ^               ^               ^  page boundaries

```

That way, if the software attempts to access data beyond the page boundary (whether because the stack pointer has moved beyond the boundary or because the array access is out of bounds and beyond the boundary), it will cause a fault by accessing an unmapped area. This only happens if the overflow is small enough: if the amount of overflow is too large, the program may end up accessing other stuff on the other side of the gap in the address space.

The downsides of the hardware approach are that it isn't fully reliable since an overflow by a large amount may not be detected, and that it doesn't detect array overflows that remain within the addressable space.

To detect array overflows, another software technique is a canary: put a special value at the top of the stack or between frames, and check that the canary value hasn't changed on function return. This is also an imperfect technique since the overflow might avoid the canary altogether or might not be detected because the canary value has been restored by the time it is checked. Nonetheless, it is useful to make it harder to exploit some security vulnerabilities.

The safest and cheapest way to avoid stack overflows is to calculate the amount of stack that the program will need before starting to execute it, by static analysis. However this is not always practical: the amount of stack needed by a program is undecidable in general and depends on the data that's manipulated by the program.

¹ <sub> The same principle can also be applied with just an MPU, or with no memory protection if there is a single thread whose stack is at the edge of the existing physical mappings. </sub>
> 26 votes

---
Tags: computer-architecture, stacks
---


# Question
Title: Methods of turning a decision problem into finding the certificate?
I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If it's yes, how can we go from that to finding a polynomial-time algorithm that gives the certificate?

For example, let's say I have a CNF formula. Let's assume we have an algorithm that outputs whether a formula is satisfiable, in polynomial time. I want to know what the actual assignment is. So I'd do a for loop (for i from 1 to n, where n is the number of variables). At each step, I can do one more assignment (assign the i'th variable to be true) and check if the new formula with the i'th value set, is still satisfiable. If yes, continue. Otherwise, assign the i'th variable to be false, and then continue. By saving each of these assignments, at the end I can output a list.

My question is, are there some good methods (in general) of finding the certificate? Perhaps some "token problems" where if you know what to do with one problem of that type, you can do all problems of that type (eg, graph theory, network design, sets/partitions, algebra/number theory, satisfiability)?

# Answer
> 2 votes
The main method is self-reducibility. Suppose that your problem is of the form "there exists an object $x$ such that $P(x)$". Consider some partition of the set of all possible objects $O$, say $O = O\_1 \cup \cdots \cup O\_m$ (here $m$ should be "small", i.e. polynomial in the size of $x$). If the problem "there exists an object $x \in O\_i$ such that $P(x)$" can be reduced to your original problem, then you can use a recursive approach for finding some certificate. The reduction should have the property that a witness for the reduced problem implies a witness for the original problem.

SAT, the example in the question, has exactly this property. In this case, $x$ is a truth assignment, and $P(x)$ states that $x$ satisfies some formula. For each variable $x\_i$ we can partition the set $O$ of all truth assignments into $O = O\_{i,true} \cup O\_{i,false}$ according to the value of $x\_i$. The problem "there exists a truth assignment $x \in O\_{i,val}$ such that $P(x)$" (where $val$ is either $true$ or $false$) is also a SAT problem. We can use this to figure out a truth assignment satisfying $P$.

A more interesting example is 3-colorability. In this case $x$ is a 3-coloring and $P(x)$ states that $x$ is a valid coloring for the input graph. For any two unconnected vertices $v,w$, we can consider the partition $O = O\_{v=w} \cup O\_{v\neq w}$, according to whether $x(v) = x(w)$ or not. We can reduce the problem "there exists $x \in O\_{v=w}$ such that $P(x)$" into an instance of 3-coloring by merging $v$ and $w$. We can reduce the problem "there exists $x \in O\_{v\neq w}$ such that $P(x)$" into an instance of 3-coloring by adding the edge $(v,w)$.

---
Tags: complexity-theory, reductions, polynomial-time
---


title: Rating elements via partial orders

text:
# Question
Title: Rating elements via partial orders
I would like to rate a set of $n$ elements, with each element assigned a rating from ${0,\dots, 10}$.

The way in which I want to rate is by repeatedly selecting subsets of $k$ elements and querying a user to rank them relative to each other. I would like a means of minimizing the number of necessary queries to assign ratings (i.e. "how do I pick which elements I should ask about?"), and a way of aggregating my partial orders into the appropriate buckets ("when do I stop, and how do I map the partial order into my range?").

Are there any decent references I should be looking at?

# Answer
What you're essentially asking is to find a total ordering of a graph of users whose partial orderings are results of querying a user for their relative rank. Your asymptotic complexity of the minimum necessary number of partial orders will relate to the Stirling number of the Second Kind mathworld.wolfram.com/StirlingNumberoftheSecondKind.html. To find this total ordering (re: "how do I map the partial order into my range?") you would topologically sort the graph you're describing. Note that for every vertex, $u\leq\_p v\Rightarrow (u,v) \in E$, and the graph would be directed.
> 2 votes

---
Tags: ordering
---


# Question
Title: Monotone Frameworks: Transfer functions for flow edges instead of labels
So, in generic program analysis, we have a lattice $L$ with a join operation $\sqcup$, program with statements labelled, and for each label $b$, a transfer function $F\_b : L \rightarrow L$.

The goal is to find, for each label $b$, a fix-point $x$ such that $F\_b(x)=x$. This is a common approach used in dataflow analysis,

In "Principles of Program Analysis" by Nielson, Nielson and Hankin, they reference that "Some formulation of monotone frameworks associate transfer functions with edges (or flows) rather than nodes (or labels)." However, in the textbook, they simply reference an exercise where the reader is asked to implement such a framework.

I'm wondering if anyone has a reference to either a book or paper where such a formulation is given. In particular, I'm wondering how a typical worklist algorithm for finding a fixed-point would be formulated.

# Answer
Your formulation is not stated in the way I typically think of it. Traditionally rather than thinking of looking for a fixed point at each node, we're looking for a solution to a system of simultaneous equations:

$$ x\_b = F\_b \left( \bigsqcup\_{p \in \mathtt{pred}\[b\]}x\_p \right) \\; \mathrm{for\\:all\\:nodes}\\:b $$

If $F\_b$ has the distributive property over $\sqcup$ then you can simply rewrite this as

$$ x\_b = \bigsqcup\_{p \in \mathtt{pred}\[b\]} F\_b(x\_p) \\; \mathrm{for\\:all\\:nodes}\\:b $$

and since you have a function evaluation for every edge $p \rightarrow b$ you might as well just rewrite it as

$$ x\_b = \bigsqcup\_{p \in \mathtt{pred}\[b\]} F\_{p \rightarrow b}(x\_p) \\; \mathrm{for\\:all\\:nodes}\\:b $$

If you don't like that handwaving, then here's some more: think of it as taking $F\_b$ for every node with one predecessor ($p$) and pushing $F\_b$ onto the edge making it $F\_{p \rightarrow b}$. For nodes $b$ with more than one predecessor split them into two nodes, $b$ and $b'$. The predecessors of $b$ are still the same, then there's an edge $b \rightarrow b'$ and then the successors of the original $b$ become the successors of $b$. Now the original label $F\_b$ becomes $F\_{b\rightarrow b'}$. The join operation still happens on the nodes.

Note that while transfer functions are associated with edges, data flow *facts* are still associated with nodes. So the worklist algorithm doesn't really change. Actually, with the normal (transfer functions on nodes) formulation, the worklist algorithm is really a worklist of edges, not nodes, so nothing changes. (For an example of this take a look at these slides that came up when I googled for "dominance frontier". http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf. They give the worklist algorithm on page 7, and it's based on edges.)

A paper using the edge formulation is:

> G. Ramalingam: Data Flow Frequency Analysis. *PLDI* 1996: 267-277.

(I haven't read the paper beyond the first couple of pages to see that they were using the edge formulation, it's what came up after a bit of Googling.)

I wasn't familiar with the edge transfer function approach until you asked this question. But I also know of at least two cases where it is important to take edges into account.

The first is when dealing with (post)dominance frontiers. The natural definition of the dominance frontier of a node is a set of edges, but the original (more complicated) formulation was in terms of nodes. See for example the (brief) discussion of this in

> Pingali, Keshav; Bilardi, Gianfranco: Optimal Control Dependence Computation and the Roman Chariots Problem, *ACM ToPLaS*, 19(3):462-491, 1997.

Another example is in the classic

> Knoop, J; Rüthing, O; Steffen, B: Lazy Code Motion, *PLDI*, 1992.

In Lazy Code Motion you sometimes need to move computations onto edges, but in the original formulation in the paper they were trying to move those computations to different nodes, which gave them trouble with branch nodes that target join nodes. They called these *critical edges* and had to add a node along the edge. This is explained in the following lecture notes by Cooper and Torczon: https://www.cs.utexas.edu/~pingali/CS380C/2013/lectures/LazyCodeMotion.pdf
> 3 votes

---
Tags: reference-request, optimization, programming-languages, compilers, lattices
---


# Question
Title: Sum of $\log n$ $n$-bit integers is in $\mathsf{AC^0}$
I am trying to show that the sum of $\log n$ $n$-bit integers can be computed in $\mathsf{AC^0}$. I know that the iterated addition is computable by fan-in $2$ circuits of depth $O(\log n)$, so the sum of $n$ $n$-bit integers is in $\mathsf{NC^1}$. This means that the bound is very tight. I found somes notes here which show that the iterated sum of $n$ $n$-bit integers actually lies in $\mathsf{TC^0}$.

Any help or hint on the subject would be greatly appreciated.

# Answer
Here is a proof sketch. We use the fact that any function on $O(\log n)$ bits can be computed in depth 2 and polynomial size.

1. The input is $\log n$ integers of length $n$, which we can think of as an $n\times \log n$ matrix.
2. Sum the columns of the matrix to get a vector of length $n$ in which each entry has length $\log\log n$. We can also think of this as a staggered sum of $n$ numbers of length $\log \log n$, which is equivalent to the original sum.
3. Divide the staggering sum into blocks of length $\log n/\log\log n$, by possibly dividing each summand into two parts. Each block contains $\log n/\log\log n$ summands of length $\log\log n$. Sum each block to obtain a result of length at most $2\log\log n \leq \log n/\log\log n$ (for large enough $n$). We can think of this as a new staggering sum.
4. Repeat the previous construction. Now each block contains two summands, so the result is of length $\log n/\log\log n + 1$.
5. Again divide into blocks. This time each block contains the sum of a full length ($\log n/\log\log n$) integer $x$ and one extra bit (a least significant bit) $y$. The actual sum also includes an extra carry bit $z$ which depends on the less significant blocks. If we could determine $z$ then we could determine the value of the sum in that block.
6. It remains to show how to calculate the carry bit coming from the addition of blocks $B\_k,\ldots,B\_0$ (most significant to least significant). Suppose that in block $B\_i$ we are adding $x\_i$ to the bit $y\_i$. Let $M$ be a block full of 1s. There is carry iff for some $i$, $x\_k + y\_k = x\_{k-1} + y\_{k-1} = x\_{i+1} + y\_{i+1} = M$ and $x\_i + y\_i = M + 1$.

If you have trouble with the proof sketch (which I haven't described very clearly), try using diagrams. The idea is to start with the initial sum and replace it with progressively simpler but equivalent sums, until the final sum can be computed in one go.
> 3 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Size of decision tree and depth of decision tree
I'm doing some classification experiments with decision trees ( specifically rpart package in R). By setting the depth of a decision tree to 10 I expect to get a small tree but it is in fact quite large and its size is 7650. So what is exactly the definition of size (and depth) in decision trees?

PS: my dataset is quite large.

# Answer
The depth of a decision tree is the length of the longest path from a root to a leaf.

The size of a decision tree is the number of nodes in the tree.

Note that if each node of the decision tree makes a binary decision, the size can be as large as $2^{d+1}-1$, where $d$ is the depth. If some nodes have more than 2 children (e.g., they make a ternary decision instead of a binary decision), then the size can be even larger. So, a size of 7650 is not unreasonable, if some nodes make binary decisions and some make ternary or multi-way decisions.
> 12 votes

---
Tags: binary-trees, classification
---