# Question
Title: What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?
I am aware that as the number increases in Digits the process of locating the two prime numbers that when multiplied produce the given number is increased as well.

I also know that is it somewhat exponential or even more and with current machines it is rendered impossible to do in less than a year to find it for numbers used in an RSA protocol (they are too big).

What I am asking is what is the actual complexity of such a task? I am looking for average and maximum complexity.

# Answer
> 4 votes
Large numbers are factored with the General Number Field Sieve, which is, as of now, the fastest non-quantum algorithm. You can find the heuristic runtime in the linked Wikipedia-article.
Also in use is the Elliptic Curve Factorization, which needs longer runtime in the worst-case, but has the advantage that the runtime depends on the second-largest factor. Thus every now and then it's faster.
The largest "RSA"-number yet factored is a 768 bit number (RSA Factoring Challenge).

# Answer
> 3 votes
The computational complexity of factorization is one of the biggest open problems in computer science. There's a summary of what's known on Wikipedia; the summary of the summary is that it's known to be in both **NP** and **co-NP** so it's unlikely to be **NP**-complete, or the polynomial hierarchy collapses.

---
Tags: time-complexity, cryptography, integers, factoring
---


# Question
Title: Encoding of integer arithmetic counting using Lambda calculus
Does anyone know a way of showing an encoding of integer arithmetic counting using Lambda Calculus?

Any references related to this would be much appreciated.

# Answer
arithmatic means normal addition,negation, etc. kind of things, you can observe this as let say we expect from a programming language that it should be capable of doing arith-metical calculations. Numbers can be represented in lambda calculus starting from zero and writing “suc(zero)” to represent 1, “suc(suc(zero))” to represent 2, and soon. In the lambda calculus we can only define new functions. Numbers will be definedas functions using the following approach: zero can be defined as

λs.(λz.z)

1 ≡ λsz.s(z)

2 ≡ λsz.s(s(z))

3 ≡ λsz.s(s(s(z)))

for more info go through this PDF \[1\]

\[1\]http://www.utdallas.edu/~gupta/courses/apl/lambda.pdf
> -1 votes

---
Tags: lambda-calculus, arithmetic
---


# Question
Title: Is the maximum coverage variant of Vertex Cover also NP-hard?
In Chapter 3 of "Approximation Algorithms for NP Hard Problems" edited by Prof. Dorit S. Hochbaum, there is such a sentence that "Maximum Coverage Problem is clearly NP-hard, as Set Cover is reducible to it" in p.135.

> Given a set system G and a parameter k, Maximum Coverage Problem is to find k sets such that the elements covered is maximized, and Set Cover Problem is to identify the smallest size of sets so that all elements are covered.

I am curious about how this reduction is conducted?

Further, considering the Vertex Cover problem which is to find a cover with smallest number of vertices, can I reduce this problem to the following problem in the same way:

The problem of concern:

> Given a Graph and a parameter k, find k vertices such that the number of edges linked to these vertices is maximized.

Is this problem also NP hard?

# Answer
> 4 votes
Optimization problems cannot be NP-complete. Only decision problems – where the answer is YES or NO – can be NP-complete. This is because the notion of NP-completeness is defined only for decision problems. When we (loosely) say that an optimization problem is NP-complete, we really mean that their decision version is NP-complete.

The decision version of Set cover: given a set system $S$ with union $U$ and a number $r$, can we cover $U$ with $r$ sets from $S$?

The decision version of Maximum coverage is: given a set system $S$, a number $r$ and a number $t$, are there $r$ sets from $S$ that together cover at least $t$ elements?

See if you can prove that the decision version of Maximum coverage is NP-complete given that the decision version of Set cover is NP-complete, and then see if you can do the same for your new problem related to Vertex cover.

---

I should mention that Uri Feige proved in 1998 the following strong result regarding Maximum coverage. There is a polytime reduction $f$ taking a 3CNF $\varphi$ to an instance $(S,r,t)$ of Maximum coverage such that:

1. If $\varphi$ is satisfiable then there are $r$ sets from $S$ that together cover at least $t$ elements.
2. If $\varphi$ is not satisfiable then all choices of $r$ sets from $S$ cover at most $(1-1/e)t$ elements.

Informally, we say that it is NP-hard to approximate Maximum coverage up to $1-1/e$. Why?

A polytime algorithm $A$ for Maximum coverage is a $\theta$ approximation if given an instance $(S,r)$ with optimal value $O$, $A$ outputs a subset of $S$ of size $r$ that covers at least $\theta O$ elements. If there was a polytime $1-1/e+\epsilon$ approximation algorithm for Maximum coverage, for *any* $\epsilon \> 0$, then you could use it to solve 3SAT, as follows:

1. Given $\varphi$, run $f$ and calculate the instance $(S,r,t)$.
2. Run $A$ on $(S,r)$, getting a cover which covers $B$ elements.
3. $\varphi$ is satisfiable iff $B \> (1-1/e)t$.

I leave you to figure out why this works.

The approximation ratio $1-1/e$ is achieved by the greedy algorithm, so this result is optimal.

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


# Question
Title: Solving the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$ using a recursion tree
I have homework from recursion tree and despite my search for hours I could not find the answer to this problem.

I appreciate if you can help.

> Draw a recursion tree and give a tight asymptotic bound on the solution of the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$. You need not prove your answer.

# Answer
> 0 votes
I don't know what a recursion tree is, but I know how to expand a formula: $$ \begin{align\*} T(n) &= 2^{n/2} T(n/2) + 2^n \\ &= 2^{n/2} (2^{n/4}T(n/4) + 2^{n/2}) + 2^n \\ &= 2^{(3/4)n} T(n/4) + 2^n + 2^n \\ &= 2^{(3/4)n} (2^{n/8} T(n/8) + 2^{n/4}) + 2^n + 2^n \\ &= 2^{(7/8)n} T(n/8) + 2^n + 2^n + 2^n \\ &= \cdots \end{align\*} $$ You take it from here, along the following lines:

1. Assume that $n$ is a power of $2$. How many times do we need to apply the recurrence identity until we get to $T(1)$? (Above I applied it three times and got down to $T(n/8)$.)
2. When we do get to $T(1)$, what are we left with? (When we get down to $T(n/8)$, we are left with $2^{(7/8)n} T(n/8) + 3\cdot 2^n$.)
3. Suppose that $T(1) = C$. Can you come up with a formula for $T(n)$? Can you deduce a tight asymptotic bound?

---
Tags: trees, recursion
---


# Question
Title: Could two decidable languages ever not have a mapping reduction?
Is it ever the case that two decidable languages $L\_1$ and $L\_2$ that cannot be reduced to one another (in either or both directions)? Intuitively, I would not expect there to be, but rigorously, are there extreme examples that prove otherwise?

# Answer
> 6 votes
If you are talking about reduction in general (not polynomial reduction), then you basically can put all the logic in the reduction function. Suppose $L\_1$ and $L\_2$ are decidable languages. To reduce $L\_1$ to $L\_2$ we need a computable function $f$ such that $x\in L\_1 \Leftrightarrow f(x)\in L\_2$. The function $f$ just works as follows. Given a word $a\in L\_2$ and a word $b \notin L\_2$:

> $f(x) = \begin{cases} a & \text{if } x \in L\_1 \\ b & \text{if } x \notin L\_1 \end{cases}$

This function is computable because $L\_1$ is decidable by assumption.

However, the above also points you to the exceptions. It assumes that there is a word $a\in L\_2$ and a word $b\notin L\_2$, and there exactly two languages for which this is not the case. Both of those languages are decidable.

---
Tags: computability, reductions
---


# Question
Title: What is the lower bound for finding the third largest in a set of $n$ distinct elements?
> What is the lower bound for finding the third largest in a set of $n$ distinct elements?

For the case of finding the second largest, we have the tight lower bound of $n + \lceil \lg n \rceil -2$. The adversary argument can be found in this lecture, which also provides an optimal algorithm using the "Tournament Method".

---

***Edit (04-04-2017):*** Removing the algorithm for finding the third largest element which turns out to be wrong.

# Answer
*Answer my own question:*

At the end of "Lecture 28: Adversary Arguments" by Jeff Erickson, I found

> A similar argument implies that at least $n - k + \lceil \lg {n \choose k-1} \rceil = \Omega \big( (n - k) + k \log (n / k) \big)$ comparisons are required to find the $k$-th largest element in an $n$-element set. This bound is tight up to constant factors for all $k \le n/2$; there is an algorithm that uses at most $O \big( n+k \log(n/k) \big)$ comparisons. Moreover, this lower bound is *exactly* tight when $k = 1$ or $k = 2$. In fact, these are the *only* values of $k \le n/2$ for which the exact complexity of the selection problem is known. Even the case $k = 3$ is still open!

Therefore, the *current* answer to the question is that it is still unknown.
> 2 votes

---
Tags: complexity-theory, reference-request, time-complexity, lower-bounds, search-problem
---


title: Why are computers so reliable?

text:
# Question
Title: Why are computers so reliable?
In any complicated system, there is always some scope for error. When I program on my computer, the system computes perfectly each time. 1+1 always turns out to be 2. We take reliability of the computer almost for granted. What gives modern computers it's reliability? Are there no errors in computation, or errors, if any, are corrected by some means?

# Answer
> 8 votes
Computers rely on physics. Transistors have some known characteristics, given some assumptions on making process. Parts that does not meet the exepected characteristics are just trashed (or sold with lower expectations, usually lower max frequency).

This ensure that computations are correct while complying operation conditions (stable power supply, EMC, ...). The whole systems are built to meet those requirements. When you use very cheap equipment (often a cheap power supply), you may face some computer crashes, as you do not meet system requirements (power supply stability) anymore.

Sometimes, external conditions make expectations unreachable. In aeronautic and aerospace, systems have to cope with cosmic rays that may disturb their behavior. In such case, several similar systems are used in parallel, to be able to maintain operation when one system has errors.

Also, some transmissions and storages are known to be unreliable, and Error Correction Codes are used to fix the data after reception.

