# Question
Title: How to solve if we have $3^{(n-2)/2}$ in recurrence relation?
In a question i found the recurrence relation $a\_n=a\_{n-2}+3^{(n-2)/2}$ then i should solve this relation with using generating factor but $3^{(n-2)/2}$ makes difficult to solve . Is there a solution for such a relations ? Or is my answer wrong ?

# Answer
> 1 votes
Expand the equation:

\begin{align\*} a\_n&=a\_{n-2}+3^{\frac{n-2}{2}} \\ &=a\_{n-4}+3^{\frac{n-4}{2}} + 3^{\frac{n-2}{2}} \\ &=\sum\_{i=1}^{\frac{n}{2}}3^{\frac{n}{2}-i} \\ &=3^{\frac{n}{2}}\sum\_{i=1}^{\frac{n}{2}}3^{-i}\\ &= 3^{\frac{n}{2}}\times \frac12 \times\left(1-\left(\frac{1}{3}\right)^{\frac{n}{2}}\right)\\ &=3^{\frac{n}{2}}\times \frac12 - \frac12\\,. \end{align\*}

# Answer
> 0 votes
If you're looking for an asymptotic bound, it is easier to observe that on the $n^{th}$ level we get $3^{(n-2)/2}$ but on the $(n-2)^{th}$ level, we get $3^{(n-4)/2} = 3^{(n-2)/2} \cdot 3^{-1}$, for any $n$. So at any level, the children contribute a factor of 3 less than the parent, causing the recurrence to be "root dominated". That is to say, the first level dominates asymptotically. So the total value of $a\_n$ is on the order of $O(3^{(n-2)/2}) = O(3^{n/2})$.

---
Tags: recurrence-relation
---


# Question
Title: algorithm for finding a straight line to separate class
I want create algorithm, which find a straight line which will separate the most objects from the class. The line must be parallel to the X or Y axis. Example:

Above example present two class: circles filled and unfilled. Red line is a solution to the problem. Has anyone the idea how to find such a simple?

# Answer
First sort data base on their $y$ value. Then find the minimum and maximum value between members of the second class which is denoted by $y\_{min\_2}$ and $y\_{max\_2}$, respectively. Then, line with equation of $y = y\_{min\_2}$ and $y = y\_{max\_2}$ are candidate. We can count the number of first class member in sides of these two lines in $O(\log(n))$.

Therefore, we find an algorithm which works in $O(n\log(n))$.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Whether equivalence of different types of automata is of P-type?
I came across following problem:

> Which of the following problems is/are P-problems?
> (I) Equivalence of DFA's
> (II) Equivalence of NFA
> (III) Equivalence of regular expressions

Now I know I there exist neat algorithm to find whether given two DFAs are equivalent or not. So (I) must be P-problem. I am doubtful about (II) and (III). There is a procedure to convert every NFA to DFA. So to check whether equivalence of two NFAs, we can first covert them into DFAs and then check their equivalence in P-time. But seems that we cannot convert NFA to DFA in P-time, hence equivalence of NFA seems not a P-problem. Same for (III). Am I correct with this?

# Answer
The short answer to your question is that 1 is in P, and for 2 and 3 we don't know, but we strongly suspect that they are not in P.

In more detail, as you point out, checking whether two DFAs are equivalent can be done in P (by observing that DFAs are closed under complementation and intersection, and that $A\subseteq B$ is equivalent to $A\cap \overline{B}=\emptyset$).

As for checking equivalence of NFAs, we know that the equivalence problem is PSPACE-complete (by a simple reduction from universality of NFAs). This means that if the problem was in P, we would get P=PSPACE, which would be a huge and unlikely surprise.

Same goes for checking equivalence of regular expressions - the problem is PSPACE-complete. This post has more details on this
> 3 votes

---
Tags: regular-languages, automata, finite-automata, regular-expressions
---


# Question
Title: Systematic approach or algorithm for designing a pushdown automata that accepts a langauge
I understand that designing automatons is mostly a creative process but, a month ago I was having a discussion with a classmate about designing a NPDA or a DPDA that accepts a non-trivial language (trivial meaning, it is straightforward to design a PDA that accepts it) and he gave me a solution while mentioning an algorithm that he used to arrive at said solution. his solution was correct but used nearly twice the number of states than my solution which was also correct (both solutions used NPDAs). unfortunately I don't have access to him to ask about what he meant by an algorithm, anymore.

I looked in both Sipser and Linz books and I didn't find anything about such an algorithm or systematic approach.

If you know of such thing please demonstrate with your own language of choice.

# Answer
> 1 votes
Your question is something very natural, that comes up a lot when first encountering computational model. The main problem is that your question does not "compile":

You ask if there is an algorithm that constructs PDAs. What would be the input for such an algorithm? This is the main crux of the problem.

Until you specify that, you won't really have an answer. As Yuval commented, if you get a CFG as input, then there is an easy procedure to convert it to a PDA.

Let's look at the other extreme: suppose you are given a Turing Machine, and you just ask whether there exists a PDA for its language (even without constructing it). As it turns out, this problem is undecidable (it's an immediate consequence of Rice's theorem, but in fact it's neither in RE nor in coRE).

This problem is something that often comes up in designing computational models - how do we specify what we want? If we give a rich specification formalism, such as Turing machines, then things become undecidable. And if we give something too poor, such as CFGs, then the construction task becomes easy, but writing down the specification becomes the hard part, so it's debatable whether we actually did any good...

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


# Question
Title: Reduction function from A to its complement
I wanted to ask a simple question.

Lets say we have A, language of all the words with more then 3 letters. so it belongs to R.

and its complement , is the language of all words with less then 3 letters.

is it possible to say that I can define a turing reduction between them?

i thought about something like this: $$ f(x) = \begin{cases} 01 & \text{if }x \in A, \\ 1234 & \text{ } else.\end{cases} $$

my friend is saying this solution is not good since, the definition is: $\qquad\displaystyle x \in L\_2 \iff f(x) \in L\_1$

and what i got is

$\qquad\displaystyle x \notin L\_2 \iff f(x) \in L\_1$

If in this case it wont work can you explain me why? Thank you!

# Answer
This is true for any recursive language $A$ different from $\emptyset$ and $\Sigma^\*$ for some finite alphabet $\Sigma$. Your definition is correct. In general you could define $f$ as following. Let $a\in A$ and $\overline{a} \in \overline{A}$.

$$f(x)= \begin{cases} \overline{a} & x\in A \\ a & x\notin A \end{cases} $$ From this definition it follows $x \in A \iff f(x) \in \overline{A}$. Moreover, since $A$ is recursive $f$ is computable for any $x$ and hence $A \leq\_T \overline{A}$.

The whole point is to decide $x \in A$ by using $f(x)$ and $\overline{A}$. So, given $x$ you can effectively say whether or not $x \in A$ only by looking at if $f(x) \in \overline{A}$. If $f(x) =\overline{a} \in \overline{A}$ then $x$ is in $A$, otherwise $x$ is not in $A$. Hence $A \leq\_T \overline{A}$.
> 1 votes

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


# Question
Title: Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?
> Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?

I think the answer is yes but i'm unable to find a computation that standard Turing machine can do but this machine can't.

Any ideas?

# Answer
> 17 votes
The type of Turing machine you describe is a linear bounded automaton (it can only write on the parts of the tape containing the input). LBAs are the acceptors for context-sensitive languages so to find a specific example of a problem that can't be solved with this restriction but can be solved in general by a Turing machine, you just need a language that is decidable but not context-sensitive.

The example given on Wikipedia is:

> An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.

For more examples, see Is there an example of a recursive language which is not context sensitive?

# Answer
> 10 votes
A Turing Machine that cannot write on blanks is by the space version of the linear speedup theorem a linear bounded automaton. Therefore any decision problem outside $\textsf{DSPACE}(O(n))$ cannot be decided by it. Such problems do exist by the space hierarchy theorem.

---
Tags: formal-languages, turing-machines, computability, automata
---


# Question
Title: Returning two array indices in an array for a given value
Give an algorithm that takes as input an array A sorted in non-decreasing order, and a value x, and that returns two indices (F and L) into A, where A\[F\] is the first value equal to x and A\[L\] is the last value equal to x. Your algorithm should run as fast as possible in the worst case. State the worst case running time of your algorithm.

A O(n) algorithm is very easy for this. A for loop running on the input array could easily find F,L. I think for sure there is a better algorithm. I am thinking of modifying binary search to search for the same value repetitively. I think O(logn) might not be possible, but something like $O(log ^2 n)$ might be. I am unable to come up with a precise algorithm that achieves something like this running time.

# Answer
Yeah, bisection'll maximize the information gained from each check. If you do any sort of check other than bisection, then in the worst-case, the sought element'll be on the larger section of the selected divide.

The worst-case scenarios will occur whenever bisection has to happen $O\left(\log{n}\right)$ times to find the first/last indices of the selected value, `x`. For example, if the array's all the same value, e.g. `A=[0,...,0]`, then bisection'll have to occur until the algorithm whittles it down to the first `0` at $i=0$, then a separate bisective search would have to go just as many times to find the last `0` at $i=n\_{\mathrm{length}}-1$.

Both searches'll be $O\left(\log{n}\right)$. But since two sequential $O\left(\log{n}\right)$ processes are still just $O\left(\log{n}\right)$, the overall algorithm's $O\left(\log{n}\right)$.
> 1 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, search-algorithms
---


# Question
Title: Programmatically checking equivalence of statements
So as part of a theorem-prover/checker, I'm using Prolog to try to determine the equivalence of statements that have been parsed into tree form, e.g. $x=2$ is represented as `eq(x,2)`, or $x=2 \land y\leq z$ if `and(eq(x,2),leq(y,z))`, and I want to determine if these statements are equal.

The way I'm currently (attempting) to do this is by trying to convert statements to some normal form, e.g. converting all greater-than statements to less-than statements, or `eq(x,x)` simplifies to `true`, and then statements would be compared syntactically to determine equivalence. However, this feels like it might be a tad tricky/complicated, and to some extent I'm a bit uncomfortable simply using syntax rather than semantics to determine whether they are the same.

Is there some standard way of solving determining these equivalences algorithmically, or perhaps can anyone think of a better alternative?

Much appreciated.

# Answer
> 1 votes
So, there are two possibilities, depending on how complex your statements are.

If your statements are relatively simple, then there's a good chance they fit in what is decidable with Satisfiability Modulo Theories. It's basically a way of taking a SAT solver and integrating it with a solver for a specific theory, for example, theory of linear arithmetic. Here is a list of common theories.

If your statements are too complex, then reducing these equations to a normal form becomes undecidable. This is because there are ways to encode logic and computation in arithmetic, so determining the equivalence of some formulas can be equivalent to solving arbitrary logical equations.

The decidability of your problems depends heavily on whether you're using integers or reals, linear or non-linear arithmetic, etc. As was mentioned in the comments, if you can encode arbitrary Diophantine equations, then you're definitely undecidable.

