# Question
Title: Explaining the difference between computer science and computer literacy
What is a good metaphor or example to explain to an English major the difference between classical computer science and "being good with using MS-Windows"

* computer science
* computer programming
* using computers

3 profoundly different things. Most people have no idea what Computer Science even is. They just see the word "computer". Hence, "he is a Computer Science major" can be interpreted as "He can hook up my printer". Or that he's "good with computers". Even fewer people know the difference between computer programming and Computer Science.

Computer Science is computing theory. CS can be learned without actual computers. CPU micro architecture. How to sort numbers, how to traverse lists, etc. State machines. Algorithms, big(Oh), etc. How to design a programming language or compiler.

Programming is writing code and creating applications in a language and compiler created by a computer scientist.

Lastly, there is using a computer (using a GUI, mouse, and keyboard. Internet, MS-Office, etc)

Yet all three of these are used interchangeably by laymen.

What is a good metaphor or example to explain to an English major the difference between classical computer science and "being good with using MS-Windows" Or simply, a pithy example of how real computer science has nothing to do with using MS-Windows.

# Answer
How about an automotive analogy?

* uses computers and maybe "is good with computers" :: a driver (can drive and refuel safely) and maybe a car enthusiast (can jump start a car; is familiar with many makes and models; knows techniques like using windshield treatment to keep rain from reducing visibility).
* programmer :: an automotive mechanic or technician. Knows how cars work. Can repair and modify cars and even build kit cars. *Ought to know* how to debug/diagnose problems by using the scientific method. Might not be aware of relevant theory and thus might write O(n2) loops.
* software engineer :: an automotive engineer. Designs cars, engines, and other components that you can entrust your life with, and does it within schedule, cost, manufacturability, and other constraints. Knows how to apply the relevant theory/math such as finite element analysis.
* computer scientist :: an automotive scientist. Researches new ideas in vehicles, human-machine interfaces, and propulsion. Does computational crash test modeling. Adds to the body of theory and experimental results.

So for people who equate all “computing” with “proficient in using some software package,” that's like equating driving proficiency with the ability to design antilock brakes that we trust lives to, that are manufacturable with consistent high quality and low cost, and work for years in extreme weather. Or equating driving proficiency with researching what kind of radar-triggered braking features will avoid collisions without freaking the driver into swerving into another lane.

Perhaps lay people confuse these terms because "computer science" classes teach computer use skills, programming, theory, or engineering. All that stuff (arguably not the first part) fits in the curriculum of computer science. None of it is the end-all "content" of computer science, just as English classes are learning on the way to an English major (a fuzzier concept).
> 29 votes

# Answer
Since it is an english major:

Computer literacy is like reading, computer programming like composition, and computer science like linguistics. All 3 are about language, but the skills are not exactly interchangable.
> 25 votes

# Answer
Somebody put it to me this way but I'm afraid I've forgotten who.

> Disinfecting your kitchen isn't microbiology; operating your computer isn't computer science.
> 11 votes

# Answer
> Computer science is to computers as astronomy is to telescopes.
>
> — Edsgar Dijkstra

I read this in some book but unfortunately I forgot which book.
> 8 votes

# Answer
I work with some "real engineers", a lot of them seem to think computer programming and CS are the same thing (apparently they think engineers do really high level math as well, different topic there). I used to be a CAD drafter back in high school so, I tell them I am basically a mechanical engineer, seems to even the playing field . I guess you could tell your English major friend you can read books already so, you might as well have an English major. Or in a less confrontational way let them know that would be the equivalent of what they are saying.
> 2 votes

# Answer
Hmm, here's another metaphor: Google search

1. Computer Scientist designs the Google PageRank algorithm.
2. Programmer knows how to take keyword input, access the database and display the results on a webpage.
3. User knows how to do a Google search.

Yea!!
> 1 votes

# Answer
I miss a fourth bullet, "computer engineering".

An engineer knows how things work. A scientist knows why things work. A builder makes things (that sometimes work). A user uses things.

For "thing" read house, computer, car, ... For "builder" substitute suitable name for manual labor professional, e.g. "programmer" when thing = computer, "mason" when thing = house, etc.
> 1 votes

# Answer
I just now found another quote, again by Edsger Dijkstra (from here):

> ...the harm was done: the topic became known as “computer science”---which, actually, is like referring to surgery as “knife science” --- and it was firmly implanted in people's minds that computing science is about machines and their peripheral equipment.

You can shorten it to

> Computer science is like referring to surgery as “knife science”.

But you don't even need to say that. It think it would be enough to say that "CS is a kind of math that has nothing to do with computers".
> 0 votes

# Answer
Computer science is the knowledge of what computers can do so that you can use them.

Computer literacy the knowledge of what you can do with computers so that they can use you.
> 0 votes

---
Tags: terminology, education
---


# Question
Title: solving recurrence by substitution, calculations doesnt add up
I have this recurrence $p(n) = 2p(n-2) + n$, and I have guessed that the solution is $O(n^2)$, however, when I do the following calculations, I cannot get the inequality to hold

$p(n-2) \leq c(n-2)^2$ (induction hypothesis)

$2c(n-2)^2 + n \leq cn^2$ (substitution)

$cn^2-8c + n \leq cn^2$

Can anyone see where I go wrong? I also tried for even larger $O(n^x)$ but it still doesn't work.

# Answer
Using the so-called substitution method, we get (for even $n$) $$ \begin{align\*} p(n) &= 2p(n-2) + n \\ &= 4p(n-4) + 2(n-2) + n \\ &= 8p(n-6) + 4(n-4) + 2(n-2) +n \\ &= \cdots \\ &= 2^{n/2} p(0) + 2^{n/2-1} 2 + 2^{n/2-2} 4 + \cdots + 2^0 n. \end{align\*} $$ Let's assume for simplicity that $p(0) = 0$. We can write $$ p(n) = \sum\_{k=0}^{n/2-1} 2^k (n-2k) = 2^{n/2+2} - n - 4 = \Theta(2^{n/2}). $$ (Solution courtesy of Wolfram alpha.)
> 2 votes

# Answer
It isn't $O(n^2)$.

Hint: $p(1)=1,p(2)=2, p(n)=p(n−2)+n$ is $O(n^2)$, but notice in what way your recurrence relation is different from this one. Try expanding it (yours). And it isn't $O(n^c)$ for some constant $c$.
> 2 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Why is the set of NFA that accept all words in co-NPSPACE?
In Sipser's book there is a section describing how to decide

$\qquad\displaystyle \mathrm{ALL}\_\mathrm{NFA} = \\{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^\*\\}$

in polynomial space. To do so, it shows $\overline{\mathrm{ALL}\_\mathrm{NFA} }$ is in NPSPACE.

I don't understand this part: If $M$, the NTM deciding the language, rejects any strings, it must reject one of length at most $ 2^q $ where $q$ is the number of states in $M$. For any longer string that is rejected, some states would repeat. But why? Is there any alternative explanation that helps in understanding this part?

# Answer
> 5 votes
Your question is really about the following statement: *If an NFA with $n$ states does not accept every string, then it rejects some string of length at most $2^n$*. (The rest of the proof comes from the fact that REACH is in NL.)

To see why this is so, first let's look at a DFA with $k$ states that does not accept every string. The transition function of the DFA corresponds to a directed graph $G$ on $k$ vertices. DFA computations bijectively correspond to walks in $G$ starting from the vertex $s$ representing the start state.

Since the DFA does not accept every string, there is a vertex representing a non-accepting state $j$ reachable by a walk from $s$. In particular, there is a simple path $P$ from $s$ to $j$, which can have length at most $k$ (e.g., DFS will produce one). $P$ corresponds to a string of length at most $k$ that is not accepted.

The NFA question reduces to the DFA one. Using the powerset construction, convert the NFA with $n$ states to a DFA with $k = 2^n$ states and then use the above argument.

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Which NP-Complete problem has the fastest known algorithm?
In terms of worst-case asymptotic runtime, which NP-complete problem has the fastest-known (exact) algorithm and what is the algorithm? Is there something known that is faster than $O(n^2\*2^n)$?

# Answer
Vertex Cover has an algorithm running in time $1.2738^k + nk$, and is thus faster than $2^n n^2$, even with $k=n$. You can check out Table of FPT races for a short list of FPT running times of different problems. Here, $n$ is the number of vertices and $k$ is the solution size.

Also, the question Are there subexponential-time algorithms for NP-complete problems? addresses similar questions.
> 19 votes

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


# Question
Title: Placing 1d items in a 2d grid with constraints
I'M looking for an algorithm (preferably polynomial) for the following problem:

Input:
\- an M x N grid, where each square can be either empty or occupied
\- a list of items
\- a list of constraints

Output:
the grid, such that all items are placed and the constraints aren't violated.

Each item is a 1d block of length k. Different items may have different length, and there may be several items with the same length. Items can't ovelap each other.

Example 1: Given 1 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:

11100

10110

11010

and so forth.

Example 2: Given 3 x 5 grid and 2 items of lengths 1, 2 respectively. The following solutions are acceptable:

00110
10000
00000

11000
10000
00000

etc.

Possible constraints:
a. Isolation - items may not touch each other. e.g. the following solutions is illegal:

Example 1:

11100

Example 2:

11000
10000
00000

However this is a legal solution:

01100
10000
00000

i.e. touching diagonals are legal.

b. Facing - 2 items must be placed one in front of the other. e.g.

11000
00000
11000

What I did so far is to find a solution for a simpler problem, where the grid is 1d and the only possible constraint is Isolation. I solved it by representing it as a search problem, and using A\* with the heuristic: sum of lengths of items not placed yet. The problem is that it suffers from state explosion which will only deteriorate in higher dimensions.

# Answer
> 1 votes
The 1-dimensional case (a $1 \times n$ grid) is straightforward. I'm not sure why you are having difficulty finding solutions when the grid is 1-dimensional. If you don't have any constraints, then you just add up the lengths of the items; if their total length is $\le n$, you can solve it (just put the items next to each other), otherwise you can't. To deal with the isolation constraint, you can note that the problem with tiles lengths $\ell\_1,\dots,\ell\_k$ and an isolation constraint is solvable if and only if the problem with tile lengths $\ell\_1+1,\dots,\ell\_{k-1}+1,\ell\_k$ and no isolation constraint is solvable.

The 2-dimensional case (a $m \times n$ grid) looks much harder. One approach, in practice, might be to use a SAT solver. Introduce boolean variables $x\_{i,j,k,d}$ and $y\_{i,j}$, with the intent that $x\_{i,j,k,d}=1$ if the $k$th tile starts at location $(i,j)$ on the grid and proceeds in direction $d$, and $y\_{i,j}=1$ if location $(i,j)$ is covered by some tile. Now you can formulate your problem as a set of boolean constraints on the $x$'s and $y$'s, then feed it to an off-the-shelf SAT solver. You could experiment with this for the parameter sizes that tend to crop up for you in practice and see how well it works. SAT solvers often work surprisingly well, though there is no guarantee: they are not a silver bullet, and the worst-case running time will remain exponential. There are many other ways to represent this as a SAT problem, too, so you could try other representations as well to see which tends to work best with existing SAT solvers.

I'm not sure you're going to be able to do much better than this: as FrankW says, for 2-dimensional grids this smells like it might be NP-complete in the general case.

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


# Question
Title: Do Higher Order Functions provide more power to Functional Programming?
*I've asked a similar question on cstheory.SE.*

