# Question
Title: Where are the address, control and data buses on a computer
So have been reading up on data buses, address buses and control buses and I understand what they do, but am confused about where they can physically be found. Some books/sites I have found state that they are inside of the CPU, some state that they transmit data all over the computer. E.g. the control bus can send signals to any other device within the computer, but then another book states that the control bus is inside of the CPU and synchronises the components of the CPU.

Can anyone help clarify this please?

# Answer
> 3 votes
The answer is "all of the above".

There are busses all over the system, some are going to be physically internal to a CPU, others might be be between CPU and memory, but not I/O, still others might connect I/O devices (EX: The PCI bus) and others may connect all 3.

Consider what a "bus" is. I would define a bus as a group of related signals that are intended for a specific purpose. Busses usually have additional qualifiers to help identify what their purpose is and define what they actually connect with. IE: A Memory Data Bus would probably connect the data lines of a cache controller on a CPU with main memory. A Memory Address bus would probably connect the address lines. A Memory Control bus would carry control signals that signal the state of the other buses and/or provide clocks. Often these 3 functions are grouped together to define a single "bus". Sometimes the physical connections on busses are multipurpose where they are used alternately to carry memory or address information.

There are usually bus adapters that allow information to be passed between different busses in a system. These will sometimes be named something like "bridge", "bus adapter", "gateway", "Hose interface", etc. These bus adapters allow a system to pass data between busses with different data widths, clock speeds and signaling characteristics. For example a PCI bridge would connect a PCI bus to a system bus that operates at a higher frequency and may transfer data in larger (or smaller) chunks.

---
Tags: computer-architecture, cpu
---


title: Turing machine for adding numbers

text:
# Question
Title: Turing machine for adding numbers
I'm having trouble in a certain problem.

I have to write a TM that gets as an input strings $\\#x\\#y$ such that $x,y \in \\{0,1\\}^\*$, and writes to the tape the output $z\\#x\\#y$ where $z = x+y$, all in binary base 2.

The addition, and knowing where to place it is rather hard. Any tips on getting started?

# Answer
Here's a pseudo-algorithm for a possible solution. I assume you know how to implement any of the sub-tasks (as they are very common and usually given as basic examples)

1. Add a $\\$$ to the right of the input.
2. Duplicate the content of the tape $\\$x\\#y \to \\$x\\#y\\$x\\#y$
3. Add a 0 at the very start $\to 0\\$x\\#y\\$x\\#y$
4. Loop until the first $x$ is all-zero string:
4.1 Subtract 1 from the first $x$, and add 1 to the first field, moving the input if necessary.
4.2 remove the all-zero field that is now where $x$ was, and repeat step 4 with $y$.
\[Note: a better algorithm will skip 4.1/4.2 for $x$, and immediately start with subtracting from $y$, where the counter $z$ starts from $x$ rather than 0, but this is equivalent.\]
5. Clean the $\\$$ and $\\#$ as necessary, move the head to the first blank, and halt.

So the only non-trivial step is how to add 1 or subtract 1 from a given number $x$ given in a binary base 2 form. I assume you know how to perform binary arithmetic: for instance, for binary addition you add 1 to the LSB; if it was 0 you are done; if it was 1 you move on to the bit next to it ("carry") until you find a 0 or until you have passed the MSB (then you assume the digit after the MSB should be 0, move the input to accommodate that zero and add 1 to it). It is a bit of a hassle to convert the algorithm into the form of a TM, but this is basically what you are requested to do. It is possible, since TM can compute any (well-defined) algorithm that a CPU-computer can do. I'll leave you to filling up the details.
> 1 votes

---
Tags: algorithms, turing-machines, arithmetic
---


# Question
Title: Describing the asymtotic complexity of processing two-dimensional data structures
Consider the following Python function:

```
def count_chars(list_of_strings):
  chars = 0
  for s in list_of_strings:
    for c in s:  # intentionally avoiding len() here for the sake of example
      chars += 1;
  return chars

```