Regardless of decidability, your problem is definitely $NP$-hard. Suppose we could efficiently check if the normal form of problems were syntactically the same. Then we could efficiently solve 3SAT by checking if a boolean formula is equivalent to False.

---
Tags: logic, semantics, boolean-algebra, prolog
---


# Question
Title: Satisfiability with relational operators instead of boolean variables
# Question

What is the state of the art for relation/equality satisfiability problems and where can I find papers clearly describing algorithms used (Or even better: implementations of them. Or even better: javascript implementations - I know that's a long shot)?

I.e. How do I solve satisfiability of: `x > 10 && y < 5 && x < y`

# Long introduction

## boolean satisfiability

The boolean satisfiability problem is quite well documented. However I cannot find algorithms for cases when propositions are relational operators rather than booleans.

For example:

To find out if a sentence like `p && !p` has any values of `p` for which it is true, is well documented and ready-made algorithms exist. Often the sentence is transformed to Conjunctive Normal Form (CNF) and then a CNF-SAT solver is used. For example:

## relational/equality satisfiability

However I cannot find algorithms for cases when propositions are relational operators rather than booleans. Think of a statement like `x > 10 && !(x < 5)` or `x > 10 && y < 5 && x < y`. This seems a way less studied problem.

For example: Transforming equality logic to propositional logic is very theoretical, I couldn't really understand it and thus use it for implementation.

Solving Satisfiability and Implication Problems in Database Systems actually lead me to a solution. It explains how to solve satisfiability for sentences with only conjunctions. Knowing that, I can transform any sentence to Disjunctive Normal Form (DNF) and apply the algorithm to each conjunction in the DNF. If one of the conjunctions is satisfiable, the whole sentence is.

However, it seems that this is not the most efficient way to solve it. First, this paper is from 1996 and I expect the field to have progressed. Second, converting to DNF is exponentially complex while converting to a equisatisfiable CNF can be done in polynomial time. Most boolean satisfiability solvers seem to convert to CNF and then solve using heavily studied algorithms. It seems a similar approach would be preferable for relational satisfiability.

So my question is: What is the state of the art for relation/equality satisfiability problems and where can I find papers clearly describing algorithms used (Or even better: implementations of them. Or even better: javascript implementations - I know that's a long shot)

I have searched for 2 days in different fields such as SQL query optimizers (contradiction/tautology detection) and theoretical CS but haven't been able to find anything else than the above DNF solution.

# Answer
Congratulations, you have invented Satisfiability Modulo Theories, also known as SMT. This is a large field of research, and deals with exactly the problem of satisfiability with not just boolean variables, but predicates over some existing logical theories, such as linear integer arithmetic, uninterpreted functions, arrays, etc.

The basic idea is that you alternate between calling a SAT solver and a theory solver. You take your relational formula, and replace every relational statement with a boolean variable, then get a solution from a SAT solver. This gives you a True or False value for each relational statement. You then plug those into your theory solver, which determines if there's a solution that is consistent with the truth value for each relational proposition.

If the solution is valid, then you are done. If it is not valid, then you add the negation of the assignment (or a reduced form) to your original boolean problem, since you know it can't hold, and you repeat until you either the theory solver succeeds or the SAT solver fails.

SMT research doesn't care a ton about theoretical complexity, since everything is NP-hard in the best case, and possibly much worse, depending on your theory. Instead, modern SMT solvers are heavily optimized with heuristics and prunings that allow them to be reasonably fast for common cases.

The two most common SMT solvers are Z3 and CVC4, but I have no clue if either work in JavaScript. Writing an inefficient SMT solver yourself is not too hard, especially if you can use an off-the-shelf SAT solver.
> 3 votes

---
Tags: satisfiability
---


# Question
Title: A simple clarification on $\#P$ closure properties
What does $\\#P$ closure under addition and multiplication mean?

Does it mean given $NTM$s $N\_1$ and $N\_2$ we can create in **deterministic** polynomial time an $NTM$ $N\_\times$ and $N\_+$ such that for every input $x$ we have $$\\#N\_\times(x)=\\#N\_1(x)\\#N\_2(x)$$ $$\\#N\_+(x)=\\#N\_1(x)+\\#N\_2(x)$$ accepting paths?

# Answer
> 2 votes
Yes, that's exactly what it means. Closure under addition can also be phrased as follows: if $f(x)$ and $g(x)$ are $\\#P$ functions, then $h(x)=f(x)+g(x)$ is also a $\\#P$ function. As an exercise: How do you construct the machines $N\_+$ and $N\_\times$? Check that these definitions mean the same. $\\#P$ has extraordinary closure properties, for example if $f\in \text{FP}$ and $p\in\\#P$ then

$$\sum\_{y=0}^{f(x)}p(y)$$

is also a $\\#P$ function. We say that $\\#P$ is **closed under exponential sums.**

In general, to say that some set $O$ is closed under an operation $\triangle$, means that if you take $a,b\in O$, then $a\triangle b\in O$. In other words, you can't "get out of $O$" by applying $\triangle$ to elements inside $O$. For example, $NP$ is closed under set intersection, because $L,K\in \text{NP}\implies L\cap K\in\text{NP}$ (why?).

# Answer
> 2 votes
$\\# P$ is a class of functions, so it makes sense to ask whether $f,g\in \\# P$ implies $f\cdot g, \hspace{1mm} f+g \in \\#P$.

When attempting to prove this, we encounter the question raised in your post. Let $M\_f, M\_g$ be the polynomial NTMs such that $f(x)=\\#M\_f(x)$ and $g(x)=\\#M\_g(x)$. We now ask whether there exists a polynomial NTM $M$ such that for all $x\in\Sigma^\*$ it holds that $\\#M(x)=\\#M\_f(x)\cdot \\# M\_g(x)$. Note that nothing is said about our ability to construct $M$, although it can be easily constructed from $M\_f,M\_g$.

For multiplication, the machine which simulates $M\_f(x)$, and in case the answer was positive (otherwise reject) simulates $M\_g(x)$ and output its result satisfies the desired property. For addition, the machine which starts by non-deterministically guessing whether to compute $M\_f(x)$ or $M\_g(x)$ will do the trick.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Should check all $2^n$ possibilities in array?
Suppose I have an array of numbers, and a function `boolean isPrime(int n)` that I'm allowed to use.

`Boolean isPrime(int n)` receives a number `n` and return `true` if the received number is a prime and `false` otherwise.

I need to write a function `int foo(int[] a)` that receives the given array and return the biggest prime number that I can "create" by adding values from the given array.

For example: for the array `8,11,8,2` the function `foo` should return `19`

It's not a homework or something, I noticed that in a lot of job exams there is this type of question. It looks simple and naïve, but it's not.

There are a lot of possibles, for array with size $n$ the are $2^n$ possible combinations. In the given example the possibilities are:$\\{8,11,2,8+11,8+8,8+2,8+11+8,\dots\\}$

What's the best way to approach this type of question? I'm sure that it's related to some smart algorithm.

# Answer
> 4 votes
The query complexity of your problem, which is the number of oracle calls that any correct algorithm needs to make, is $2^n-1$ (or even $2^n$, if the oracle is allowed to return "No" on all inputs, in which case the answer to your problem is "Infeasible"). *This assumes your oracle is a black box.* When your oracle is given explicitly, the complexity of the problem could depend on the oracle. For the primality oracle, your problem is likely hard, but this could be challenging to prove since the additive properties of primes are not well-understood.

Indeed, suppose that you have an algorithm solving your problem on arrays of length $n$ using less than $2^n-1$ oracle calls in the worst case. Run it on the array $1,2,4,\ldots,2^{n-1}$. Whenever the oracle asks a question, always return "No" (i.e., cannot be used). When the algorithm has finished, there are at least two sets $S,T$ that have not been queried. There we can consider two oracles, one that says "Yes" only on $\Sigma(S)$ (the sum of elements in $S$) and the other that says "Yes" only on $\Sigma(T)$. By construction, $\Sigma(S) \neq \Sigma(T)$, and so the correct answer is different in both cases. However, the algorithm cannot distinguish between the two oracles, and so its output will be wrong for at least one of these two oracles.

If we allow the oracle to return "No" on all inputs, then we can get a contradiction even given an algorithm that makes exactly $2^n-1$ oracle calls in the worst case. Running it on the same array and answering every query negatively, there is always a set $S$ which has not been queried, and the algorithm cannot distinguish between the oracle which answers "Yes" only on $S$ (in which case the answer is $S$) and the oracle which always answers "No" (in which case the answer is "Infeasible").

---
Tags: algorithms, arrays
---


# Question
Title: Why is $MOD_{p^k}P=MOD_pP$ at every prime $p$?
Complexity zoo states that $MOD\_{2^k}P=MOD\_2P$.

It is clear that if $MOD\_2P$ accepts (number of accepting paths is off) then $MOD\_{2^k}P$ accepts.

Why is it clear that if $MOD\_2P$ rejects (number of accepting paths is even ) then $MOD\_{2^k}P$ rejects?

Does $MOD\_{2^k}P=MOD\_2P$ have a different interpretation? I mean somehow we can construct a $MOD\_{2^k}P$ machine from a $MOD\_2P$ machine at every $k\in\Bbb N$?

I am interested in when $k$ is polynomial in input length.

# Answer
> 0 votes
The correct interpretation is: a problem belongs to $MOD\_2 P$ if and only if it belongs to $MOD\_{2^k} P$.

Equivalently, a language is accepted by some $MOD\_2 P$ machine if and only if it is accepted by some $MOD\_{2^k} P$ machine. It doesn't have to be the same machine.

The way you prove these equivalences is through identities like this:

* $x \equiv 0 \pmod{2}$ iff $2x \equiv 0 \pmod{4}$.
* $x \equiv 0 \pmod{4}$ iff $1+(x+1)(\frac{x(x+1)}{2}+1) \equiv 0 \pmod{2}$.

I'll let you work this out.

---
Tags: complexity-theory, complexity-classes
---


title: Finding running time

text:
# Question
Title: Finding running time
Apologies for this simple question. I found it in the book Algorithms by Sedgewick and Wayne.

Give a formula to predict the running time of a program for a problem of size N when doubling experiments have shown that the doubling factor is $2^b$ and the running time for problems of size N0 is T.

$$ \frac{T(2N)}{T(N)}=2^b.$$

$$ T(N\_0)=T. $$

I am not sure how to proceed after that.

# Answer
Instead of solving the question for you, let me show you what steps you need to take in order to solve this problem on your own.

Suppose that $T(1) = T\_0$ and $T(2n) = C T(n)$ for all $n$.

* What is $T(2)$? What is $T(4)$? What is $T(8)$? What is $T(2^k)$?

Now suppose that $T$ is monotone: $T(n\_1) \leq T(n\_2)$ whenever $n\_1 \leq n\_2$.

* If $2^k \leq n \leq 2^{k+1}$, what can you say about $T(n)$?
* Can you now deduce the asymptotic rate of growth of $T(n)$ for arbitrary $n$?
> 0 votes

---
Tags: runtime-analysis
---


# Question
Title: Complexity of computing the antiderivative of a given function
**Disclaimer:** I don't know much computational complexity theory. I am nevertheless curious.

---

If function $f(x)$ has a certain level of computational complexity (which I actually don't know how to measure), what can we then say about the computational complexity of the following indefinite integral?

$$\int f(x) \\, \mathrm d x$$

For example, can we say something about how long it takes to approximate the integral of $f$ within an error of $\epsilon$, given that we know how long it takes to compute $f$ within an error of $\epsilon$?

# Answer
> 3 votes
Kawamura, in his paper Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete, mentions a classical result of Friedman (Theorem 3.4) which implies that computing the integral of an easy function could be a hard task (check the paper for the exact definitions), essentially since integration is like summing over many different values.

The result mentioned above is in the framework of computable analysis. The answer could be different in other models of computation. See Real-number Computability from the Perspective of Computer Assisted Proofs in Analysis for a recent survey of models of computation on real numbers.

---
Tags: complexity-theory, time-complexity, approximation, mathematical-analysis
---


# Question
Title: Time complexity of finding an integer between $x$ and $2x$
Consider receiving as input $x\in\mathbb N$ and computing some (any) prime $p\in\[x,2x\]$.

> **What is the complexity of the above problem?**

---

A natural way to approach this problem is to generate random integers in $x,\ldots,2x$ and check for their primality using Miller-Rabin or a deterministic algorithm such as AKS.

However, this may be suboptimal. What is the best-known runtime for the problem?

# Answer
> 2 votes
You can speed up this algorithm somewhat by generating a random integer which is coprime to all small primes. This can be done efficiently using a sieve: pick an appropriately sized random interval inside $\[x,2x\]$, and cross off all integers in the interval which are multiples of small primes (you can do this efficiently by finding the first multiple of a given prime, and then iterating over the remaining multiplies). Now use your favorite algorithm to find a prime within the integers not ruled out. The size of the interval should be chosen so that it guarantees that there is a prime (so about $\log x$ or somewhat larger).

---
Tags: algorithms, primes
---


# Question
Title: A $log(k)$ algorithm for the matroid secretary problem
I'm reading the following article that presents a $log(k)$ algorithm for your secretary problem.

I'm in the analysis section at the left part of page 5 there is the following claim:

> $B^\*$ is a set with elements $x\_1,...,x\_k$ with respective values $v\_1,...,v\_k$ where $v\_1\geq...\geq v\_k$. Denote $n\_i(B^\*)$ as the number of elements in $B^\*$ with value at least $v\_i$. Then the sum of the $q$ largest elements is $\[\sum\_{i=1}^{q-1}(v\_{i+1}-v\_{i})n\_{i}(B^{\*})\]+v\_{q}n\_{q}(B^{\*})$

I fail to see how the sum presented is the sum of the largest $q$ elements. From what I understand $n\_{i}(B^{\*})=i$ since the elements with value at least $v\_{i} $ are $v\_{1},...,v\_{i}$.

If I open the sum than all the inner element ($v\_{2},...,v\_{q-1}$) has a coefficient of $1$, but the coefficient of $v\_{1}$ is $-1$ and the coefficient of $v\_{q}$ is $2q$.

Can someone help me understand this equality?

# Answer
> 1 votes
It seems that there is a typo – $v\_{i+1} - v\_i$ should be $v\_i - v\_{i+1}$.

Suppose first that all elements are distinct. Then (using the convention $v\_0 = 0$) $$ \sum\_{i=1}^{q-1} (v\_i-v\_{i+1}) n\_i(B^\*) + v\_q n\_q(B^\*) = \\ \sum\_{i=1}^{q-1} i (v\_i-v\_{i+1}) + q v\_q = \\ \sum\_{i=1}^q i v\_i - \sum\_{i=2}^q (i-1) v\_i = \sum\_{i=1}^q v\_i. $$

Consider now the general case, in which we have $$ v\_1 = \cdots = v\_{j\_1} \> v\_{j\_1+1} = \cdots = v\_{j\_2} \> \cdots, $$ where $j\_r = q$. Then for $j\_0 = 0$, $j\_{r+1} = j\_r+1$, and $v\_{q+1} = 0$, we have $$ \sum\_{i=1}^{q-1} (v\_i - v\_{i+1}) n\_i(B^\*) + v\_q n\_q(B^\*) = \\ \sum\_{\ell=1}^{r+1} \sum\_{t=0}^{j\_\ell-1} (v\_{j\_{\ell-1}+t} - v\_{j\_{\ell-1}+t+1}) n\_{j\_{\ell-1}+t}(B^\*) = \\ \sum\_{\ell=1}^{r+1} (v\_{j\_{\ell-1}} - v\_{j\_{\ell-1}+1}) (j\_1 + \cdots + j\_{\ell-1}) = \\ \sum\_{\ell=1}^r v\_{j\_\ell} j\_\ell = \sum\_{i=1}^q v\_i. $$ (This calculation might not be 100% correct, but you get the idea.)

---
Tags: equality, matroids
---


# Question
Title: What are applications of the levels of the Chomsky hierarchy?
I've recently finished a course on languages in computer science, so we covered characteristics of regular, context-free, decidable and semi-decidable languages. While that is all well and good, we never went into any detail on what applications of this knowledge are (other than compilers being context-free language recognizers). I've tried googling for answers but wasn't able to find anything relevant. I'm wondering if someone can just explain what current applications for each 'type' of language are and perhaps link further material for reading.

Thank you.

# Answer
> 1 votes
First, let's be clear, there are two separate types of languages, Turing Decidable (also called recursive), and Turing Recognizable (also called semi-decidable or recursively-enumerable).

The "application" of decidable languages is all of computer science. It's a huge class that includes exactly the problems that can be solved by algorithms. So you're not going to find specific applications like you would for compilers and CFGs, because the applications covered by decidable languages are "everything else." If you can write code for it, it's in this class.

Recursively-enumerable problems are ones where you know a solution when you see one, but might never know when you're out of potential solutions. You always halt on a "yes" answer, but might never halt for "no". This class is basically first-order theorem proving: we recognize proofs when we see them, but with quantifiers, there's no way to know if no proof exists.

It's also worth mentioning that *parsers* are CFG recognizers. Other parts of compilers, like translation and type-checking, are definitely *not* context-free.

# Answer
> 0 votes
I'll add some applications of regular languages:

* Being able to write a regular expression for a language allows us to perform input validation and search, such as on phone numbers, email, and more. The command line tool `grep` uses regular expressions to search in text documents (incidentally the name "grep" comes from "globally search a regular expression and print").
* Regular expressions are useful in natural language processing, having applications in segmentation, normalization, and stemming.
* Regexes are also useful in syntax highlighting.
* As touched on in comments, finite state machines are used to model the behavior of everyday objects and processes such as circuits and network protocols. Another cool example of this is a standard HTML button.
* Directed acyclic word graphs are data structures for storing a set of strings as essentially a minimum-state DFA, allowing for fast lookups and good space efficiency.
* Applications in molecular biology such as improving DNA sequence alignment and splicing languages which are a subset of regular languages that formalize the concept of gene splicing.

To round out the list, the discussion in What is the enlightenment I'm supposed to attain after studying finite automata? addresses the relevance of regular languages from a theoretical/philosophical perspective and is an excellent read!

---
Tags: formal-languages, turing-machines
---


# Question
Title: Extremal related question regarding Intersection of neighbourhood of vertices
What is the maximum number of edges that a simple directed graph on $n$ vertices can have, if the graph has the following restriction.

Size of Intersection of Neighbourhood of any pair of vertices is at most $k$?

Neighbourhood is defined as follows. If a vertex $v$ has directed edges towards exactly three vertices $a$, $b$ and $c$, then $\\{a,b,c\\}$ constitutes the neighbourhood of $v$.

My hunch is $O(kn)$ but I am not able to prove it? Its easy to create such a graph which has $O(kn)$ edges, and has maximum intersection of neighbourhood to be at most k.

Simply create an empty graph on $n$ vertices say $v\_1,v\_2\ldots v\_n$. Then for each $v\_i$ give their neighbourhood to be $v\_{i+1}$ to $v\_{i+k}$. This gives a graph $O(kn)$ edges.

Can you show that this is the best which can be done?

# Answer
> 1 votes
This problem has been solved in the undirected case by Füredi, New asymptotics for bipartite Turán numbers, who showed that for constant $k$, the optimal bound is $$ \frac{1}{2} \sqrt{k} n^{3/2} + O(n^{4/3}), $$ when counting *undirected* edges. When counting directed edges, you have to double the number. The lower bound also holds in the directed case — it is given by an explicit construction based on finite fields.

Following Füredi's footsteps, we can generalize the upper bound to the directed case. Denote by $P\_2$ a path consisting of two directed edges pointing at the central cases. The number of copies of $P\_2$ in your graph is at most $k \binom{n}{2}$, since for every choice of the outer vertices there are at most $k$ choices of the inner vertex. On the other hand, the number of copies of $P\_2$ is also $\sum\_v \binom{d\_{in}(v)}{2}$, where $d\_{in}$ is the in-degree of $v$, since for every $v$, we can choose any two vertices in its incoming neighborhood to create a copy of $P\_2$. Convexity now shows that $\sum\_v \binom{d\_{in}(v)}{2}$ is minimized when all in-degrees are the same. If the graph contains $m$ edges, then the total in-degree is $m$, and so $$ k \binom{n}{2} \geq n \binom{m/n}{2}, $$ from which we can deduce $m \< \sqrt{k} n^{3/2} + n/2$.

---
Tags: graphs
---


# Question
Title: Generate a unique number for a set of sequences of letters
A sequence of English letters are given, every sequence forms a *word* and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I need to search if the $w$ exists in the database of words.

The framework of the database and the application is on the web and this job is part of an online game, So may be hundreds of requests come to website in a second so I need to do it as fast as possible. To do so as fast as possible, I want generate a unique number for every word in the database. For every string query, I generate its number using the algorithm used to generate numbers for the database, then check if the new number exists in the database or not using binary search tree.

*Here is an algorithm that works perfectly to generate a unique number for a sequence:*

For a sequence $\<a\_1, a\_2, \cdots, a\_n\>$ where $a\_i \in \mathbb{Z^{+}}$ (it is easy to map every letter to a number) the unique number is

$$ \prod\_{i=1}^{n}{p\_i^{a\_i}} $$

where $p\_i$ is the $i$-th prime number. But the problem is, the produced numbers are too large to be stored in current programming language variables.

## My Solution

First I set the following mapping:

$MAP: \[a=\>2, b=\>3, c=\>5, \cdots, z=\>101\]$

So I set the $i$-th prime number to the $i$-th letter. (Actually it is not necessary to regard this order, more frequent characters can take smaller prime number)

For a sequence $\<a\_1, a\_2, \cdots, a\_n\>$ where $a\_i$s are letters this is my formula:

$$ \prod\_{i=1}^{n}{MAP(a\_i)^i} $$

For valid words, this formula generally, produces smaller numbers than the first one. I just wanted to know :

* if this formula always generates a **unique** number? I couldn't generate two words with the same numbers, but clearly it is not enough to convince other people
* Is there any solution that search for words in $O(\log n)$ (like binary search tree)?

thanks.

# Answer
> 1 votes
Use a hash function. Since you have less than $2^{16}$ words, if you use a hash of 32 bits then you are likely to not have any collisions. If you do get collisions, you can try varying the key (hashes usually use some magic numbers, which in some cases are known as keys), or you can just use a longer hash.

Another possibility is to store the dictionary as a decision tree. The decision tree contains a node for each prefix of a word in your dictionary, and as you read a new word, you travel along the decision tree until you hit a leaf (the word is in the dictionary) or you get stuck (the word is not in the dictionary). But that amounts to storing the entire dictionary, which perhaps you are trying to avoid for some reason.

If for some reason you don't like these solutions, I have two other solutions to offer, though I don't recommend using them. The first one is to encode your words in base 26. This will be much more efficient than your prime-based code, though still somewhat unwieldy (the result could be up to 71 bits long). A more economic but more complicated solution is to use a Huffman code, either first order (the same code for each letter), second order (one code for the first letter, and henceforth the code depends on the previous letter), or even higher order.

---
Tags: search-algorithms, strings, number-theory, binary-search-trees
---


# Question
Title: black-box function optimization with binary vector input: terminology and NP-hardness proof
I have a black-box function optimization problem: $$\arg\max\_{\vec{x}} \\; f(\vec{x}, \vec{y}) \\\text{subject to } \vec{x} \in \mathbb{Z}\_2^N, \\|\vec{x}\\|\_1=K, K\<N, \vec{y} \in \mathbb{Z}\_2^M$$

The function $f(\cdot)$ is a black-box function whose output I can only simulate: I cannot access its exact form. The variables $\vec{x}$ and $\vec{y}$ are two binary vectors as the inputs of $f(\cdot)$. Given $\vec{y}$, I am seeking the optimal $\vec{x}$ that maximizes $f(\vec{x},\vec{y})$.

My questions:

1. Is there similar research having the same form as my problem? What is the terminology for such problems?
2. The brute force method to do the optimization is to exhaust all $\binom{N}{K}$ possible $\vec{x}$. Is this problem NP-hard? How can we prove this problem is an NP-hard problem?
3. In practice there should be some heuristics and techniques to be used to speed up the search and return an approximate optimal solution. Can someone point me out the names of possibly feasible techniques?

# Answer
NP-hardness is a property of *languages*, that is, of subsets of $\Sigma^\*$ for some finite alphabet $\Sigma$. Your problem is not of this form, since you also need to give the algorithm access to the function $f$. Such problems are known as "optimization with a value oracle" (and several other similar names) — the value oracle in your case is the function $f$.

To show that such a problem is hard, we typically given an information-theoretic lower bounds on the number of value oracle calls of any valid algorithm. This captures much, but not all, of the difficulty of solving the problem (it ignores the computational complexity of deciding which questions to ask the oracle). In your case, it is easy to show that any valid algorithm must query the oracle at *all* possible inputs, using an adversary argument. This makes your problem not so interesting.

In practice, problems tend to have more structure. For example, if you know that for each $\vec{y}$, the function $\vec{x} \mapsto f(\vec{x},\vec{y})$ is submodular, then you can use approximation algorithms for (non-monotone) submodular maximization. In some cases, for example maximizing supermodular functions, there are efficient algorithms that find an optimal solution. In other cases, for example maximizing submodular functions, finding even an $\alpha$-approximate maximum can be hard (requiring exponentially many value oracle queries) if $\alpha$ is too close to 1, but at some point the problem becomes easy again (can be solved in polynomial time).

Any heuristics to your problem will have to rely on some properties of your function. So your first task is to learn more about the structure of your function. In some cases, such as cryptography, there is nothing more to learn, and then there is no real way to speed up the search. But in most optimization contexts you are able to say more about your function, at least roughly, and this informs the algorithms and heuristics that you subsequently use.
> 1 votes

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


title: Manipulating Intersection of oracles

text:
# Question
Title: Manipulating Intersection of oracles
Suppose for different classes $A,B,C$ we have that $A\subseteq P^B$ and $A\subseteq P^C$.

1. We have $A\subseteq P^{B}\cap P^{C}$. Does it also mean $A\subseteq P^{B\cap C}$?
2. Supposing $A\subseteq P^{B\cap C}$ also holds does it also give $A\subseteq {B\cap C}$?
3. If $P^B=B$ then does it mean $A\subseteq {B\cap C}$ or $A\subseteq B\cap P^C$?
4. If $B\subseteq P^{B\cap C}$ then does it mean $A\subseteq {B\cap C}$ or $A\subseteq B\cap P^C$?

Do we know anything else about intersection of oracles?

# Answer
The answer to all of those questions is no, and not for some especially deep reason, as most of these can be ruled out by forcing the intersection to be simple enough.

Suppose $B$ contains all languages with only even length words, and $C$ contains all languages with odd length words. Clearly $B\cap C =\emptyset$, so $\mathsf{P^{B\cap C}=P}$, but $P^B, P^C$ both contain undecidable problems. This example rules out $1,2$.

To rule out $3$ you can set $\mathsf{B=EXP}$ and $C=\emptyset$. Choosing $B=\emptyset$ rules out $4$. Not allowing the empty set won't change much, as we can always do the same tricks with finite languages (or simple infinite langauges), so it is probably not possible to claim anything interesting in the general case.
> 1 votes

---
Tags: oracle-machines, oracles
---


title: Intuition behind the Master Theorem

text:
# Question
Title: Intuition behind the Master Theorem
The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following:

> For a recurrence of the form $T(n) = aT(\frac{n}{b})+f(n)$ with constants $a \ge 1$ and $b\>1$,
>
> Case 1: if $f(n) = O(n^{\log\_b(a-\varepsilon)})$ for some $\varepsilon \> 0$, then $T(n) = \Theta(n^{\log\_b(a)})$
>
> Case 2: if $f(n) = \Theta(n^{\log\_b(a)})$, then $T(n) = \Theta(\log n \cdot n^{\log \_b(a)})$
>
> Case 3: if $f(n) = \Omega(n^{log\_b(a+\varepsilon)})$ for some $\varepsilon \> 0$, and if $a f(\frac{n}{b}) \le c f(n)$ for some constant $c\<1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

I have seen proofs of this theorem which go through the algebraic derivation of these results and I understand how to apply it but I don't have a very strong intuitive understanding of *why it works*. Here's what I understand so far, using these explanations of the Master Theorem on Quora as a starting point:

* The first answer frames the three cases in terms of the relative amount of work done at each level (either increasing geometrically, staying the same, or decreasing geometrically). At a high level, I understand this intuition and if the Master Theorem were *given to me* I could explain it using this reasoning, but I'm unconvinced that I could take this idea of geometric growth/decay and then *derive* the theorem.
* I think the second answer is closer to the kind of intuition I'm looking for. It explains the $aT(\frac{n}{b})$ term and the $f(n)$ term as opposing forces of replication and merging, respectively. However, I'm having trouble understanding how the intuitive cases (the replication step winning, the merging step winning, and the forces being equal) actually translate into the three different cases of the Master Theorem.

This explanation also follows a similar argument and simplifies the Master Theorem in the following way:

> If $T(n) = aT(\frac{n}{b})+f(n)$ then compare $n^{\log\_b a}$ with $f(n)$
>
> + If $f(n) \< n^{\log\_b a}$, then $T(n)=n^{\log\_b a}$
>     + If they are equal, then $T(n)=f(n)\log n$
>     + If $f(n) \> n^{\log\_b a}$, then $T(n)=f(n)$

While I see the connection with the Master Theorem cases here, there isn't an intuitive explanation for where the $n^{\log\_b(a)}$ term comes from. That is, if I were just looking at the recurrence relation $T(n) = aT(\frac{n}{b})+f(n)$, how would I know to compare $f(n)$ with $n^{\log\_b(a)}$? Perhaps there is some connection between $n^{\log\_b(a)}$ and $aT(\frac{n}{b})$ that I'm missing?

In summary, I'm looking for something of the form **"here is a high level concept/understanding (eg. geometric growth/decay, competing forces), and now here is how you can derive the Master Theorem from that idea."** I would be satisfied with an explanation of how to get from the replication and merging intuition posed in the second bullet point above to the three different cases of the Master Theorem but I'm also interested in any other more intuitive perspectives.

# Answer
> 8 votes
You can use repeated substitution to obtain $$ T(n) = f(n) + af(n/b) + a^2f(n/b^2) + \cdots $$ Now suppose that $f(n) = n^\gamma$. Then $$ \begin{align\*} T(n) &= n^\gamma + a (n/b)^\gamma + a^2 (n/b^2)^\gamma + \cdots \\ &= n^\gamma \left\[ 1 + \frac{a}{b^\gamma} + \left(\frac{a}{b^\gamma}\right)^2 + \cdots \right\]. \end{align\*} $$

Let us assume that $n$ is a power of $b$, and that there is a base case $T(n) = C$ for some $C\>0$.

There are three different cases to consider:

1. If $a \< b^\gamma$ then the stuff in the brackets is a converging geometric series, and so $T(n) = \Theta(n^\gamma)$.
2. If $a = b^\gamma$ then all terms are the same. Since there are $\log\_b n+1$ of them, $T(n) = \Theta(n^\gamma \log n)$.
3. If $a \> b^\gamma$ then the terms keeps increasing, and so we can approximate $T(n)$ by the last term, which is $a^{\log\_b n} C = \Theta(n^{\log\_b a})$.

The condition $a \lesseqqgtr b^\gamma$ is the same as $\log\_b a \lesseqqgtr \gamma$, which is how the theorem is usually presented.

The actual theorem has some extra conditions that are needed in some of the cases when $f(n)$ is not a function of the exact form $n^\gamma$, but these are just technicalities.

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: Maximum number of different substrings in big string
I'm trying to find the maximum number of different substrings of string consisting only of lowercase letters 'a' - 'z', if the length of string can be up to $5000$

Firstly, I was thinking that the number of substrings is $\frac{n\cdot(n-1)}{2}$ but then I noticed that a lot of the substrings will be the same, and also because of the length of the string of most $5000$ we cannot put all the possible strings with length 3 for example.

What is the maximum number of different substrings we can get in one string of length $5000$

# Answer
> 5 votes
Here is a general solution for an alphabet of size $d \geq 3$ and a string of length $n$.

Every string of length $n$ has $n-\ell+1$ substrings of length $\ell$. Hence the number of different substrings, of any length, is at most $$ \sum\_{\ell=1}^n \min(n-\ell+1,d^\ell). $$ Consider now an infinite de Bruijn sequence, in which each prefix of size $d^r + r - 1$ is a non-cyclic de Bruijn sequence for length $r$. When $d \geq 3$, such sequences exist, as shown by Becher and Heiber, On extending de Bruijn sequences. Truncate such a sequence to length $n$. We leave the reader to show that the truncated sequence achieves the bound stated above.

---
Tags: strings, substrings
---


# Question
Title: Is there a generic way to parallelize algorithms?
Take:

* An algorithm $A$ that is analytically nice in some way, say, for some class of inputs of length $n$ it runs at $O(f(n))$ on some Turing machine.
* $k+2$ independent, identical such machines.

Is there a generic method to produce algorithms $A\_{in}, A\_{out}, A\_{1},\dots, A\_k$ for which tapes can be made so that:

* $A\_{in}$ finishes after $O(k)$ and transforms a length-$n$ input for $A$ into $k$ inputs, each to one of $A\_\ell$, $\ell \in \\{1,\dots, k\\}.$
* Each $A\_\ell$ runs in $O(f(n)/k)$
* $A\_{out}$ runs in $O(k)$ and combines the the outputs of the $A\_\ell$ into what $A$ would have produced on the input of $A\_{in}$

# Answer
No, there cannot be such a generic method to produce algorithms $A\_{in}, A\_{out}, A\_{1},\dots, A\_k$ with the requested properties. The basic problem is that the requested parallel algorithm only uses a single round. (And allowing $A\_{in}$ and $A\_{out}$ only $O(k)$ time is very restrictive, they cannot even read length-$n$ input or write a length-$n$ output in that time.)

One simple problem which even has a parallel algorithm (but not of the form stated in the question) is the **all-prefix-sums** operation. Input is a list of numbers, and output is another list, whose elements are the sum of all previous elements in the original list. See section "3.2 Scans" on page 23 in

Parallel Algorithms (64 pages)
https://www.cs.cmu.edu/~guyb/papers/BM04.pdf
by Guy E. Blelloch and Bruce M. Maggs – 1996

---

There are at least two possible criticisms of this answer. (1) The counter-example problem took a list of size $n$ and output a list of size $n$. Maybe the question expected the output to be much shorter than the input, like in a decision problem. (2) No explicit proof is given that the counter-example problem has no parallel algorithm of the form stated in the question.

Regarding (1), an output of length-$n$ is used to get around Barrington's theorem, as explained in a comment below the question. Regarding (2), one might look at the elements from $n/2$ to $n$ of the output. Each of them would require more than $n/2$ additions, if computed in isolation. $A\_{out}$ can only output $O(k)$ of them in $O(k)$ time, so most of them must be computed in partial isolation. Hence, the algorithms $A\_i$ outputting them will need more than $O(n/2)$ time.
> 3 votes

# Answer
No. There are some problems that appear to be inherently sequential and not amenable to a speedup on a parallel computers. See, e.g., https://crypto.stackexchange.com/q/606/351 and https://crypto.stackexchange.com/a/5962/351. These schemes cannot be parallelized much, assuming certain cryptographic hardness assumptions are true.

You might also be interested in P-complete problems, which are good candidates to be hard to parallelize (see also the NC complexity class).
> 1 votes

# Answer
Sure, just use data-flow analysis, e.g. like this:

,

where you trace out the causal flow of effect.

Then, where ever a node forks, that'd be $A\_{\text{in}}$ in your notation. And whenever there's a join, then that'd be $A\_{\text{out}}$. Each route between a fork and a join would be another $A\_i$.

Practically speaking, most computer code can be parallelized pretty easily. The problem's that small parallelizations tend to induce far more overhead than they're worth, effectively slowing down the code.

It's often possible to parallelize further. But, obviously, you can't do things out-of-order unless you know a way to rewrite them. So, one common strategy for increased parallelization effectiveness is to rewrite the code with longer routes before split paths rejoin.

---

### Maximum parallelization

> Each $A\_\ell$ runs in $O(f(n)/k)$

This notation's not quite correct, but it looks like you meant "*$k$-times faster*", i.e. a speed-up ratio of $k$ (also known as a 100% parallelization efficiency).

Anyway, that's possible if the problem can be broken into an initial fork and a final join. That's the ideal limit which can only be reached in such a special case. Obviously, most algorithms won't fall into that special case, so usually the speed-up ratio will be less than $k$.
> 0 votes

---
Tags: complexity-theory, reference-request, parallel-computing
---


# Question
Title: Difference between Tail-Recursion and structural recursion
Is there any difference between structural-recursion and Tail-recursion or they both are same? I see that in both of these recursions , the recursive function is called on the subset of the orignal items.

# Answer
1. **Structural recursion:** recursive calls are made on *structurally smaller* arguments.
2. **Tail recursion:** the recursive call is the *last thing* that happens.

There is no requirement that the tail recursion should be called on a smaller argument. In fact, quite often tail recursive functions are *designed* to loop forever. For example, here's a trivial tail recursion (not very useful, but it is tail recursion):

```
def f(x):
   return f(x+1)

```

We actually have to be a bit more careful. There may be several recursive calls in a function, and not all of them need to be tail recursive:

```
def g(x):
  if x < 0:
    return 42             # no recursive call
  elif x < 20:
     return 2 + g(x - 2)  # not tail recursive (must add 2 after the call)
  else:
     return g(x - 3)     # tail recursive

```

One speaks of *tail recursive calls*. A function whose recursive calls are **all** tail-recursive is then called a tail-recursive function.
> 28 votes

# Answer
Tail recursion is a very simple case of structural recursion, where the structure in question is a *linked list*. In the language you are probably using primarily, this list is probably not literally in the code; rather, it is a conceptual "list of calls to the function", a concept that may not be possible to express as written using that language. In Haskell (my language), any tail-recursive function call can actually be replaced by sequencing actions on a literal list whose elements literally are "calls to a function", but this is probably a functional-language thing.

Structural recursion is a way of operating on an object defined as a composite of other (possibly composite) objects. For example, a binary tree is an object containing references to two binary trees, or is empty (thus, it is a *recursively defined* object). Less self-referentially, a pair (t1, t2) containing two values of some types t1 and t2 admits structural recursion, although t1 and t2 need not also be pairs. This recursion takes the form

> action on the pair = combination of the results of other actions on each element

which doesn't sound very profound.

It is often the case that a structural recursion *cannot* be tail-recursive, although any kind of recursion can be rewritten as a tail recursion (proof: if you run the original recursion, the actions are completed in a certain order; therefore, the recursion is equivalent to performing that particular sequence of actions, which as I discussed earlier, is tail recursion).

Either the binary tree or the pair example above demonstrate this: however you arrange the recursive calls on the subobjects, only one of them can be the last action; possibly neither one is, if their results are combined in some way (say, addition). As Andrej Bauer says in his answer, this can happen even with only one recursive call, as long as the result is modified. In other words, for *every type of object* other than those that are effectively linked lists (only one subobject all the way down), structural recursion is not tail recursion.
> -1 votes

---
Tags: recursion
---


title: Reception of numerical infinities

text:
# Question
Title: Reception of numerical infinities
A group of computer scientists associated with numerical analyst Yaroslav Sergeyev have published numerous publications recently on a scheme proposed by Sergeyev that uses terms like *Infinity Computer*, *numerical infinitesimal* and *numerical infinity*, claiming that the approach facilitates the solution of many problems.

The mathematicians (including logicians) have been for the most part sceptical but there are a few exceptions, such as Elemer Rosinger and Gabriele Lolli. How have these ideas been received by computer science professionals?

Note. On 19 dec '17 a retraction page was created for this issue.

# Answer
> 3 votes
So the paper's

and it's basically a discussion on the author's "*grossone*" approach that they've been pushing for quite a while now (at least since 2004).

The *tl;dr* on it is that they're proposing a slightly abstracted data type, kinda like how complex number data types generalize real number data types, except this one's focused on infinities instead of imaginaries.

The author seems to want CPU's to include support for *grossone*'s in their arithmetic logic units (ALU's), e.g. as specified in their patent. The author's website and publications seem to focus on applied use in mathematical optimization; they seem to justify their work in terms of theoretical work as an afterthought.

Some of the harshest criticism seems to come from folks who're knocking it as-though the author were trying to report their work as some new theory, arguing that it's weaker and less sophisticated than prior work, e.g. hyperreal numbers. The weird part about this is that, as far as I can tell, that's what the author wanted to do; they're trying to make an abstract data type to replace floating-point data types for common calculation units, not solve the mysteries of the universe.

In general, I'd expect folks who get the author's intent to receive it with a bit of a yawn. The arguments for modifying mainstream ALU's don't seem too compelling, and at-current there's likely not much demand for custom CPU's that implement it.

The author appears to have implemented *grossone*'s at a software level, kinda like how computers do complex-number operations. Since they're using a non-primitive numeric data type, their calculations'll be slower for it; but if they distribute the library and can demonstrate how it's worth the performance hit in some useful applications, some folks might start using it in those cases.

In short, it looks like the controversial proposal's for an abstract data type that includes infinities for use in common calculations. It looks like applied work rather than theoretical, a misunderstanding which seems to have ruffled some feathers; however, at the end of the day if the authors can show that it's useful in real-life coding scenarios and make it available, then folks might use it.

---
Tags: terminology, numerical-analysis
---


title: What is static complexity?

text:
# Question
Title: What is static complexity?
**Definition :** Kolmogorov complexity is a static complexity measure that captures the difficulty of describing a string.

For example, the string consisting of three million zeroes can be described with fewer than three million symbols (as in this sentence)

From wikipedia

> In algorithmic information theory (a subfield of computer science and mathematics), the Kolmogorov complexity of an object, such as a piece of text, is the length of the shortest computer program (in a predetermined programming language) that produces the object as output. It is a measure of the computational resources needed to specify the object, and is also known as descriptive complexity, Kolmogorov–Chaitin complexity, algorithmic entropy, or program-size complexity

I am not able to understand few things like " static complexity " and why we need it

# Answer
> 4 votes
Complexities in this context could be divided into dynamic and static:

* **Dynamic complexity** is an attribute of the execution of a program with the string as an input. For example, the time or space complexity of a Turing machine to accept or reject a string.
* **Static complexity** is an attribute of a program that receives the string as input but not its execution. As you stated, Kolmogorov complexity is a static complexity since it is the length of the shortest program that creates the given string, an attribute that implies nothing about the execution of the program.

---
Tags: complexity-theory, terminology, kolmogorov-complexity
---


title: Rummikub algorithm

text:
# Question
Title: Rummikub algorithm
I have just played a few games of Rummikub and the manipulations I made during my turns became more and more complex transactions. A few turns reordered the whole field, so that other players did not recognize anything and had to plan their turns again.

As always, I thought about representing this in a computer program and having an algorithm that can put in the most pieces on my deck possible. I considered the various transactions that are possible and leave the field valid. However, there is no need for this. We only do little transaction because rearranging the whole field on the table is a bunch of work, especially if one made a mistake.

Basically I only need to find *some* legal arrangement for the set of pieces already on the table and the ones that I want to get rid of. So there is no actual need for transforming the current game state into a new one.

I do not see how to proceed, though. My background is more in numerical methods, and this is a combinatoric problem. Basically I want this:

Let $T$ be the set of pieces $(c, n)$ with a color $c \in \\{ 1, 2, 3, 4 \\}$ and a number $n \in \\{ 1, \ldots, 13 \\}$ on the table. This is not really a set as each piece can occur multiple times. In a second iteration of this question one could also include two joker pieces $J$ that can substitute for everything.

The player has additional pieces in the set $P$. Ideally we would find an arrangement for $T \cup P$, but just finding an arrangement for $n \leq |P|$ elements of $P$, like $T \cup \\{p\_1, \ldots, p\_n \\}$, would also be a good step forward for one move.

One arrangement $A$ is a set of set of pieces such each of these sets satisfies these conditions:

* At least three pieces
* A set is either a “run” where the color $c$ is the same and the numbers are consecutive or it is a “group” where all colors are different and the numbers are the same.

A “group” can only contain four pieces at maximum whereas the “run” can contain up to 13 pieces. If one plays with periodicity, then they can be longer.

A brute force algorithm would just take all possible partitions of the pieces and then check the validity. I would presume that this get out of hand rather quickly.

Some guided approach might be to first try to find the largest consecutive “runs” and group everything that is left as “groups”. But often I have found in the game that taking away pieces from “runs” to make “groups” allows one to integrate a new piece. Sometimes it is the other way around, so there has to be some interplay.

I fear that this question is overload broad in its naivity, but how would I proceed to construct an algorithm that finds a valid arrangement for a set of pieces?

# Answer
Note that I'll use slightly different notation for my convenience.

First, I'll describe an algorithm to determine whether some collection has a valid arrangement assuming we have 4 colours, no jokers and all tiles are distinct. We'll extend this into the general case afterwards.

---

Given are four lists $a\_1,a\_2,\ldots, a\_A ; b\_1,b\_2,\ldots, b\_B ; c\_1,c\_2,\ldots, c\_C; d\_1,d\_2,\ldots,d\_D$ with elements distinct in $\mathbb{N}$ for some $A,B,C,D\in \mathbb{N}$. These four lists correspond to tiles of the four colours $A,B,C,D$. Assume that these lists are sorted from small to large. (If not, we can sort them before starting the algorithm; this will usually take less time than the other parts, most certainly so if the lists are of equal length)

Now, define $R\[w,x,y,z\]:= \text{true}$ if the lists $a\_1,a\_2,\ldots, a\_w ; b\_1,b\_2,\ldots, b\_x ; c\_1,c\_2,\ldots, c\_y; d\_1,d\_2,\ldots,d\_z$ have a valid arrangement and $\text{false}$ otherwise. We'll choose $R\[0,0,0,0\]:=\text{true}$ and $R\[w,x,y,z\]:=\text{false}$ if one of the indices $w,x,y,z$ is negative.

To get a recursive formulation for $R$, consider when a collection has a valid arrangement if we add a few tiles to it. We can add a single tile to complete (or extend) a run of the same colour with size at least $3$ and make some valid arrangement on the remaining tiles. Note that our new tile must be at the end of the run, since we assume in our definition of $R$ that all tiles on the board have a smaller value. A formalisation of this for colour $A$ is the statement $\bigvee\_{i=0}^{w-2} (\text{Run}(i,w,A)\wedge R\[i-1,x,y,z\])$, where $\text{Run}(i,j,X)$ is true if and only if the tiles $x\_i,x\_{i+1},\ldots,x\_j$ form a valid run.

The other way to get a valid arrangement by adding some tiles is add a group of size $3$ or $4$ and make an arrangement on the remaining tiles. This can be formalised as $a\_w=b\_x=c\_y\ \wedge R\[w-1,x-1,y-1,z\]$ if we make a group of $3$, excluding the colour $D$ and as $a\_w=b\_x=c\_y=d\_z\ \wedge R\[w-1,x-1,y-1,z-1\]$ if we make a group of $4$.

As these are the only methods to construct valid arrangements, the following recursive formula holds:

$$ R\[w,x,y,z\] = \begin{cases}\bigvee\_{i=0}^{w-2} (\text{Run}(i,w,A)\wedge R\[i-1,x,y,z\])\\ \vee\bigvee\_{i=0}^{x-2} (\text{Run}(i,x,B)\wedge R\[w,i-1,y,z\])\\ \vee\bigvee\_{i=0}^{y-2} (\text{Run}(i,y,C)\wedge R\[w,x,i-1,z\])\\ \vee\bigvee\_{i=0}^{z-2} (\text{Run}(i,z,D)\wedge R\[w,x,y,i-1\])\\ \vee (a\_w=b\_x=c\_y\ \wedge R\[w-1,x-1,y-1,z\])\\ \vee (a\_w=b\_x=d\_z\ \wedge R\[w-1,x-1,y,z-1\])\\ \vee (a\_w=c\_y=d\_z\ \wedge R\[w-1,x,y-1,z-1\])\\ \vee (b\_x=c\_y=d\_z\ \wedge R\[w,x-1,y-1,z-1\])\\ \vee (a\_w=b\_x=c\_y=d\_z\ \wedge R\[w-1,x-1,y-1,z-1\])\\ \end{cases} $$

As the right-hand side of the formula only references $R$ with smaller indices than the left-hand side, we can use this formula to compute our result $R\[A,B,C,D\]$. To compute the result efficiently, we use dynamic programming, which gives an $O(ABCD(A+B+C+D))$ time algorithm if we pre-compute $\text{Run}$. Note that in this recurrence, we compute $\text{Run}(i,x,B)\wedge R\[w,i-1,y,z\]$ multiple time. We can change the recurrence to ensure this occurs only once while maintaining correctness, which leads to $O(1)$ time for every 'cell' in the DP-table, so we can compute our result in $O(ABCD)$ time. As usual with dynamic programming, we can get the actual solution by reading the DP-table or storing the decisions made while we construct the table.

---

Now, what happens when the values of our tiles are no longer unique? We get in trouble with constructing runs, as won't always use consecutive tiles to construct a run due to the adjacent duplicates. So, instead, we split a list for a single colour into multiple sub-lists such that the sub-lists have distinct tiles, order those sub-lists and merge them back into one list again. Now, we can try to use the recurrence as before, but now be careful to only use a single sub-list in every run.

However, we now get the problem that we no longer only have to remember whether prefixes of a sub-list have a valid run, but also for suffixes! (e.g. we can construct an arrangement with $1,2,3,4,5;3$ as we can append $3$ to $\\{1,2\\}$ and $\\{3,4,5\\}$ is valid, but not with $1,2,3,4;3$, as $\\{3,4\\}$ is invalid. So we must indeed check the suffix) Fortunately, we can also compute the validity of all suffixes of the first sub-list similarly to how we did with the prefixes.\*

So, our new algorithm, after splitting in sub-lists, is as follows: for every sub-list except the last, compute the validity of all prefixes and suffixes as before (possibly using the values from the previous sub-list). For the final sub-list, compute only the prefixes and find the answer. Since we 'only' compute parts of our list twice, the asymptotic running time stays $O(ABCD)$.

---

How can we handle jokers? As we may use a joker at any place in our arrangement, we add an additional index $j$ such that $R\[w,x,y,z,j\]$ indicates whether there is a valid arrangement for $R\[w,x,y,z\]$ using (exactly) $j$ jokers. The recursion remains the same if $j$ doesn't change, but now the right-hand side may contain $R\[w',x',y',z',j-1\]$ for some change that would be valid by using a joker (as we still either make runs or groups, this is similar to the cases already described). The final value is now at $R\[A,B,C,D,J\]$ and we can compute this value similar to above in $O(ABCDJ)$ time.

---

\*: You may wonder why we still can assume our new tile is at the end of a run. This is because if we would place our tile somewhere else, we can simply 'swap' with our earlier tile, which was placed at the end of a run.
> 3 votes

---
Tags: combinatorics, board-games
---


# Question
Title: How to find the minimal path cost from left edge of a grid to the right edge using dynamic programming?
> I need to find the minimal path cost from left edge of a $n\times n$ grid to the right edge where each node has some non-negative weight $cost(i,j)$. $i$ represents horizontal coordinates while $j$ represents vertical coordinates. Only the following movements are allowed in the grid: $$ (i,j)\to(i+1, j-1) \quad\text{aka diagonal down}\\ (i,j)\to(i+1, j) \quad\text{aka right}\\ (i,j)\to(i+1, j+1) \quad\text{aka diagonal up}\ $$ The algorithm must run in $\Theta(n^2)$ time and use dynamic programming.

I thought:

1) first to select the minimal cost node in the left-most column, that is find $min(cost(i, 1))$. Let the node be $s$ (start node).

2) Now we can use Bellman-Ford algorithm as described here (page 53) in order to find the minimal cost path from $s$ to any other node. The recurrence for Bellman-Ford would be: $$ opt(i,j) = cost(i,j) + min(opt(i+1,j-1),\\ opt(i+1, j),\\ opt(i+1,j+1)) $$

3) We'd get a $n\times n$ matrix in the end where the right-most column would represent the right-most edge of the grid. Therefore the minimal cost path from left edge to the right edge would be the minimal cost in the right column.

---

Is my logic on the right track? I'm really not sure regarding the steps 1) and 3). Also because Bellman-Ford calculates edges costs do I need to perform any reduction in this algorithm because costs are not stored on edges but rather on nodes?

# Answer
> 1 votes
You can solve this problem filling the following table.

Let's say that $cost(row,col)$ is the minimal cost that can be achieved starting from one node on the leftmost edge of the grid and ending in the cell $(row, col)$, only performing valid operations.

The answer to the problem will be the minimum among all $cost(i,j)$ where $j=last\\\_col$. Notice that table $cost$ table is the same as $opt$ table, but now you have the proper semantic of it's entries, so it's easy to fill base values, and extract final values.

* Step 1: Base values: Fill first column entries with there current value. i.e $cost(i,j)$ where $j=0$. It is $cost(i,0)=value(i,0)$ since the only way you can reach node $(i,0)$ starting in a leftmost node and performing valid operation, is starting in the node itself.
* Step 2: The same you described before. This holds, because you can only get nodes on the $j^{th}$ column from the $(j-1)^{th}$ column, and since you are filling $cost$ table in increasing order of columns, previous values will be computed when you need to compute current values. \[This is dynamic programming\]
* Step 3: As I said before, and you said too, return the minimal value among all entries in the last column of $cost$ table.

---

Why Bellman Ford (BF) works here in the way you do it.

BF algorithm finds shortest path in a graph from a single source to every other node inside the graph. In the $k^{th}$ step BF have already computed shortest path starting from source node $S$ to every other node using at most $k$ edges.

Let's transform our problem into a valid instance for BF, and the let's modify BF to run in $O(n^2)$.

Let's say we convert each cell of the grid into a node, and you put an edge between node $u$ and $v$ if the transition from $u$ and $v$ is valid. Let the cost of edge between $u-v$ be the original cost of the cell $v$, so moving through this edge adds to the overall cost getting into node $v$, as we expect.

Now we have two problems.

* Problem 1, the running time of our algorithm will be $O(nodes \cdot edges)$ where $nodes$ is $n^2$ and $edges$ is $O(nodes) = O(n^2)$ so overall complexity will be $O(n^4)$.
* Problem 2. There are several sources, so we need to run BF starting at every source, and this increase the overall complexity by a factor of $n$.

Let's get rid of both problems, starting from problem 2. If you add an extra node connected to every node at the first column, you simulate the process of starting at every node in one run. Look at the following image for more understanding. I didn't pain all connection but just a few.

To get rid of the first problem, you need to exploit the structure of our graph. It is not so general. You can only reach nodes in the $k^{th}$ column in the $k^{th}$ step, and since there is no backward edge, in this step only nodes in this column needs to be updated. So overall complexity will be $O(nodes) = O(n^2)$.

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


# Question
Title: Why do we need binary trees when we have multi branch trees?
Why do we need binary trees when we have multiway trees. Are binary trees even used. Are they used only for teaching the concepts of trees?

# Answer
> 1 votes
Yes, binary trees are used in standard libraries, implementing various data structures. For example, implementation of *ordered set* in the C++ STL library is typically based on red-black tree, which is a binary search tree of special kind.

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


# Question
Title: Is there no sorting algorithm with all specific desired properties?
On the Sorting Algorithms website, the following claim is made:

> The ideal sorting algorithm would have the following properties:
>
> * Stable: Equal keys aren't reordered.
> * Operates in place, requiring $O(1)$ extra space.
> * Worst-case $O(n\cdot\lg(n))$ key comparisons.
> * Worst-case $O(n)$ swaps.
> * Adaptive: Speeds up to $O(n)$ when data is nearly sorted or when there are few unique keys.
>
> There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.

My question is, is it true that

> there is no \[sorting\] algorithm that has all of these properties

and if so, why? What is it about these properties that makes all of them simultaneously impossible to fulfill?

# Answer
> 6 votes
WikiSort and GrailSort are two fairly recent algorithms that do in place, stable, worst case $O(n\ lg(n))$ key comparisons. Unfortunately I don't understand them well enough to know if they approach $O(n)$ swaps or are adaptive so I don't know whether they violate the fourth and fifth conditions you have.

From looking at the paper "Ratio based stable in-place merging", by Pok-Son Kim and Arne Kutzner linked to by the WikiSort GitHub page, Kim and Kutzner claim to have a 'merge' operation that is $O( m (\frac{n}{m} + 1))$ (WikiSort is a variant of Mergesort) but I'm not sure if that translates to WikiSort having $O(n)$ swaps. GrailSort is claimed to be faster (in the WikiSort GitHub page) so I could imagine that it's likely they both have worst case $O(n)$ swaps and are adaptive.

If anyone does manage to understand WikiSort and/or GrailSort I would appreciate them also answering my open question about it

# Answer
> 5 votes
Dijkstra's smoothsort comes close, but isn't stable.

# Answer
> 2 votes
No known algorithms satisfy all of these properties. These properties became sought after as we developed more sorting algorithms. For example, bubble sort (arguably the most primitive sorting algorithm), was most likely non-stable the in the first implementation, but was designed to be stable as computer scientists sought to make it more efficient in later implementations. So, computer scientists most likely picked the best traits from the best algorithms, and as a result, you have brought up a list of all of these desirable traits. In reality, it is difficult to have the best of all worlds in anything. Not impossible, but possibly impossible with our current architectures.

P.S. Use Big-O ($O$) as an asymptotic upper-bound, and Big-Omega ($\Omega$) as an asymptotic lower-bound. Theta ($\Theta$) for the in between.

# Answer
> 2 votes
(Even though this is an old question, I stumbled upon it and so might others.)

There indeed is an algorithm that satisfies (1) - (4) and the second half of (5), so comes very close to the above requirement. It is described in \[1\] and combines several tricks invented over the last decades.

\[1\]: Franceschini, G. Theory Comput Syst (2007) 40: 327. https://doi.org/10.1007/s00224-006-1311-1

---
Tags: algorithms, sorting
---


# Question
Title: Has this generalization of Turing machines studied before?
## Introduction

Hello, I'm designing a generalized model of Turing machines for a formalization in MIZAR. Mizar needs some concrete objects to work with, so I spent some time figuring out how the "tape" of a Turing machine could be defined since that part is usually left out when introducing Turing machines.
After some thinking I concluded it would be best to use graphs, so I define a "Turing Space" $T$ as a function from an cardinal $C$ to graphs. A position $p$ in the Turing Space is then defined as a function from the cardinal into the vertex sets of these graphs, so that for $c\in C$, $p.c$ is a vertex of $T.c$. From this basis one can built transition functions and so forth.

## Examples

Given a double ray (a path graph that is infinite in both directions) $R$ and a positive integer $k$, the function $f\_k:k\ni i\mapsto R$ (defined on $\\{0,\ldots,k-1\\}$) would be a Turing space describing the bands of a $k$-band TM.
Given a positive integer $d$, set $E\_d:=\\{\\{a,b\\}:a,b\in\mathbb{Z}^d,\sum|a\_i-b\_i|=1\\}$ and graph $G\_d=(\mathbb{Z}^d, E\_d)$, this is the grid on $\mathbb{Z}^d$. Now the function $g\_d:\\{0\\}\ni i\mapsto G\_d$ describes the hyperspace of a $d$-dimensional TM.
These two examples are of course quite different, as the first has $k$ pointers, that can move in 3 directions (left, right, stay) each, and the second has one pointer that can move in $2d+1$ directions. That they are nevertheless computational equivalent (because they are Turing-complete) is well known. Also both reduce to a simple Turing tape in case of $k=d=1$.
It is easy to see that other well-known tape variants can be described by this definition just as well.

## But it doesn't end there

However, the definition above allows much more complex examples for tapes, most notably when using infinite cardinals. And when I'm about defining Turing machines, I wonder why I would restrict the alphabet and set of states to be finite. Of course, these generalizations make it much more difficult to image any kind of realization in the real world. Nevertheless, I think it is kind of interesting if these generalizations of a TM would make it possible to archive something beyond Turing completeness. Other known generalizations such as non deterministic TMs and quantum TMs do not seem to have archived greater computability. Maybe I missed something?

## The Question

Has my kind of generalization (the different "Turing Spaces") been studied before? Or any kind of allowing infinite states and/or alphabets besides the kind appearing in quantum TMs?

# Answer
A general notion of machines based on graphs was given by Wilfried Sieg and John Byrnes in K-Graph Machines: Generalizing Turing's Machines and Arguments. It may or may not be related to what you are doing.

Also note that it is quite easy to find a complete formalization of Turing machines. Why are you saying that "the tape of a Turing machine ... is usually left out when introducing Turing machines". That's an odd thing to say. Let's perform an experiment. For instance, what is unclear about the definition given on Wikipedia (following a standard textbook)? All you need is a formalization of finite sequences, and I'd be flabbergasted if Mizar hasn't got those.
> 3 votes

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


title: Questions about Amdahl's law?

text:
# Question
Title: Questions about Amdahl's law?
Doing exam papers now and I came across two questions which I cannot get my head around sadly. Both are regarding Amdahl's law and Parallel Computing but they seem rather simple and frustratingly enough I cannot really find a definitive answer to any of those questions.

The questions are:

> Why must Amdahl's law always apply to a computation?
>
> Why is the existence of superlinear speedup not in contradiction with Amdahl?

---

The best description of Amdahl's law I found is this one:

> At the most basic level, Amdahl's Law is a way of showing that unless a program (or part of a program) is 100% efficient at using multiple CPU cores, you will receive less and less of a benefit by adding more cores. At a certain point - which can be mathematically calculated once you know the parallelization efficiency - you will receive better performance by using fewer cores that run at a higher frequency than using more cores that run at a lower frequency.

I just cannot find a suitable answer on why the law must be always applied to a computation. And **superlinear speedup** is just when a parallelised speedup can reach far beyond the speedup of a sequential processor. How would it actually contradict Amdahl's law I do not really know apart from it looking a bit like a glitch in the matrix.

# Answer
> 2 votes
1. Amdahl's law is used to get an idea about where to optimize while considering parallelism.The theory of doing computational work in parallel has some fundamental laws that place limits on the benefits one can derive from parallelizing a computation. Amdahl's Law have detalied explanation of Amdahl's law and it's use.
2. Processor comes with some other resources like cache which can affect the performance. So if we add more processor, cache memory also increases. Each processor will get less data size to process that can fit into processor's cache which will increase the Performance(Superlinear speedup). But Amdahl's Law considers processors as the only resource but does not consider cache memory.

---
Tags: parallel-computing, linear-programming, process-scheduling
---


# Question
Title: How does Server know window size for TCP Header?
I'm trying to understand TCP right now. In the header there is "Window Size" which to my understand is the maximum amount of data that can be sent at once. My question: How does the server know how much data it can send? If I understand it correctly, the only information the server gets from the client is the ACK number that says "Package Received". Or is there more? Do I miss something?

# Answer
The Window Size field in the TCP packet header is the number of bytes the sender will buffer for the response. Basically, during the handshake each side will say how large its receive window is. That is, the Window Size field in a packet sent by the *client*, tells the server how much data the *client* can receive and thus how much the server can send before the client would need to drop packets. Symmetrically for the packets the server sends to the client. See the flow control section for details on how the window size changes. Of course, see the relevant RFCs for the authoritative recommendations.

As far as how the initial receive window is calculated, this is based on local resources and policies. Clearly, the initial receive window shouldn't be set to be larger than the amount of buffer memory you have. For a specific connection, larger is better for throughput if packets aren't being dropped, but larger packets are more likely to be dropped and when they are dropped require more data to be resent. RFC3390 presents a recommendation for what the initial receive window size should be assuming local resource limitations aren't a concern. This link describes what the Linux 2.6 kernel did (at least for RedHat distributions), though it may be out of date.

There is a different thing called the congestion window which each host may maintain itself as an estimate for how much data it can reliably send. This isn't communicated since it's unlikely there's anything the receiving end can do about it as it may well be intermediate nodes in the network that are limiting the rate. Again, this is an estimate and many variations of TCP are due to different strategies to estimate this value. Hosts don't have to agree on these congestion control algorithms for TCP to work.
> 5 votes

---
Tags: computer-networks
---


title: Is this graph algorithm more efficient?

text:
# Question
Title: Is this graph algorithm more efficient?
Suppose we are given a digraph A. We need to calculate its connectivity digraph B.

I conceived two algorithms:

1.

* Set X = A.
* Loop
* Set Y = X\*A united with identity
* Stop the loop if Y = X
* Set X = Y
* End loop
* B = X

2.

* Set X = A. \[Or instead "X = A united with identity" and remove "united with identity" in the third step?\]
* Loop
* Set Y = X\*X united with identity \[or should it be Y = (X united with identity)\*(X united with identity)?\]
* Stop the loop if Y = X
* Set X = Y
* End loop
* B = X

I think that the algorithms are equivalent but the second one is faster.

Are they really calculating connectivity and are really equivalent?

Is the second algorithm faster not only for incidence matrix representation but also for hash-map or like this representation of digraphs?

Is there an even more efficient algorithm?

# Answer
You are asking a lot of questions. Let me answer some of them.

Let us denote the contents of the Boolean matrix $X$ after $t$ iterations by $X^{(t)}$. The first algorithm uses the recurrence $$ \begin{align\*} &X^{(0)}(i,j) = A(i,j), \\ &X^{(t+1)}(i,j) = X^{(t)}(i,j) \lor \bigvee\_k \bigl(X^{(t)}(i,k) \land A(k,j)\bigr). \end{align\*} $$ You can prove by induction that $X^{(t)}(i,j)$ is true iff there is a directed path from $i$ to $j$ of length at most $t+1$.

The second algorithm uses the recurrence $$ \begin{align\*} &X^{(0)}(i,j) = A(i,j), \\ &X^{(t+1)}(i,j) = X^{(t)}(i,j) \lor \bigvee\_k \bigl(X^{(t)}(i,k) \land X^{(t)}(k,j)\bigr). \end{align\*} $$ You can prove by induction that $X^{(t)}(i,j)$ is true iff there is a directed path from $i$ to $j$ of length at most $2^t$.

Since $2^t$ grows much faster than $t+1$, the second algorithm will use less iterations. The worst case number of iterations in the first algorithm is $n$, whereas in the second algorithm this goes down to $O(\log n)$.
> 2 votes

---
Tags: algorithms, graphs, efficiency
---


# Question
Title: How would i go about calculating the Big Theta of the following nested loop?
```
for i = 0 ... log(n) - 1
    for j = 2^i + 1 ... 2^(i + 1)
         [code with Big-Theta(1) running time]

```

Given this piece of code the outer loop runs log(n) times. But I'm confused as to how to try to calculate the running time of the second loop so as to multiply them. Thank you for reading.

# Answer
Each internal loop does $2^i$ iterations of $\Theta(1)$ so it takes $\Theta(2^i)$. Therefore the time complexity of the code is the $\Theta(\Sigma\_{i=0}^{log(n)} 2^i)=\Theta(n)$.

You could intuitively think of summation here as writing in binary base a number where all its digits are 1, and has the same number of digits as n, it is linear to the size of n.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Is this the correct time complexity of my algorithm?
I have an algorithm broken down into the pseudish code below. But the gist of it is, we go through every person in a list, we then ask them to talk to all of their friends. Every time we choose a person to eval in the list, it costs $log N$ time. Every time that person talks to a friend it costs $log N$. What is the time complexity? Is my answer right?

My answer: $O(N \cdot log(E \cdot log(N)))$

```
List[People] // N

forall People in List:  //O(Log N) to get a person in list
   forall friends of Person:    // Person has a set of Friends E that is [0, N)
       Person.talkToFriend(friend)  //Costs O[LogN] to talk to a friend

```

# Answer
> 1 votes
For each of the n people in the list you do $|E|\cdot log(n)$ plus the time of getting it from the list, which is $log(n)$. So the time you start with is complexity: $O(n(log(n)+(log(n)|\cdot|E|)))=O(n\cdot|E|\cdot log(n))$

Assuming E could be as big as n, you could simply say the time complexity is $O(log(n)\cdot n^2)$.

---
Tags: time-complexity
---


# Question
Title: How to get Loop invariants to prove program is correct in Hoare logic
start off stating the definition of a loop invariant. It is a condition that must be true at the start of the loop and must be true after each iteration of the loop. I understand what it is but i have trouble trying to come up with one.

Here below is a program which i know is correct and I have stated the loop invariant. Could someone please go through explaining simply why this is the loop invariant. I've been looking at it for awhile now but cannot see why the loop invariant is what it is. I am very new to Hoare logic.

```
{N >=0}//Pre condition

x = 1;

i = 0;

{x == A^i}//Invariant

while (i != N)

{x == A^i || i != N}//Invariant and Guard

x = x * A;

i = i + 1;

{x == A^i} //invariant

{x == A^i    ||    i==N}// Invariant and !Guard

{x == A^N}//Post condition

```

# Answer
By definition, an invariant of `while guard do c` is a property `I` for which `{I && guard} c {I}` is a valid Hoare triple.

In your case, it is enough to prove the validity of what you wrote in the body, namely

```
{x == A^i && i != N}//Invariant and Guard
x = x * A;
i = i + 1;
{x == A^i} //invariant

```

This can be done using the rules for assignment and composition. Usually, it's best to proceed backwards, from the bottom of the code block, recovering the (weakest) precondition in the process.

```
{x == A^i && i != N}
{x*A == A^(i+1)}
x = x * A;
{x == A^(i+1)}
i = i + 1;
{x == A^i}

```

We now get two Hoare assertions one after the other at the top. This means that we proved the validity of

```
{x*A == A^(i+1)}
x = x * A;
i = i + 1;
{x == A^i}

```

when we actually need instead

```
{x == A^i && i != N}
x = x * A;
i = i + 1;
{x == A^i}

```

For that, we can exploit the weakening rule (AKA "Pre-" or "PrePost" rule). Such rules simply states that we need to prove the implication between the topmost assertion and the other one. Concretely, we need to prove the implication

```
(x == A^i && i != N)
   ==>
(x*A == A^(i+1))

```

which trivially follows by arithmetic.
> 0 votes

---
Tags: loops, loop-invariants, hoare-logic
---


# Question
Title: Is graph search of shortest (optimal) path an instance of optimisation?
* I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm.
* I am not too familiar with graphs / trees and their search.
* But it does seem like all possible solutions can be represented as a graph and a graph search algorithm can then be used to explore the space and determine the "shortest" (or could be some other criterion) path. It seems that this is what Breadth First Searcha and Dijkatra algorithm are doing. Is this correct? Is tree search actually linked to a more general concept of optimisation?

# Answer
> 2 votes
Although I'm not sure what you're calling 'optimisation', I can tell you that both Dijkstra's algorithm and BFS are not some form of searching a solution space. If they were, they would start with an initial solution, i.e. some path from A to B, and eventually find the shortest path between A and B after considering multiple such paths. But this is not the case, as these algorithms both construct partial solutions before eventually getting a complete solution.

On other hand, it is true that locally, the distance to some node is at first estimated by some path and possibly later improved, so there is some similarity here. However, the incremental approach to a solution is an important aspect in these algorithms, which doesn't occur in gradient-based optimisation, as these cases usually don't even have a concept of a partial solution which can be extended into a full solution.

---
Tags: optimization, trees, search
---


# Question
Title: Is it possible to prove Turing irreducibility
Given two languages $L\_1$ and $L\_2$, is there a known way to show that $L\_1\not\leq\_T L\_2$?

In other words, is it possible proving that there is no Turing reduction from $L\_1$ to $L\_2$?

# Answer
Let $A\_{TM}$ be the language of the Halting problem. Then $\overline{A\_{TM}} \nleq\_T A\_{TM}$, otherwise $A\_{TM }$ would be recursive.

Another well-known theorem by Friedberg–Muchnik proves (using the finite injury priority argument) that there are recursively enumerable languages $A$ and $B$ such that $A \nleq\_T B$ and $B \nleq\_T A$ (pairwise incomparable).

R. Soare's book, for example, has more on this subject.
> 4 votes

# Answer
Yes, in some cases it is possible to prove that a set does not Turing-reduce to another.

For instance, if $L\_2$ is recursive, and $L\_1$ is not, then surely we can not have $L\_1 \leq\_T L\_2$. (This does not generalize to r.e. sets, unlike for $\leq\_m$-reduction).
> 2 votes

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


# Question
Title: Is there any language for which $\overline{L^*}=\big(\overline L\big)^*$?
This question was asked in peter linz exercise. I have tried languages such as $\phi,\epsilon,\Sigma^\*$.

# Answer
No, thanks for Ariel's correction, since for every $L$ it holds that $\epsilon \not\in \overline{(L^\*)}$ and $\epsilon \in (\overline{L})^\*$ and therefore $ \overline{(L^\*)}\neq (\overline{L})^\*$
> 3 votes

---
Tags: formal-languages
---


# Question
Title: How to prove that a custom iterative algorithm will determine all shortest paths to a graph node?
I'm not sure what the following algorithm does but it seems that it calculates the shortest paths from a node $t$.

Initially we're given a graph $G=(V,E)$ with non-negative weights $c(e) \ge0$ for each edge $e\in E$ and we're given a node $t\in V$.

The algorithm is as follows:

> Initialize array $A$ such that $A\[v\] = 0$ if $v=t$ else $A\[v\]=\infty$.
>
> Outer loop which is repeated continually
>
> $\quad$ Inner loop: we scan all edges in lexicographical order and for every $e=(u,v)\in E$ we $\quad$ do the following:
>
> $\qquad$ if $A\[v\] \>A\[u\]+c(e)$ then $A\[v\] =A\[u\]+c(e)$
>
> $\quad$ if no updates were performed in the inner loop the algorithm exits.

I need to prove by induction what the algorithm does. For example for the following graph below and if $s=b$ the initialization of $A$ will be as follows:

Then the first run of the inner loop would be:

1) $A\[1\]$ is not bigger than $A\[0\]$ so we do nothing