According to this answer on Stackoverflow there is an algorithm that on a non-lazy pure functional programming language has an $\Omega(n \log n)$ complexity, while the same algorithm in imperative programming is $\Omega(n)$. Adding lazyness to the FP language would make the algorithm $\Omega(n)$.

Is there any equivalent relationship comparing a FP language with and without Higher Order Functions? Is it still Turing Complete? If it is, does the lack of Higher Order on FP makes the language less "powerful" or efficient?

# Answer
In a functional programming language that is powerful enough (for example, with data types to implement closures) you can eliminate all uses of higher order by the transformation of defunctionalization. Since this method is used to compile this kind of language, you can reasonably assume that this does not affect performances and that *in this setting* higher order does not make the language any less powerful. However it does affect how to write code.

However if the language is not powerful enough, then yes, higher order does provide expressive power. Consider the lambda-calculus: without any higher-order function, it really can't do anything, mostly because the most basic data types (integers, booleans) are implemented using functions.

In conclusion, it really depends on the language.

---

Above is my answer. Below, a comment about a usual assumption on imperative languages.

> about an algorithm that on a non-lazy functional programming language has an $\Omega(n \log n)$ complexity, while the same algorithm in imperative programming is $\Omega(n)$. Adding lazyness to the FP language would make the algorithm $\Omega(n)$.

I would like to see this reference. The usual assumption is that an access to a array of length $n$ in a RAM is in time $O(1)$ and the equivalent in pure FP is in in time $O(\log n)$. That is not entirely true: the access time in a RAM is in $O(\log m)$ where $m$ is the size of the memory. Of course, $m≥n$. In practice accessing an element of an array is much faster. A reason would be that $m$ is bounded but... so is $n$!

EDIT: thank you for the link (the link for the paper about laziness is not available, here is another one). As posted in the comments and above in my answer, the model of RAM is a little unfair to pure FP by providing $O(1)$-time look-ups even when the size of one address is not bounded. I am yet to understand how the lazy trick works but I think it is important to note that this is only for this particular problem.
> 11 votes

# Answer
It depends on what you mean by expressiveness.

Here is an argument that higher-order does add something: with first-order languages, primitive recursion is not enough to express the Ackermann function. However, in the presence of higher-order functions, primitive recursion is enough:

$$ \begin{array}{lcl} \textit{Ackermann} \ 0 & = & \lambda x. x+1 \\ \textit{Ackermann} \ ( m+1 ) & = & \textit{Iter}\ ( \textit{Ackermann}\ m ) \\ \textit{Iter}\ f\ 0 & = & f\ 1 \\ \textit{Iter}\ f\ ( n+1 ) & = & f\ ( \textit{Iter}\ f\ n ) \end{array} $$

This defines the Ackermann function using primitive recursion only.

Note that $ \textit{Iter}$ is not definable in conventional recursion theory, because $\textit{Iter}$ is higher order. In conventional recursion theory all definable functions have type $\mathbb{N}^k \rightarrow \mathbb{N}$ for some $k$, while $\textit{Iter}$ has type $(\mathbb{N} \rightarrow \mathbb{N}) \rightarrow (\mathbb{N} \rightarrow \mathbb{N})$.
> 4 votes

---
Tags: complexity-theory, lambda-calculus, functional-programming, turing-completeness
---


title: Reducibility in Computability Theory

text:
# Question
Title: Reducibility in Computability Theory
In Sipser's book of Theory of Computation, related to Reducibility, it's written

> if A is undecidable and reducible to B, B is undecidable.

The confusion is, only a solution to B determines a solution to A, if i'm not wrong. So, for instance if B is decidable and A is undecidable, what does it mean? Here B isn't undecidable.

Hope you got it.

# Answer
Suppose $A$ is undecidable and reducible to $B$. Given an algorithm for $B$, you can use the reduction from $A$ to $B$ to get an algorithm for $A$, which we assumed is impossible. Therefore $B$ must be undecidable.

If $A$ is undecidable and reducible to $B$ and $B$ is decidable then we obtain a contradiction and everything goes. Pigs can fly.
> 3 votes

---
Tags: computability, reductions
---


# Question
Title: Relationship between graph expansion and conductance
I'm quite confused about the exact relationship between the expansion of a graph and its conductance. My first question is:

* Could someone point me to a reference that discusses *both* of these notions? (I've found various lecture notes on related topics but these seem to focus either on expansion *or* on conductance...)

I've read that the expansion of $G$ is a measure for the speed of mixing of a random walk on $G$, i.e., the time for getting close to the stationary distribution. For a $d$-regular graph with constant expansion, for example, the mixing time is $\Theta(\log n)$. The same seems to be true for the conductance $\Phi(G)$, i.e., if $\Phi(G)$ is constant, then a random walk on $G$ will also mix in $\Theta(\log n)$ time. Moreover, this property of conductance holds even in non-regular graphs, and, for $d$-regular graphs the expansion of $G$ can be found by simply dividing the conductance of $G$ by $d$. This begs the following question:

* Why should we consider the expansion of a graph $G$, when the conductance seems to be a stronger measure (that subsumes expansion)?

# Answer
There are several different definitions for the expansion of a graph, but all of them are spatial. One common definition defined the expansion $h(G)$ of a graph $G$ as $$ h(G) = \min\_{|S| \leq |G|/2} \frac{|\partial S|}{|S|}, $$ where $S$ is a set of vertices containing at most half of the vertices, and $\partial S$ is the *(edge) boundary* of $S$, the number of edges connecting $S$ to $\overline{S}$. For a $d$-regular connected graph, there is a strong connection between $h(G)$ and a spectral parameter, the *eigenvalue gap* $\lambda(G)$, which is the smallest non-zero eigenvalue of the Laplacian. For a $d$-regular connected graph, *Cheeger's inequality* states that $$ \frac{\lambda(G)}{2} \leq h(G) \leq \sqrt{2d\lambda(G)}. $$ This is often put in terms of the second largest eigenvalue $\lambda\_2(G)$ of the adjacency matrix of $G$, which satisfies $\lambda\_2(G) = d - \lambda(G)$. There must be versions of Cheeger's inequality for non-regular graphs, and I'll let you look them up.

A lot of information on expander graphs can be found in the survey (based on course notes) Expander graphs and their applications by Hoori, Linial and Wigderson. Other information is scattered among lecture notes and even recent papers.
> 4 votes

---
Tags: graphs, reference-request, combinatorics, expanders
---


# Question
Title: Is $a^n b^m$ never regular if n and m have some relation between them?
I know what regular and context free language are and how regular language needs finite memory and other stuff.

What concerns me is that I think if $a^nb^m$ such that $n$ and $m$ have some relation between them then they can not be regular. But I can't find any such thing written anywhere. Am I correct to state so?

# Answer
> 5 votes
For a relation $R(n,m)$, let $L\_R = \\{ a^n b^m : R(n,m) \\}$. Call a relation *residual* if for some $k \geq 1$ and for some $A \subseteq \[k\]^2$, $$ R(n,m) \Leftrightarrow (n,m) \pmod{k} \in A. $$ Call a relation *semi-residual* if it differs from a residual relation by a finite number of points.

**Claim:** $L\_R$ is regular iff $R$ is semi-residual.

**Proof:** It is not hard to check that if $R$ is semi-residual then $L\_R$ is regular. For the other direction, consider an automaton for $L\_R$. For each state $\sigma$, let $L\_\sigma$ be the set of all $n$ such that upon reading $a^n$, the automaton reaches $\sigma$. Since $L\_\sigma$ is unary, it is eventually periodic. By taking the least common multiple of all periods, we see that the state that for $n \geq n\_0$, the automaton find itself upon reading $a^n$ depends only on $n\pmod{k\_a}$ from some $k\_a$. Doing the same for $b^m$, we see that for $n \in L\_\sigma$, the set of all $m$ such that $a^n b^m \in L$ is eventually periodic, and so for $m \geq m\_0$, depends only on $\sigma$ and on $m\pmod{k\_b}$ for some $k\_b$. Taking $k$ to be the LCM of $k\_a,k\_b$, we find that for $n \geq n\_0, m \geq m\_0$, $a^n b^m \in L$ depends only on $(n,m) \pmod{k}$. Hence the corresponding $R$ is semi-residual.

# Answer
> 4 votes
Let $L = \\{ a, b \in \Sigma \mid a^nb^m, R(n,m) \\}$. This language *may* be regular: if for example $R = \mathbb{N} \times \mathbb{N}$, then $L = a^\*b^\*$. So you can't say whether $L$ is regular or not without knowing something about $R$.

There *are* languages with a relation $R$ that are not regular; for example $L = a^nb^n$.

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


# Question
Title: Writing programs with a block programming environment vs. Writing programs using high level prgramming language
I'm a GCSE Computing student and I've been asked to compare writing programs in a block programming environment (I think this means using programs such as Scratch or App Inventor but I'm not entirely sure) compared to writing programs using high level programming languages such as Python, Java etc. I'm honestly not trying to ask you to do my work for me, I just desperately need some help on the advantages and disadvantages of both ways of writing programs because we haven't really been taught it by my teacher and I haven't found much on the Internet about it.

# Answer
> 1 votes
Scratch is a Turing-complete language, so any problem that can be solved with computers can be solved using Scratch (just like Python or Java). However, you would have to reduce the problem to one that can be solved with Scratch.

In application, Scratch can't do anything that you may be interested in as an engineer, such as hardware interfacing.

# Answer
> -2 votes
I'm doing the same course right now and I'm having the same problem but i do know that block programming languages like app inventor are easier to use because you don't need to (effectively) learn a completley new language and the syntax that goes with it all you need to learn is what task the blocks perform and how they fit together.

---
Tags: programming-languages
---


# Question
Title: Should we not reuse constants in tableaux proofs?
I am trying to understand the proof of the following using tableaux: $$ \exists x\forall y.r(x,y) \to \forall x \exists y . r(x,y) $$

This is how it works out: $$ (1) \space \exists x \forall y .r(x,y) \\ (2) \space \lnot(\forall x \exists y . r(x,y)) \\ | \\ (3) \space \forall y.r(a,y) \\ (4) \space \lnot \exists y.r(b,y) \\ (5) \space r(a,a) \\ (6) \space r(a,b) \\ (7) \lnot r(b,a) \\ (8) \lnot r(b,b) $$

I understand that (4) is derived from (2). However, shouldn't that be $$ \lnot \exists y.r(a,y) $$ reusing the constant a which was introduced by (3)? This is because we are expanding the quantifier: $$ \lnot(\forall ...) $$

Can anyone explain?

# Answer
> 2 votes
On the contrary, you never want to reuse constants. Each time you witness an existential quantifier, you should use a different constant. For example, consider the following two sentences:

1. Some integer is even.
2. Some integer is odd.

You wouldn't want to instantiate them with the same variable.

---
Tags: logic, proof-techniques, first-order-logic
---


title: Recurrence doesn't add up

text:
# Question
Title: Recurrence doesn't add up
I made a recurrence tree and guessed that solution to $T(n)=2T(n-2)+n$ is $O(2^{n/2})$ and I am now trying to prove this through substitution. These are my steps so far, but I can't get it to pass for some reason:

\begin{align} T(n-2) &\leq c2^{(n-2)/2}\\ T(n) &= 2(c2^{(n-2)/2})+n\\ &\leq c2^{n/2} \quad (?) \end{align}

But as far as I see, it can never add up, because it will always be greater than the $+n$ term and times $2$. Any help will be much appreciated.

# Answer
> 1 votes
The hints you've been given almost work. The important idea is that your guess, $T(n)≤c2^{n/2}$, while correct, doesn't behave nicely in your induction proof, as you noted. What's the problem? Clearly, it's that "$+n$" term in the recurrence, so let's try to make it work by choosing a better guess: $$ T(n)≤c2^{n/2}−kn \quad\text{for some suitable } k $$

With this guess, we'll have $$\begin{align} T(n)&=2T(n−2)+n\\ &\le 2(c2^{(n−2)/2}−k(n−2))+n\\ &=c2^{n/2}−2k(n−2)+n\\ &=c2^{n/2}−2kn+4k+n \end{align}$$ and if we can find a suitable $k$ to make this less than or equal to $c2^{n/2}−kn$ we'll be done. In other words, we need to find $k$ such that $$ −2kn+4k+n≤kn $$ It's not hard to see that this will happen if $$ k\ge\frac{n}{n−4} $$ and this will be satisfied when $k=5$ for any integer $n\>4$. Now go back to the inductive proof and recast it for the guess $T(n)\le c2^{n/2}−5n$. You'll find that everything works nicely. Finally, observe that $c2^{n/2}−5n=O(2^{n/2})$ and you'll be done.

This is explained in a bit more detail in this answer to a similar question.

# Answer
> 0 votes
Hint: Prove by induction that $$ T(n) = 2^{n/2} T(0) + 2^{n/2+2} - n - 4. $$ (See the calculation in my answer to your former question.) Alternatively, you can try proving by induction that $T(n) \leq c 2^{n/2} - n$, for an appropriate $c$. Let us know if that works.

More generally, what you call the *substitution method* is used to get a bound on some recurrence without solving the recurrence explicitly. If you already know the explicit solution, and the explicit solution yields itself to asymptotic analysis, then there is no reason to use the substitution method other than to get a possibly shorter proof, or one that is more easy to generalize.

I realize that there is one more reason, namely that the exercise requires you to use the substitution method, but in that case you can defeat this silly and narrow request by using the substituting method to find the *exact* asymptotics.

---
Tags: recurrence-relation
---


# Question
Title: Need of reducing problems if we already know that a problem is undecidable
In the Reducibility chapter of Sipser's Theory of Computation book, an example is:

We reduce A(TM) to HALT(TM). And then we claim that if H decides HALT(TM), then A decides A(TM), but since A(TM) is undecidable, so is HALT(TM)

My question is, if we already know that A(TM) is undecidable, what is the need for deciding HALT(TM). It's a basic question though.

Hope you got it.

# Answer
> 1 votes
There's a difference between the statements:

* There is an undecidable problem.

and

* The problem HALT(TM) is undecidable.

For the first one, it sounds like you proved by by showing directly

* The problem A(TM) is undecidable.

The point of using a reduction, is that it lets you deduce the undecidability of HALT(TM) from the undecidability of A(TM), as opposed to starting "from scratch". More generally, reductions let you compare the hardness of different problems to each other, which is a general theme in computability and complexity.

---
Tags: computability, reductions
---


# Question
Title: How to perform local search on simple paths?
I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph.

The question is: given a current solution (an $S$-$T$-path), how can I generate a set of neighbour solutions?

To elaborate, I have an optimization (minimization) problem, on which I have to select the "best" path $S$-$T$ path. The evaluation function is complex and can't be evaluated until all the edges in the path are known. This plus the fact that the number of paths is exponential, lead me to draw on local search.

I know how to find an initial solution in polynomial time. The only piece missing in order to be able to use a local search algorithm (i.e. hill climbing) is to be able to generate a set of successors from the current path. I find this not to be trivial because simply switching one random node in the path for one not in it does not necessarily generate a still valid $S$-$T$ path.

Edit: I did not want to enter in the details of my specific problem because I think the question about how to define a relationship of neighbourhood in the space of path graphs is interesting in itself. But since you have asked, this is the evaluation function: $$\mbox{length}(\mbox{path}) \times \sum\_{i=1}^n \left ( p\_i \times -\mbox{log}\_2(p\_i) \right )$$, where $p\_i$ is the relative frequency of nodes in the path tagged with the number $i$ (every node in the graph is tagged with a number $1..n$.

# Answer
I can't comment yet, so I'll post this as an answer:

Assuming you can find the S-T path with a pathfinding algorithm, why not use the same algorithm with an "antiheuristic" topology?

As you increase the "heat," the further away your found paths will be from your initial solution.

Additionally, you could add some grainy noise wavelets, or random hills and valleys, into the landscape to toss things up a little.

But still:

> The evaluation function is complex and can't be evaluated until all the edges in the path are known

This is always the case. It is usually better to try and find a proper heuristic/path abstraction than monte-carloing it. I recommend you post more info about your problem.
> 1 votes

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


title: Iterated logarithm $\log^* n$

text:
# Question
Title: Iterated logarithm $\log^* n$
I am to come up with a function based on these premise:

Give an example of a function which is $o(\log^k n)$ for any fixed $k$, but which is also $\omega(1)$.

The answer is the iterative logarithm $\log^\* n$, and I want to show each of these steps.

1) show that $\log^\* n \leq \log^{k+1} n$

2) show that $\log^{k+1} n = o(\log^k n)$

3) show that $\log^\* n = \omega(1)$