So systems are designed to prevent errors to happen in almost every cases, using a broad range of dedicated methods. Working in consumer electronics, I have some failure rates on the hardware around 10 faulty parts per million in the first year of use. This is much better than the mechanical parts or the software, but not perfect (even if it's too good for the consumer market. Average return rate on consumer products is around 1%, 100 faulty parts per million would be acceptable on this market).

---
Tags: computer-architecture, reliability
---


# Question
Title: Average time to solve maze through backtracking
Given a set A consisting of all possible solvable mazes on an n by n square grid, what is the average running time to solve the mazes in A using a standard backtrack algorithm with no optimizations?

The algorithm checks each ajacent space clockwise for a channel, then visits each channel and either marks it off if it encounters a dead end, or previously covered point, or if it reaches the end point the algorithm completes.

This question was on an exam, and I figured O(n^2) cause there is O(n^2) spaces to visit for each maze, but my prof insisted the correct answer could be O(n log n).

A proof would be greatly appreciated.

Thanks!

# Answer
> 2 votes
Your question on the exam is asking for average case analysis -- visiting all the cells to solve the maze is the worst case.

Informally think this way: Whenever you move to a new cell, you can move to at maximum 3 directions, which one direction is to go back to your previous cell (this choice is discarded since it's of course not what you want to do to explorer the maze.) In the two other options left, one of the direction will lead you to the target, the other one does not. What's the expectation of find the target in each move? Does it hint something $O(n \log n)$?

Also try to picture this as you are exploring a tree structure. What's the average height of a tree?

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


# Question
Title: Which permutations can not be obtained by moving elements through two stacks?
I have a Stack1 which has the entries a,b,c ( with a on the Top) and Stack2 which is empty.The condition is.

> An entry pooped out of the stack1 can be printed immediatly or pushed to stack2. An Entry popped out of the stack2 can only be printed.

In this Arrangement, which of the permutation of a,b,c is not possible.

I tried diagrammatically by popping out the initial stack and found the first arrangement as c,a,b...Then i mind a formula taught in Permutation's course as (n-1)! possibilites so came up with answer of 5.

so, which arrangement will be not possible.??

# Answer
This process is called stack sorting. Wikipedia has a page on the subject.

Here you read that the number of possible sequences when the input is $1,2,\dots,n$ equals the Catalan number $C\_n = \frac{1}{n+1} {2n\choose n}$, which differs from your guess.

In fact there is a nice characterization of the orders which are possible, they avoid the permutation pattern $231$. However your problem is "backwards", not the strings that can be sorted using a single stack, but the strings that can be obtained that way.
> 1 votes

---
Tags: data-structures, combinatorics, stacks
---


# Question
Title: Doesn't a formula that tests each boolean string of length $N$ force SAT to execute at least $2^N$ tests?
Since you are free to chose any formula for the SAT problem, doesn't the choice of a formula that requires a test for each subset of the group of variables force it to perform $2^N$, essentially making SAT unsolvable in polynomial time in respect to the number of variables on the input?

# Answer
> 3 votes
When talking about the complexity of SAT, we usually care only about the complexity in terms of *input size*. This is because the classes P and NP are defined this way: they are oblivious to what the input represents. Your formula, while depending on a small number of variables, will be very long.

3SAT is nicer in this regard, since assuming clauses don't repeat and every variable appears at least once, the number of variables, the number of clauses, and the bitlength of the input are all polynomially related, so from the point of view of complexity theory, any of them could serve as the parameter against which complexity is measured.

Moreover, I don't see why any particular choice of formula would "require a test for each subset of the group of variables". We don't know how to substantiate claims of this sort in the case of SAT.

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Is the Source Coding Theorem straightforward for uniformly distributed random variables?
Shannon's source coding theorem states the following:

> $n$ i.i.d. random variables $X\_1,\dots,X\_n$ each with entropy H(x) can be compressed into more than n⋅H(x) bits with negligible risk of information loss, as n→∞; conversely if they are compressed into fewer than n⋅H(x) bits it is virtually certain that information will be lost.

I was thinking about the easy case when the $X\_1,\dots,X\_n$ are uniformly distributed on the integers $\[1,n\]$. Now suppose I want to transmit a value of $(X\_1,\dots,X\_n)$. Clearly, each $X\_i$ has entropy $\log n$ and thus, if we were to send $o(n\log n)$ bits, we would lose information about some of the $X\_i$, with high probability $1 - o(1)$.

The way to argue the Theorem for this case, is that it $\log n$ bits suffice to reconstruct any $X\_i$, and conversely, if you receive, for example, only $(1/4)n\log n$ bits, then, you would need to correctly guess $3/4 n\log n$ bits, which happens with probability of only $2^{-3/4n\log n}$. Is my reasoning correct?

# Answer
The theorem you quote is not stated formally, so it is in fact impossible to prove it. That said, the idea behind the source coding theorem is that a variable of entropy $H(X)$ behaves (roughly) as if it was uniformly distributed on $2^{H(X)}$ values. When the distribution of $X$ is uniform, the theorem becomes trivial, once stated formally. So it's a good idea for you to look up a formal statement of the theorem, and then verify that it indeed holds for uniformly distributed random variables.
> 1 votes

---
Tags: probability-theory, information-theory, coding-theory
---


# Question
Title: Find a CFG for the set of prefixes of a CFL
How do i generate grammar for Prefix of Langauge L, SupposeG=(V,,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈∗ : ∃ y such that xy∈L}.

I understand for Suffix(L) we would do something like this .. Can someone here help me how do we do for the Prefix(L) if L is CFL.

1. For each variable X of G , add a new variable X' . (X' will generate the suffixes of the language that is generated by using X as the start variable.)
2. Whenever X' →YZ is a rule of G , we add two new rules,X' →Y' Z and X' → Z' .
3. for each variable in G , we add X' → X and X' → ε
4. If S is the start variable of G , we let S' be the start variable of G'. Now the new CFG G' can generate the suffix of A , and hence context-free language is closed under the suffix operation.

# Answer
If you know how to do *Suffix*, then you also know how to do *Prefix*. Explicitly, show how transform a context-free grammar for a language $L$ to a context-free grammar of its *reverse* $L^R = \\{x^R : x \in L \\}$, where $x^R$ is the word $x$ in reverse (for example, $(for)^R = rof$). Then use the fact that $$ \mathit{Prefix}(L) = \mathit{Suffix}(L^R)^R. $$ If you unroll this definition, you will actually get a direct construction for *Prefix*.
> 3 votes

---
Tags: formal-languages, context-free, formal-grammars, closure-properties
---


# Question
Title: Are there any exponential-time iterative algorithms?
Is it possible to implement an exponential-time algorithm using iteration, as opposed to recursion? I didn't have any particular algorithm in mind, I was just thinking theoretically.

The way I was thinking was to iterate not by adding 1, but by adding a small number j at the end of each loop. So the 3rd parameter in the for-loop would look like i+j instead of i++, and j would be really small (negative exponent perhaps? Like 2^-n)... Still, I'm not sure how such an algorithm could actually work, though.

Thanks for any input.

# Answer
> 1 votes
Yes. Given an input of length $n$, overwrite it and use the space to count to $2^n$ in binary.

Once you've done that, you could write out $2^n$ zeroes and then count to $2^{2^n}$ and so on, *ad infinitum*.

# Answer
> 0 votes
Many combinatorial algorithms can be implemented recursively and usually have exponential time complexity. For example, if S is a set, all the possible permutations of the elements in S can be computed using the following:

```
permutations(S): list[tuples] {
  c = an empty list of tuples
  for each x in S
    S' = S \ x
    for each tuple y in permutations(S')
      x.append([x, y])
  return c
}

```

where the notation `combinations(S): list[tuples]` means that the method returns a list of tuples and the notation `[x, y]` represents the concatenation of the element `x` (or the one element tuple `x`) and the tuple `y` and indentation indicates nesting. The code above is actually O(n!) which if I'm not mistaken is actually \> O(2^n).

---
Tags: algorithms, asymptotics, recursion
---


# Question
Title: How can random array access be considered $O(1)$ if bits must be stored in space and light travels at finite speed?
Bits are usually stored linearly in space. We can say, thus, that the length of a memory chip, for example, is linearly proportional to the number of bits it can hold. Since signals must travel at finite speed in our universe, the time it takes to read the last element an array will always be proportional to the length of the array. Am I missing something?

# Answer
When we talk about "running time" of algorithms, we don't mean literally time in seconds but number of operations in some abstracted machine model. In such a model, accessing a memory cell is taken to be a single operation, taking unit time.

Note that this is hiding much more significant details of real computers than the speed of light across a chip. Whether or not the required data is in the cache will have a much more significant effect than any consideration based on the speed of light.
> 4 votes

# Answer
Think of it in terms of the number of statements that need to be executed to perform what you want.

The growth factor of the function f(n) is O(n) if the runtime increases linearly with the size of the input. If you are iterating through an entire list, going through 100,000,000,000,000 should time a proportionally longer time than iterating through 100 elements. Obviously, you are executing the (same) statement many more times, so it takes more time to process.

The growth factor of the function f(n) of accessing an element in an array doesn't depend on the size of the input (its a simple access to an offset of an address), so its constant O(1). Accessing the ith element of an array of 100,000,000,000 elements shouldn't take any appreciable more time then accessing the ith element of an array of 100 elements. In both cases, you end up with "go to to my address + i and return the value there". One statement.
> 2 votes

---
Tags: complexity-theory, asymptotics
---


# Question
Title: Is Bin-Packing with only 2 types of objects polynomial?
**Is the following problem polynomial ? Or NP-Complete ?**

**Problem:** Bin packing with 2 types of objects.

**Input:** $C$, the capacity of each bin, $N\_a, N\_b$ the numbers of objects $a$ and $b$, $w\_a,w\_b$ the weight of the objects, $k$, the maximum number of bins.

**Output:** Yes if all objects fit in the $k$ bins without exceeding the capacity of any bin or cutting objects, No otherwise

My first intuition was that with only two types of objects, there must be less solution and maybe enumeration is polynomial, so I tried count them.

For an instance of size $n$ (with $n$ objects), we can encode solutions as $n$-tuples $\[0,1,1...,0,1\]$ (the first objects being in the first bin until it's full, then the second, etc). For instances of size $n$, there are $2^n$ distinct solutions. Since there are $n$ instances of size $n$ (I mean, $n$ pairs $(N\_a,N\_b)$ such that $N\_a+N\_b=n$), and by the pigeonhole principle, there must be an instance with at least $2^n/n$ solutions. So a simple enumeration of solutions doesn't work.

Then, I started thinking that the problem may be NP-Complete. Reducing a graph problem seems no to be a good idea: graphs are big structures, and this problem as only a few numbers as an input. At this point, I realized that all the NP-Complete problems I've heard of had biggers inputs.

Now, I'm a bit confused. I can't figure out a good algorithm or a reduction.

# Answer
The problem can be solved in polynomial time. See A Polynomial Algorithm for Multiprocessor Scheduling with Two Job Lengths, An Asymptotically Exact Algorithm for the High Multiplicity Bin Packing Problem, or On the bin packing problem with a fixed number of object weights.
> 1 votes

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


title: Big O notation and "input"

text:
# Question
Title: Big O notation and "input"
Suppose I have an algorithm that reads lines in a file(linear) and for each line in the file, it sorts each word(nlogn). This algorithm is mnlogn, where m is the number of lines and n is the number of characters in a word.

Asymptotically, as the file gets longer the number of lines becomes small in comparison to the number of characters, so the running time of this algorithm is O(nlogn)? How do you determine big O like this where the inputs are different?

# Answer
The asymptotic running time of your algorithm is $O(mn\log n)$, as you mention. If we don't know anything further about $m$ or $n$, there is no way to simplify this. If you know that $m = O(f(n))$, then the running time is also $O(f(n)n\log n)$. For example, if you know that $m = O(\sqrt{n})$, then the running time is also $O(n^{1.5}\log n)$. It will be $O(n\log n)$ only if $m = O(1)$, that is, $m$ is constant.
> 1 votes

---
Tags: algorithm-analysis
---


title: Black box with O(n) calls

text:
# Question
Title: Black box with O(n) calls
Let's say a procedure called 'decision(x,q)' is available as a 'black box' X is the input set and Q is a real number Q.

I need to design an algorithm that reports "yes" if there exists a subset of X whose total sum is = Q otherwise, it reports "no".

Running time is not an issue, it just needs to have all actual numbers in the subset and it can't make more than O(n) calls to the procedure.

I believe this can be solved with dynamic programmming.

# Answer
I believe you have misunderstood the question. You are given a black box that can answer queries of the form "does $X$ have a subset summing to $Q$", and you need to construct an algorithm that given $X$ and $Q$, finds a subset summing to $Q$ if one exists.

Here is a hint:

> Choose an arbitrary $x \in X$. Ask the black box whether there is a subset of $X - x$ summing to $Q - x$.
> 2 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Dynamic Programming Subset Sum Problem with twist
Question: You are given an input , which is a sequence of positive integers $w\_1, w\_2, . . . , w\_n$ with parameters $W, ∆. $We wish to find $S ⊆ \\{1, 2, . . . , n\\}$ such that $\sum\_{j \in S} w\_j$ is as large as possible, subject to the constraints that (a)$\sum\_{j \in S} w\_j≤ W$, and (b) for all $i, j ∈ S$, if $i \neq j$ then $|w\_i − w\_j | ≥ ∆.$

Here is the recursive formula I came up with (which is incorrect).

$$OPT(i,w) = \begin{cases} OPT(i-1, w) & : \text{if } w \< w\_i \\ w\_1 & : \text{if } i = 1 \text{and } w\_1 \le W\\ OPT(i, w) = max(OPT(i-2, w), OPT(i-1, w), w\_i + OPT(i-2, w-w\_i)) & : \text{if } |w\_i - w\_{i-1} | \< \Delta\\ OPT(i, w) = max(OPT(i-1, w), w\_i + OPT(i-1, w-w\_i)) & : otherwise \end{cases}$$ A The problem with the above formula is that it only checks if the $i-1^{st}$ weight is compatible with the $i^{th}$. It doesn't check if the $i^{th}$ weight is compatible with all the weights in the optimal solution. For example, if $\Delta = 2, W = 6, w\_1 = 3, w\_2 = 1, w\_3 = 2$ then the recursive formula returns 5 instead of 3.

I would appreciate any help. Thanks.

# Answer
Hint: Arrange the weights in increasing order. You might also need to make other changes, but sorting the weights is a good first step.
> 2 votes

---
Tags: dynamic-programming
---


# Question
Title: Can we obtain a state diagram of a single Turing machine
When illustrating what states are in Turing machine, often the examples of programs, like a checker that checks an input number is even number, are given. But different programs seem to have different number of states - if so, how can Turing machine be described with the set of finite number of states, along with others? In other words, if we follow the formal definition of Turing machine, can we construct a state diagram of a Turing diagram, assuming infinite memory exists?

# Answer
> 1 votes
There are two possible meanings of state here:

1. One of the finite states in the finite control mechanism of the Turing machine.
2. The entire state of the Turing machine, including its internal state (the one from the previous definition), the locations of the heads, and the contents of the tapes.

If you are looking for a state diagram of the second type, then it's infinite. If you're looking for a state diagram of the first type, then it's finite.

*Different programs seem to have different number of states* – every program is finite (has finitely many states, under the first interpretation above), but there is no bound on its length: it can be as long as you want, as long as it's finite. The same is true for Turing machines.

---
Tags: computability, turing-machines, computation-models
---


# Question
Title: Simulate a regular Turing Machine with one that cannot write blanks
Consider a Turing machine that cannot write blanks. How does one show that such a machine can simulate a standard Turing machine?

# Answer
To simulate a Turing machine $M$ that can write blanks with a Turing machine $M'$ that can't, just give $M'$ an extra character in its alphabet. Whenever $M$ writes a blank, $M'$ writes this new character and, whenever $M'$ sees the blank or the new character, it does what $M$ would do if it saw the blank.
> 1 votes

---
Tags: turing-machines, computation-models, simulation
---


title: Designing a prefix code for integers?

text:
# Question
Title: Designing a prefix code for integers?
trying to figure out how to approach this problem.

> Suppose a sender in a network wanted to communicate the length n of the block it will be using in a subsequent transmission. If there were not limits on the value of n, there would be a problem to simply send the number in binary, since the receiver would find it difficult to know where the end of the number is. Hence we need to encode the integer n using some variable length prefix code, and send the code for n before the code of the length-n block. Design a prefix code for integers and show that an integer n can be encoded with a codeword of length at most log n + O(log log n) - bits.

So I know Huffman's greedy algorithm for generating prefix codes, but I don't have any frequencies to build the 2-tree. I was thinking to solve the problem, I would build a tree for 0-9, but I have a feeling I'm way off with that approach. I'm also not quite sure how to show that an integer can be encoded using log n + O(log log n) bits.

Any help to get me started would really be appreciated. Thank you for your time!

# Answer
The following code is often used as a *standard prefix-code for natural numbers*, which bounds the length of each codeword by $\log n+O(\log\log n)$:

At first, we identify the natural numbers by binary strings: $$(0,\epsilon),(1,0),(2,1),(3,00),(4,01),...$$

Lets call $l(x)$ the length of the binary representation of the natural number $x$. Note that for each $x\ge2$ the following holds: $$\lfloor\log x\rfloor\le l(x)\le \lceil\log x\rceil$$

Secondly, lets define $s(x\_1x\_2...x\_n)=\underbrace{11...1}\_{n\text{ times}}0x\_1x\_2...x\_n$ for binary sequences $x\_1x\_2...x\_n$.

Note that the length of $s(x\_1x\_2...x\_n)$ is $2n+1$. Lets further define $x'=s(l(x))x$, where both, $l(x)$ and $x$ are interpreted as their binary representations.

Finally, the code $D(x')=x$ is a prefix code satisfying that for each natural number $x$, the length of the encoding $x'$ is $\log x+2\log\log x+1$ (ignoring the rounding error).
> 4 votes

---
Tags: algorithms, data-compression, encoding-scheme
---


title: Prove Σ* is decidable

text:
# Question
Title: Prove Σ* is decidable
I see that Σ\* is claimed to be decidable in many documents, but I have never seen an example or easy demostration that it is decidable.

What is the proof that Σ\* is decidable?

# Answer
> 5 votes
**Theorem:** *The set $\Sigma^{\*}$ of all words is decidable.*

*Proof.* According to the definition of decidability, we must provide a computable function $d$ which takes a word $w$ and outputs $1$ if $w \in \Sigma^{\*}$, and outputs $0$ if $w \not\in \Sigma^{\*}$. Such a function is very easily constructed, it is $$d(w) = 1,$$ That is, because every word is in $\Sigma^{\*}$, the decision function always says "yes". QED.

---
Tags: computability
---


title: Simple question COQ

text:
# Question
Title: Simple question COQ
I'm a beginner in the coq proof assistant, so sorry if my question is silly. I would like to prove properties of a mathematical object. For clarity I will describe an over-simplified version of my object. Intuitively, the object has three sets A, B, C. The list A is of the form $$A= \\{(0,x\_1) (0,x\_2), ... ,(0,x\_n)\\}$$ i.e, all pairs consist of the number zero and an arbitrary number. Analogously, the set B is of the form $$B = \\{(1,y\_1)(1,y\_2)...(1,y\_m)\\}$$. And the set $C$ is such that C = A U B. For concreteness the sets $A,B,C$ can be defined as lists, if for some reason it is not inconvenient in Coq

So the simplified object would be of the following form:

Object

A : Set of elements of the form (0,x) where x is some number

B : Set of elements of the form (1,y) where x is some number

C : Set such that C = A U B

The Condition that the structure must satisfy is:

If (0,a) belongs to A then (1,a) belongs to B.

**Questions:**

1) How do I define a type consisting of pairs in which the first element is 0 and the second an arbitrary natural number? (Obs: This was answered by @KonstantinWeitz but his answer received a minus. Why wouldn't Konstantin's answer be satisfactory in Coq?)

2)How do I define the object above in coq? I tried to do it with records. But the problem is that I have no idea of how to define a type of question 1.

3) How to I impose the condition that this object is valid only if for each (0,x\_n) in A there is a (1,y\_n) in B with y\_n=x\_n? And the condition that $C = A \cup B$?