Clearly this is a linear operation, since we iterate over every element/character once. But I've often seen the Big-O of this function as $O(n\*k)$ where $n$ is the length of the list, and $k$ is the length of the longest string. In a sense, that's polynomial or quadratic (at a minimum, I've heard people refer to this type of algorithm as such).

What is the appropriate way to refer to this type of function? Is there an intuitive way to understand this is linear, despite multiple variables? In particular, how can we discuss that this is worse than a solution that uses `len()` (which is $O(1)$) without getting hung up on the fact that, in practice, both are linear?

---

Context: I'm posing an interview question that, while more complex than this example, involves identifying and eliminating $k$. I've had candidates struggle to see that and it's felt like a communication issue more than a understanding problem.

I'm looking for ways to help guide a discussion, and to recognize that while this is linear, it is still asymptotically worse than an operation that avoids hitting each character individually.

# Answer
The solution is that you shouldn't just ask whether it is "linear" -- ask what variable it is "linear" in.

Your example code has running time that is linear in the total length of the input strings. There's a long history of characterizing the running time of an algorithm as a function of the length of the input to the algorithm, and that's an entirely valid thing to do.

It's also true that its running time is $O(nk)$ where $n$ is the number of strings and $k$ is the length of the longest string. This might be a looser bound.

Both statements are true, and don't contradict each other. It's just a matter of identifying which upper bound on the running time is more useful.
> 6 votes

# Answer
You say it yourself: "this is a linear operation, since we iterate over every element/character once". Hence the complexity is $O(m)$, where $m$ denotes the total number of characters: this is linear in the number of characters.

It turns out that the gross estimate $m\le nk$ holds, hence the complexity is also $O(nk)$. This is linear in the product $nk$ (!) Rigorous wording could be "this is bilinear in $n$ and $k$", but this isn't used.

Now, if you freeze $n$ (actually bound it by a constant), the complexity reduces to $O(k)$, linear in the length of the longest string. And if you freeze $k$ (actually bound it by a constant), the complexity reduces to $O(n)$, linear in the number of strings. And if you freeze both, you get $O(1)$.

---

It could be more appropriate (and more accurate) to consider the average string length, let $\bar k$, with the obvious equality $m=n\bar k$.
> 5 votes

# Answer
As you say, this is a linear time function. Its running time is linear in the size of the input. Parametrizing the input in terms of the number of strings and the maximum length is suboptimal.

The solution using constant time `len` is better since it is linear in the *number* of strings rather than in the total input length, which could potentially (but not necessarily) be much larger.

A similar situation occurs in graph search algorithms, say DFS. You can state the complexity as $O(n^2)$, where $n$ is the number of vertices, or as $O(n + m)$, where $m$ is the number of edges. Since potentially $m \ll n^2$, we see that DFS is potentially much more efficient than some $\Theta(n^2)$ algorithm.

While the DFS example is artificial, exactly this situation occurs in linear algebra on sparse matrices, where naive algorithms run in $\Theta(n^2)$, and more sophisticated algorithms run in $O(n + m)$. For a dense matrix there is no difference, but for sparse matrices the latter are much faster.
> 3 votes

# Answer
This algorithm does not have linear complexity and as posed, provides (and uses) two separate variables, as you described n and k. From the candiates perspective, there is no indication that the list length or the string length is bounded in any manner.

Remember: f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

I am going to ignore the n ≥ k for the rest of this argument.

What this means is that we are defining an upper bound to the complexity for f(n) (to less than g(n)) that can only grow as a scalar multiple of c in relation to the complexity of g(n).

In your example there are two variables so any attempt to define an upper bound based on one, can easily be violated by changing the other.

The inner loop is clearly bounded by the length of the longest string O(k) which is really saying there exists constants where 0 ≤ f(k) ≤ cg(k) for all k. However, that isn't the end of the problem, there is an arbitrary number of strings in the list that violates this. Simply speaking, if the list length is greater than c then the assertion 0 ≤ f(k) ≤ cg(k) becomes incorrect. The problem is that for any c provided, defining a list length of c+1 will cause this assertion to fail. (and changing c makes it no longer a constant).

The answer is O(n\*k)
> -1 votes

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


title: What is an "encoding" of a TM?

text:
# Question
Title: What is an "encoding" of a TM?
I'm currently working on a reduction from $A\_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \\{ \langle M,w \rangle | \text{ ...etc} \\}$, where obviously this would normally stand for $M$ being a TM and $w$ being a string. However, later in the proofs, we replace the $w$ (a string) with an "encoding of a turing machine". Sometimes it's even "an encoding of the TM, $M$".

I'm rather lost on this idea. How do we pass an "encoding of a TM" into a parameter for a string? How do we run that on a TM? Maybe I'm misunderstanding the definition of an "encoding of a TM", which I assume to be the TM itself somehow converted into a string format.

Would anyone mind explaining this to me? I'm sure truly understanding this concept would immensely help me in writing further reductions.

# Answer
> 7 votes
A Turing machine $M$ can be described as a 7-tuple $(Q,F,q\_0,\Sigma,\Gamma,\delta, blank)$. This means that if someone gives you this 7-tuple, then the TM is well-defined, and you can precisely define how it behaves, etc.

The **encoding** of a TM, usually denoted as $\langle M \rangle$ is a string that encompasses all the information of the 7-tuple describing $M$. You can think of it as "writing the 7-tuple as a binary string" (but this is a simplification). So the encoding of M, is just a string that describes how the TM works.

The last observation is that if you know the encoding - you know everything about the TM; specifically, if $\langle M \rangle$ is given as an input (to a machine $M'$), the TM $M'$ can "run" or "simulate" what $M$ would have done on any given input -- the machine $M'$ knows the states $Q$ of $M$ and the transition $\delta$ of $M$, so it can imitate its actions, step by step.

# Answer
> 5 votes
Part of your confusion seems to be about the nature of $\langle\\,M\\,\rangle$. That's just a string like any other, except that it is a complete description of $M$. For example, a managable project for an introductory programming course might be to write a program which, when given an input describing a TM, shows the action of that TM on some input. What would such a program need as a description of a TM? We might decide to do something like this:

1. A list of the states, `[q0, q1, ... , qn]`.
2. A description of which states are start, accept, and reject states, `s, a, r`, where each of these is one of `q0 ... qn`
3. A list of move rules, of the form `(p, a, r, b, d)` corresponding to the move $\delta(p, a) = (r, b, d)$, i.e., in state $p$ with input $a$, change to state $r$, write $b$ on the tape, and move in direction $d$ (left or right).

With that information, the program to simulate the TM wouldn't be too hard to write. The point here is that the string

```
[q1, q2], q1, q1, q2, [(q1, 0, q1, 1, R), (q1, 1, q2, 1, L), ... ]

```

would be a complete description of a TM, suitable for use as the basis of the simulation by our assigned program. This description is what we call $\langle\\,M\\,\rangle$. Now we might further encode this in a more limited alphabet, but that's immaterial. The point is that it can be done: any TM can be described by a suitable string.

---
Tags: turing-machines, automata, reductions, encoding-scheme
---


title: Term for shifting work to idle machines

text:
# Question
Title: Term for shifting work to idle machines
I am looking for a term here. A while ago, i was told about a network in which all the computers are connected in parallel, and when a computer is idle, the central server sends heavy cpu usage tasks to that idle computer.

This is often used in pharmaceutical companies working on protein structure configurations, or as the CS community more commonly knows, the bit mining community.

Any who, i know this is often called grid computing, however there was another name for it. Scapegoating? or something like that. Not quite sure. The term has really been bugging me. Can you guys help me out?

# Answer
> 1 votes
This is called **volunteer computing**.

---
Tags: terminology, distributed-systems, computer-networks
---


title: how to prove the periodity of an LFSR

text:
# Question
Title: how to prove the periodity of an LFSR
everywhere I've searched it says that the minimal period of an LFSR given by a characteristic polynomial $c(x)$ is the least number $r \in \mathbb{N}$ that: $$c(x)|(x^r-1)$$ but how do I prove it's correctness? I've tried o prove it like that: given $c(x)$ the characteristic polynomial and $h(x)$ theinitial state polynomial, I'll denote the minimal period with $\pi$ then: $$ {h(x) \over c(x)}=G(x)= \sum^\infty\_{k=0}a\_kx^k=\sum^{\pi -1}\_{k=0}a\_kx^k(1+x^\pi+x^{2\pi}...)={\sum^{\pi -1}\_{k=0}a\_kx^k \over 1-x^\pi} $$ and I'm not sure where to go from here

# Answer
Hint: The LFSR changes its state by multiplying it by $x$ modulo $c(x)$. So if the initial state is $x\_0$, the state after $t$ steps is $x\_t \equiv x\_0 x^t \pmod{c(x)}$. In particular, $x\_t = x\_0$ if $x\_0 (x^t-1) \equiv 0 \pmod{c(x)}$.
> 1 votes

---
Tags: algorithm-analysis, proof-techniques, pseudo-random-generators
---


# Question
Title: Why is the set of all regular expressions classified as context-free, instead of regular?
As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?

# Answer
> 12 votes
Going by the OP's comments, the real question here is not the one in the title, but "Why is the set of regular expressions a context-free (rather than regular) language?"

The reason is simply the occurrence of parentheses in more complex regular expressions like $(a+b)^\*b(a+c)^\*$. In order for such an expression to be well-formed, the parentheses must be balanced properly; this is one of the classical conditions which make a language non-regular (because a r.e. which begins with sufficiently many opening parentheses can always be pumped such that it becomes unbalanced).

# Answer
> 5 votes
> As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?

No, for several reasons:

1. Don't say *regular languages can be closed under concatenation*. What does that mean? Do say *the regular languages are closed under concatenation*. That means: when you take two regular languages, their concatenation (which is the set of strings formed by concatenating the strings from the first and second language pairwise) is always a regular language. This is true.
2. Don't confuse regular languages with regular expressions. A regular expression is a way to denote a regular language. The regular language itself is not an expression, it is a set of strings. For instance, $(a^\*b)^\*$ and $(a\cup b)^\*$ are two different regular expressions. They denote the same regular language.
3. Regular expressions are strings, so the set of regular expressions is a language. What I think you're saying is that this language is closed under concatenation. That is true: the concatenation of two regular expressions is always another regular expression. However, there are infinitely many different regular expressions. Therefore, if you concatenate all of them, you get an infinitely long expression. Infinitely long strings are not considered in the language theory you're studying, so that is not something you can do. Also, concatenating strings is not the same as forming a set of those strings: when I concatenate $aa$, $bb$ and $cc$, in that order, I get $aabbcc$, which is a string; it is not the same as the set of strings $\\{aa, bb, cc\\}$, which is not a string, but a language (a set of strings).
4. The regular languages are closed under concatenation, and the language of regular expressions is also closed under concatenation; from this, does it logically follow that the language of regular expressions is regular? No, it doesn't - that reasoning would be an example of affirming the consequent.
5. The language of regular expressions is not regular. This is due to the fact that brackets must always match up, which is something regular expressions cannot express.

# Answer
> 4 votes
The regular languages are closed under finitely many applications of choice, star, concatenation. If you allowed infinitely many applications, every language would be regular since every language $L$ satisfies $L = \bigcup\_{w \in L} \\{w\\}$. I'm not sure how context-free languages come into this.

Also, what is the concatenation of all regular languages over a given alphabet $\Sigma$? If we do concatenate $\emptyset$, then we end up with $\emptyset$. If we exclude that from the concatenation, then the length of the words in the concatenation is monotonically increasing in the number of languages you concatenate, and since after each finite number of concatenations you are left with at least one language $L$ you haven't concatenated yet and which satisfies $\epsilon \not \in L$, we get that $(\circ\_{L \in REG - \\{\emptyset\\}} L ) \cap \Sigma^\*= \emptyset$. This may seem weird, but $\sum\_{n \in \mathbb{N}} n = \infty \not \in \mathbb{N}$. You might even be tempted to say $\circ\_{L \in REG- \\{\emptyset\\}} L = \emptyset$, but I'm not comfortable enough with a convergence issue here (similar to non-absolutely-convergent series, reordering the order of concatenated languages might yield different $\omega$-regular languages).

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


# Question
Title: Proving that $A=\{w_{2i}|w_{2i}\not\in L(M_i)\}$ is not Turing-recognizable
In this problem, $w\_{2i}$ is the $2i$th string in the lexicographic order of binary strings and $M\_i$ is the TM whose binary code is $w\_i$. We are given the diagonalization language $A\_D=\\{w\_i \mid w\_i \notin L(M\_i)\\}$. We know $A\_D$ is not Turing Recognizable.

Basically, $w\_i$ is the $i$th string in the following lexicographic ordering: $\epsilon, 0, 1, 00, 01, 10, 11, ...$

The proof for $A\_D$ is the following: Suppose by contradiction, there is a TM $M$ such that $A\_D = L(M)$. Then $M=M\_i$ with code $w\_i$ for some $i$. $w\_i \in A\_D$ iff $w\_i \notin L(M\_i)$ by definition of $A\_D$. $w\_i \in A\_D$ iff $w\_i \in L(M\_i)$ by $A\_D = L(M\_i)$. A contradiction.

The problem is I don't understand the proof above. Therefore, I have no idea how to approach the topic question. It would be very helpful if someone can give a brief explanation of how $A\_D$ proof works and what approach I can take to prove $A$ is not Turing recognizable. For instance, is it possible to reduce $A\_D$ to $A$? Or is it better to follow the same proof format as $A\_D$?

# Answer
> 0 votes
1. Lets reformat your language $A\_D$ to say $A\_D=\\{ \langle M \rangle| \\; \text{M is a Turing machine ( TM ) and does not accept }\langle M \rangle\\}$. Here $\langle M \rangle$ means encoding of Turing machine $M$, and I assume the inputs are always valid encodings TM's ( as you can always check if a string is a valid encoding or not ). Now say there was a decider for $A\_D$, let it be $D$. Now if you give input $\langle D \rangle $ to $D$ it has to halt ( we assumed it is a decider ) and either reject or accept. If it accepts it, it means $\langle D \rangle \in A\_D$ and thus $D$ does not accept $\langle D \rangle $, which is a contradiction. If $D$ reject $\langle D \rangle $ it means $D$ accepts $\langle D \rangle $ acccording to definition of $A\_D$ which again is a contradiction. Either ways it is a contradiction, thus our assumption that $D$ exists is not correct and $A\_D$ is undecidable ( this proof is related to Cantor's diagonal method ) .
2. This logic cannot be applied to prove $A\_D$ is not Turing recognizable. I leave the reason for you to figure out ( hint: no assumption about halting on all inputs is made ).
3. I will prove non recognizability of a general language ( which implies undecidability ) instead of $A\_D$ and the one you specify in your question.

$L=\\{ w | \\; f(w) \\;\text{ is a valid encoding of some Turing machine where } f \\; \text{is some computable function and the Turing machine given by } \\; f(w) \\; \text{does not accept} \\; w\\}$
( $f$ is such that for every TM encoding $\langle M \rangle \exists w $ s.t. $ f(w)=\langle M \rangle$ )
Now suppose $L$ was Turing recognizable, let the TM be $R$. We construct another Turing machine $H$ which given an input $w$ first finds $f(w)$ ( again assuming it is a valid encoding of a TM, if not $H$ can directly reject ). Then $H$ gives $w$ to $R$ and simulates $w$ on $f(w)$ in parallel. If $f(w)$ accepts $w$ $H$ rejects, if $R$ accepts $w$, H accepts. This way you are able to decide language $L$ which is undecidable. You can prove $L$ is undecidable yourself ( see when $f$ is the identity function, $L$ reduces to $A\_D$ which is undecidable ).
I leave it for you to figure out how non recognizability of $L$ can be used for proving that of your languages.

---
Tags: turing-machines
---


# Question
Title: Approximate Subset Sum with negative numbers
I am interested in the approximation version of the Subset Sum problem with negative numbers. Wikipedia says there is an FPTAS algorithm for SS. That Wikipedia page states:

> If all numbers are non-negative, the approximate subset sum is solvable in time polynomial in N and 1/c.

Similarly, in the CLRS version of the algorithm, the numbers are required to be positive. For the exact version there is this reduction that makes all numbers positive but I believe that it cannot be applied to the approximation version. Because the approximation algorithm behaves differently for larger numbers it would not give the same results if instead of -10 I have 10000. The trim function would cut a lot more numbers in the new, all positive version than in the original.

My question: Is there a FTPAS for General-SS, as defined below?

General-SS:
Given an input set $S=\\{a\_1,\dots,a\_n\\}$, where $a\_i$ are possibly negative numbers, and a target $C$ find a subset $S'\subseteq S$ that sums to $C$.

All-positive-SS (defined below) has an FTPAS. Does this algorithm remains an FPTAS for General-SS?

All-positive-SS:
The same as General-SS, but where we restrict $a\_i\geq 0$.

Alternatively, if we transform General-SS to All-positive-SS with the above reduction and then run the FPTAS algorithm for the new instance, does this also give an FTPAS for General-SS?

# Answer
> 2 votes
I believe the issue is with the definition of approximation.

Let's assume that we want to find a subset that sums to $C=0$. Then the approximate subset sum problem determines whether or not there is a subset within $(1-c)C$, which is just $0$.
Thus "approximate" subset sum is exactly subset sum if there are negative numbers (and thus can't be solved in polynomial time).

You can demand that the target value $C$ is nonzero, but this is insufficient---if $A$ is integral, then if $C = 1$ we can set $c = 1/2$ and again our algorithm is forced to obtain an exact answer. In fact, $C$ must be more than polynomial to avoid a contradiction. Thus, previous work has simply assumed a positive $A$, and we get a nice definition for what we want.

Note that if $A$ is positive, the interesting $C$ are very large, whereas with possibly-negative $A$ they may not be. This is part of the reason that positive $A$ is a sufficient condition for interesting approximation algorithms.

On the other hand, positive $A$ is probably not quite necessary. It is possible that one can limit $C$ and $A$ in such a way as to ensure that the problem is interesting even for possibly-negative $A$. Looking at the reduction, it seems that $C \>\> NM$ may do the trick (if $M$ is the absolute value of the smallest negative number in $A$); particularly if $C$ is exponential in $N$, and $M$ is polynomial (in other words, the negative numbers of $A$ are all very small). But at first glance, this seems to add complexity to the analysis without gaining much in return. Also, more work would have to be done to make sure this matches the approximate subset sum definition correctly.

---

As for the reduction: that reduction as-is does not work well if the goal is $C = 0$. Let's say, for example, that you start with a possibly-negative set $A = \\{a\_1,\ldots,a\_N\\}$, where the largest negative number is $\geq -M$, for a large positive $M$. We want to find a subset that sums to 0. Then, as per the reduction you cited, we construct $A' = \\{a\_1 + M,\ldots, a\_N + M, M, \ldots, M\\}$ with $N$ copies of $M$. We want to find a subset that sums to $NM$. This can trivially be accomplished by taking the $N$ copies of $M$.

Even if $C\neq 0$ this reduction doesn't work quite the way we would (probably) want. We obtain a solution within $\[(1-c)(NM + C),NM+C\]$. This may be significantly different than a solution within $\[(1-c)C,C\]$ for the original problem. However, as noted above, if $C \>\> NM$ this is somewhat close to a $(1-c)$ approximation ratio. We would need to be careful about solutions within $\[C,NM+C\]$, however.

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


# Question
Title: Dempster-Shafer theory initial belief values
I am looking to implement D-S Theory in my (computer science) research, I'll be using it to determine the probability that a triggered sensor event is a true positive.

How would you calculate an initial belief value without having the ability to perform data mining on a dataset (a cold start)?

One solution that has been postulated is to use the manufactures performance statistics that the sensors are working correctly and then adjust this over time to take account for false positives. Although this will result is a very high initial belief rate for some sensors (95% belief).

# Answer
> 0 votes
If the 95% (initial) belief corresponds to the probability of a true positive according to the performance statistics, then that seems appropriate to me.

---
Tags: probability-theory
---


title: Horn clause for the following formula

text:
# Question
Title: Horn clause for the following formula
Let be

$$F=A\land (\neg A\lor B)\land(A\lor \neg C)\land(\neg A\lor\neg B\lor D)\land(\neg A\lor\neg B\lor\neg C)$$

a formula. Is $F$ satisfiable?

Well, firstly, I've put $F$ into another form:

$$F\equiv (1\to A)\land(A\to B)\land(C\to A)\land(A\land B\to D)\land(A\land B\land C\to 0).$$

Then, I've started with HORNSAT:

* Mark $A$, because of $1\to A$.
* Mark $B$, because of $A\to B$.
* Mark $D$, because of $A\land B\to D$.

How can I go on?

# Answer
> 0 votes
Are you sure you want to prove that $F$ is *valid* and not that it is *satisfiable*?

By "$F$ is valid" we mean that $F$ holds true under all truth assignments of its propositions. Just by looking at the 1st conjunct, it seems that if $A$ is false, already $F$ does not hold true.

---
Tags: algorithms, logical-validity
---


# Question
Title: Context-free languages not closed under making them "extension-free"
For a language $L$, define: $$ NE(L) = \\{x \in L : x \text{ is not the proper prefix of any string in } L\\} $$

I'm trying to show context-free languages are *not* closed under this operation. I've been struggling for a long time now trying to find a counterexample, that is, a language $L$ such that $L$ is context-free but $NE(L)$ is not context-free, and have come up with nothing. I'd appreciate ideas or hints about languages to look into.

Edit: For the vast majority of context-free languages, it seems that either $NE(L) = L$ or $NE(L) = \varnothing$. I'm having trouble even finding candidate languages.

# Answer
> 6 votes
Rather than the language $L\subseteq \Sigma^\*$ consider the language $L' =L\\$\\$$, so concatenate every string by two copies of $\\$$ where $\\$$ is a new symbol not in $\Sigma$.

Let $x\in \Sigma^\*$. String $x\\$$ is not a proper prefix of $L'$ iff $x\\$\\$ \notin L'$ iff $x\notin L$.

That should start you going.

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


title: Proof of APSPACE = EXP

text:
# Question
Title: Proof of APSPACE = EXP
I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book.

Please give a semi-detailed proof of this. I have found a paper which has this proof(by Chandra, Kozen et al.) but found it too hard to understand.

# Answer
> 6 votes
I Asked this once and my post was closed. I remember saying i have no idea, and i'm in need of some enlightenment. Eventually i found the solution somewhere and i think that my problem was that i was not as comfortable as i thought with the ideas appearing in the proof of the Cook-Levin theorem.

The interesting direction is $EXP\subseteq APSPACE$. Let $L\in EXP$ be some language decidable in $2^{n^c}$ time, i.e. there exists a Turing machine $M\_L$ which runs in $2^{n^c}$ time deciding $L$.

For any input $x$, we can look at the $2^{|x|^c}\times 2^{|x|^c}$ computation table of $M\_L$ on x. The i'th row describes the $i'th$ configuration during the computation: $\sigma\_1\sigma\_2...\sigma\_i q\sigma\_{i+1}...\sigma\_{2^{|x|^c}}$, where $\sigma\_i\in \Sigma\cup \Gamma, q\in Q$. This means that at the $i'th$ step $\sigma\_1...\sigma\_{2^{|x|^c}}$ is the content of the working tape, we are at state $q$, and the head is at the symbol appearing after $q$ (we should also include the input somewhere, but specifics don't really matter here).

We denote by $C\_{ij}$ the content of the cell in the $i'th$ row and $j'th$ column in the computation table of $M\_L(x)$.

Our APSPACE machine will be able to decide whether or not $C\_{ij}=\sigma$ (then you can go over the last row and check if $q\_{acc}$ is written somewhere). Note that the index $i$ can be written in polynomial number of bits.

As in the Cook-Levin theorem, the important fact is that computation is local. The value of $C\_{ij}$ is determined by the values $C\_{i-1,j-1},C\_{i-1,j},C\_{i-1,j+1},C\_{i-1,j+2}$, say by some known function $g$ ($g$ of course depends on the transition function of $M\_L$), meaning:

$\forall \sigma\in\Sigma\cup \Gamma\cup Q: \hspace{1mm} C\_{ij}=\sigma \iff \exists \sigma\_1,\sigma\_2,\sigma\_3,\sigma\_4: \hspace{1mm} C\_{i-1,j-1}=\sigma\_1 \land C\_{i-1,j}=\sigma\_2\land C\_{i-1,j+1}=\sigma\_3 \land C\_{i-1,j+2}=\sigma\_4 \land \sigma = g\left(\sigma\_1,\sigma\_2,\sigma\_3,\sigma\_4\right).$

To decide whether $C\_{ij}=\sigma$, **under existential quantifiers**, nondeterministically guess $\sigma\_1,\sigma\_2,\sigma\_3,\sigma\_4$. Verify that $\sigma = g\left(\sigma\_1,\sigma\_2,\sigma\_3,\sigma\_4\right)$, if not reject.

The next step is to verify recursively that $C\_{i-1,j-1}=\sigma\_1 \land C\_{i-1,j}=\sigma\_2\land C\_{i-1,j+1}=\sigma\_3 \land C\_{i-1,j+2}=\sigma\_4$. Let us denote by $S\_i$ the space used by our machine, when it begins with the i'th configuration (i.e. verifying $C\_{ij}=\sigma$ for some $j,\sigma$). Even if we use the same space for all four calls, you get $S\_i=S\_{i-1}+poly(|x|)=...=2^{|x|^c}poly(|x|)$. This happens because we keep a call stack (we dont overwrite the current frame), to overcome this:

**under universal quantifiers**, write nondeterministically $\left(J,\sigma\_J\right)\in \left\\{\left(j-1,\sigma\_1 \right),\left(j,\sigma\_2 \right),\left(j+1,\sigma\_3 \right),\left(j+2,\sigma\_4 \right)\right\\}$ (suppose for simplicity that your machine has four transition functions), and output "yes" if $C\_{i-1,J}=\sigma\_J$.

The universal quantifiers allowed us to compute the conjunction of four recursive calls simultaneously, thus we dont need to keep a call stack. In that case, in all times we need only remember $i,j,\sigma$, which requires polynomial space (in the recursive call for $C\_{i-1,J}$, we use the same space that was used to store $i$).

# Answer
> 5 votes
The proof is very similar to the proof that ALOGSPACE=P, given for example in these lecture notes (in fact, you can probably derive APSPACE=EXP from ALOGSPACE=P by padding). For your convenience, here are the main ideas.

APSPACE$\subseteq$EXP: Consider some machine operating in alternating space $s$. The machine has $2^s$ configurations, and we can ensure that no run involves a repeated configuration. Construct a circuit which corresponds to this computation. The vertices are the individual configurations, and these are annotated by AND or OR according to the player in charge (its a DAG since no configuration repeats). This circuit has exponential size and so can be evaluated in EXP.

EXP$\subseteq$APSPACE: Consider some machine operating in exponential time. Represent its computation as a uniform circuit of exponential size. Note that the *name* of a node takes up only polynomial space. Convert the circuit into an alternating machine in the natural way. This machine only needs space to store one or two nodes.

---
Tags: complexity-theory, time-complexity, complexity-classes, space-complexity
---


# Question
Title: Hash Table: Relation between position of a value and Hash table size
I need to know whether hash table size, $S$ has any impact on distribution of a value in hash table.

At the moment I'm using SHA512 and I can tolerate up to 50 elements in any bucket, and I have $10^6$ elements; I set hash table length to $S=50000$. This is far more larger than what is suggested in the literature \[1\]. However, if I reduce the table length I would get overflow (as I have tested and saw it).

To find position of an element in hash table I do $hash(val) mod S$.

---

**Question:** Does $S$ play any role in distribution of the value in hash table? In other words, do I need to set $S$ as a prime number or power of two ?

---

\[1\]. http://www14.in.tum.de/personen/raab/publ/balls.pdf

# Answer
> 1 votes
An an ideal world - the answer is **no**. (but life is not ideal..)

In an ideal world, a hash function can be imagined as a random function, that takes a random input $x$ to a random place in $S$, uniformly distributed. In this case, the size of $S$ doesn't change the distribution -- any item is always uniform over $\[1,...,S\]$, no matter what $S$ is.
(Of course, a smaller $S$ will mean more collisions, but I think you understand that part).

However, in the real world, it matters how things are implemented. For instance, you say that use SHA512, and I assume your output is 512 bits (but it doesn't matter if you use a smaller digest size). This means, that (assuming SHA is closed to being ideal), that any item is sent to a uniform location over $\[1,...,2^{512}-1\]$. But your $S$ is smaller, say, $S=5000$. How do you "fold" the hash output into $\[1,...,S\]$? This transformations changes the distribution over $\[1,...,S\]$ and it may not be uniform anymore (unless you carefully choose $S$ and carefully make this transformation "balanced"). For instance, if $S$ is not a power of 2, some locations will be more probable than others: simply because of the pigeonhole principle, any transformation from $\[1,...,2^{512}-1\]$ to $\[1,...,S\]$ cannot be (perfectly) balanced.

# Answer
> 3 votes
No. If you use SHA512, you can use any modulus $S$ you want: it doesn't need to be prime. A power of two is fine and is no better or worse than a prime.

The reason is that the cryptographic properties of SHA512 ensure that the output of SHA512 is (for all practical purposes) essentially a uniformly random 512-bit string. Because $2^{512}$ is so much larger than your modulus, after reducing modulo $S$, the result will be approximately uniform. Any non-uniformity will be incredibly, exponentially small: so small that it's not detectable within your lifetime, or the lifetime of the solar system. (I know there's another answer that claims non-uniformity is a problem, but that answer failed to quantify the extent of the non-uniformity and thus came to the wrong conclusion; the amount of non-uniformity is so exponentially small that it's completely irrelevant in practice).

So, go ahead and use any modulus that's convenient. It doesn't need to be a power of two or a prime number, if you're using SHA512 as your hash function.

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


# Question
Title: Automaton for 'almost' same word in language
I have some finite language L, which is regular.

I want to find a finite automaton (DFA/NFA) that for every word w in L, it accepts any word with the same length but only with 1 char diffrence.

I thought about maybe accept DFA for L, because it a regular language and think about an NFA solution, but my problem is those possible "circles" in the automata..

Any idea?

# Answer
Main Idea:
Construct two copies of the DFA for $L$. The first copy will be connected to the second copy by moves that will allow the "difference" of a single letter. For example, if $q\_1$ and $q\_2$ are connected by a $0$-move in the original DFA, then $q\_1$ in the first copy will be connected to $q\_2$ in the second copy by a $1$-move.
> 5 votes

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


# Question
Title: Is the complement of { www | ... } context-free?
Is $\left ( 0+1 \right )^{\ast }-\left \\{ www : w \in \left \\{ 0,1 \right \\}^{\ast } \right \\}$ context-free?

If it is what is a grammar generating it?

# Answer
Here is an idea for you to elaborate on. \[*Edited after Hendrik's comment:*\] But maybe the idea does not work so well.

Call your language $L$ and consider $L'=L\cap 0^\*10^\*10^\*10^\*$. When does a word $w$ of the form $0^a10^b10^c10^d$ belong to $L'$? When $2a\not=b\lor b\not= c\lor c\not=2d$. It seems difficult for a pushdown automaton to read $w$, compare $2a$ with $b$ and then remember enough of $b$ to compare it with $c$. What should one conclude ?!

When trying to show that a language is not context-free, intersecting with a regular language is a *reduction* that often permits simpler ways of showing what is not context-free in the language at hand. Without such reductions using the pumping lemma can be unnecessarily painful.
> 1 votes

# Answer
What @Raphael says and the following diagram, with $a\neq b$.

But let me be more precise. A string is *not* of the form $www$ if either its length is not divisible by three or, when it is of length $3n$, then there are two positions exactly $n$ apart that have different letters. Hence the following diagram.

$\underbrace{\dots a}\_k \\; \underbrace{\dots\dots\dots b}\_n\\; \underbrace{\dots\dots\dots\dots\dots}\_{2n-k}$

To get a language like this we have to do two things: get the lengths of the three segments right, and synchronize the $a\neq b$. As a first step towards a grammar I would consider the segment lengths, and study a related language: $K= \\{ a^k b^n c^m \mid m+k=2n \\}$. That is, for each $b$ write two $a$'s or two $c$'s, or if these numbers are odd, add one each.
> 0 votes

---
Tags: formal-languages, context-free
---


# Question
Title: How are variables accessed in the correct order from the stack?
I'm learning about the stack but one thing I am unable to understand is how variables can be accessed in the correct order.

So if I had a basic program calculating the sum of some user entered values (pseudocode)

```
Input value1
Input value2
Input value3
Input value4
Input value5
result = value1 + value2 + value3 + value4 + value5

```

Am I correct in thinking the variables value1 through to 5 would be stored in the stack? If so this means that value 5 would be the first out for the next section but since my program needs value1 first how does it get this value? (assuming a simplistic computer with minimal registers).

# Answer
> 3 votes
That depends on how your program is written, its language, and how exactly your compiler implements variables. Some languages just don't place variables on any stack (everything is global). This is how FORTRAN and early versions of BASIC used to work. "Normal" languages (like C, Pascal and such) allocate a structure (often called *activation record*) on the stack, containing space for the local variables, and use architecture-dependent (and compiler-dependent) code to get at the variables. Many scripting languages will have the variables handled by allocating space elsewhere and just linking to the values from an activation record-like place in the stack. Even other languages, particularly LISP-derived ones, don't enforce the last call done -- first call finished rule, and thus can't use a stack for activation records. As @YuvalFilmus comments, there are languages like FORTH around, where it is *your* responsibility to manage such details.

# Answer
> 3 votes
This stack here is different from the data structure: you *can* access every element (typically). The stack is just a piece of memory the compiler uses with a certain structure; it's a stack of frames, one for each (nested) method call. Inside each frame, we don't have a stack.

The compiler knows, at compile-time, the offset for every variable from the top-of-the-stack pointer (i.e. its position in the stack frame) -- because it defines it. So the compiler has no trouble at all writing code to access whichever variable is needed.

The details depend, of course, on the compiler (and thus, indirectly, on source and target language/platform). There also *are* (virtual) stack machines on which you have to work differently, e.g. the JVM.

# Answer
> 1 votes
When performing reverse engineering on a software created by a compiler such as C or C++, we can see how the stack is manipulated.

Before calling a function, each parameter value is pushed on the stack. The function is then called with the instruction "CALL" which perform two operations : it push the current instruction pointer on the stack, then perform a "JUMP" by over-writing the instruction pointer with the address of the function.

The first operation performed when entering a function is to add a specific constant to the stack pointer. The constant is equal to the number of bytes needed by all the local variables. Adding a constant is like performing a number of pushes all at once. This is a very efficient way to reserve a frame on the stack. However, it does mean that local variables are not initialized before they are first used.

Every part of the function which needs to access a local variable will use an indexed instruction. In other words, it can read/write any variable without first pop-ing any value from the stack.

In the case of x86 processor, since it lacks instructions to access the stack pointer, the convention is to copy the value of the stack pointer to another register, EBP, which does have indexing address mode. The register EBP is copied before reserving the space for the local variables. The beauty of this convention is that all parameters are using positive index values and all local variables are using negatives values.

Final remark: when a compiler uses aggressive optimization techniques, the reverse engineered code may be very hard to understand. For example, if a local variable is used only near the top of a function, the compiler may pop it out. After executing that line, the index value used is adjusted to take account of the updated stack pointer. Another optimization which makes lots of sense is for the compiler to use a register for some local variable instead of reserving space on the stack. The reverse engineered code would show that the index used on the stack would effectively have values not assigned to some local variables.

---
Tags: compilers, memory-management, stacks
---


title: How do neural networks learn concepts?

text:
# Question
Title: How do neural networks learn concepts?
I've been learning neural networks and some back propagation stuff, and I heard about google's Tensorflow and how it could learn things like how to carry on conversations. It got me thinking about how someone could give a computer data so that it could learn how to do that. So I was trying to figure out how you could teach a computer something like how to round a number to the nearest ten if a neural network can only output a number between 0 and 1. My question is how does someone teach a neural network concepts such as rounding a number to the nearest ten. For example how would you give a neural network data so that it could solve...

> What is 47 to the nearest 10?

The answer is obviously 50. Another example also having to do with math is teaching a computer the concept of PEMDAS (Order of operations).

The answer I am looking for would be basically the steps for training neural networks to understand for example how to round numbers to the nearest ten.

# Answer
Computers don't learn - they compute. They are given a set of instructions and generally follow those instructions to the letter, with the occasional blue screen of death.

The computer uses an algorithm that is developed to solve a particular problem. The algorithm will iterate on a problem using the criteria and input data it is given. As the algorithm progresses it's internal state is modified in some way, which you could say it is "learning", based on however it is processing of the data.

So in the case of learning how to do basic math - the network would have to be given the input of the numbers and operations, it would need to be "trained" on how to use them, and then given data to operate on.

The problem with that is... computers are really, really good at doing basic math - it's pretty much what they are designed for doing, but they are not good a "learning" things, because deep down they are just build to move the ones and zeros around really fast.

What could be more useful is to train the network to try and understand if a question is a math question or not, e.g "what is one plus one" vs "is that a banana over there", and/or do natural language processing on it to determine the logic of the problem, resolved as a trivial problem for a computer "1+1=?".

i.e. the actual math itself is the easy bit for the computer - processing understanding how you are phrasing a question is what the network would need to do.

And the answer of course is 42.
> 2 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks
---


# Question
Title: How exactly the "load word" instruction loads from RAM?
PS: MIPS architecture

This is a model of a memory RAM of 4GB: it has 4,294,967,295 addresses, and each address has 32 bits. Can somebody tell me why the **load word** instruction needs an offset to the address? My book says that the offset must be multiplied by 4, but for me, I could simply give the address of the array, and then specify which word I wanted to load by saying that the first word is the number 1, the second is the number 2...

So why I need to multiply the offset?

**Update:**

My book says MIPS architecture adresses bytes, not words like I thought. So... wtf? So each address of a memory RAM stores only 8 bits? Does it means that when I access a 32bit address of the RAM via the bus, the RAM outputs just 8 bits data through the same 32 bit BUS? Then,the load word instruction would have to access the RAM 4 times just to transfer the entire word to the register. I don't understand it.

# Answer
> 4 votes
Responding only to your UPDATE: MIPS always had load/store byte. The original models may not have allowed unaligned word accesses. Load byte is (relatively) easy on a 32-bit bus. For example, you could fetch the entire word from memory (by setting the bottom 2 address bits to "0") and then add a little circuit so that when the word reaches the processor you use the bottom 2 address bits to shift and mask the correct byte into the destination register.

Store byte is somewhat more complicated. At the beginning of the store-byte operation the processor shifts the byte into the desired position in the 32 bit word, and then sends the entire 32-bit word along with the entire address (including the 2 low-order bits) to the cache. The cache uses the 2 low-order bits to control which bytes do and do-not get written. (The cache has such control (at the word level) anyway, since typically the SRAM array is something like 256x256 bits (= 8Kbytes) or 512x512 bits (= 32Kbytes).)

The only recent architecture I can think of that didn't include load/store byte instructions was the DEC Alpha 21064 (released 1992). Instead they added a lot of special bit shift-and-mask operations to extract bytes from words. If you needed to store a byte on the 21064, I think you may have had to load the word that contained the byte, shifted and masked in the byte that you wanted to write, and then write back the entire word.

They added load/store byte instructions in the 21164A (released 1996) because the extra instructions to do all that extra work in software were making the instruction cache less effective than it should have been for programs with a lot of byte operations.

# Answer
> 1 votes
If every byte has an address, virtual word adresses ("load the 10th word!") have to be translated into byte addresses ("load the word starting at the 40th byte!"). If you don't do this, you'll load from the middle of the third word (which contains the tenth byte).

You can still load four bytes at once, that is the whole word if the base address was properly chosen. The CPU will just get four bytes starting from the address you give, no questions asked.

Whether you allow for individual bytes to be loaded is mostly a design decision; I think x86 has such instructions but MIPS does not.

# Answer
> 1 votes
Normally, you would not need to worry about the specific restrictions imposed by the MIPS processor. When defining an array, the compiler perform the multiplication automatically. The compiler/linker would also make sure that the start address of the array is aligned the way the processor need.

However, if you need to understand the details because you are working with the hardware engineer to bring up a new board or you encounter some exceptions related to memory alignment or you just like to know how it work "under the hood", then you may enjoy to read the following.

It is a convention for many processors to define any address in bytes even if every instruction only deal with words.

Let's look at the hardware side relevant to your question. A very common configuration is defined as follow:

data bus (words size): 32 bits

address bus: 30 bits

On the schematic, or when looking directly at the PCB, it can be seen that 32 distinct pins on the CPU are connecting to the RAM for the data bus. As for the address bus, only 30 pins are used. If the processor can connect directly to DRAM, the address bus will actually use only 15 pins, as the bus is multiplexed.

When reading a half word or a byte, the processor actually read all 4 bytes, then it select the appropriate part of the 32 bit value based on the value of A1-A0. We need to remember that the two least significant bits, A1 and A0, do not appear on the actual address bus.

Even if the RAM is using a 32 bit data bus, it allow to write only one byte at a time by using 4 distinct write enable pin. The processor will normally set all 4 write enable to "active" when writing a word. It will set only two of the four write enable when writing a half-word, 16 bits. Finally, only one of the four write enable line will be set to active when writing a byte.

Brief, any 32 bit address inside the processor can effectively appear almost as is on the address bus. More specifically, the 30 most significant bits A31-A2 do appear as is while A1-A0 is kept internally. These 2 bits will determine the value of the 4 write enable signal when writing to RAM.

The multiplication by 4 specified in the MIPS documentation has for effect to uset the 30 most significant bits of the address, A31-A2 while leaving the two least significant bits, A1-A0 to the binary value '00'. In binary, multiplying by 4 is actually shifting the value left by 2 bits.

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


title: Variations of Greedy Algorithm

text:
# Question
Title: Variations of Greedy Algorithm
What is the definition of an "orthogonal greedy algorithm"?

What is the definition of a "relaxed greedy algorithms"?

Can you give an example to illustrate how these notions differ from ordinary greedy algorithms?

Wikipedia's article on greedy algorithms says:

> There are a few variations to the greedy algorithm:
>
> * Pure greedy algorithms
> * Orthogonal greedy algorithms
> * Relaxed greedy algorithms

Wikipedia does not explain further or provide any examples, so it's not clear what the Wikipedia article is referring to.

# Answer
> 1 votes
I have no clue what these various types are. You might want to ask the Wikipedia author who added these types, Wleizero. I can add to the list other types, such as *double greedy algorithms*, *randomized greedy algorithms*, *reverse delete algorithms*, and probably many more.

There are several *frameworks* for greedy algorithms which might interest you, for example *priority algorithms* studied by Allan Borodin and his coauthors. However, a laundry list of algorithms does not make a classification. I suggest you just ignore this list of types.

---
Tags: algorithms, terminology, greedy-algorithms
---


# Question
Title: Efficient algorithm for rectangle containment
Given a set of $n$ intervals on a line, there is a $O(n \log n)$ algorithm to find intervals which are contained in other intervals (e.g., Manber, "Using induction to design algorithms", 1988). Is there a $O(n \log n)$ algorithm for axis-aligned rectangles in higher dimensions?

I did some search on the internet, and tried to think about it myself, but could not find a generalization for higher dimensions. For example, given $n$ axis-aligned rectangles on the plane, the task is to find which rectangles are contained in other rectangles.

# Answer
Have you considered multi-dimensional indexes? They are usually quite efficient to find overlapping or included rectangles.

I personally wrote a kind of prefix-sharing binary quadtree: Java sources It has an API for rectangles with a special method for searching rectangles included in another rectangle: `PhTreeSolidF.queryInclude()`.

I'm not sure what the complexity is but it's roughly something in the order of O(n\*k\*log n) to build the tree and O(k\*log n) for each query (k is the number of dimensions). For strongly clustered datasets it may even become something lose to O(1) for each query (I tested this with n=10.000.000 and 2\<=k\<=15).
> 2 votes

# Answer
there is a natural extension/ generalization of range searching for axis-aligned rectangles and higher dimensional hypercubes.

the problem reduces to checking range inclusion on each axis separately and then finding the intersection of the rectangles or hypercubes that "own" each 1-d range inclusion. it takes k\*O(f(n)) where f(n) is the time to check a single dimension and k is the number of dimensions. this is based on the simple idea that for axis aligned rectangles/ hypercubes, a hypercube is in another hypercube iff all its separate sides are also. this does not determine merely *overlapping* axes-aligned rectangles/ hypercubes although a similar algorithm can do so.

am not aware of this published in the literature but its not complex and presumably it is cited somewhere at least in passing. the literature on this subject generally works with Kd-trees or quadtrees (2d case) and falls in the general category of database range query/ searching. the approach there would generally be to allow general geometric objects to be defined such as polygons and then find all the nodes in the Kd that the polygon overlaps with and do the range computation over all the nodes of the polygon(s) to determine intersections.
> -1 votes

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


# Question
Title: Sum of heights in a complete binary tree (induction)
I need to prove the following statement using induction on the number of nodes in the tree:

The sum of heights of a complete binary tree is $\theta(n)$.

Note: I've tried proving this using mathematical sums. I did manage to show that the sum of heights (lets call it $sum(n)$) is in fact $sum(n)≤c\_1n$ for some $c\_1$. But, I couldn't show the lower bound ($sum(n)≥c\_2n$ for some $c\_2$).

The base case is a complete binary tree, with 3 nodes in the height of 1.

The assumption is that for a complete binary tree $T$ with $n$ nodes $sum\in\theta(n)$

I got stuck when i got to the phase of the step. My intuition is to add to the tree another depth of leaves and to prove for the new tree.

Can someone explain how to complete this step?

# Answer
A *complete* binary tree of height $h$ has exactly $2^{h-k}$ nodes of height $k$ for $k=0,\ldots,h$, and $n=2^0+\cdots+2^h = 2^{h+1}-1$ nodes in total. The total sum of heights is thus $$ \sum\_{k=0}^h 2^{h-k}k = 2^h \sum\_{k=0}^h \frac{k}{2^k} = 2^h \left(2 - \frac{h+2}{2^h}\right) = 2^{h+1} - (h+2) = n - \log\_2 (n+1). $$

---

The answer below refers to *full* binary trees.

I'm assuming the following definition of *height*. The height of a tree is the length of the longest root-to-leaf path. The height of a vertex in a tree is the height of the subtree rooted at this vertex. Denote the height of a tree $T$ by $h(T)$ and the sum of all heights by $S(T)$.

Here are two proofs for the lower bound. The **first proof** is by induction on $n$. We prove that for all $n \geq 3$, the sum of heights is at least $n/3$. The base case is clear since there is only one complete binary tree on $3$ vertices, and the sum of heights is $1$. Now take a tree $T$ with $n$ leaves, and consider the two subtrees $T\_1,T\_2$ rooted at the children of the root, containing $n\_1,n\_2$ vertices, respectively. Suppose first that $n\_1,n\_2 \geq 3$. Then $$ S(T) = h(T) + S(T\_1) + S(T\_2) \geq 1 + n\_1/3 + n\_2/3 = n/3 + 2/3 \> n/3. $$ If (say) $n\_2 = 1$ then $$ S(T) = h(T) + S(T\_1) + S(T\_2) \geq 1 + (n-2)/3 = n/3 + 1/3 \> n/3. $$ This completes the proof.

The **second proof** proceeds by bounding the number of leaves in a complete binary tree. Order the children of every node so that it has a left child and a right child. Exactly half of the leaves are left children. Each left child has a different parent, and in particular each left leaf has a different parent. So a tree $T$ with $f$ leaves has at least $f/2$ non-leaves. In particular, the total number of vertices $n$ satisfies $n \geq f + f/2 = (3/2)f$, so that $(2/3)n \geq f$ and so $n-f \geq n/3$. We conclude that $S(T) \geq n-f \geq n/3$.

The *upper bound* can be proved along the lines of the second proof. Suppose that there are $f$ leaves. Thus there are at most $f/2$ vertices at height $1$, at most $f/4$ vertices at height $2$, and generally speaking, at most $f/2^h$ vertices at height $h$. Therefore the total height of vertices is at most $$ \sum\_{h=0}^\infty h \frac{f}{2^h} = f \sum\_{h=0}^\infty \frac{h}{2^h} = 2f \leq 2n. $$
> 1 votes

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


# Question
Title: Why Do Computers Use the Binary Number System (0,1)?
Why Do Computers Use the Binary Number System (0,1)? Why don't they use Ternary Number System (0,1,2) or any other number system instead?

# Answer
Since we're in Computer Science, I'll answer this way: they don't.

What do we mean by a "computer?" There are many definitions, but in computer science as a science, the most common is the Turing machine.

A turing machine is defined by several aspects: a state-set, a transition table, a halting set, and important for our discussion, an alphabet. This alphabet refers to the symbols which the machine can read as input, and that it can write to its tape. (You could have different input and tape alphabets, but let's not worry about that for now.)

So, I can make a Turing machine with input alphabet $\\{0,1\\}$, or $\\{a,b\\}$, or $\\{0,1,2\\}$, or $\\{\uparrow,\downarrow\\}$. It doesn't matter. The fact is, I can use any alphabet I choose to encode data.

So, I can say that $0001001$ is 9, or I can say that $\uparrow \uparrow \uparrow \downarrow \uparrow \uparrow \downarrow$ is 9. It doesn't matter, since they're just symbols we can distinguish.

The trick is that binary is enough. Any sequence of bits can be interpreted as a number, so you can convert from binary to any other system and back.

But, it turns out unary is enough too. You can encode 9 as 111111111. This isn't particularly efficient, but it has the same computational power.

Things get even crazier when you look into alternate models of computation, like the Lambda calculus. Here, you can view numbers as functions. In fact, you can view everything as functions. Things are encoded not as bits, 0s and 1s, but as closed mathematical functions with no mutable state. See the Church numerals for how you can do numbers this way.

The point is that, 0s and 1s is a completely hardware specific issue, and the choice is arbitrary. What encoding you're using isn't particularly relevant to computer science, outside of a few subfields like operating systems or networking.
> 32 votes

# Answer
Some other things to consider:

Part of the reason for using a binary number system is that it's the lowest-base number system that can represent numbers in logarithmic, rather than linear, space. To uniquely distinguish between $n$ different numbers in unary, the average length of representations must be proportional to at least $n$, since there is only one string of length $k$ where $k \< n$; $1 + 1 + ... + 1 = n$. To uniquely distinguish between $n$ different numbers in binary, the average length of representations must be proportional to at least $\log\_2 n$, since there are $2^k$ binary numbers of length $k$; $1 + 2 + ... + \frac{n+1}{2} = n$. Choosing a larger base improves on the space requirement by a constant factor; base 10 gets you $n$ numbers with an average representation length of $\log\_{10}n$, which is $\log\_{10}2 \approx 0.3$ times the average length of a base two representation for all $n$. The difference between binary and unary is much greater; in fact, it's a function of $n$. You get a lot by choosing binary over unary; you get much less by choosing a higher base, by comparison.

There is some truth to the idea that it's easier to implement digital logic if we only have to distinguish two states. Electric signals are analog and, as such, can be interpreted to represent as many discrete states as you'd like... but you need more precise (hence expensive and finicky) hardware to reliably distinguish more states over the same range. This suggests choosing as low a base as you can.

Another potentially important consideration is that logic has classically been understood to involve two distinct values: $true$ and $false$. Now, we have fancier logics than this, but a lot of mathematics and science still rests on pretty foundational notions. When you consider that computers are used to compute, and that logic is important for computation, it suggests having good support for at least two distinct states... but logic doesn't really require more than that.
> 22 votes

# Answer
There do exist quantum computers in research labs that use q-bit as the basic unit of information that can be both 0 and 1 simultaneously.
http://en.wikipedia.org/wiki/Quantum\_computer

There have also been ternary quantum computers built as per this reference http://en.wikipedia.org/wiki/Ternary\_computer

So, It is indeed possible to build alternative computing devices that do not rely on the binary number system. Fiber optic systems for example use 0 for dark and two different orthoganal polarizations of light as 1 and -1.

The reason why I mention these things is because I want to show that although binary numbers are sufficient for computing, there are alternative number systems that can be used for computing.

The binary number system is nice in these sense we can encode all integers $x \in \mathbb{Z}$ by using radix representation of numbers. http:// en.wikipedia.org/wiki/Radix These values can represent the ASCII code A=0x41=01000001, or the value could represent a machine instruction nop=0x90=0x10010000.
> 9 votes

# Answer
One of the big reasons that most computer circuits use two states is that the quantity of circuitry necessary to distinguish between *n* different voltage levels is roughly proportional to *n*-1. Consequently, having three discernible states would require twice as much circuitry per signal, and having four would require three times as much. Tripling the amount of circuitry while only doubling the amount of information would represent a loss in efficiency.

Note that there are some places in computers where information is stored or communicated using more than two states per element. In a flash memory array, hundreds or thousands of memory cells may be serviced by one set of level-sensing circuitry. Using four levels per cell rather than two when storing a certain amount of information might more than triple the size of the level-sensing circuitry, but would cut by half the number of memory cells required. When communicating over 100-base-T or faster Ethernet, the cost of the circuitry necessary to detect multiple signal levels on the cable will likely be dwarfed by the cost of either having to use a cable with more wires or use cables that can handle more signal transitions per second without an unacceptable level of distortion.
> 9 votes

# Answer
At the heart of the digital computers processing power is a transistor, which works like a switch. By raising the current at at the "gate" of the switch, it allows current to flow between the "collector" and "emitter" - the switch is turned on. The transistor will be designed to operate in one of two modes - fully on or fully off ('saturated') - with a clear division of what those states are. The transistor can switch between the two states quickly, will remain in the state with very limited errors.

This circuitry forms the basis for logic devices, such AND, NAND, OR, XOR and other functions. The NAND function being the most basic of the building blocks. These logic devices are assembled to provide processors which remain in a predictable state, and lots of transistors can be packed in a small space to provide the functionality needed.

A transistor can manage multiple, or varying states, but when operating in that manner they do not produce conventional "digital" computers - they do not tend to stay in a predictable state and they are prone to interference, saturation, osculation, etc - so they have limited applications in terms of computational abilities. Op-amps could be considered analog computers.
> 5 votes

# Answer
We only use binary(1,0) because we currently do not have the technology to create "switches" that can reliably hold more than two possible states. (Quantum computers aren't exactly on sale at the moment.) The binary system was chosen only because it is quite easy to distinguish the presence of an electric current from an absense of electric current, especially when working with trillions of such connections. And using any other number base in this system ridiculous, because the system would need to constantly convert between them. That's all there is to it.
> -3 votes

---
Tags: computer-architecture, binary-arithmetic
---


# Question
Title: What is the difference between dynamic programming and a mere caching?
I mean why should we use such epic buzzword when you can say: "cache your results!".

# Answer
There are some other key aspects of dynamic programming besides caching, namely, it is about writing solutions of optimization problems recursively to exploit the fact that optimal solutions are constructed out of optimal solutions to subproblems, and further that caching limits the number of recursive calls to the maximum number of distinct subproblems that need to be solved.

Also, dynamic programming is not so much a formalism, as an intuitive framework for solving many optimization problems recursively.

Further, the use of such an "epic buzzword" is largely the result of brilliant marketing by Richard Bellman...
> 4 votes

---
Tags: dynamic-programming
---


# Question
Title: Application Ambiguity in Untyped Lambda Calculus
So, untyped lambda calculus has the following formal grammar for its terms:

$$e::= x \mid \lambda x . e \mid e\_1 e\_2$$

Usually this is presented in some ML-esque language as (using de Bruijn indices)

```
data term = variable Nat | lambda term | apply term term

```

My question is: `apply (variable Nat) term` is syntactically valid, but the rator is just a free variable, isn't this an invalid expression? If not, what does it evaluate to?

# Answer
> 1 votes
You can't evaluate (x t), where x is free, since evaluation ($\beta$-reduction) is usually defined in terms of substitution, but here you have neither a bound variable nor a function body for $t$ to be substituted into.

A term that cannot take a further step is called a normal form.

---
Tags: lambda-calculus
---


# Question
Title: Does the Bondy-Chvátal theorem have algorithmic applications beyond Ore's theorem?
I'm toying around with graph properties and I want to make some effort to check whether a given graph is Hamiltonian. I understand that the general problem is NP-complete, but I'm looking for simple checks that are easy to implement and computationally inexpensive to get some indication.

So I've implemented Dirac's and Ore's theorems to check the sufficient conditions for whether a graph is Hamiltonian (in my implementation Dirac's is a cheap check before I run Ore's). Digging around I found that the Bondy-Chvátal theorem generalizes both and is thus more powerful, but it seems to be less useful for algorithmic purposes.

If I understand it correctly, the theorem states that a graph is Hamiltonian if and only if its closure is Hamiltonian. The only constructive application of this however seems to me to verify that the closure of a graph is a complete graph, which is the case if (and only if?) the graph meets Ore's condition anyway, which is easier to implement efficiently.

I'm wondering though, might there be some other algorithmic application I may have missed, or is Bondy-Chvátal indeed impractical in my scenario (and more of theoretical use in general)?

# Answer
> 2 votes
Other way than Bondy-Chvátal theorem is brute force search. However brute force search isn't an efficient way of solving this problem - there can be an exponential number of possibilities to test.

You won't have to test so many possibilities, if you will try following algorithm:

http://arxiv.org/pdf/1405.6347.pdf

The main principle of algorithm is "to think over" which paths(possibilities) should be checked than check many wrong paths.

Algorithm can remove unnecessary edges from graph and test when Hamiltonian cycle can't exist in graph.

Algorithms implementation:

http://findinghamiltoniancycle.codeplex.com/

---
Tags: graphs, hamiltonian-path
---


# Question
Title: How to make a NFA (or DFA) from $\varepsilon$NFA?
I need to build a DFA from $\varepsilon$NFA, so first of all I assume that I need to convert the $\varepsilon$NFA to NFA and then to DFA (because I know the method of converting from NFA to DFA, and we learn how to remove $\varepsilon$'s from $\varepsilon$NFA and make it NFA.
But the I'm still stuck at some cases....

For example:
See this $\varepsilon$NFA:

I want to make it NFA (I don't know if to write the whole algorithm...), and I'm not sure which is right:

This:

Or this (at the comments.... I can't put more then 2 images)

I think that the first is the right one, but I'm not sure...
At the second one - the number of the 0-s must be even to be at $q\_1$ but at the original $\varepsilon$NFA it can be any number of 0-s...

One more thing, it's correct that I'm not putting 0,1 insted of the $\varepsilon$? (Because 1 from $q\_0$ brings me to $\varnothing$...)

# Answer
I think the following should work. For each state q, define E(q) to be the set of all states reachable from q by following zero or more ε-transitions. Then, create a new NFA as follows:

* The set of states in the NFA is the set $\\{ E(q) | q \in Q \\}$.
* The start state is $E(q\_0)$.
* For each state $E(q)$ in the new NFA, the transitions are given as follows: for each state $r \in E(q)$ that has a transition to a state $s$ on a character $a$, add a transition from $E(q)$ to $E(s)$ on $a$.
* The accepting states in the NFA are the states containing at least one accepting state in the original NFA.

The basic idea behind the construction is to have each NFA state correspond to a set of states in the ε-NFA. This effectively simulates taking all possible ε-transitions at each point in time.
> 2 votes

# Answer
I think I know the answer, I try few times, then I look at the definition of ε-closure and how to make NFA from εNFA, and I think I got the answer -

First of all I followed the definition: $\delta '(q,a) = E(\delta(q,a))$ \[$\delta'$ is the $\delta$ function of the new NFA\].

Now:

* $\delta'(q\_0,0)=E(\delta(q\_0,0))=E(\\{q\_1\\})=\\{q\_0,q\_1\\}$.
* $\delta'(q\_1,0)=E(\delta(q\_1,0))=E(\varnothing)=\varnothing$.
* $\delta'(q\_1,1)=E(\delta(q\_1,1))=E(\varnothing)=\varnothing$.

So the first option that I put was right....

Here:

Thank you!
> 0 votes

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


# Question
Title: Can we use a different encoding scheme to solve an unsolvable language?
Say we have a particular decision problem and that we have an alphabet and an encoding scheme, which gives us a language L that we say is not recursive (i.e. we do not have a Turing Machine that can decide (YES or NO) the problem).

Is it possible to use a different encoding scheme to make the problem solvable?

I have thought about suggesting that we can reduce all such problems to the halting problem, which would imply that no new encoding will allow us to make one solvable (since this would contradict the unsolvability of the halting problem).

# Answer
Ultimately, no.

First, remember that a language is, literally, a set of strings over some alphabet. There is no coding at this level: a string (a sequence of characters from the alphabet) is either in the language or it's not. For example, the language of even-length strings over $\\{0,1\\}$ is what it is; if you change it at all, it's a different language.

However, you probably don't mean for your question to be interpreted so literally, and you're presumably asking about languages such as "the set of strings that encode Turing machines with property $X$." Strictly speaking, the description of such a language should always say, "Fix an encoding scheme $f$ of Turing machines as strings. Now consider the language of strings $f(M)$ such that $M$ is a Turing machine with property $X$." After all, if you don't say what the encoding is, you can't know if a particular Turing machine is in the language or not. So, presumably, your question is "Well, what if I use some other encoding scheme, instead?"

As long as there's a computable translation between the two encoding schemes, changing the encoding can't alter the computability of the language. To see this, fix any set $S$ of Turing machines and consider codings $f$ and $g$ of these machines as strings. Suppose there's a computable translation between $f$ and $g$, i.e., a computable function $t$ such that, for all $M$, $g(M) = t(f(M))$. If the language $L\_g = \\{g(M)\mid M\in S\\}$ is decidable, then we can decide $L\_f = \\{f(M)\mid M\in S\\}$, too. To decide whether $w\in L\_f$, just ask if $t(w)\in L\_g$. The reason people tend to be quite informal and just talk about "the language of Turing machines with some property" is precisely this: it doesn't matter what encoding you use, as long as you stick to encodings you can computably translate to the "standard" encoding, whatever reasonable encoding you want to view as standard.

In a strong sense, it's impossible to use any other encoding. For example, consider an encoding $f$ that isn't computably translatable to some standard encoding. Now, suppose I describe a Turing machine to you by listing the symbols in the alphabet, the states, the transition function and so on. You can't even compute $f(M)$, so you can't do anything useful with that encoding.

There are even encodings that make the halting problem decidable but they're a trick: they're not computable, so you can't actually use them. For example, fix a computable encoding $g$. Now, define $f(M)$ (uncomputably) as follows. If $M$ halts when started with a blank tape, let $f(M)$ be $2n$ written in binary, where $n$ is the number of Turing machines $M'$ such that $M'$ halts when started with a blank tape and $g(M')$ lexicographically precedes $g(M)$. Otherwise, let $f(M)$ be $2n+1$, where $n$ is the number of Turing machines $M'$ that do not halt when started with a blank tape and whose encoding $g(M')$ lexicographically precedes $g(M')$. Now, the language $\\{f(M)\mid M \text{ halts when started with a blank tape}\\}$ is decidable: it's just the set of even numbers in binary. But, as I said, this is a trick: it doesn't really let you decide the halting problem because, again, you can't compute $f(M)$ given a description of $M$. (In particular, you can't even tell if $f(M)$ is even or odd.)
> 6 votes

---
Tags: computability, turing-machines, halting-problem
---


# Question
Title: Why is the step property in a balancing network defined as it is?
I was trying to understand why the equation $y\_i = \left( \frac{n}{w} \right) + (i \pmod w) $ describes the step property in a balancing network?

First, recall $x\_i$ to be the number of tokens a network gets as input and similarly $y\_i$ to be the number of output tokens. Recall that a balancing network is just a network that distributes tokens to its output.

I was reading the art of multicore programming and in page 272 it says:

> If the number of tokens n is a multiple of four (the network width), then the same number of tokens emerges from each wire. If there is one excess token, it emerges on output wire 0, if there are two, they emerge on output wires 0 and 1, and so on. In general,
>
> $$ n = \sum x\_i $$
>
> then
>
> $$y\_i = \left( \frac{n}{w} \right) + (i \pmod w) $$
>
> we call this property the **step property**.

It also defines equivalent ways to see the step property as:

1. For any $i\<j$, $0 \leq y\_i - y\_j \leq 1$

i.e. as we go up the output wires, the wire can only increase one step at a time or not increase (so top values are always larger or equal). An example:

However, the formula $y\_i = \left( \frac{n}{w} \right) + (i \pmod w) $ doesn't make sense to me also, specifically the following doesn't make sense:

> if there are two, they emerge on output wires 0 and 1, and so on...

I tried plugging in the numbers too say, $ n = 6 $, but the results don't quite make sense.

For example according to the formula above we get:

$$ y\_0 = \left( \frac{6}{4} \right) + (0 \pmod 4) = 1 + 0 = 1 $$ $$ y\_1 = \left( \frac{6}{4} \right) + (1 \pmod 4) = 1 + 1 = 2 $$ $$ y\_2 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 2 = 3 $$ $$ y\_3 = \left( \frac{6}{4} \right) + (2 \pmod 4) = 1 + 3 = 4 $$

which doesn't agree with what the picture of the diagram would be because it seems to be backwards. Not sure if I made a mistake or misunderstood the formula, but it should be giving something as in the figure/diagram/picture from the book. Also, according to the formula, is it ever possible for it be equal? It seems to always increase in the wrong direction.

# Answer
The formula is wrong. The correct formula is $$ y\_i = \lfloor \frac{n}{w} \rfloor + \[i \< (n \mod{w})\], $$ where $\[C\]$ equals 1 if $C$ holds, and 0 otherwise.

Sometimes books contain mistakes. When you see a mistake, correct it and proceed. No need to ask us for permission.
> 3 votes

---
Tags: algorithms, parallel-computing
---


# Question
Title: Why clear the child's and not the parent's mark in Fibonacci heaps?
According to Cormen et al.'s Introduction to Algorithms chapter 21 on Fibonacci heaps (3rd edition), the FIB-HEAP-LINK($H$, $y$, $x$) clears mark of $y$ which will in the end be the child on the resulting merge. I just don't get it, why should we bother clearing this mark? In particular:

1. What happens if we leave their marks as is?
2. Why clear the child's mark rather than the parent's?

A reminder of FIB-HEAP-LINK:

FIB-HEAP-LINK($H$, $y$, $x$)

1. Remove $y$ from the root list of $H$
2. Make $y$ a child of $x$, incrementing degree\[$x$\]
3. Set mark\[$y$\] to FALSE

# Answer
> 6 votes
To understand Fibonacci heaps, it may help to understand binomial heaps first.

A binomial heap is a forest of heap-ordered binomial trees. A binomial tree of degree k is a node whose children are binomial trees of degree k-1, k-2, ... 0. Note that the number of nodes in a binomial tree of degree k is $2^k$.

If you never do any decrease key operations (or delete operations of nodes other than the minimum), then the Fibonacci heap is a binomial heap.

Conceptually, a Fibonacci tree is a binomial tree which allows for a controlled amount of "damage".

The degree of a Fibonacci heap node is redefined to be the number of children that it has. The structural constraint is designed so that the tree can tolerate a certain amount of deviation from the binomial heap constraint. Most textbooks don't precisely define it, but the key property is this:

> Suppose that x is any node in a Fibonacci heap. If you order its children in the order that they were linked to x, then the ith child has a degree at least i-2. If it has degree equal to i-2, the node must be marked. If it is greater than i-2, then it may or may not be marked.

In particular, a mark signifies that a node may be one degree too "small" for its parent. (Note that this property is *almost* lemma 1 from the original paper.)

The first thing to notice is that when we cut a node, we unmark it. The reason for this should be obvious: it has no parent, so it can't possibly be too "small".

Now think about the link operation. We only ever link two nodes together if they have the same degree. Let's suppose that d is the degree of x and y, and we want to make x the new parent of y.

Since we are adding a child to x, so this changes the degree of x to d+1. The node y is the (d+1)th child linked to x, so to preserve the structural constraint, it must be marked if it has degree d-1. However, by construction it has degree d. It is not too "small", so we unmark it.

Of course, the structural constraint is preserved whether or not y is marked. Why, then, do we clear the mark? Intuitively, it's because encountering a mark during an unlink operation triggers a cascading cut. We want to avoid those, so we want to have as few nodes marked as possible. At any point, if we can tell that a node doesn't have to be marked, we make sure it's not marked.

Did that help?

---
Tags: data-structures, heaps
---


title: Interpretation in scripting languages

text:
# Question
Title: Interpretation in scripting languages
Why is pure interpretation more common for scripting languages compared to programming languages?

I mean, why are programs written in a scripting language not converted to machine language and then executed? From what I have read, one of the reasons is speed; for scripting purposes speed is not so important and since interpretation is slower it doesn't matter for scripting languages.

Are there more reasons for using interpretation in scripting?

# Answer
> 7 votes
Scripting languages are a class of programming languages. This class is rather fuzzily defined.

One possible definition is that they're languages that are designed to automate small tasks, rather than to write large, complex programs. Because they are small tasks, the author tends to spend some time tweaking them, so it makes sense to make the path from source code to executable as simple as possible, and it doesn't get simpler than making the source code itself executable. Because they are simple tasks, the end-user might want to tweak them, too, so it makes sense to distribute them as source code. Because the tasks are relatively small and simple, there's little to be gained by static checking and optimization, so there's little value in using a compiler.

Another possible definition is that a scripting language is one in which the source code is executable. In other words, a scripting language is pretty much defined as one that's intended to be interpreted.

Few scripting languages are purely interpreted though. Most at least parse the whole file before starting execution. Many even compile to some form of bytecode that can be saved to disk.

# Answer
> 2 votes
Interpreted languages are used because of their simplicity.

A compiler will assemble all the parts and link them together as an executable. If there is a bug in any one of the parts the build will fail and there will not be any executable to run (missing symbols, missing libraries, incompatible libraries, etc). Also compiled programs often need to manage memory allocation themselves, and thus are prone to bug like memory leaks, buffer overruns, null pointers, etc.

Many interpreters will get right to it and run the program with limited requirements (syntax mostly). If there is a bug in the code the program may run until it gets to that bug then stop. New code can be loaded on the fly. Memory is usually managed for you, so you don't need to worry about deleting allocated memory.

Also interpreters can often be run as a command prompt and commands can be typed in, to test different parts of the program or to interact with your program in different ways.

Interpreters are also used in programs to allow you to modify the behavior of the program as it runs, e.g. MS Word macros.

You don't have to stop the program and recompile the code run it again to make a change.

Compiled programs usually run faster, and have access to lower level operations of the internal workings of the computers (registers, memory locations, permissions, etc).

It can be a blurry line, as some interpreted languages need to be compiled to microcode to run (e.g. Java), and some compiled languages have memory management features commonly found in interpreters (e.g. C#).

---
Tags: programming-languages, compilers, interpreters
---


# Question
Title: Macro expansion is done in which phase of a compiler?
This is question raised by my teacher in the class room. I don't have enough knowledge about phases of compiler and macro expansion. Could someone help me in finding out proper solution to this

# Answer
> 4 votes
It's completely dependent on the language. Different languages have wildly different notions of macros. I'll just give a few examples; other situations are possible.

### The original C language (K&R C)

Macros are expanded by the preprocessor, which is a separate program that runs before the compiler proper. Macros perform a simple text substitution. This program prints `1`, because `PLUS()PLUS()` expands to `++` which is the increment operator.

```
#include <stdio.h>
#define PLUS() +
int main()
{
    int x = 0;
    PLUS()PLUS()x;
    printf("%d\n", x);
    return 0;
}

```

### The modern C language (ANSI C)

Macros are expanded by the preprocessor, which acts on tokens, after lexical analysis. Thus, a macro only expands to whole tokens, but can contain things like unbalanced parentheses. The program above prints 0, because each `PLUS()` expands to a `+` token, so the instruction is equivalent to `+ + x;`.

### Lisp

Macros act on the program's representation as an abstract syntax tree, i.e. after parsing. Thus a macro expands to a sexp (Lisp's term for an abstract syntax tree), and its arguments are themselves sexps. Macros are expanded before variable resolution. Such macros are said to be unhygienic. Care must be taken not to mix up variables introduced by a macro from the variables of the program fragments.

```
(defmacro repeat (count func)
  `(loop for i from 1 to ,count
      do (apply ,func nil)))
(repeat 3 (lambda () (print "hello")))
(let ((i 5))
  (repeat 3 (lambda () (print i))))

```

The first call to `repeat` prints `hello` three times as expected. The second call to `repeat` does not print `5` three times, it prints `1` then `2` then `3`, because the variable `i` from the macro shadows the variable `i` from the context of the macro call.

### Scheme

Scheme is similar to Lisp, but with a few differences. One of the differences is that Scheme macros are hygienic. The Scheme equivalent of the program above prints `hello` three times then `5` three times.

```
(define-syntax repeat
  (syntax-rules ()
    ((repeat count func)
     (do ((i 1 (+ 1 i)))
         ((> i count))
       (func)))))
(repeat 3 (lambda () (display "hello") (newline)))
(let ((i 5))
  (repeat 3 (lambda () (display i) (newline))))

```

### TeX

TeX expands macros in its mouth but defines them in its stomach. But don't set too much store by this: from a language design perspective, TeX is weird.

# Answer
> 0 votes
Macro expansion is done by a preprocessor before the compiler ever looks at the file. This is at least how it works in C/C++.

---
Tags: compilers
---


# Question
Title: O(1) access into an array-like data structure with numerical ranges for keys
Preface: It's been a long time since I've been in school, and my terminology is probably all wrong. Apologies...

Summary: I have a data structure with probability ranges assigned to the elements, and I want to "roll the dice" and get the element at that spot. I'm wondering if there's a (good) way to do this in O(1) time?

Assume I've got a data structure like this, where the indices/keys represent ranges, and the values are what I want:

```
a = {
  [0..0.3) -> "foo",
  [0.3..0.4) -> "bar",
  [0.4..0.9) -> "baz",
  [0.9..1.0] -> "qux"
}

```

I want to retrieve a value from that array using a randomly generated number between 0 and 1. So, using that previous example, I do something like:

```
a[0.2] == "foo"
a[0.3] == "bar"
a[0.5565] == "baz"
a[0.8] == "baz"
...and so forth

```

I think I could store the data in a tree structure where I could walk to the correct element in O(log(n)) time, but I'm wondering if there's a clever way to do it in O(1) time.

I'm also curious if there is a specific name for this kind of data structure. It seems like someone would have played with this at some point.

As background, I'm toying with creating a Markov generator, and that requires storing the frequencies for all the words/token pairs. I'm guessing this is a solved problem already, and there are probably better solutions than what I'm proposing, but it seemed like an interesting problem and now I'm curious about the index-by-range problem all by itself, independent of the Markov aspect.

# Answer
> 2 votes
Perhaps what you're looking for is a **Direct-adress Table**

You can set up the keys as the ranges you've provided. Since the set of keys is quite small (4 intervals), a Direct-adress Table is a simple solution to your problem. It has the advantage of retrieving data in *O*(1)

The keys would hold a pointer to the data you want to retrieve.

For example, you can set a variable key1 as the interval \[0..0.3). We generate a random number x, and get 0.1. Since 0.1 meets the conditions of the first key *( x \>= 0 and x \< 0.3)*, we can retrieve the data stored in key1 in O(1) time.

If you want more information about a Direct-adress Table or O(1) operations on dictionaries, I recommend ***Introduction to Algorithms, 3rd Edition, Chapter 11***

# Answer
> 1 votes
The best algorithm I know of is to build a binary search tree (where the keys are the endpoints of your ranges), as a pre-processing step. Then when you pick a randomly generated number $x \in \[0,1\]$, you can traverse the binary search tree to see which interval it is contained in.

The running time of this approach is essentially $O(\lg n)$, for a suitable definition of $n$.

I don't know of any way to achieve $O(1)$ time and don't expect that to be possible in general, though it might be possible in special cases. For example, if all ranges are of the form $\[a\_i/k,b\_i/k)$ and where $k$ is the same for all ranges, then with preprocessing you can build an array of length $k$ that lets you do a $O(1)$-time lookup of the correct range. But this technique doesn't work for arbitrary ranges.

---
Tags: data-structures, time-complexity, dictionaries
---


title: How to Apply Binary Transformations?

text:
# Question
Title: How to Apply Binary Transformations?
One of the steps in Binary Index Tree algorithm is to find a node's parent which is done by un-setting the rightmost SET bit. For example: if a node has index 1010 than it's parent is 1000. To apply such transformation the following method is applied:

```
1) Find 2's complement of the index.
2) AND the result of 1 with index.
3) Subtract the result from 2 with index.

```

If the following method is applied to 1010 then we get 1000 as the answer. Now I want to understand how to create such formulas? In Algebra we solve such type of problems by solving linear equations. How do we do it with Binary numbers to achieve such answers?

# Answer
This is a one-off trick which is not part of a complete methodology. To see why the trick works, suppose that the index has the form $x10^m$. To calculate its two's complement, we first complement it to $\bar{x}01^m$, then add 1 to get $\bar{x}10^m$. ANDing the index and its two's complement, we get $0^{|x|}10^m$. Subtracting this from the index, we get $x0^{m+1}$, as needed.
> 1 votes

---
Tags: binary-trees, arithmetic, boolean-algebra
---


# Question
Title: Why does this graph show the tightness of MST heuristic's 2-approximation bound?
This is a homework problem I've been given and I've been raking my brain for hours (so I'm satisfied with some pointers). I know already that the approximation ratio cannot be worse than $2$. I have a wheel graph, where each edge has cost $1$ and the distance between all nodes which are not connected by edges is $2$. The wheel graph $W\_6$ is this one:

I have marked in blue what I believe to be the output of an MST heuristic algorithm. But I also think this is the optimal solution, since all nodes can only be visited once. So the cost of the tour would be $7$ for both optimal and MST.

I do not see how this type of graph shows that the $2$-approximation bound of MST heuristic is tight (not necessarily this instance, but the graphs $W\_n$ in general). Can someone enlighten me?

# Answer
> 3 votes
The graph I posted is missing some edges, adjacent nodes in the cycle are supposed to be connected. (**Edit**: Fixed the graph with TSP tour).

The actual graph is this

My solution goes as follows. Now the MST computed for for the MST heuristic is obviously

allowing many euler tours, among others these ones:

where the cycle nodes can be visited in any order. Now any of the tours are valid so we can choose the worst one, for instance $v\_0,v\_4,v\_0,v\_1,v\_0,v\_3,v\_0,v\_6,v\_0,v\_2,v\_0,v\_5,v\_0$. Based on that tour, MST heuristic finds this TSP solution:

Now since all edges have cost $1$ and and all nodes not connected in the graph have distance $2$, the cost of the tour is $2(n-1) + 2$ where the optimal tour would have cost $n+1$. In the limit

$\begin{equation\*} \lim\_{n\rightarrow\infty} \frac{MST(W\_n)}{Opt(W\_n)} = \lim\_{n\rightarrow\infty}\frac{2n}{n+1} = 2 \end{equation\*} $

# Answer
> 4 votes
There is a lot of freedom in the algorithm: several minimum spanning trees, and several corresponding Eulerian tours. Try to find the *worst* choice and show that it produces an inferior tour. What you are showing is that the algorithm *could* make this choice, and so *could* produce an inferior approximation.

If you don't like this idea of choice, you can sometimes guarantee that the algorithm makes the choices you want by slightly tweaking the weights.

---
Tags: algorithms, algorithm-analysis, approximation, traveling-salesman
---


# Question
Title: Why do we need $k \geq n$ in Dijkstra's token ring self-stabilizing system?
Let's say I have a ring with four nodes $n=\\{0;1;2;3\\}$ and three possible states $k=\\{0;1;2\\}$. A transient failure happens and the system ends up in an illegal state.

I know from the restriction ($k \geq n$) that there should be an execution that makes the system stay in its illegal state indefinitely, but for all the executions I try in my head and on paper, it still stabilises at some point. Could you give me an execution where it loops always back into its illegal state?

# Answer
> 1 votes
Here is how to solve this for your particular $n$ and $k$. Your system has $k^n = 81$ possible states. You can describe the evolution of the system as a directed graph: there is an edge $s\_1 \to s\_2$ if state $s\_1$ evolves in one step to state $s\_2$. Some states are legal, some are illegal. You want to find an illegal state $s$ from which no legal state is reachable. This is a question that can be solved using a graph traversal algorithm such as DFS.

Once you find such a state, you can try to generalize the construction to other values of $n$ and $k$. Other simulations (with other values of $n$ and $k$) could be helpful here.

---
Tags: mutual-exclusion
---