I am stuck on mathematics behind these step because of my lack of knowledge of the iterated Logarithm. Can I ask for assistance at this?

# Answer
Let's assume the definition under which $\log^\* 2 = 1$, $\log^\* 2^2 = 2$, $\log^\* 2^{2^2} = 3$, and so on. In order to show that $\log^\* n = \omega(1)$, all you have to do is show that $\log^\* n \to \infty$. Since $\log^\*$ is increasing, it is enough to give a sequence of values $n\_1,n\_2,\ldots$ such that $\log^\* n\_i \to \infty$. Can you think of such a sequence?

In order to show that $\log^\* n = o(\log^k n)$ for any fixed $k \> 0$, find numbers $n\_\ell$ such that $n \leq n\_\ell$ implies $\log^\* n \leq \ell$, and notice that for $n\_{\ell-1} \< n \leq n\_\ell$, $\log^\* n/ \log^k n \leq \ell/(\log^k n\_{\ell-1})$. Perhaps you can show that $\log^k n\_{\ell-1}$ is much larger than $\ell$ for large enough $\ell$. More concretely, you can try to show that $\log^k n\_{\ell-1} \geq \ell^2$ (for example) for large enough $\ell$.
> 2 votes

---
Tags: asymptotics
---


title: Don't understand this graph definition

text:
# Question
Title: Don't understand this graph definition
I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows:

> Given a graph $G= \langle V\_G, E\_G \rangle$, we can construct the $H(G)=\langle V\_H, E\_H\rangle$ as follows: $$V\_H = V\_G\times\\{0,1\\}$$ $$E\_H = \\{((v,0),(v,1))|v\in V\_G\\}\cup\\{((x,1),(y,0))|(x,y)\in E\_G\\}.$$ Say that we have a graph $\langle G,u,v\rangle$ where $G$ is some directed graph, which contains vertices $u$ and $v$ then $H(G)$ can be used to find the smallest number of nodes that must be removed from $G$ to separate $u$ to $v$, meaning there will be no simple path from $u$ to $v$.

I really don't understand what's going on here, partly because I can't visualise $H(G)$. I assume we'd get some bipartite graph and maybe apply Edmonds-Karp only because the flow networks sections is succinct and there's not much else in this chapter. Could someone tell/show me what $H(G)$ is doing exactly and why this result is true. Much appreciated.

EDIT:

I've added some images of the what I got for $H(G)$ for some simple graphs. I understand that the function will transform a graph into a bipartite graph. But, how does this graph tell us the minimum number of vertices that have to be removed so there doesn't exists a simple path from $u$ to $v$ in the original graph? I'm perhaps wondering if it is a maximum matching problem in disguise.

# Answer
D.W.'s advice to consider some small examples is excellent. Two great examples to start with are an isolated vertex and a single edge! Once you can how the construction transforms vertices and edges, you know what happens to the building blocks.

Also, some familiarity with the basics of these constructions helps. In particular, any time you see "Let the vertex set of the new graph be $V\times S\\,$" for some set $S$, you should think: "Take a copy of $V$ for every element of $S$, and label each copy with the element it's associated with." So, here, the vertex set of $H$ is two copies of $G$'s vertex set: one labelled $0$ and one labelled $1$. Now, look at the edges. The first set of edges says, "For every vertex $v\in G$, add an edge from copy $0$ to copy $1$." The second set says, "For every edge $(x,y)\in G$, add an edge from copy $1$ of $x$ to copy $0$ of $y$."
> 3 votes

# Answer
As David already pointed out, the construction replaces each vertex $v$ with two vertices $(v,0)$ and $(v,1)$ and an edge from $(v,0)$ to $(v,1)$ (I'll call this edge $e\_v$ in the following).

Now, since all incoming edges of $v$ are connected to $(v,0)$ and all outgoing edges are connected to $(v,1)$, the edge $e\_v$ will have exactly the flow of the node $v$ in the original graph.

You probably were presented an algorithm that finds a minimal edge cut in the lecture. It should be obvious how this gives a minimal vertex cut for $G$, if only edges $e\_v$ are in the cut. If the cut contains edges from the second set, it is less obvious, but we may still translate this into a set of vertices to remove. (We have more than one choice about which vertex to remove for any such edge.) I'll leave it to you to figure out the details.
> 2 votes

---
Tags: graphs, terminology, network-flow
---


# Question
Title: Optimal Algorithm for checking if a number is a multiple of three
I'm just starting a course on Computational Number Theory and have very little Computer Science background but definitely know enough about the big-O notation.

I currently have an assignment to work on:

> An algorithm reads in the binary digits of a positive integer $N$ and determines whether $N$ is a multiple of 3. Show that the algorithm takes time at least of order $n$, where $n$ is the number of binary digits of $N$.

Basically, I have thought up of an algorithm which I'm pretty sure is correct: (I don't know what's the best/correct way to write an algorithm but here's my attempt)

1. Start with a binary number $x=a\_na\_{n-1}\dots a\_1a\_0$.
2. Then compute $x'=\sum^{i=n}\_{i=0} (\frac{3}{2}+\frac{1}{2}(-1)^{i+1})a\_i$.
3. Then $x'=0 \mod3 \iff 3|x$

This works because $2^{2k}=1\mod3$ and $2^{2k+1}=2\mod3$

I can guess that my algorithm takes time at least of order $n$ because I need order $n$ steps to compute $x'$.

However, I have my doubts:

1. How do I know my algorithm is the optimal algorithm?
2. Am I 'cheating' by saying $x'=0 \mod3 \iff 3|x$?
3. Am I even answering the question correctly by providing such an algorithm or is there some other sort of analysis to show lower bounds for algorithm time?

# Answer
> 9 votes
If an algorithm that takes less than $O(n)$ time, this means that the algorithm won't be able to look at all the digits of the number. Thus you can prove a lower bound of $O(n)$ by showing that you *have* to look at all (or almost all) digits of the number in order to decide divisibility.