2) $A\[2\]$ is bigger than $A\[1\]$ so $A\[2\]=2$

3) $A\[3\]$ is bigger than $A\[2\]$ so $A\[3\]=5$

The next time the inner loop will not make any updates because all the reachable nodes were already updated.

I'm not really sure if I understood correctly what the algorithm does and how to prove this inductively.

How does the fact that the algorithm checks nodes in lexicographical order come into play?

# Answer
You can prove by induction that for every iteration $i$, the array $A$ during this iteration, $A\_i$, contains the weights of some paths originating at $t$. More formally, for all $v\in V$, $A\_i\[v\]$ is either $\infty$ or the weight of some path from $t$ to $v$.

Now, it is easy to show that the values of $A\_i$ are monotonically non increasing, which combined with the above statement implies that the algorithm terminates. I leave the details to you.
> 1 votes

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


# Question
Title: How to proof UNIQUE-SAT is in $\Delta^p_2$
How to proof UNIQUE-SAT is in $\Delta^p\_2$ or in $P^{sat}$

1) when given a bool formula can I ask oracle whether the given formula has at least one satisfying truth assignment and whether it has at least two?

2) Is UNIQUE-SAT in NP?

# Answer
> 2 votes
UNIQUE-SAT is complete for the complexity class US. It is not hard to reduce coSAT to UNIQUE-SAT (by adding a trivial satisfying assignment), and so if UNIQUE-SAT is in NP, it would imply that NP=coNP, which is considered unlikely. There is a randomized reduction from SAT to UNIQUE-SAT, which implies that UNIQUE-SAT∉P unless NP=RP.

A SAT oracle can only answer one type of question: is the given formula satisfiable or not. However, you can use it to answer other questions. For example, in order to determine whether there are at least two satisfying assignments for some formula $\varphi$, you can ask whether the following formula is satisfiable: $\varphi(x) \land \varphi(y) \land x \neq y$ (you can convert this into CNF).

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