# Answer
> 2 votes
Set-theoretic thinking is creating trouble, as you are trying to do things in non-Coq ways. Let me show you a solution which works better, and then you can explain what your actual non-simplified problem is -- we can probably optimize that one to.

If we have two lists `A` and `B` then we do not have to tag the elements of the first list with 0 and the second one with 1. That is, rather than having

> `A = [(0,x_1), ..., (n,x_n)]` and `B = [(1,y_1), ..., (m, y_m)]`

we can equivalently have just

> `A = [x_1, ..., x_n]` and `B = [y_1, ..., y_m]`.

So, we are really trying to define:

> *A pair of lists such that the elements of the first one are contained in the second one.*

We are going to use the standard library for lists (by the way if you are simulating sets by using lists, you shouldn't).

```
Require Import List.

(* We define what it means for the elements of list X to be
   contained in list Y. *)
Definition contained_in {T} (X : list T) (Y : list T) :=
   forall x, In x X -> In x Y.

(* Now we define our data structure. It is a Record with three fields. *)
Record MyLists := {
  A : list nat;
  B : list nat;
  valid : contained_in A B
}.

(** For example, suppose we want to construct A = [1,2,3] and B = [2,3,3,1,5]. *)
Definition example : MyLists.
Proof.
  (* We give Coq the fields we know about. *)
  refine {| A := 1::2::3::nil ; B := 2::3::3::1::5::nil |}.
  (* Coq tells us we also have to provide the 'valid' field. *)
  (* We tell Coq to do it itself. *)
  firstorder.
Defined.

```

# Answer
> -1 votes
Here you go:

```
Require Import List.

Definition Singleton (n:nat) := {n':nat | n' = n}.   (* 1) *)

Definition zero : Singleton 0. compute. eauto. Defined.
Definition one : Singleton 1. compute. eauto. Defined.

Record MyLists := {   (* 2) *)
  A : list ((Singleton 0) * nat);
  B : list ((Singleton 1) * nat);
  valid : forall n, In (zero,n) A -> In (one,n) B   (* 3) *)
}.

```

---
Tags: coq, proof-assistants, inductive-datatypes
---


# Question
Title: Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$
Can anyone tell me what is the difference between the following regular expressions: $(0^\*1^\*)^\*$ and $(0+1)^\*$ ? To me they look like generating the same string.

# Answer
> 9 votes
The language of both regular expressions is the same, $L((0+1)^\*)=L((0^\*1^\*)^\*)$. This follows from the following three claims:

### Claim 1:

> if $L\_1 \subseteq L\_2$, then $L\_1^\* \subseteq L\_2^\*$.

### Claim 2:

> $L(0+1) \subseteq L(0^\*1^\*)$

### Claim 3:

> $ (0^\*1^\*)^\* \subseteq (0+1)^\* \equiv \Sigma^\*$

The 2nd and 3rd claims are trivial. Prove the first claim and you're done.

Note however, that the two regular expressions are not *the same* (ie., they are different!). They are **equivalent** in the sense of the language they generate. They are different in *the way* they generate it.

# Answer
> -3 votes
They are not the same. When we say $0+1$ it signifies a union operation, which is "either or". So either $0$ or $1$ can be present and the ${}^\*$ indicates that it can be present any number of times.

On the other hand, $01$ is a concatenation of the symbols $0$ and $1$. So $(0^\*1^\*)$ means $0$ can occur any number of times followed by $1$ occurring any number of times and the outer asterisk denotes that such a sequence can occur in the string $n$ times.

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Understanding a proof in the sweep line algorithm when finding all line segment intersections
You have a set of line segments and you want to find all intersections.

**First sweep line approach:**

Use a priority queue `Q` for the events as they come, where each event is just an end point of a line segment.

Use an unordered list `L` for the status of the sweep line, that is, all the segments that are currently intersecting the sweep line.

If you reach a beginning of a new segment, add it to the status and test it for intersections against all other segment in the status.

If you reach an end of a segment, remove it from the status.

This algorithm is `O(n^2)` if for example all segments are intersecting the x coordinate and assuming that you are sweeping from top to bottom.

**Second sweep line approach:**

It can be proved that we only have to test for intersections horizontally adjacent segments that are currently in the status of the sweep line. If you understand this proof then you can just use an ordered set for the status and come up with an easy `O(nlogn)` algorithm.

Here's part of the proof that I don't understand:

I don't think this is a clean proof of the lemma. Events are only either end points or intersections. So in practice the sweep line will never have no event points on it and from the image it seems like the sweep line is moving continuously, which is wrong because the sweep line moves from either an end point to another end point or end point to an intersection or an intersection to another end point.

How would you prove this lemma correctly?

# Answer
> 1 votes
The proof is absolutely correct. Of course, the algorithm only computes something when the sweep line comes to an eventpoint. Nevertheless you can think of the sweep line as a continiously moving line even if the algorithm does not hold everywhere to compute something.

Therefore you can always find a position, where the sweep line $l$ is close enough to $p$ and has no event point on it. In other words, you can always find a position above $p$ without eventpoints, where $p$ is the next eventpoint (maybe one of many). On this position, $s\_i$ and $s\_j$ are adjacent. There is no word here, that the algorithm computes something at this point and there is no conflict between the continuously moving sweep line and the discrete computing-positions of the algorithm.

---
Tags: algorithms, proof-techniques, correctness-proof
---


# Question
Title: Shouldn't complexity theory consider the time taken for different operations?
I have read the answer found here which considers the size of integers when doing comparisons and how that affects on the basic cost of comparison.

I am trying to understand why each basic operation takes $O(1)$ time. For example branches in general are considered to run in $O(1)$ time when they usually don't.

In computer architecture branches are considered the most time-consuming and problematic part of the code and this is one of the reasons why a loop is unrolled by the compiler in order to reduce the amount of branches the processor needs to execute.

For example a simple branch (let's say `if a>b`) needs to do at least four things

1. Get `a` from memory (whether it is cache or RAM or on disk does not matter; cache misses and hits are a different field of study).
2. Get `b` from memory
3. Evaluate the two and select the proper answer
4. Search in instruction memory a new value for the Program Counter depending on the result of the evaluation.

Now get the variables from RAM is something done everywhere. So let's not count that. But since all modern processors load more than just one instruction from instruction memory (let's say for our case 100) so as to reduce instruction memory accesses and a branch usually leads to a different place in the instructions list (let's say `if a>b` call a method that swaps them), that would mean that branches take a lot more time than any other basic function.

Also in all modern processors multiplications and divisions take significantly much more time than additions and subtractions. Which is the reason why when multiplying or diving by numbers that are powers of two we should use logical bit shifting.

I know that in CS Theory and evaluating an algorithm we do not care. But in practice when implementing an algorithm the operations we use really effect the efficiency and complexity of our code.

So let's say we have three algorithms

1. $n$ additions
2. $n$ multiplications
3. $n$ branches

In Theory all three of these compute in time $n$ but in practice, 1 is faster than 2, which is faster than 3.

# Answer
> 7 votes
All complexity theory is relative to some model of computation. Typically, we consider models of computation where all basic operations take unit time because that's usually precise enough and, frankly, it's already difficult enough to do that kind of analysis.

Typically, running time analyses are only quoted asymptotically anyway. As long as there's a constant bound on the number of clock cycles required for any operation, saying that an algorithm takes $O(f(n))$ operations is exactly the same thing as saying that it takes $O(f(n))$ clock cycles: the difference is just in the constant hidden in the $O()$ notation.

Having said that, models of computation *do* vary in what operations they consider as being unit-cost. For example, ordinary Turing machines count moving the head one step as unit-cost; random access Turing machines can move the head farther at unit cost. People who study the complexity of matrix multiplication are often interested in the number of times you need to multiply matrix elements, rather than the total number of arithmetic operations, precisely because of your observation that multiplies are significantly more expensive than additions on a real CPU.

But, again, many things are swept under the carpet by asymptotic analysis. Suppose you did produce a model in which branches are much more expensive than other operations. Fine but, if you have a loop that needs to be iterated $n$ times, where $n$ is an input, your compiler can only unroll a constant number of iterations of the loop. So, instead of doing $n$ branches, you do, say, $n/8$ branches: that's still $O(n)$.

# Answer
> 3 votes
actually complexity theory has *many* "timing" and "cost" models but these tend to be more advanced and are not typically outlined at earlier/ introductory levels (where just the difficulty of asymptotic complexity analysis can be nontrivial or even difficult at times). some take into account the complexity of "low level" operations. for example

* arbitrary precision arithmetic. see eg analysis of the complexity of the RSA algorithm or factoring large numbers. here arithmetic operations scale roughly at $O(n)$ or $O(n \log(n))$ for the size of the numbers instead of "unit cost".
* there is a model called the RAM model of computing where their complexity is not exactly equivalent to other standard models eg Turing machines for array access etc.
* cache oblivious algorithms are designed to scale well with arbitrary size caches.
* even circuits can be considered a basic computation model that are not exactly identical in complexity to Turing machines & other models

there are many others! so the answer is yes, CS is a vast field now and has many theoretical models for the complexity of computation which are used according to context/ relevance.

# Answer
> 0 votes
What if someone came up with a new architecture (maybe something that is not based on transistor tech at all) which has different performance characteristics of the operations? For example: Multiplication is now as fast as addition and so on. Then you would need to create a new complexity theory for that particular architecture and update all the theories based on this new architecture - doesn't sound like theory anymore :)

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Are the complements of $NP$-languages with only $n$ words of length $n$ also in $NP$?
Assuming $\Sigma = \\{ 0, 1\\}$..

Given a language $L$, such that for each $n\in \mathbb{N}$ we have $n$ words of length $n$ in $L$ and assuming $L\in NP$, can we prove also that $L\in Co-NP$?

So it is the same as showing that $\overline{L}\in NP$, but I'm not really sure on how to prove this.

Does anyone have an idea?

# Answer
Hint: Suppose we are given a word $w$ of length $n$ which is not in $L$, and let $w\_1,\ldots,w\_n$ be the words of length $n$ which are in $L$. A witness that $w \notin L$ is the list $w\_1,\ldots,w\_n$ (all different from $w$!) together with witnesses that $w\_1,\ldots,w\_n \in L$.
> 6 votes

---
Tags: complexity-theory, closure-properties, np
---


# Question
Title: Show that functions in O(1) can't grow faster than their composition with themselves
Let $f(n)$ be a function s.t $f(n)\geq 1 $ for every $n$.

I want to disprove that if $f(n) = \omega (f(f(n)))$ then it means that $f(n) = O(1)$.

I thougt of 2 approaches to show that this statement is incorrect:

1. Give an Example of a function that $f(n) = \omega (f(f(n)))$ for it,

for example: $f(n) = \sqrt n$

and then I'm supposed to get a contradiction, and show that $\sqrt n \neq O(1)$ but that's the step I'm stuck at, but I'm not sure how that contradiction is derived. I mean formally, because I understand it by intuition.

2. Start with the function that suffice $f(n) = O(1)$ and then show that it's impossible to get the condition under that function (It's sort of going from the end to the beginning)

what's the right approach and how do I get it right?

# Answer
To complete the first approach and show that $\sqrt{n}\notin O(1)$, you just need to show that the statement "There exist constants $c$ and $n\_0$ such that, for all $n\geq n\_0$, $\sqrt{n}\leq c\cdot1$" is false. That is, you need to show that, for any $c$ and $n\_0$, there is an $n\geq n\_0$ such that $\sqrt{n}\>c$. For example, you can take $n=n\_0+c^2$ (or $\max\\,\\{n\_0,c^2\\}$, if you prefer).

I don't really understand your second approach. If $f(n)=O(1)$, it's perfectly possible that $f(n)\in \omega(f(f(n)))$: take any constant function, for example.
> 1 votes

# Answer
Regarding the second approach, suppose that $f(n) = O(1)$. Then for some $C \geq 1$, $f(n) \leq C$ for all $C$. On the other hand, since $f(n) \geq 1$, we have $f(f(n)) \geq 1$. Therefore $f(n) \leq Cf(f(n))$, implying that $f(n) = O(f(f(n)))$. In particular, it is not the case that $f(n) = \omega(f(f(n)))$.

Note, however, that this doesn't disprove the claim you were interested in. Let $P(f)$ be the property that $f(n) = \omega(f(f(n))$, and let $Q(f)$ be the property that $f(n) = O(1)$. Also, let $F$ be the set of functions $f$ such that $f(n) \geq 1$ for all $n$. The claim you want to disprove is $$ \forall f \in F, P(f) \Rightarrow Q(f). $$ The negation of this claim is $$ \exists f \in F, P(f) \text{ and not } Q(f). $$ Your second approach instead shows that $$ \forall f \in F, Q(f) \Rightarrow \lnot P(f). $$ This does not disprove the original claim. For example, it might be the case that $P(f)$ is always false, and then the original claim would actually be correct.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Is the identity function a many-one reduction from a language to super-set?
I need help with a question.

Prove or disprove the following claim:

> Let $f\colon \Sigma^\* \to \Sigma^\*$ be the identity function, i.e., $f(w) = w$ for all $w \in \Sigma^\*$. Let $L\_1$ and $L\_2$ be two languages such that $L\_1 \subseteq L\_2$. Then $f$ is a many-to-one reduction from $L\_1$ to $L\_2$. In particular, if $L\_2$ is decidable, $L\_1$ is decidable as well.

I'm almost certain it's false, but I'm having a hard time with the justification. Can anyone help me out?

# Answer
> 2 votes
In order to disprove this, it is enough to disprove the conclusion that if $L\_2$ is decidable then so is $L\_1$. Can you think of a counterexample for the latter claim?

Another option is to directly disprove the fact. For $f$ to be a many-one reduction from $L\_1$ to $L\_2$ would mean that $x \in L\_1$ iff $x \in L\_2$, that is, $L\_1 = L\_2$. So to disprove this you only need to find two languages $L\_1,L\_2$ such that $L\_1 \subsetneq L\_2$.

---
Tags: computability, reductions
---


# Question
Title: Is concurrent language CCS or CSP turing-equivalent in language power?
1. Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines?
2. Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?

# Answer
> 4 votes
The answer to your (1) depends on what exactly you mean by "model" and by "interacting machines". The $\pi$-calculus in particular is usually deemed to be a good simplification of the core aspects of message passing concurrency.

Regarding (2), you can simulate Turing machines in CSP, CCS, the $\pi$-calculus as well as in C. Hence they are all equivalent in terms of the functions they can compute on the natural numbers.

---
Tags: computability, programming-languages, parallel-computing, concurrency, computation-models
---


title: Twos complement arithmetic

text:
# Question
Title: Twos complement arithmetic
If I have the expression:

```
 1011 0000 1110
-1000 1110 0001
----------------

```

Then, I find the twos complement of the second number:

```
 0111 0001 1110
+0000 0000 0001
---------------
 0111 0000 1111

```

I then add this to the first number:

```
 1011 0000 1110
+0111 0000 1111
---------------
 0010 0001 1101

```

But the answer given is:

```
 0010 0001 1100

```

Can anybody see my error?

# Answer
> 1 votes
The given answer can't be correct: Just from the last digits it claims that the result of subtracting an odd number from an even number is even.

However, you also made a mistake in your calculation: The 2's complement should be `0111 0001 1111`.

---
Tags: arithmetic
---


title: Unlimited Knapsack Problem

text:
# Question
Title: Unlimited Knapsack Problem
How would I solve the unbounded knapsack problem, only this time aiming to maximize the weight instead of the value?

# Answer
> 0 votes
One simple way is to consider the value of each pack as $cost(object)=weight(object)$ (Now every object has a uniform value) and solve the same knapsack problem. The other way is to consider a variation of packing problems link

---
Tags: knapsack-problems
---


# Question
Title: Proving equivelance of a multijump turing machine and a turing machine
I'm having trouble getting started on this proof, and I was hoping you guys could give me a couple hints/point me in the direction of where to start? Here's the problem:

Consider a multijump Turing machine, which is like an ordinary Turing machine except the transition function is δ : Q × Γ → Q × Γ × {LL, L, R, RR} In other words, the multijump TM can move left or right either one or two times. Show that a language can be recognized by a multijump TM if and only if it can be recognized by a TM.

I'm trying to answer it formally in terms of the 7-tuple and show that the TM and multijump TM are equivelant, but I'm having trouble getting started on that.

Any and all tips are appreciated, thanks

# Answer
The basic idea is to simulate every LL and RR move using an extra state. Whenever the machine wants to move twice to the right, instead make it move once to the right, and transition to a new state, at which the machine always moves to the right and then transitions to the original target of the RR transition. Implementing this idea using the 7-tuple representation is a routine but tedious exercise.
> 1 votes

---
Tags: turing-machines, computation-models, simulation
---


# Question
Title: Betweenness centrality measurement ignoring inverse paths?
I'm implementing the **Betweenness Centrality** algorithm proposed by **Brandes** (first algorithm on this paper - also below), and I'm running into a very weird issue: **it seems to be ignoring some paths** (i.e. for vertexes `v-w`, it may count the path `v-e-w`, but not the inverted path `w-e-v`). I'm not sure how to prove or debug this issue, but I'm pretty certain that's what happening. The precise issue that I can see in the debugger is that two nodes that should have the same BC value are off by roughly three units. I'm using the `double` type to store the values.

Am I missing something about this algorithm? The graph I'm examining is *unweighted* and *undirected* btw.

Also, on a totally unrelated note: the value being computed on each step is the following:

Shouldn't the value be between 0 and 1?

Algorithm:

# Answer
The algorithm that you have mentioned here is definitely correct. You can refer to the correctness proof in the paper.

This algorithm is implemented in many libraries and ready to be used including NetworkX, Boost, GraphStream, and MATLAB (3rd party I guess) and many others. Also, many other people (including myself) and companies have employed the same algorithm.

If you are getting unexpected results, please revise your implementation.
> 2 votes

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


# Question
Title: Deterministic Communication Complexity of Equality if inputs differ by at most 1
The set equality problem in 2 party communication complexity is known to require $n$ bits of communication between Alice and Bob, for $n$-bit inputs $X$ and $Y$.

Suppose that we promise that the symmetric difference of $X$ and $Y$ is $\le 1$. Is the required communication for a deterministic protocol still $\Omega(n)$?

My thoughts: I believe that the complexity becomes $O(\log n)$ because of the following: When Alice gets its input $X$ of size $k$, she knows that Bob's input differs at $\le 1$ index. Thus, there are only $\le {n \choose 1}n + 1 = O(n^2)$ possibilities for $Y$, given $X$; the "+1" is the case where $X=Y$. So there should be a way to convey this information from Bob to Alice using only $O(\log n)$ bits. Is my reasoning correct?

# Answer
> 1 votes
Hint: Compare the parities of the inputs. (Can you generalize this idea to at most $k$ differences?)

---
Tags: complexity-theory, communication-complexity
---


# Question
Title: Finding a maximum-diameter tree in an undirected unweighted graph
The diameter of a graph is the largest of all shortest-path distances in it. How can we find a tree of maximum diameter within an undirected unweighted graph?

Note that the tree does not have to be a spanning tree.

# Answer
This (probably) can't be done efficiently since a maximum-diameter spanning tree could be a Hamiltonian path.

More specifically, an $n$-vertex graph has a tree of diameter $n-1$ as a subgraph if, and only if, it has a Hamiltonian path (the tree is the Hamiltonian path). Therefore, the problem of finding a maximum-diameter subtree is **NP**-hard, since you can reduce Hamiltonian path to it by finding the maximum-diameter subtree and checking whether or not it's a path of length $n-1$.
> 1 votes

---
Tags: algorithms, graphs, trees
---


# Question
Title: Is the Weighted Maximum Coverage Problem with frequency weights NP-hard?
I want to prove the following case of Weighted Maximum Coverage problem with special weights is NP-hard. But I have no idea. So I am here seeking for help.

The Weighted Maximum Coverage problem is formulated as follows (known to be NP-hard):

Given a set *I* of *m* elements with each element e*j* has a weight w(e*j*), a collection of subsets S=S1,S2,...Sn with each set covers some elements, and an integer k, the object is to find k subsets to maximize the sum weights of covered elements.

Now, my concern is as follows:

When the weight for each element is the number of subsets that cover this element, is the problem still NP-hard? How to prove it?

For example, given I={a,b,c,d}, S=S1,S2,S3, and S1={a,b,c} S2={b,c} S3={c,d}, then the weight of element b is 2, since there are two subset, S1 and S2, covers b.

# Answer
If you allow sets to repeat, then you can show that this is still NP-hard by making all the weights equal. The idea is to reduce from unweighted maximum coverage to your version of maximum coverage. Given an instance of unweighted maximum coverage, where element $e\_i$ appears $w\_i$ times, let $W = \max\_i w\_i$, and for each element $e\_i$ of non-zero weight, add $W-w\_i$ sets of the form $\\{e\_i\\}$. In the new instance, each element appears the same number of times, so all have the same weight; and one checks that the added sets cannot improve the optimal solution.

If you insist that the sets are disjoint, you repeat the same construction, but to each set in the construction (old and new) you add a unique dummy element. This increases the value of each feasible solution by exactly $k$.
> 1 votes

# Answer
Try 3-hitting set. For your special weight setting, the weights are uniform.
> 0 votes

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


# Question
Title: Sound and complete algorithms for boolean satifiability
To my best knowledge, these are the sound and complete algorithms for boolean satisfiability

* Variations of DPLL algorithm (e.g. CDCL, Look-ahead solvers)
* Stalmarks method
* Binary Decision Diagram (BDD)

I am looking for other sound and complete algorithms for boolean satisfiability?

# Answer
Resolution is sound and complete. In recursive learning, you recursively evaluate the clause satisfiability requirements for identifying common assignments. Look at say page 29 and onwards in these slides.
> 2 votes

---
Tags: satisfiability, 3-sat, sat-solvers
---


# Question
Title: Time complexity for two multiplications modulo $p$
The time complexity of computing $MK\bmod P$ is $O((\log n)^2)$. What is the time complexity of computing $MK^2\bmod P$? Is it $O(2(\log n)^2)$ or $O((\log n)^2)$?

# Answer
> 5 votes
$O(2(\log n)^2$ is exactly the same thing as $O((\log n)^2)$. This follows from the definition of $O()$.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Understanding constraint formula concept in Java
**JLS** defined a concept called "constraint formula". There is a formal definition:

> Constraint formulas are assertions of compatibility or subtyping that may involve inference variables. The formulas may take one of the following forms:
>
> * ‹Expression → T›: An expression is compatible in a loose invocation context with type T (§5.3).
> * ‹S → T›: A type S is compatible in a loose invocation context with type T (§5.3).
> * ‹S \<: T›: A reference type S is a subtype of a reference type T (§4.10).
> * ‹S \<= T›: A type argument S is contained by a type argument T (§4.5.1).
> * ‹S = T›: A reference type S is the same as a reference type T (§4.3.4), or a type argument S is the same as type argument T.
> * ‹LambdaExpression →throws T›: The checked exceptions thrown by the body of the LambdaExpression are declared by the throws clause of the function type derived from T.
> * ‹MethodReference →throws T›: The checked exceptions thrown by the referenced method are declared by the throws clause of the function type derived from T.

I have some misunderstanding about it. As far as I've understood we have a set of all Java types, denote it by `M`. Could we say, that any constraint formula defines a subset of `M`, for instance

‹S \<: T› = {S | (S belongs to M) and (S is a subtype of T) }

# Answer
> 2 votes
First, not all of the constraint formulas work with types, some of them work with expressions, or other objects. For example, what would be the set for the formula ‹1+1 → Integer›?

Second, a formula might contain zero, one (at either position) or two inference variables (denoted by Greek letters). What would be the set for ‹String → Object›, ‹α → Object›, ‹String → α›, or ‹α → β›?

Third, I think you should think about constraint formulas as *predicates*, not as sets. For example, the formula ‹String \<: Object› is satisfied, while ‹Object \<: String› isn't.

And when you have a constraint formula with inference variables, you can start talking about sets of types (or sets of pairs of types for formulas with two variables) that satisfy the formula.

This means that I think that the closest you can get to your equation would be something like:

{α | ‹α \<: T› } = {α | (α belongs to M) and (α is a subtype of T) }

(Though the second part is unnecessarily verbose, "α is a subtype of T" already implies "α belongs to M".)

# Answer
> 1 votes
Constraint formulas are assertions: they are either true or false (given a context where they are valid). For example, `‹byte → int›` is true (in any valid context) because it is an instance of a widening primitive conversion which is a loose invocation context for the destination type. `C1` is a subclass of `C2`, then `‹C1 <: C2›` is true. On the other hand, `‹String <: int›` is false, because there is no such subtype relation.

When a formula contains inference variables (which is the useful case), the truth value of the assertion depends on the value of the variable. The formula is a predicate: it can be seen as a function from the set of types to the set of booleans. This is equivalent to a set of types — the set of types for which the function is true. Thus a formula like `‹α <: String›` can be seen as the set of subtypes of the `String` class type.

A formula containing multiple inference variables can likewise be interpreted as a set of *tuples* of types — a set of pair of types if there are two variables, a set of triples of types if there are three variables, etc.

In general, a formula can be interpreted as a set of *lists* of types, where each element of the list is the value of one variable. A formula contains a finite number of variables, therefore it is enough to consider finite lists. For example, the formula `interface A {α₀ m(α₁ x, α₂ y);} → α₄` can be interpreted as the set of lists of types `[T₀, T₁, T₂, T₃, T₄]` such that `interface A {T₀ m(T₁ x, T₂ y);}` is compatible with a loose invocation context with type `T₄`.

Note that a formula is a syntactic object. The interpretation of a formula as a boolean or as a set is a denotational semantics for formulas. The JLS defines an operational semantics for constraint formulas, which consists of a reduction to bound sets.

---
Tags: terminology, type-theory, abstract-data-types
---


# Question
Title: Why does lower integer represent higher priority in scheduling literature?
I'm studying Real Time Systems, and in the textbook most of the focus is on scheduling algorithms. (Textbook: Real-Time Systems by Jane W. S. Liu)

In the algorithms that involve priorities, it is said that smaller integer represents higher priority (e.g. a process with priority 1 has more priority than one with 3). Then, in the subsequent discussions, there are terms involved like: "Let Pi be a process with a higher priority..." On such occurrences, I get confused whether higher priority means actually higher priority or larger integer. In most of the cases it means the former, however sometimes I've to guess that from the context, which is a bit time consuming.

As far as I know, all algorithms will work well with slight modifications if larger integers represented higher priority, and that would avoid confusion. So my question is: Is there any reason, apart from conventional / historical one, for using smaller integer for denoting higher priority? If not, why not amend it and avoid confusion?

# Answer
> 5 votes
This has always troubled me too. The problem is with the origins of the English word and the difference between ordinal numbers ("first", "second", "third", ...) and cardinal numbers (the numbers you use to count things).

In schedulers we use the word *priority* in the sense of:

> the right to take precedence or to proceed before others\[1\]

It came into English from Norman French after the Norman conquest of England in 1066. It came into Norman French from the Latin word *prior*, which (in English) means

> existing or coming before in time, *order*, or importance\[1\]

I added the emphasis on the word *order* to emphasize that we are using the word in the sense that requires we use *ordinal* numbers. So you should think of it in terms of a medieval court hierarchy. The king is seated at the dinner table *first* because he has the *highest* rank. The prince (etymology: via Norman French from Latin *princeps*, which means "first citizen"\[2\]) is seated *second* because he has the next highest rank. Then the dukes are seated *third* because they have the next highest rank. And so on. The knights are seated *last* because they have the lowest rank. (The common folk with no title don't get seated at all because they have no rank at all.)

\[1\] This is from the definition from Google. I think they may have gotten it from Oxford English Dictionary. \[2\]http://en.wikipedia.org/wiki/Royal\_and\_noble\_ranks

# Answer
> 2 votes
> There is no general agreement on whether 1 is the highest or lowest priority.Some systems use low numbers to represent low priority ; others use low numbers for high priority.

*Operating System Concepts*, by Abraham Silberschatz and James Peterson

# Answer
> 1 votes
I've always assumed it was related to time. Most people agree that time travels in one direction, and assign larger numbers as it continues.

This works whether you are referring to "which task has the earliest deadline" or "which task was inserted into the priority queue first" (which is often phrased as "which task has been waiting longer", but it doesn't make sense to constantly increment a counter for that, it is derived from the current time and the start time).

Even in the presence of more complex scheduling algorithms, it still makes sense to have all the numbers pointing the same way.

---
Tags: algorithms, scheduling
---


title: Product with floating point

text:
# Question
Title: Product with floating point
I was studying the product with floating point and I saw this example. I made the translation, sorry if something is not grammatically correct.

!\[enter image description here\]\[1\]

# Answer
> 2 votes
Here is the complete calculation: $$ \begin{align\*} &2.5 = (.101)\_2 \times 2^2 \\ &12.125 = (.1100001)\_2 \times 2^4 \\ &(.101)\_2 \times 2^2 \cdot (.1100001)\_2 \times 2^4 = (.0111100101)\_2 \times 2^6 = (.111100101)\_2 \times 2^5 \\ &(.111100101)\_2 \times 2^5 = 30.3125 \end{align\*} $$ Ignore what the book says, and just make sure that you understand why this calculation works out.

Also, actual floating point formats usually omit the leading 1 in the mantissa, which is usually interpreted as the first digit *before* the dot rather than the first *after* the dot. Using this convention, the exponents add without correction (under your convention, you have to subtract 1, essentially since 1/2 times 1/2 equals 1/4 rather than 1/2).

---
Tags: floating-point
---


# Question
Title: Relation between the size of sub-problems and number of sub-problems in a recurrence
Below is a well-known equation for generalized recurrence relation in a divide and conquer paradigm (as described in CLRS) --

$$T(n) = aT(n/b) + f(n), \quad \text{where} \quad a \gt 1 \text{ , } b \geq 1$$

If we consider a case for merge-sort, the relation will look like this --

$$T(n) = 2T(n/2) + \Theta(n) \qquad \qquad (i)$$

which is quite straight-forward, i.e. we have $2$ sub-problems of size $n/2$ each, ($1/2$ of the original sub-problem), and $\Theta(n)$ operations to merge them.

Now if we have a relation like --

$$T(n) = 3T(n/2) + \Theta(n) \qquad \qquad (ii)$$

then we can assume that there are $3$ "overlapping" sub-problems, as each of them with size $n/2$. Let's consider again --

$$T(n) = 2T(n/4) + \Theta(n) \qquad \qquad (iii)$$

now, what does it mean? Are there $2$ sub-problems with size $n/4$? How is it possible? If we divide the whole problem into $4$ equal sizes then we should need something like $4T(n/4)$ instead of $2T(n/4)$ to balance the recurrence tree (each node with 4 leaves), right? Is this relation realistic?

If this is the case, then why there is no constraint like $b \< a$ ? Moreover, is there any algorithm that follows the recurrence as in $(ii)$ and $(iii)$?

# Answer
A simple, specific example of an algorithm with a type $(iii)$ recurrence is binary search. At each point you decide whether to look in the left or the right half of the current section of the array, so your problem halves, and you only have one subproblem. The recurrence is then $T(n) = T(\frac{n}{2}) + O(1)$.

So you might get a type $(iii)$ any time you "discard" part of the input at each step.

A divide and conquer approach to multiplying large numbers can give you a type $(ii)$ recurrence (obviously there's faster algorithms now though). If you split the numbers in half, you can turn one multiplication of two large numbers in to four multiplications of half-sized numbers, plus some addition. Gauss reduced this to three multiplications of half size numbers (but with more addition and subtraction), so the recurrence for this algorithm is $T(n) = 3T(\frac{n}{2})+O(add)$ (the exact recurrence depends on how you deal with addition/subtraction).
> 7 votes

# Answer
One of the wonderful examples that "discard" some sub-problems is the "VLSI Layout Problem". You can find this example in this MIT OCW Lecture (from 55m:30s). I summarize it here.

> The problem is to embed a complete binary tree $T$ with $n$ leaves (it is circuit) into a grid (no crossing edges) with minimum area. For simplicity, we assume the height of $T$ is even.

A so-called $H$-layout (wiki) gives us an $O(n)$ solution. The following figure shows an example of $T$ of height 4.

> The key point here is although we divide the origin problem into 4 sub-problems, either for the width $W(n)$ or the height $H(n)$ of the rectangle area, *only two sub-problems count*.

In terms of recurrence, we have $$W(n) = H(n) = 2T(n/4) + O(1) = O(\sqrt{n}).$$
> 4 votes

---
Tags: algorithms, algorithm-analysis, recurrence-relation
---


# Question
Title: Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?
The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary search ($T(n) = T(n/2) + O(1)$) and merge sort ($T(n) = 2T(n/2) + O(n)$).

> Do you know any algorithms (probably using "divide and conquer") that have the time complexity of the form $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + O(n)$?

# Answer
> 3 votes
Think of an algorithm, which do something linear with an integer list of length $n$, for example computes the maximum. Afterwards, the algorithm divides the list of length $n$ into $\sqrt{n}$ lists of length $\sqrt{n}$ and starts the algorithm for them. The result of the algorithm is for example the product of the computed maximum and the results of the $\sqrt{n}$ lists. For the base case, a list of length $1$, you can return the value of the only element.

This algorithm has the time complexity, you asked for.

---
Tags: algorithms, algorithm-analysis, reference-request, runtime-analysis, recurrence-relation
---


# Question
Title: How is the number of states in a Turing machine bounded?
The definition of Turing machine says that the number of states is finite. However, I do not get how this can be true. Is the number of states in a Turing machine actually not fixed, that is not bounded? If not, can anyone explain how this is possible?

# Answer
> 7 votes
You seem to have misunderstood the definition of a Turing machine. The "state" refers not to the whole configuration of the machine (tape contents, position of the head, etc.) but to the state of the finite automaton that controls the tape head. The automaton has a finite number of states by definition.

# Answer
> 5 votes
The tape isn't part of the machine, so the tape contents aren't part of the machine's internal state. Of course (a finite fragment of) the tape content *is* part of the state of a *computation* conducted with the machine: its *configuration*.

The configuration is the machine's "external" state: the state of the machine executing a particular process within its environment; the state of that process.

The same distinction can be made for any other machine, e.g.

* A car: its position on a map isn't part of the internal state of a car, but it is part of e.g. its state within a navigation application.
* You: where you are isn't part of your internal state, but it is part of your state when describing an activity in which your whereabouts play a role.
* A copier: paper in its input and output trays can be regarded as not being part of the machine's internal state (this is a matter of choice), but it is definitely part of the state when describing how the machine works.

---
Tags: terminology, turing-machines, computation-models
---


# Question
Title: What's the big deal with the knapsack problem?
In my CS course, we are covering things from one topic to another in sort of a sensible manner. For example, binary search tree -\> 234-tree -\> red-black tree -\> heap -\> greedy algorithms -\> dynamic programming.

And all the sudden, bam, there is this whole chapter on the knapsack problem. How is this problem different from weighted interval scheduling? Or longest common sub-sequence?

What's the importance of the knapsack problem?

# Answer
> 2 votes
The choice might indeed be arbitrary in a sense that with the knapsack problem, the instructor can introduce required concepts or techniques. But one could also argue that the knapsack problem is an important practical problem. In \[1\], Skiena analyzes 1503135 WWW hits recorded on the Stony Brook Algorithms Repository. Knapsack was the 18th most popular problem, and the 4th most needed algorithm implementation was for knapsack as well.

---

\[1\] Skiena, Steven. "Who is interested in algorithms and why?: lessons from the Stony Brook algorithms repository." ACM SIGACT News 30.3 (1999): 65-74.

# Answer
> 4 votes
I think mainly the techniques that are covered in that section (dynamic programming and greedy algorithms) are very important.

There are several other properties. First of all, integral knapsack problem belongs to the famous class of problems called NP-complete (there is no known polynomial time algorithm for them), while the fractional knapsack is polynomial time solvable using a greedy algorithm. Thus, as an algorithm designer, you need to be able to recognize the difference between the nature of these two problems in order to solve them.

Also, one interesting point is that, although the dynamic programming technique is psuedo-polynomial time for the integral knapsack problem, it can be run exponentially in general case.

---
Tags: complexity-theory, education, knapsack-problems, didactics
---


# Question
Title: When using the Pumping lemma, how do I deal with different cases of y?
I want to prove L is not regular:$$L={\\{www|w \in \Sigma^\*\\}}$$ $$\Sigma=\\{a,b\\}$$

I am sure I can do so using pumping lemma. I used $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know how to handle different cases of y in pumping lemma.

# Answer
> 4 votes
To review, the PL says that if a language $L$ is regular, then there is an integer $p$ such that for any string $s\in L$ of length, $|s|\ge p$ we can write $s=xyz$ with

1. $|y|\>0$
2. $|xy|\le p$
3. $xy^iz\in L$, for all integers $i\ge 0$

Assume your language is regular and select the string $ab^pab^pab^p$ to pump. Now, where can $y$ live? Since $|xy|\le p$ you know that $xy$ lives in the first $p$ or fewer characters of $s$, namely $xy=ab^k$ for some $k\<p$. We then have two possibilities for $y$: it either contains the first $a$ or it doesn't, so we have two possibilities, where I've colored the string y: $$\begin{array}{c} (\color{red}{ab\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b)\\ (a\color{red}{b\dotsm b}b\dotsm b)\ (ab\dotsm b)\ (ab\dotsm b) \end{array}$$

Then for each case we argue thus:

1. $y$ is $ab^n$ (i.e., $x=\epsilon$), with $0\le n\le p$. Then $xyz=ab^pab^pab^p=(ab^n)b^{p-n}ab^pab^p$. Then $xy^2z=(ab^n)(ab^n)b^{p-n}ab^pab^p=ab^nab^pab^pab^p$. It's not difficult to see that this cannot be in $L$, so we've reached a contradiction.
2. $y$ is $b^n$ (i.e., $x=ab\dotsc b$). Then $xy^2z = ab^pb^nab^pab^p$ and again, this string can't be in $L$.

In all cases, we reach a contradiction, so our initial assumption, that $L$ was regular, was false.

By the way, it's easier to use the candidate string $a^pba^pba^pb$, since for this we only have one possibility for where $y$ could live, namely among the first string of a's.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Algorithm to find smallest difference in array
We want an algorithm that, given an array of length $n$ of integers, find the minimum difference between two integers in the array.

One such algorithm is to sort the array and check adjacent pairs of numbers. This takes time $O(n\log n)$.

Is there a faster way, e.g., an $O(n)$ algorithm?

# Answer
This depends on your model of computation. If you only allow arithmetic and comparisons (the algebraic decision tree model) then there is an $\Omega(n\log n)$ lower bound for *element distinctness*, the problem of deciding whether all elements are distinct. Your problem is of course even harder, so the same lower bound applies.

(There is some fine print: the lower bound only holds if the degree of the polynomials being compared is bounded. If all you're doing is comparing various differences $x\_i - x\_j$, then you're good to go. The algebraic decision tree model also allows you to compare more general polynomials in the inputs, as long as they have bounded degree.)

There are other models which might perform better — for example, in some models you can sort integers in $o(n\log n)$. But I imagine you don't want to allow the sort of trickery used in such algorithms.
> 7 votes

# Answer
If integers in the array has a limited number of digits you can sort an array with radix sort algorithm, that is O(kN) and than check the adjacent pairs of numbers (O(N))? Resulting complexity will be O((k+1)N), linear.
> -1 votes

---
Tags: algorithms, arrays
---


# Question
Title: Concurrent programming language being Turing-equivalent and difference between Turing-complete and equivalent
In Is concurrent language CCS or CSP turing-equivalent in language power?, the answer says that CCS or CSP is Turing-complete. But that does not seem to answer whether CCS or CCP is Turing-equivalent.

According to my understanding, Turing-equivalence and Turing-completeness is a different thing, but I may have been confused.

# Answer
> 1 votes
CCS, CSP, and the $\pi$ calculus are Turing-equivalent. As the answer there says, you can simulate a Turing machine in CCS, CSP, or the $\pi$ calculus. That means they are Turing-complete. It is easy to see that you can write an interpreter for CCS, CSP, or the $\pi$ calculus in C or Python or any Turing-equivalent language, so given a Turing machine, you can simulate CCS, CSP, or the $\pi$ calculus. Therefore, they are all Turing-equivalent.

I suggest doing a little more background reading and study, e.g., https://en.wikipedia.org/wiki/Turing\_completeness, and chapters in undergraduate complexity theory textbooks. That will help you solidify your understanding of Turing completeness and Turing equivalence. You'll probably also find it helpful to learn about the Church-Turing hypothesis.

---
Tags: computability, programming-languages, parallel-computing, concurrency, computation-models
---


# Question
Title: Aggregate Rate and Poisson Process in Aloha
I'm having a hard time understanding what is mean't by the aggregrate rate $\lambda$ and what it means for throughput in unslotted and slotted Aloha protocols. The more I seem to read about poission process the more confused I get.

I understand that the probability a packet is transmitted in a time interval $\delta t$ is $\lambda \times \delta t$ where you have $N$ senders and $Y$ is the aggregate rate from all $N$ senders.

However I don't understand what is mean't by *aggregate rate*. It's quite a perculiar phrase. Does it mean the probability that any of the $N$ senders will try to transmit, or is the number of packets to be sent by $N$ senders over the time?

Next we're then told that the individual rate for a sender is $\lambda / N$. Because I'm so confused by what is mean't by *rate* it's hard to begin to think about what this even means.

# Answer
> 1 votes
The dictionary definition of aggregate might be helpful: https://www.wordnik.com/words/aggregate

You have $N$ senders. Each sender sends packets on a network at some rate, say, $\lambda/N$. Now think about all the packets that are sent over that network, without regard to who sent it. What's the rate at which such packets appear on the network? That's a total over all packets. The aggregate rate will be something like $\lambda$.

It might also be helpful to refresh your understanding of what a rate is. A rate is an amount divided by a time period: e.g., the number of packets sent by Alice per unit time interval. The aggregate rate is also a count divided by a time period, but in this case, the count is of a different quantity: it's a count of all packets, not a count of the packets sent by Alice. So, the number of packets sent (in total, from anyone) per unit time interval is a rate. That is what your book is calling the aggregate rate.

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


# Question
Title: Algorithm for random generation of two connected partitions of a finite set
Given the set $X=\\{1,2,\ldots,n\\}$; $\\,\\,$ $n=mp=kq$ where $m,k,p,q$ are positive integers.

Please help me to programme an algorithm that realizes random generation of the following two partitions of $X$: $$ \mathcal{D}\_{1} = \big\\{A\_{i}\big\\}\_{i=1}^{p}; \quad \bigcup\_{i=1}^{p} A\_{i} = X; \quad A\_{i\_{1}} \cap A\_{i\_{2}} = \emptyset \quad (i\_{1} \neq i\_{2}); \quad |A\_{i}|=m, \quad i=\overline{1,p} $$ and $$ \mathcal{D}\_{2} = \big\\{B\_{j}\big\\}\_{j=1}^{q}; \quad \bigcup\_{j=1}^{q} B\_{j} = X; \quad B\_{j\_{1}} \cap B\_{j\_{2}} = \emptyset \quad (j\_{1} \neq j\_{2}); \quad |B\_{j}|=k, \quad j=\overline{1,q} $$ such that $$ A\_{i} \cap B\_{j} = \emptyset, \quad i=\overline{1,p}, \quad j=\overline{1,q}. $$

Here, as usual, $|S|$ denotes the number of elements of the set $S$.

# Answer
> 1 votes
There do not exist such partitions $D\_1$ and $D\_2$. Recall your assumptions: $$\bigcup\limits\_{i=1}^{p} A\_i=X,\\;\bigcup\limits\_{i=1}^{q} B\_i=X$$ It follows, that for each $x\in X$ there exists a set $A\_k$ $(k\in\\{1,...,p\\})$ and a set $B\_j$ $(j\in\\{1,...,p\\})$ such that $x\in A\_k$ and $x\in B\_j$. Therefore $x\in (B\_j\cap A\_k)$ which contradicts that $B\_j\cap A\_k=\emptyset $.

---
Tags: algorithms, randomized-algorithms, sampling, partitions
---


title: Shannon-Fano puzzle

text:
# Question
Title: Shannon-Fano puzzle
I was playing around with Shannon-Fano (SF) entropy encoding when I ran into this issue.

I am aware that the compression that can be achieved with SF is sometimes inferior to that of Huffman encoding, but I just though it meant that code lengths were sometimes sub-optimal in the sense that an encoding exists, which yields a better overall result. I did not expect SF to generate codes that are clearly sub-optimal in the sense that a particular input value can achieve a shorter encoding than another one with a higher frequency gets, but that is exactly what I am observing.

This is most likely something I am doing wrong or something I misunderstood, but I am not able to see it at the moment.

Please consider the following data:

```
input     frequency code
a         16        00
b         12        010
c          9        0110
d          7        0111
e          6        100
f          6        1010
g          6        1011
h          5        1100
i          3        11010
j          3        11011
k          3        11100
l          2        11101
m          1        111100
n          1        111101
o          1        111110
p          1        1111110
r          1        1111111

```

Observe that the encoding for `e` with a frequency of 6 is shorter than that of `c` and `d` with frequencies of 9 and 7, respectively.

Clearly I would get better overall compression by swapping the codes for `c` and `e`.

Let me show - at least in part - how the codes are derived.

First I split between `d` and `e` giving a combined frequency of 44 on the left and 39 on the right (a distance of 5). Splitting between `c` and `d` would yield 37 and 46, a distance of 9, and between `e` and `f` yields 50 and 33, and distance of 17 - both inferior.

So `a`, `b`, `c`, and `d` start with `0` \- the remaining inputs start with `1`.

Recursively I then process the `abcd` side.

There I find that splitting between `a` and `b` or between `b` and `c` yield exactly the same 'error' or distance, namely 12, so I just pick the first one, yielding the encoding you see above.

When I noticed this problem I then modified the algorithm to favor the split point closest to the center of the segment I am working on in case of equality. That does indeed yield 3-bit codes for the four inputs on the left-hand side of the tree, thus "repairing" the table in the sense that no input has a shorter code than another one with a higher frequency, but I have not heard before that something like this would be necessary and besides that is still inferior in terms of compression ratio compared to the table above with the codes for `c` and `e` swapped.

What gives? Is this a known limitation of Shannon-Fano, or did I make a mistake somewhere?

# Answer
As you mention, Shannon–Fano coding is not optimal, and has been superseded by Huffman coding. Huffman codes can be found efficiently, so there is no reason to use Shannon–Fano coding nowadays. Shannon–Fano was never intended to be an optimal algorithm, it's just the best Fano could think of, and was enough to prove the source coding theorem.

Shannon–Fano coding indeed has a "limitation" – it doesn't always produce an optimal code. You're suggesting an improvement of Shannon–Fano coding, namely generate the codewords, and then assign them according to the frequencies. The resulting coding improves on Shannon–Fano coding, but is still probably inferior to Huffman coding. The crucial property of Huffman coding is that it's optimal, so we know that it has no "limitations".
> 2 votes

---
Tags: data-compression
---


# Question
Title: Characterizing cycles in a directed graph with optional edges
Consider a directed graph in which some edges are marked as "optional". A graph with $N$ optional edges induces a family of $2^N$ graphs depending on which edges are removed. In some cases, some of these graphs may be acyclic while others contain cycles.

For example, consider the graph with vertices $\\{1, 2, 3, 4\\}$ and edges $\\{1 \rightarrow 2,\ 2 \xrightarrow{?} 3,\ 3 \rightarrow 1,\ 2 \xrightarrow{?} 4,\ 4 \xrightarrow{?} 1\\}$ where the optional edges are the ones marked with a question mark.

This defines a family of eight different graphs with the same vertices but different sets of edges. If we denote the presence or absence of an edge between vertices $u$ and $v$ as $E(u \rightarrow v)$, then the following Boolean expression describes whether a particular graph in this family in cyclic: $E(2 \rightarrow 3) \vee \[E(2 \rightarrow 4) \wedge E(4 \rightarrow 1)\]$

Given a particular graph containing some optional edges, I'd like to be able to describe compactly the combinations of optional edges that must be present for the graph to be cyclic without having to specify the entire original graph. In particular, I'd like to know if there is a description whose length is polynomial in the number of *optional* edges rather than the *total* number of edges.

More formally: **Is there a pair of (ideally efficient) algorithms $P$ and $Q$ such that $P$ takes in a description of a directed graph with $N$ optional edges and produces an "encoded" string whose length is polynomial in $N$, and Q can read in that encoded string and a subset of the $N$ optional edges and determine whether, with those edges present (and the other optional edges removed), the original graph would be cyclic?**

# Answer
Yes, this is doable. An encoded string of length $O(N^2)$ suffices.

Let me describe how to do it. Let $V'$ denote the set of vertices that are the endpoints of the optional edges. Obviously, $|V'| \le N$. I'll describe the two procedures P,Q below.

Procedure P: Compute reachability information for each pair of vertices in $V'$. In other words, for each $s,t \in V'$, compute whether $t$ is reachable from $s$ in the original graph (without using any optional edge); the answer is either "yes" or "no". Note that there are $O(N^2)$ pairs $s,t$, so we can encode the answer to all those questions using $O(N^2)$ bits (one bit per pair $s,t \in V'$). Let this be the encoded string. Of course, the length of this encoded string is polynomial in $N$.

In particular, we can think of this encoded string as the representation of a graph $G'=(V',E')$. $G'$ has vertices $V'$ and has an edge $s\to t$ if and only if $t$ is reachable from $s$ in the original graph (without optional edges). The length of the encoding of $G'$ is $O(N^2)$, so polynomial in $N$.

Procedure Q: Given a set $S$ of optional edges and the encoded string, here's how we can tell whether adding those edges would create a cycle. Basically, add every edge in $S$ to the graph $G'$. (The encoded string tells us $G'$, so we can treat $G'$ as known, i.e., it is one of the inputs to Q.) Now you can do depth-first search in the resulting graph, $G''=(V',E' \cup S)$, to test whether $G''$ contains any cycle. $G''$ will have a cycle if and only if adding $S$ to the original graph (without any other optional edges) has a cycle.
> 1 votes

---
Tags: graphs
---


# Question
Title: Proof that a node N balanced binary search tree has $2^i - 1$ children where $i$ is the position of the first 1-bit in N, starting from 0
I was binary indexed trees and I came across this article. One part of the justification was the following:

> Given that the (binary search tree) tree is perfectly balanced, a node N will have exactly $2^{i}-1$ children on each side, where $i$ is the position of the first 1-bit in N, starting from 0, and counting from least significant to most significant. For example, for $N=11000$, we have $i=3$. For $N=111$, we have $i = 0$. This can easily be checked by recalling that the left children of $N$ consist of every number lower than $N$ (similarly for the right side). The “minus 1″ is there because we can’t count $N$ itself as being a child of $N$.

First off, I believe that the authors claim that

> "This can easily be checked by recalling that the left children of $N$ consist of every number lower than $N$"

is not entirely accurate, as for example, in the following BBST:

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

The left children of node 6 do not contain every number lower than 6. Nevertheless, the formula $2^i - 1$ still holds true. Why does this work?

# Answer
*Since I'm still learning proof techniques, this is a good practice for me too. Please verify the solution yourself. We shall prove this with a series of lemma.*

***Lemma 1.*** A perfectly balanced tree with height $h$ would have $n = 2^{h+1}-1$ nodes.

*Proof.* Trivial proof by induction.

***Lemma 2.*** A perfectly balanced indexed binary search tree have root with value $2^h$.

*Proof.* By lemma 1, there are $2^h-1$ nodes on the left subtree of the root. By constraint of binary search tree, the root element will have value $(2^h-1)+1=2^h$.

***Lemma 3.*** In a perfectly balanced indexed binary search tree, any node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$ and right child with value $k+2^{h-1}$.

*Proof.* Due to the properties of the tree, the value of the left child of $A$ is the value of $A$ itself, which is $k$, subtracted by the number of nodes on the right subtree of the left child, which is $2^{h-1}-1$ from lemma 1, added by one. This is trivial upon drawing out such a tree, which I shall not include here. Hence, the value of left child is $k-(2^{h-1}-1)-1=k-2^{h-1}$. A similar proof will suffice for the value of right child.

***Theorem.*** In a perfectly balanced binary search tree with height $h$, any node $A$ will have exactly $2^i−1$ children on each side, where $i$ is the position of the first $1$-bit in the value of node $A$, starting from $0$, and counting from least significant to most significant.

*Proof.* We shall prove by induction from root down to leaves. By lemma 2, the root value is $2^h$, which binary representation is

$$ 1\overbrace{0\dots0}^h $$

The position of the first $1$-bit will therefore be in the $h$ position. Substituting $i=h$, we have $2^h-1$ children on each side, which agree with lemma 1.

Now, we assume any node $A$ satisfy the stated theorem. By lemma 3, the left child of node $A$ with value $k$, and its rooted subtree of height $h$, have left child with value $k-2^{h-1}$. By lemma 1, we know that $i=h$, so it suffice to show that the position of the first $1$-bit in $k-2^{h-1}$ appears a bit before that in $k$. In other words, we can assume that the first $1$-bit in $k$ appears at position $h$, and we need to show that the first $1$-bit in $k-2^{h-1}$ appears at position $h-1$.

In binary, we can represent $k$ as

$$ 1\dots1\overbrace{0\dots0}^{h} $$

and we are subtracting it from $2^{h-1}$, as represented by

$$ 1\overbrace{0\dots0}^{h-1} $$

Since $k$ is all zeros in the first $h$ bits, subtracting by $2^{h-1}$ will cause bit $h$ to become $0$ and bit $h-1$ to become $1$, which retain the stated proposition. A similar prove can be done for the right child of $A$. In addition, one also need to prove the termination case to complete this prove, which I also leave out here.
> 2 votes

---
Tags: proof-techniques, binary-trees, search-trees
---