To show the latter property, assume you had an algorithm that decides divisibility by 3 by looking at $n-2$ or fewer of the digits. This gives you 2 digits that you can set freely, since the algorithm has to give the same answer for any choice of these digits (it doesn't look at them) and it has to be always correct. However you can show that no matter where these digits are and what the value of the remaining digits is, you always have a choice for the digits that gives a number divisible by 3 and another choice that doesn't. Thus, the assumed algorithm can not exist. (I'll leave it to you to show the existance of such choices.)

# Answer
> 6 votes
Answering your questions one by one:

1. From what you know, you don't; you'd have to show that no algorithm can be better, that is it attains a (tight) lower bound.
2. I don't know what you mean by "cheating". If it's valid, it's okay, unless you are not allowed to use the modulo operation.

However, *is* it valid? What do you compute in step 2?
3. No, not at all! Providing an algorithm with a certain runtime only proves an *upper* bound on the complexity of the solved problem. Lower bounds are tougher; there is no genereal method that I know of.

Some notes and hints that might get you on the right track:

* You give very abstract pseudo code; it's level is often okay when communicating ideas of algorithms, but can get you in trouble when analysing runtime. There are many examples for more detailed ("lower level") pseudo code around, e.g. here.
* Remember elementary school. Is there a simple property by which you can tell if a number is divisible by three?
* Which cost model do you assume? The algorithm you give does take linear time in the uniform cost model, but not in the logarithmic model.
* Towards a lower bound, assume a (deterministic) algorithm that solves the problem could do so without looking at all digits of the input number. What can you conclude?

# Answer
> 4 votes
Let's answer your questions one by one:

1. You have a misunderstanding here. There is no clear notion of "the optimal algorithm", for two reasons. First, it depends on the exact computational model. Second, usually it is too much to expect to obtain the absolute optimal algorithm. Therefore we usually only worry about optimality up to multiplicative constants (big O), or if we want to be more careful, optimality up to lower order factors. In the first case, given an algorithm with running time $O(f(n))$, we would like a matching lower bound of $\Omega(f(n))$. In the second case, given an algorithm with running time $f(n)$, we would like a lower bound of $f(n) - o(f(n))$.
2. You are totally cheating. You could just as well compute $x \pmod{3}$ at the outset. It is true that $x'$ is much smaller than $x$, but still it needn't be constant size. Moreover, even your addition in the second step of your algorithm is problematic since the summand gets bigger and bigger.
3. Lower bounds are *not* shown by giving algorithms. (Unless in a very fancy way, like in Ryan Williams' recent work).

The standard way to compute the residue modulo 3 is as follows:

1. Initialize $a$ to $0$.
2. For $i$ from $0$ to $n$, compute $a \gets (a + x\_i) \pmod{3}$. (You can implement this instruction using a table if you wish.)

This takes $O(n)$ time in any reasonable computation model (even a Turing machine, if you're very careful). There is also an equivalent way of stating this algorithm using finite automata, which amounts to the very same algorithm.

Lower bounds in general are very difficult, but here all we need to do is prove a linear lower bound, thus showing that the algorithm is optimal up to multiplicative constants. The trick is showing that the algorithm needs to read all the input bits. The reason is that $2^i \not\equiv 0 \pmod{3}$ for all $i$. I'll let you fill in the details. (The analysis become simpler if you allow leading zeroes).

# Answer
> 2 votes
It is rather easy to construct a DFA that recognizes the language of binary strings divisible by 3. States are the residue classes modulo 3, your transition function is $\delta (q, d) = (2 \cdot q + d) \bmod 3$, initial and final state is 0.

The exact same construction works for other bases and divisors.

In any case, no algorithm can take less than $O(n)$, where $n$ is the length of the string; this is optimal.

# Answer
> 1 votes
Actually you gave the answer yourself: since $2^{2k}=1\mod3$ and $2^{2k+1}=2\mod3$, one must consider all $n$ binary digits to check if the number is a multiple of $3$, there is no way around. Hence any algorithm is at least $O(n)$. This is the answer to the question, there is no need to provide an algorithm which is $O(n)$.

---
Tags: algorithm-analysis, runtime-analysis, arithmetic
---


# Question
Title: Why does introsort use heapsort rather than mergesort?
As part of a homework assignment covering implementation of introsort I'm asked why heapsort is used rather than mergesort (or other $O(n\log(n))$ algorithms for that matter).

> Introsort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. (Wikipedia, retrieved 2014-May-06.)

The only reason I can think of is that heapsort is "in place" ... But tbh I don't really understand why this would matter here though.

# Answer
The 2 downsides of quicksort is that it requires $O(\log n)$ extra space (to keep the unsorted intervals) and bad pivot selection (or contrived sequences designed to make you select a bad pivot) may cause it to be a $O(n^2)$ time and $O(n)$ extra space algorithm.

Switching to heapsort when the recursion depth becomes too large (at around $\log n$) means we have a guaranteed upperbound that is $O(n \log n )$ time and $O( \log n)$ extra space.

Heapsort's $O(1)$ extra space requirement makes it a better choice to mergsort's $O(n)$ where for a contrived array that $n$ could still be large.

The reason heapsort isn't used for the full sort is because it is slower than quicksort (due in part to the hidden constants in the big O expression and in part to the cache behavior)
> 9 votes

---
Tags: algorithms, algorithm-analysis, sorting
---


title: NP Completeness of 3-SAT problem

text:
# Question
Title: NP Completeness of 3-SAT problem
I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the classical problems. I have started with 3-SAT problem.

3-SAT problem — was shown to be NP-complete:

> Input: A boolean Formula F in CNF where each clause contains at most three variables.
>
> Question: Is that formula satisfiable?

Show now that the simple 3-SAT problem is also NP-complete:

> Input: A boolean Formula F in CNF where each clause contains at most three variables and only clauses of length two may contain negated variables.
>
> Question: Is that formula satisfiable?

Can any please explain the main idea? Thank you in advance.

# Answer
Main idea: For each variable $x\_i$ introduce a new variable $y\_i$ and add a new clause $(\lnot x\_i, \lnot y\_i)$. Replace each occurence of $\lnot x\_i$ in the original clauses by $y\_i$.

The new clauses ensure that $y\_i$ can be set to true if and only if $x\_i$ is false. Thus we neither add nor remove satisfying assignments for the original clauses, while the new clauses can always be satisfied.
> 4 votes

---
Tags: complexity-theory, np-complete, reductions, satisfiability, 3-sat
---


# Question
Title: Can you recognize or decide if a Turing Machine has an infinite sized language?
That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language?

Similarly, can you recognize or decide if a Turing Machine has an uncountably-infinite language?

# Answer
To elaborate somewhat on Yuval's comment:

(1) Some languages have an infinite number of strings, some do not. This makes the property non-trivial, and Rice's theorem says that recognizing whether the language of a Turing Machine has a non-trivial property is undecidable. This problem is undecidable.

(2) All languages are countable; none are uncountable. This makes the property trivial. Deciding whether the language of a TM has a trivial property is always decidable: if it's a property all languages have, then answer yes; if it's a property no languages have, answer no.

(A word of general caution, though it doesn't apply here. Rice's theorem applies only to properties of languages themselves, not properties of the TMs that might accept them. This is an important distinction. Rice's theorem only works for properties that have to do with the language and strings it contains.)

For reference: Rice's Theorem
> 1 votes

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


# Question
Title: Calculating time complexity of two interdependent nested for loops
Consider the following code segment :

```
for (int i = 1; i <= n; i++ ) {
    for (int j = 1; j <= n; j = j + i ) {
          printf("Hi");
    }
}

```

Here, the outer loop will execute $ n $ times, but the execution of inner loop depends upon the value of $ i $.

* When $ i = 1 $ inner loop will execute $ n $ times.
* When $ i = 2 $ inner loop will execute $ \frac{n}{2} $ times.
* When $ i = 3 $ inner loop will execute $ \frac{n}{3} $ times.
$ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots $
* When $ i = n $ inner loop will execute $ 1 $ time

So complexity will be given by
$$ \begin{align} T(n) &= \frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \cdots + \frac{n}{n}\\ \\ &= n \left( 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \right) \\\\ &= n \sum\_{k = 1}^{n} { \frac{1}{k} } \end {align} $$ I am not able to solve $ \sum\_{k=1}^{n} \frac{1}{k} $. Upon searching I found that it is the $ n^{th} $ Harmonic number ( $ H\_n $), but couldn't find any closed formula for it. How can I proceed further to calculate $ T(n) $?

# Answer
> 5 votes
The $n^{th}$ harmonic number can be approximated by the integral $\int\_1^n \frac{1}{x} \mathrm{d}x$.

\begin{align} H\_n \approx \int\_1^n \frac{1}{x} \mathrm{d}x = \left\[ \ln x \right\]\_1^n = \ln n - \ln 1 = \ln n \end{align}

The limit of $H\_n - \ln n$ is $\gamma \approx 0.577$, which is the Euler-Mascheroni constant.

Therefore, we get \begin{align} H\_n & = \ln n + \gamma + r(n) \\ r(n) & \in \mathcal{O}\left(\frac{1}{n}\right) \end{align}

Since $H\_n - \ln n$ is not exactly $\gamma$, we need some remainder $r(n)$, whose limit is $0$.

So we get $T(n) = n \ H\_n = n\ln n + n\gamma + n \ r(n) \in \mathcal{O}(n \log n)$

# Answer
> 4 votes
Since you are only interested in the time complexity and can ignore a constant factor of two: Replace

```
1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9 + 1/10 ...

```

with

```
1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + 1/16 + 1/16 ...

```

for a lower bound, and with

```
1 + 1/2 + 1/2 + 1/2 + 1/4 + 1/4 + 1/4 + 1/4 + 1/8 + 1/8 ...

```

for an upper bound. Then add the 3rd and 4th term, the 5th to 8th term, the 9th to 16th term and so on.

Not that knowing the sum of harmonic numbers isn't a good thing to know, but having a good strategy helps you in cases where an exact formula isn't available.

# Answer
> 2 votes
The $n$th harmonic number is asymptotically $\ln n + \gamma + O\left(\frac{1}{n} \right)$, with $\ln n$ being the natural logarithm and $\gamma $ the *Euler Constant*. You can find all on Wikipedia's entry on the harmonic number.

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Mutual Information in a Binary Erasure Channel
Imagine a Binary Erasure Channel as depicted on Wikipedia.

One equation describing the mutual information is:

$$ \begin{align\*}I(x;y) &= H(x) - H(x|y) \\ &= H(x) - p(y=0) \cdot 0 - p(y=?) \cdot H(x) -p(y=1)\cdot 0\end{align\*}$$

Why is it "$p(y=?) \cdot H(x)$" and not "$p(y=?) \cdot H(x|y=?)$"?

# Answer
If $y = ?$ then $H(x) = H(x|y=?)$ since $y = ?$ gives you no information about $x$.
> 0 votes

---
Tags: information-theory
---


# Question
Title: Find a maximal subgraph on a tree with conditions
Given a tree, find a path on which every vertex has at most 4 leaves (can have 0 as well) and is the "biggest" (has the maximum amount of vertices possible - including the leaves). Time complexity: $O(n)$.

I'm getting nowhere with this problem. I have tried BFS/DFS (seemed like such an obvious method), but even if I could modify them correctly, their time complexity is $O(|V|+|E|)$.

Any hint, thought is appreciated.

***edit:*** so now I get that BFS/DFS is valid for this problem, but I'm still having difficulties with figuring out the algorithm itself. Help please.

# Answer
The idea is that if you have a vertex having more than 4 leaves in the tree you could never take it in your final path. The steps of the Algorithm is as follows:

1. Delete the vertices having more than 4 leaves and the edges incident on them.
2. By deleting those vertices and edges you'll get a forest having trees say T1,...,Tk.
3. Then find simply the biggest path in each of those trees.
4. Take the maximum over all of those paths.

In 1st step you can keep a counter for all the vertices. Add one to the counters of the neighbors of each leaf. Delete the vertices having counter value \> 4. So, it takes O(n) time.

Now in 3rd step finding a biggest path in a tree is straightforward using DFS.

Thus in total it takes O(n) time.
> 0 votes

---
Tags: graphs, trees, graph-traversal
---


# Question
Title: Show that the running time of the build_heap function is $O(n)$
> Given the following two functions, prove that the build\_heap function, which transforms an array A into a max-heap-sorted array A' runs in $O(n)$.
>
> ```
> heapify(A, i):
>
> Input: array A of length n, index i
>
> left = 2i + 1 (left child node)
> right = 2i + 2 (right child node)
> largest = i if left < n and A[left] > A[i] then
>     largest = left
> end if
> if right < n and A[right] > A[largest] then
>     largest = right end
> if if largest != i then
>     swap(A, i, largest)
>     heapify(A, largest)
> end if
>
>
> build_heap(A):
>
> Input: Array of length n
>
> for i = floor((n-1)/2) to 0 do
>   heapify(A, i)
> end for
>
> ```
>
> Hint: Assume that A has $2^j-1$, for $j \in \mathbb{N}$, elements. You can also use the fact that $\sum\_{k=0}^{\infty}\frac{k}{2^k} = 2$.

I don't really understand why the formula is given in the hint, or rather how to explicitly use it to prove that `build_heap(A)` runs in $O(n)$.

I would say that the worst case for the heapify function is given when a call of \`heapify(A,0) calls itself recursively as much as possible. I think a binary tree with n nodes has depth of $\lceil lg(n) \rceil $, so the maximum number of recursive calls should be $\lceil lg(n) \rceil $.

I'm not sure but my guess is that the formula is trying to tell me that the running time of heapify is $O(1)$? But I don't really see how that's possible. If it were a constant then clearly `build_heap(A)` would run in $O(n)$, but how can it be constant?

Can someone please help me out?

# Answer
The main point is to do the analysis exactly without being sloppy. Let me define the **depth** of a node in this way. Depth of any leaf is 0 and depth of any non-leaf node is maximum depth among its children plus 1. One can note that depth = $\log n - $ height.

Then for a particular node how much time does heapify take? By definition of depth you can see it is order of depth of the node.

Now the total time for buildheap is $$\sum\_{d=0}^{\log n} \text{(number of nodes of depth d)}\cdot O(d).$$

Now my claim is that there are at most $n/2^d$ nodes at depth $d$ (can you see why?). For example number of leaves (depth 0) is at most $n/2^0 = n$.

Then, building time is $$ \sum\_{d = 0}^{\log n} \frac{n}{2^d} \cdot O(d) = O(n)\cdot\sum\_{d = 0}^\infty \frac{d}{2^d} = O(n) \cdot 2 = O(n). $$
> 4 votes

---
Tags: algorithm-analysis, data-structures, heaps
---


# Question
Title: Is polynomial time reducibility reversible?
If a language $A$ is reducible to some language $B$, does it follow that $B$ is reducible to $A$?

My guess is no, it having something to do with the function $f$ in the definition of $A$ reducing to $B$ needing to be invertible.

# Answer
> 6 votes
This is provably not the case. Let $A$ be any non-trivial language in P (different from $\emptyset$ and $\Sigma^\*$), and let $B$ be any EXPTIME-hard language. Clearly $A$ is polytime-reducible to $B$ (since $A$ is polytime and $B$ is non-trivial; or since P$\subseteq$EXPTIME and $B$ is EXPTIME-hard), but if $B$ were polytime-reducible to $A$ then it would follow that EXPTIME=P, contradicting the time hierarchy theorem.

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


# Question
Title: Algorithm to match numbers with minimum number of moves
This is a sort of edit-distance question, and is very easy. I am just quite brain dead on this subject and can't figure it out so far.

---

Given a series of numbers, e.g.

```
[3, 1, 1, 1]

```

How would one most efficiently turn all of the numbers into the same number, with the minimum number of "moves"? By "move" is meant adding or removing one from a number.

In the above example, the most efficient moves would be:

```
[1, 1, 1, 1]

```

This would require 2 moves, reducing the first number twice.

I can't figure out the best way to find this out, given much larger arrays of hundreds of numbers.

I originally tried computing the rounded average number (sum of all divided by length), and then reducing them to the computed average, but the above example broke this, requiring 4 moves instead of 2.

I suppose I could figure:

1. The average,
2. The mode,
3. The median

and get the edit distance of each of them, choosing the minimum distance. However, I am not sure that this would be correct in every single instance. How can I know?

# Answer
The answer is to take the median. One of the properties of the median is that it minimizes the L1 distance to each element. (To make sense of the Wikipedia article, take the probability distribution to be the uniform distribution over your original series of numbers).

This is the algorithm which solves the problem (originally written by dc2):

```
function median(arr) {
  arr.sort(function(a, b) { return a - b; });
  var half = floor(arr.length/2);
  if ( arr.length % 2 ) {
    return arr[half];
  } else {
    return (arr[half-1] + arr[half]) / 2.0;
  }
}

function minl1(arr) {
  var moves = 0;
  var mdn = median(arr);
  for ( var i = 0; i < arr.length; ++i ) {
    moves += Math.abs(mdn - arr[i]);
  }
  return moves;
}

minl1([3, 1, 1, 1]); // -> 2

```
> 10 votes

# Answer
As TCSGrad mentions, given a list of integers $x\_1,\ldots,x\_n$, you're looking for the integer $m$ minimizing $$ \delta(m) = \sum\_{i=1}^n |m - x\_i|. $$ It is instructive to compute $\delta(m+1) - \delta(m)$: $$ \delta(m+1) - \delta(m) = \sum\_{i=1}^n \begin{cases} +1 & m \geq x\_i \\ -1 & m \< x\_i \end{cases} = \\#\\{i : m \geq x\_i\\} - \\#\\{i : m \< x\_i\\}.$$ As $m$ goes from $-\infty$ to $+\infty$, the quantity $\delta(m+1) - \delta(m)$ goes from $-n$ to $n$. Moreover, it switches values only at the points $x\_1,\ldots,x\_n$. It is not hard to check that an optimal value of $m$ is the minimal point at which $\delta(m+1) - \delta(m) \geq 0$. This minimal point is one of the $x\_i$, so the editing distance is $\min(\delta(x\_1),\ldots,\delta(x\_n))$.

Suppose further that all $x\_i$ are distinct and that $n$ is odd. Let $m$ be the median of the $x\_i$. Then $\delta(m+1) - \delta(m) = 1$ while $\delta(m) - \delta(m-1) = -1$, and so $m$ is the unique optimum. If $n$ is even then a similar calculation shows that we can choose any point in the interval connecting the medians. Similar but more elaborate reasoning shows that any median is optimal even when the $x\_i$ are not distinct. So there is actually no need to calculate $\delta$ on all $x\_i$.
> 10 votes

# Answer
The problem can be formulated as a LP problem:

Given a set of $n$ numbers $\[a\_1,a\_2... a\_n\]$, solve the following LP:

$$ \min \sum |a\_i - x| $$

(Removed constraints on $x$, which weren't necessary as Raphael pointed out)

Once the LP is solved, you'll get a value of $x$ corresponding to the solution. If $x$ is an integer, you are done - else, round it to the nearest integer.

**EDIT**: As pointed out in the comments, the objective function should be sum over absolute differences. In order to transform it back to a standard LP, we can rewrite the LP as:

$$ \min \sum a'\_i $$

subject to:

$$ a'\_i \geq a\_i - x\ \forall i $$ $$ a'\_i \leq a\_i - x\ \forall i $$ $$ a'\_i, x' \geq 0\ \forall i $$

At the optimal solution, $a\_i' = | a\_i - x|\ \forall i$, and we can get the value of $x$ from the solution.
> 5 votes

---
Tags: algorithms, optimization
---


title: NP hardness of Partition

text:
# Question
Title: NP hardness of Partition
I'm trying to show that PARTITION is NP-hard. I'm not sure if what I have is correct so I'll write what I have. I tried to reduce it from SUBSET\_SUM:

$$PART= \\{S\subset\mathbb{Z}|\exists C \subset S: \sum\_{x\in C} x=\sum\_{x\in S-C}x\\} $$ $$SUBSET SUM = \\{\langle T,u\rangle| T\subset \mathbb{N}, u \in \mathbb{Z}\quad\exists B\subset T: \sum\_{y\in B}y = u\\}$$

$$SUBSETSUM \leq\_p PART$$

$\text{Let} \quad f\left(\langle T,u\rangle\right)=\langle S\rangle$ be a polytime computable function that accepts an instance of subset sum and outputs an instance of partition.

The basic gist of my proof was that if I made the restriction that my $$u =\sum\_{y\in T-B} y $$ and then allowed $T=S$, $B=C$ and $x=y$ I'd prove the equivalence of subset sum and partition.

# Answer
Your reduction completely ignores $u$. Certainly the answer for SUBSET SUM depends on $u$, doesn't it?

Also, you can't guarantee $x=y$, $B=C$. Rather, given $T$ and $u$, you need to produce $S$ (in polynomial time) such that there is a subset of $T$ summing to $u$ iff $S$ can be partitioned into two equal halves. This is the meaning of reduction.

Your suggestion $S = T$ doesn't work. For example, if $T = \\{1,2,3\\}$ and $u = 7$ then there is no subset of $T$ summing to $u$ but $S$ can be partitioned as $\\{1,2\\} \cup \\{3\\}$.

Here is another suggestion: choose $S = T \cup \\{\sum T - 2u\\}$. The idea here is that if $A$ is a subset of $T$ summing to $u$ then there is a partition $S = (A \cup \\{\sum T-2u\\}) \cup (T \setminus A)$; indeed, the first part sums to $u + (\sum T-2u) = \sum T-u$, which is what the second part sums to. In other words, if $T$ has a subset summing to $u$, then $S$ can be partitioned into two parts with equal sum.

What about the other direction? Suppose that $S$ can be partitioned into two parts. One of these parts contains $\sum T - 2u$, say $A \cup \\{ \sum T - 2u \\}$. Since $\sum S = \sum T + (\sum T - 2u) = 2(\sum T - u)$, it follows that $\sum A + T - 2u = \sum T - u$, or $\sum A = u$.

You might be worried that $\sum T - 2u \in T$. I'll let you figure out what to do in this case.
> 0 votes

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


title: Minimising height of a 2-3-4 tree

text:
# Question
Title: Minimising height of a 2-3-4 tree
I'm wondering how a set of keys could be assigned to nodes in a 2-3-4 tree in order to minimize the height of the tree?

Does the sequence of insertion matter with 2-3-4 trees?

# Answer
The insertion order is relevant for the height of the tree. Inserting (in this order) 1,2,3,4,5,6,7,8 gives a tree of height 3, while inserting these keys in the order 1,3,4,6,7,8,2,5 gives a tree of height 2.

In order to create a tree of minimal height, you can place the keys with ranks $\lceil \frac{n}4\rceil$, $\lceil \frac{n}2\rceil$, and $\lfloor \frac{3n}4\rfloor$ in the root, partition the remaining keys accordingly into the subtrees and apply the this recursively to each of the subtrees. Depending on the number of keys, you may have to shift a few keys around between leaves and their parents to make sure that all leaves are at the same level.
> 1 votes

# Answer
No, the sequence of insertion does not matter, as 2-3-4 trees are self-balancing data structures. A 2-3-4 tree of $N$ nodes has the following height:

$$ \frac{1}{2} \log (N + 1) \leq height \leq \log (N + 1) $$

That holds because as per Wikipedia:

> 2–3–4 trees are B-trees of order 4 (Knuth 1998); like B-trees in general, they can search, insert and delete in O(log n) time. One property of a 2–3–4 tree is that all external nodes are at the same depth.
> -1 votes

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


# Question
Title: How can an LBA check legality of TM transitions without extra memory?
In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A\_$\_{\text{TM}}$.

The reduction is proposed in the following manner: we receive a TM $M$ and a word $w$, and build an LBA $B$ that accepts if is fed an accepting computation history of $M$ on $w$.

At page 224, it describes how $B$ checks that the configuration $C\_{i+1}$ is legal for M on $w$ at the step $i+1$, and states "then $B$ verifies that the updating was done properly by zig-zagging between corresponding positions of $C\_i$ and $C\_{i+1}$. To keep track of the current positions while zig-zagging, $B$ marks the current position with dots on the tape."

How can we know that $B$ does not need additional memory to check for legality of configuration change from $i$ to $i+1$? $B$ is an LBA, that says it has only the memory it got with initialisation and cannot go beyond it on the tape, so if it needs additional memory it has a problem.

# Answer
> 3 votes
B is given the complete computation history as input. All it does on that input, according to the description, is moving around, reading, marking, and unmarking things. Moving around and reading obviously don't need extra space, and marking/unmarking can be done in-place as well. (For each letter of M's alphabet B's alphabet can contain a marked copy, so that marking just means replacing the unmarked symbol with the marked one.) Thus, all is well.

---
Tags: computability, undecidability, linear-bounded-automata
---


# Question
Title: Counting number of sums from contiguous subarrays of an array
We are given an array $a\[1 \ldots n\]$ with all $a\[i\]\>0$.

Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a\[j\ldots k\]$ for some $j,k$, the sum is the sum of all of the elements of the subarray). For example, if $a=\[1,2,1\]$, then the answer is 4: we can form $ 1,2,3,4$.

I know how to count the number of distinct sums in $O(n^2)$ time.

Furthermore, I have come to realise this is similar to the classical problem where we need to find the number of distinct substrings of a string. I was thinking of the possibility of constructing a suffix array and solving it in a similar fashion (in $O(n)$ time). But I have not been able to figure out how to modify that to work here. For example, if we use suffix array for $a=\[1,2,1\]$ we will get 5 cases instead of the four acceptable ones. Is this possible to do this using suffix arrays or am I thinking in the wrong direction?

Also there is one more direction I have been thinking in. Divide and conquer. Like if I divide the array into two parts every time until it is reduced to a single element. A single element can have one sum. Now if we combine two single elements, It can be done in two ways: if both single ranges have same element then we get 2 different sums, or if both have different elements we get 3 different sums. But I am not being able to generalize this for merging arrays of length greater than 1. Is it possible to merge two m size arrays and get the answer in $O(m)$?

# Answer
You almost surely can't get better than $O(n^2)$ in the worst case since the number of different sums can be in $\Theta(n^2)$.

Consider e.g. the array $\[1,2,4,8,\dotsc, 2^n\]$. Here each of the $\frac{n(n+1)}2$ contiguous subarrays has a different sum.

---

The "almost surely" is due to the fact that the problem does not require the values of the sums as output. However, I don't think duplicates can be avoided without determining at least most of the values.
> 2 votes

---
Tags: arrays, substrings, suffix-array
---


# Question
Title: On "The Average Height of Planted Plane Trees" by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" want to prove that the average height $h\_n$ of a tree with $n$ nodes (that is, the maximum number of nodes from the root to a leaf) satisfies $h\_n \sim \sqrt{\pi n}$.

The outline is as follows. Let $A\_{nh}$ be the number of trees with height less than or equal to $h$ (with the convention $A\_{nh} = A\_{nn}$ for all $h \geqslant n$) and $B\_{nh}$ the number of trees of $n$ nodes with height greater than or equal to $h+1$ (that is, $B\_{nh} = A\_{nn} - A\_{nh}$). Then $h\_n = S\_n/A\_{nn}$, where $S\_n$ is the finite sum $$ S\_n = \sum\_{h \geqslant 1} h(A\_{nh} - A\_{n,h-1}) = \sum\_{h \geqslant 1} h(B\_{n,h-1} - B\_{nh}) = \sum\_{h \geqslant 0} B\_{nh}. $$ It is well known that $A\_{nn} = \frac{1}{n}\binom{2n-2}{n-1}$, for the set of general trees with $n$ nodes is in bijection with the set of binary trees with $n-1$ nodes, counted by the Catalan numbers.

Therefore, the first step is to find $B\_{nh}$ and then the main term in the asymptotic expansion of $S\_n$.

At this point the authors use analytical combinatorics (three pages) to derive $$ B\_{n+1,h-1} = \sum\_{k \geqslant 1} \left\[\binom{2n}{n+1-kh} - 2\binom{2n}{n-kh} + \binom{2n}{n-1-kh}\right\]. $$

> My own attempt is as follows. I consider the bijection between trees with $n$ nodes and monotonic paths on a square grid $(n-1) \times (n-1)$ from $(0,0)$ to $(n-1,n-1)$ which do not cross the diagonal (and are made of two kinds of steps: $\uparrow$ and $\rightarrow$). These paths are sometimes called *Dyck paths* or *excursions*. I can express now $B\_{nh}$ in terms of lattice paths: it is the number of Dyck paths of length 2(n-1) and height greater than or equal to $h$. (Note: a tree of height $h$ is in bijection with a Dyck path of height $h-1$.)
>
> Without loss of generality, I assume that they start with $\uparrow$ (hence stay above the diagonal). For each path, I consider the first step crossing the line $y = x + h - 1$, if any. From the point above, all the way back to the origin, I change $\uparrow$ into $\rightarrow$ and vice versa (this is a *reflection* wrt the line $y=x+h$). It becomes apparent that the paths I want to count ($B\_{nh}$) are in bijection with the monotonic paths from $(-h,h)$ to $(n-1,n-1)$ which avoid the boundaries $y=x+2h+1$ and $y=x-1$. (See figure.)

In the classic book *Lattice Path Counting and Applications* by Mohanty (1979, page 6) the formula $$ \sum\_{k \in \mathbb{Z}} \left\[\binom{m+n}{m-k(t+s)} - \binom{m+n}{n+k(t+s)+t}\right\], $$ counts the number of monotonic paths in a lattice from $(0,0)$ to $(m,n)$, which avoid the boundaries $y = x - t$ and $y = x + s$, with $t \> 0$ and $s \> 0$. (This result was first established by Russian statisticians in the 50s.) Therefore, by considering a new origin at $(-h,h)$, we satisfy the conditions of the formula: $s=1$, $t=2h+1$ and the destination point (the upper right corner) is now $(n+h-1,n-h-1)$. Then $$ B\_{nh} = \sum\_{k \in \mathbb{Z}} \left\[\binom{2n-2}{n+h-1-k(2h+2)} - \binom{2n-2}{n-h-1+k(2h+2) + 2h+1}\right\]. $$ This can be simplified in $$ B\_{n+1,h-1} = \sum\_{k \in \mathbb{Z}} \left\[\binom{2n}{n+1-(2k+1)h} - \binom{2n}{n-(2k+1)h}\right\], $$ which, in turn, is equivalent to $$ B\_{n+1,h-1} = \sum\_{k \geqslant 0} \left\[\binom{2n}{n+1-(2k+1)h} - 2\binom{2n}{n-(2k+1)h} + \binom{2n}{n-1-(2k+1)h}\right\]. $$ The difference with the expected formula is that I sum over the odd numbers ($2k+1$), instead of all positive integers ($k$).

Any idea where the problem is?

# Answer
> 2 votes
The monotonic paths from $(−h,h)$ to $(n−1,n−1)$ that you construct only avoid the boundary $y=x+2h+1$ before they cross $y=x+h$ for the first time. Thus the formula you use is not applicable.

---
Tags: combinatorics, discrete-mathematics, trees, average-case, random-walks
---


# Question
Title: How does the runtime of the Ukkonen's algorithm depend on the alphabet size?
I am concerned with the question of **the asymptotic running time of the Ukkonen's algorithm**, perhaps the most popular algorithm for constructing **suffix trees** in linear (?) time.

Here is a citation from the book "Algorithms on strings, trees and sequences" by Dan Gusfield (section 6.5.1):

> "... the Aho-Corasick, Weiner, **Ukkonen** and McCreight algorithms all either require $\Theta(m|\Sigma|)$ space, or the $O(m)$ time bound should be replaced with the minimum of $O(m \log m)$ and $O(m \log|\Sigma|)$".
>
> *\[$m$ is the string length and $\Sigma$ is the size of the alphabet\]*

I don't understand why that is true.

* **Space:** well, in case we represent branches out of the nodes using arrays of size $\Theta(|\Sigma|)$, then, indeed, we end up with $\Theta(m|\Sigma|)$ space usage. However, as far as I can see, it is also possible to store the branches using hash tables (say, dictionaries in Python). We would then have only $\Theta(m)$ pointers stored in all hash tables altogether (since there are $\Theta(m)$ edges in the tree), while still being able to access the children nodes in $O(1)$ time, as fast as when using arrays.
* **Time**: as mentioned above, using hash tables allows us to access the outgoing branches of any node in $O(1)$ time. Since the Ukkonen's algorithm requires $O(m)$ operations (including accessing children nodes), the overall running time then would be also $O(m)$.

I would be very grateful to you for any hints on why I am wrong in my conclusions and why Gusfield is right about the dependence of the Ukkonen's algorithm on the alphabet.

# Answer
> 2 votes
As @jogojapan mentions in the comments, hasing generally is only amortized $O(1)$, so you would only get amortized bounds for the algorithm. However, I think you do not even get these: In order to get amortized $O(1)$ hashing, the hash tables have to be of size $\Omega(\Sigma)$, so you still have $\Theta(m\Sigma)$ space (and the same time requirement for initialization).

What's more, in practice the time for setting up all these hash tables will be much higher than the time to set up arrays.

You might fare better with using a global hash table that is indexed with (node, character)-pairs, but at least the "only amortized" argument will remain.

---
Tags: algorithms, data-structures, algorithm-analysis, strings
---


title: NFAs with more than one initial state

text:
# Question
Title: NFAs with more than one initial state
I'm trying to give a meaningful definition for NFAs with more than one initial state. I know from the formal definition in Wikipedia that it is possible to have more than one initial state, it mentions that "There is an easy construction that translates a NFA with multiple initial states to a NFA with single initial state, which provides a convenient notation."

I believe the power set construction could help me on this matter but I'm having a hard time understanding it. It could probably be modified so that it can be applied into the definition I want to give, but i don't know how.

I would appreciate any help I can get on this matter.

# Answer
> 16 votes
An NFA with multiple starting states makes a non-deterministic choice of the starting state, in the same way that it makes non-deterministic choices throughout its operation. It is equivalent to an NFA with a single new starting state connected to the former starting states with $\epsilon$ transitions.

For example, here is an NFA which accepts the language of all words not containing all letters in the alphabet $\Sigma$. For each $\sigma \in \Sigma$ there is a state $s\_\sigma$. For each $\tau \neq \sigma$, there is a self-loop labelled $\tau$ around $s\_\sigma$. All $s\_\sigma$ are starting states as well as accepting states. The state $s\_\sigma$ is supposed to represent all words not containing $\sigma$.

In order to convert this to an NFA with a single starting state, add a new state $s$ which is the new starting state, and connect $s$ to all $s\_\sigma$ with $\epsilon$ transitions. The semantics of both NFAs are exactly the same.

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


title: Building Simple Parse Trees

text:
# Question
Title: Building Simple Parse Trees
I am trying to learn how to build parse trees.

I have watched videos and tried to do some on my own, but am a little lost.

In this example, I am given the following:

$$ \begin{align\*} &S\to(L) \\ &S\to a \\ &L\to L,S \\ &L\to S \end{align\*} $$

and then I am told to draw a parse tree for the expression $(a,(a,a))$.

I know that the first $S$ is the start symbol, I know that since I am trying to draw it for a specific string, I should use the bottom up approach, but I am very confused.

Can the lines above also be written as $$ \begin{align\*} &S\to(L)|a \\ &L\to L,S|S \end{align\*} $$ or can they not be combined that way?

How would you write this tree? What confuses me the most is how to write the tree using the $L$ and $L,S$ but resulting in $(a,(a,a))$.

I would appreciate any explanation or demonstration offered.

# Answer
> 5 votes
The notation $S\to(L)|a$ is shorthand to $S\to(L)$ and $S\to a$, so you can rewrite the grammar in your equivalent form; I don't see how this makes things any different, since the two grammars are exactly the same.

The first step in writing a parse tree is coming up with a derivation. In the derivation below, I use boldface to indicate the non-terminal being expanded. $$ \begin{align\*} \mathbf{S}&\to(\mathbf{L}) \\ &\to(\mathbf{L},S) \\ &\to (\mathbf{S},S) \\ &\to (a,\mathbf{S}) \\ &\to (a,(\mathbf{L})) \\ &\to (a,(\mathbf{L},S)) \\ &\to (a,(\mathbf{S},S)) \\ &\to (a,(a,\mathbf{S})) \\ &\to (a,(a,a)) \end{align\*} $$ There are several different derivations which "feel" the same. For example, in this derivation I always expanded the left-most non-terminal, but you could just as well expand any other non-terminal. When you draw the derivation tree, all these derivations give rise to the same tree.

Here is the actual derivation tree, drawn by Rick Decker:

---
Tags: context-free, parsing
---


# Question
Title: Can't understand why the DP Subset Sum algorithm is not polynomial
I can not understand why the dynamic programming algorithm for the Subset Sum, is not polynomial.

Even though the sum to find 'T' is greater than the total sum of the 'n' elements of the set , the number of iterations is always (T * n) and not exponential I'm not understanding it.

The algorithm always do 'n\*T' comparisons, and writes in the matrix only 'n\*T' times...I'm missing something and I don't know what it is.

# Answer
The reason is that you have to take into account the binary encoding of numbers. The input size $m$ is really the total number of bits, so if your instance is $a\_1,\ldots, a\_n, T$, then $m = \log T + \sum\_{i\in \[n\]} \log a\_i$.

In particular, $T$ can be super-polynomial in $m$, so the dynamic programming algorithm's runtime can be made super-polynomial as well, since it needs to take one step to build every cell of its table. (The quantity $nT$ can be made $\Omega(2^{m/3})$ for example.)

On the other hand, when all the numbers in the instance are restricted to be "small" (i.e., polynomially bounded in $m$), the SUBSET-SUM becomes tractable. (Notice that the usual reduction from 3SAT has very large numbers in it.)

A problem is strongly NP-Complete when it remains NP-Complete even when all the numeric values are polynomial in the input length. SUBSET-SUM isn't (it's called weakly NP-Complete).

The kind of running time that is polynomial in the numeric values in the input is known as *pseudo-polynomial*.
> 5 votes

# Answer
Another way to think about it which may be easier to understand: If we double $T$, we need one more bit to represent it, and $T$ is part of the input, so the input size increases by one bit. However, the run time doubles, and we can keep doing this and the run time will double each time while the input size will increase by one each time.

We measure the complexity of algorithms *by considering the run time as a function of the input size*, and in this example, the run time grows exponentially *with respect to the input size*, so we know that the run time cannot be polynomial.
> 4 votes

# Answer
The algorithm is exponential in the size of the input because of the assumption that integers are represented in binary. The running time is $O(T \cdot n)$, where $T$ is the integer (sum) and $n$ is the size of the set. Since $T$ is - typically and realistically - represented in binary, $T$ is represented by at least $O(log\_2 T)$ bits`*`. So it takes $O(log\_2 T)$ time to read this bit-vector sequentially. In the DP algorithm, you have to consider all values (sums) from $1$ to $T$ (assuming $T$ is positive); *this is exponential in the length of $T$*. To see this, note that:

$k = log\_2 T$
$T = 2^{k}$

So if you have a bit-vector that is $b$ bits long, the largest number you can represent is approximately $2^b$; a number exponential in $b$.

**Example**
The maximum value of a $32$ bit signed integer is $T = 2^{31} - 1$. In order to read this bit-vector sequentially you have to read $32$ bits. But if you want to, say, make an array of length $T$, this would yield an array of length $T = 2^{31} - 1 = 2,147,483,647$. To construct the array would also take $T$ time.

**Alternative representation**
You could represent integers in unary, which means that the length of the representation of the integer is equal to the value of the integer. Then you could say that the running time of the algorithm is polynomial. But this is of course not an improvement. Algorithms like this, which are polynomial in the *numeric* value of the input, are said to run in **pseudo-polynomial time**.

---

`*` Typically, integers are stored in a fixed size representation, e.g. $32$ bits or $64$ bits. I also use big-oh notation to omit the details of how to exactly get the length of the representation of the integer, or the minimum length that would be needed in order to represent an integer in binary, since I feel that it might lead to a lot of details that don't help convey the overall idea.
> 1 votes

---
Tags: complexity-theory, terminology, np-complete, dynamic-programming, polynomial-time
---


title: Why do servers use ECC memory?

text:
# Question
Title: Why do servers use ECC memory?
I understand that ECC checks for errors and corrects them automatically without the knowledge of the operating system or user. I don't understand however why servers often use ECC memory?

# Answer
> 2 votes
The idea of ECC memory is that sometimes memory bits spontaneously flip --- this is rare but happens with noticeable probability, especially if memory is large. Using ECC memory, you can recover from such errors, at a certain cost (overhead).

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Automata Theory Questions: Rule Trees, Context-Free Grammar, Proving Ambiguity
I'm currently taking a class in Automata Theory and it's kicking my butt. I have an assignment that my teacher gave me that consists of three questions. I have no idea where to start. My teacher and I have a language barrier that I can't seem to break. If anyone could help me understand how to solve the following problems or guide me in the right direction, I would appreciate it! Sorry if I write some of the symbols wrong. I will attach images of the handout as well an assignment/answer sheet he gave us on a previous assignment. Thank you!!

1. Define the language generated by the grammar $G\_c= (V\_n, V\_t, P, \delta)$ where:

* $V\_n = \\{\delta, A\\}$,
    * $V\_t = \\{0, 1\\}$,
    * $P = \\{(\delta, A0), (\delta, 0\delta 0), (\alpha A,\alpha^T \alpha \alpha^T)\\}$

Give a rule tree for one sentence of the language $L(G\_c)$ generated by the grammar $G\_c$.
2. Assume that we are given the language: $L(G\_b) = \\{0^n 1^k 0^k 1^n \mid k, n = 1, 2,... \\}$. Find a context-free grammar for this language.
3. Assume we are given the following grammar $G\_a = (V\_n, V\_t, P, \delta)$ where:

* $V\_n = \\{\delta, A, B\\}$,
    * $V\_t = \\{0, 1\\}$, and
    * $P = \\{(\delta, 0A), (\delta, 1B), (A, 1), (B, 0B), (B,1)\\}$.

Find the language $L(G\_a)$ generated by the grammar $G\_a$.

The Assignment: https://i.stack.imgur.com/E3Xqx.jpg

Previous Assignment + Answers:https://i.stack.imgur.com/ryM2Q.jpg

# Answer
(1) It's always helpful to start listing some strings to get an idea of what kind of language we accept. I'm going to be making some assumptions here, but you should verify that these assumptions are true with whoever gave the assignment (they might be bad assumptions).

$\delta$ is the start symbol. We want to derive this until we get a string of only terminal symbols, either $0$s or $1$s. What's the smallest string we can derive? Well, we can get $0A$ from $\delta$, and from $\alpha A$ (I assume $\alpha$ is any string), we can derive $\alpha^T \alpha \alpha^T$; therefore, from $0A$ we can derive $0^T 0 0^T$. Since $T$ isn't defined, I assume it's a free variable - from context, I assume an integer - which means it can assume any natural value. Therefore, we can derive $0$, $00$, ... (i.e., $0^+ = 00^\*$) from $0A$.

The next observation is that there is no way to get $\epsilon$, the empty string. Only the $A$ symbol can ever be removed, and the only productions that add $A$ also add $0$.

The final observation is that productions only add the $0$ terminal symbol, so whatever language the grammar generates, it's a subset of $0^\*$.

In summary, we know that: 1. The language contains $0^+ = 0^1 + 0^2 + ...$; 2. The language doesn't contain $\epsilon = 0^0$; 3. The language is a subset of $0^\* = 0^0 + 0^1 + 0^2 + ...$.

I'm not entirely sure what a *rule tree* would look like for a context-sensitive grammar, so someone else might need to address that. To get the string $000$ one could apply the rules $\delta \rightarrow 0A \rightarrow 0^T 0 0^T = 000$ by taking $T = 1$.

(2) Something like this should work:

```
Start := 0 Inner 1 | 0 Start 1
Inner := 10 | 1 Inner 0

```

Nonterminals are Start and Inner. Terminals are 0 and 1. Let's consider how this works: first, `Start` can generate $0^{n-1} S 1^{n-1}$ by applying the rule `Start := 0 Start 1` $n-1$ times. It can then get $0^n I 1^n$ by applying `Start := 0 Inner 1`. Next, we can get $0^n1^{k-1}0^{k-1}1^n$ by applying `Inner := 1 Inner 0` $k - 1$ times. Finally, we apply `Inner := 10` once to get $0^n1^k0^k1^n$.

(3) See the approach given for problem (1). You should find the language looks roughly like $01, 11, 101, 1001, ..., 10^n1, ... = 01 + 10^\*1$.
> 1 votes

---
Tags: context-free, automata, trees
---


title: Filing systems using index blocks

text:
# Question
Title: Filing systems using index blocks
I know that a disadvantage of the index block system is that it can be wasteful of space if the files involved are mostly small in size, as index blocks are allocated from free space as required and at least one index block is needed for each file regardless of size. On average there is ½ block wastage per file in the index block system however what I don't understand is how the index block structure could possibly be modified to reduce this wastage.

If anyone can help it would be greatly appreciated.

# Answer
> 4 votes
First of all, it is not necessarily true that on average half a block is wasted. The main reason why this is false is that for small files it might be the case the more than half a block is wasted on average. Moreover, this is your main worry regarding this wastage, since is you waste half a block per large file, the fraction of blocks wasted is actually quite small. So you have to worry mainly about small files, whose size is at most a handful of blocks, and most of all for files whose size is much smaller than one block.

Second, you're asking how the index block structure can be modified to reduce this wastage. Here it's your time to be creative. One idea is to have special blocks for storing small files. I'll let you flesh this idea out. Another idea is to allow the first block of a file to start at the middle, so that two files can share one block. Of course this becomes somewhat problematic when files are updated.

---
Tags: operating-systems, filesystems
---


# Question
Title: Help with a dynamic programming solution to a pipe cutting problem
I'm trying to complete a problem where I have to design and implement a dynamic programming solution to the following problem

> You have to cut a metal pipe into several pieces. To do so, you bring it to a company that charges money according to the length of the pipe being cut. Their cutting method means that only one cut can be made at a time.
>
> Different ways in cutting the pipe can lead to different overall total prices. For example, suppose that a pipe of length 10 meters has to be cut at 2, 4, and 7 meters from one end. There are several ways to do this. One way is to first cut at 2, then 4, and then at 7. This gives a price of 10 + 8 + 6 = 24 because the first pipe was 10 meters in length, the second was 8 meters, and the third was 6 meters in length. Another way is to cut at 4, then at 2, then at 7. This would give a total price of 10 + 4 + 6 = 20, which is a cheaper price.
>
> Figure out (a method to determine) what is the cheapest price that is possible (to make sure that the company isn't cheating you). The procedure that you write (in Java) should return a single integer, which will be the cheapest possible total cost for performing all of the cuts. Only one cut can be performed at a time, and the cost of making a cut is equal to the length of the pipe being cut (before the cut is performed).

But I'm having trouble knowing where I even need to start. If anyone could point me in the direction of where I can research similar problems or give me an idea of what I should be thinking about with this problem it would be great.

# Answer
> 4 votes
For me, it makes more sense to think about this problem in reverse. The problem is posed as a destructive process - you have 1 pipe, and you split it into many. However, in terms of the cost calculation, the reverse process results in the same answer. That is, if you take the resulting pipe segments and start gluing them back together, using the sum of the length of the two pieces you're gluing as the cost of the operation, you end up with the same cost.

So then the question becomes the following:

given a set of pipe segments, what is the cheapest order of gluing segments together until you have only one segment? This assumes a cost function where c(x1,x2) = len(x1) + len(x2).

This is trivial when you have two segments. There's only one way to glue them together, so that has to be the cheapest way.

With three segments, it starts to be a bit more interesting.

Lets say we have lengths x1, x2, and x3. We have three options for our first operation: x1 + x2, x2 + x3, and x1 + x3. No matter what values are in x1, x2, and x3, the operation after this one will cost the same. That is to say the following:

(x1 + x2) + x3 == (x2 + x3) + x1 == (x1 + x3) + x2

As a result, the cheapest way of putting the three pieces of pipe back together is going to be the way that has the cheapest first step.

Then the question becomes, which of the first steps is the cheapest?

That depends on what the values in x1, x2, and x3 are. Lets assume the three values are in ascending order. So x1 \<= x2 \<= x3. Now you can determine which starting pair is the cheapest, right? Its the pair containing the smallest values, or x1 and x2. Note that there is the possibility that two or more of the three values are the same. I'll leave it up to you to convince yourself that such a scenario is not a problem.

So we've got a solution for either 2 or 3 pieces. This should give you some insight towards a general solution.

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


title: Minimizing Cost by minimizing delay

text:
# Question
Title: Minimizing Cost by minimizing delay
There is a complete binary tree with its leaves as components of some system

The values from one node to another gives propagation time for a signal to propagate from one junction to another For the signal to arrive at the leaves at exact same time starting from the root we must add delays to some wires. The cost of adding delays into the system is given by the total amount of extra delay added to all the edges.

For example, one way to remove clock skew from the tree to the right would be to increase each edge so that it has delay 6. This has cost 44.

Second way is to raise the costs of all edges in the bottom layer to 6, all edges in the middle layer to 5, and all edges in the top layer to 4. This has cost 36.

One another way is calculate max delay and modify the bottom layer such that it has delay equal to maximum delay from the root

Is there any other way to get the best solution for minmizing cost to add delay??

# Answer
> 3 votes
You can do a lot better than a total delay of 36. In fact you can get a total delay of half that. The idea is to recursively adjust the delays from bottom up.

In your example, I'll count the edges in the bottom level starting at the left at what I'll denote by edge 1, then edge 2, and so on up to the rightmost edge at the bottom level, namely edge 8.

At the start, the component delays, reading from the left are:

> 8, 11, 8, 12, 5, 5, 7, 10

In order to make the leftmost subtree at the bottom level have the same delays, add 3 to edge 1. The next subtree after that can be made to have the same delays by adding 4 to edge 3. The subtree after that needs no adjustments, and the final subtree will be adjusted by adding a delay of 3 to edge 7.

After the first adjustments, the component delays are now

> 11, 11, 12, 12, 5, 5, 10, 10

Now pass up to the second level, where we'll have 2 subtrees. Label the second-level edges as we did, from 1 to 4. The leftmost subtree can be made to have the same times by adding 1 to edge 1, and the rightmost subtree can be similarly adjusted by adding 5 to edge 3.

After the second adjustments the delays are

> 12, 12, 12, 12, 10, 10, 10, 10

Finally, pass to the top level, where we'll have a single tree. By adding 2 to the rightmost edge, both its left and right subtrees will have the same delays, so all the leaves will be in sync.

So finally, the component delays are

> 12, 12, 12, 12, 12, 12, 12, 12

We added delays of 3, 4, 0, and 3 to the bottom level, 1, and 5 to the second level and 2 to the top level, for a total added delay of 18.

It's only slightly difficult to turn this into what's essentially a recursive depth-first traversal of the tree. Now all you have to do is convince yourself that this gives the minimum amount of added delay.

# Answer
> 1 votes
As the tag suggests, this is a classic greedy algorithm. Some notations:

* $ancestor(i, c)$ denotes the ancestor on the $i$-th level (root $R$ is at level 0)
* $delay(c)$ denotes the propagation delay from $R$ to component $c$ (without addition of any delays)
* $M = \max\_{i} {delay(c\_i)}$. In this example, $M = 12$ for component $c\_4$ (= 4 + 2 + 6)

The idea is to compute the $delay(c\_i)$ for all components $c\_i$, and then assign the difference of delays between components to edges of the tree. I'm doing this via example:

$delay(c\_1) = 8,\ delay(c\_2) = 11,\ delay(c\_3) = 8,\ delay(c\_4) = \mathbf{12}$ $delay(c\_5) = 5,\ delay(c\_6) = 5,\ delay(c\_7) = 7,\ delay(c\_8) = 10$

That means, we have to adjust the edges of the tree such that the net propagation delay of each component is 12 (= $M$)

Now, the trick is to adjust the edges starting from the top level.

* Add a delay of 1 to the left edge of $ancestor(1, c\_1)$
* Add a delay of 3 to the left edge of the parent of $c\_1$
* Add a delay of 4 to the left edge of the parent of $c\_3$

After the three delay additions (net cost = 8) to the left subtree, the propagation delay to each component is now 12.

We repeat the same steps on the right sub-tree:

* Add a delay of 2 to right edge of $R$
* Add a delay of 5 to the left edge of $ancestor(1, c\_5)$
* Add a delay of 3 to the left edge of parent of $c\_7$

Total cost = 8 + 10 = 18 of delays added to the tree, and you can verify that the propagation delay for each component is now 12, the same as $M$.

---
Tags: algorithms, optimization, greedy-algorithms
---


# Question
Title: Decidable languages and unrestricted grammars?
Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are.

We can define the decidable languages with Turing machines by saying that a language is decidable iff there is a TM for the language that halts and accepts all strings in the language and halts and rejects all strings not in the language. My question is this: *is there an analogous definition of decidable languages based on unrestricted grammars rather than Turing machines?*

# Answer
> 7 votes
A language is decidable, iff it is semi-decidable and its complement is semi-decidable. Moreover, a language is recursive-enumerable iff it is semi-decidable and thus you can find an unrestricted Grammar. Therfore:

A language $L$ is decidable iff there is both an unrestricted Grammar $G$ with $L(G) = L$ and an unrestricted Grammar $\bar G$ with $L(\bar G) = \bar L$.

# Answer
> 2 votes
There can not be a useful class of grammars for $\mathrm{R}$ (the set of recursive languages), since

* every useful class of grammars is enumerable, and
* $\mathrm{R}$ is not semi-decidable or, equivalently, not enumerable.

The first is obviously not a rigorous theorem (and can't be), it's just judgemental conjecture. The set of all grammars is enumerable, and any restriction that is not decidable is likely not very useful¹ in itself; in particular it won't be a syntactic restriction (like Chomsky's).

The second is formally true, see also here.

---

1. Of course, people have defined such restrictions, and those classes *have* their uses, but it is even hard to see whether a given grammar falls into simpler subclasses.

# Answer
> 2 votes
This question is addressed in a paper by Henning Fernau from 1994. Henning states:

> As an example, we consider the family of recursive languages. It is an open question whether there is a 'natural' grammatical characterization of this language class. As we will show in the following, any grammar family characterizing the recursive languages must have some strange properties.

We direct the reader who is curious to learn about those strange properties to the paper.

---
Tags: computability, turing-machines, formal-grammars
---


# Question
Title: why recursive languages does not come under Chomsky hierarchy?
why recursive languages does not come under Chomsky hierarchy ? why Chomsky did not classified it? any real life resemblance of recursive language something that i can connect it with like regular language are ones which needs finite memory or context free languages are those which can be parsed using single stack .something like that .

# Answer
> 2 votes
The hierarchy is defined in terms of grammars. It is still an open question whether there is a natural grammar formalism for recursive languages (check out this question), and certainly no such formalism had been known at the time Chomsky wrote his paper.

---
Tags: formal-languages
---


# Question
Title: Computer Science - System Security : How to Prove that KISS principle is Implemented in Security?
I basically have this homework question that needs me to support the below statement. Any suggestions on how i could go around proving it ?

the Exact Question was :

"The KISS principle is frequently applied in the implementation of security."

I was thinking on the line of KISS being applied on Android Pattern lock-screen as a form of security. would this be a good start ? or am i in the totally wrong path.

edit: i have changed the topic, im am studying in a computer science subject, if i am in the wrong place, could you let me know which place i should be at ? thanks in advance

# Answer
It would be easier to demonstrate the opposite by reference to http://www.cert.org/ -- there should be plenty of materials to show that people screw up security all the time. KISS is about keeping things tractable by scrupulously avoiding complexity. But we attempt secure systems on complex platforms like Windows or Unix, which is quite at odds with the KISS principle.

A "simple" implementation of security demands a simply-understood threat model, a simply-understood platform, a simply-understood development, manufacturing, and chain-of-custody model, and so forth. In the real world, these are hard problems. Practical systems need to come to grips with that and often the compromises yield vulnerabilities.
> 3 votes

# Answer
As stated, to prove that the KISS principle is frequently applied, you would need to make a study of design documents of a large number of security-related projects, and measure how often rationales mention KISS as a choice of strategy.

I suspect that this isn't what you're being asked, though — but rather, to look for evidence that KISS is a good idea for security. This would be fishing for the notion of attack surface: simpler systems have fewer opportunities for an attacker to find a flaw.
> 3 votes

# Answer
You might want to look at the recent spate of problems with SSL, across a number of implementations:

and try to figure out if the complexity of X509 and SSL played any role.
> 2 votes

---
Tags: security
---