# Question
Title: How does the Vertex Cover algorithm by Chen et al find its tuples?
I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus).

My current problem is that it's specified that the main vertex cover algorithm `VC` (page 7/21) has the following header `VC(G, T, k)`, where `G` is the graph to process, `T` is *a set of tuples* and `k` is the bounding parameter.

My question is: **what should the set of tuples contain in the first execution of VC**?

It's said multiple times that the algorithm maintains this structure and *generates* tuples. This is obvious, given the `Reducing` subroutine behavior.

What is giving me trouble is that `Reducing` is called before any further logic in `VC` and `Reducing` itself begins with a loop saying `for each tuple (S, q) in T`, which implies that the set `T` should be pre-populated.

Should I scan the whole graph for all the structures that would fulfill the criteria for being included in `T`? This seems a bit drastic, since the operations of `Struction` and `General-Fold` will cause the structures in `T` to be *invalidated*.

Currently, my best bet is that, given the list of priorities (page 8/21) of certain structures as well as the definition of a *good pair* (page 5/21, after Observation 3.3) I should search the whole graph for *tuples*, *good pairs* and vertices with high degrees and put them into `T` with appropriate priorities. The first sentence from section *4. The algorithm VC* (page 8/21) seems quite convincing:

> A tuple, a good pair, or a vertex of degree at least seven, will be referred to by the word structure. The algorithm will maintain a list of structures T, and then it will pick a structure and process it.

Can somebody provide some intuition? Maybe I'm just missing something that's staring at me from the paper itself...

Reading deeper into section *updating tuples* (page 6/21), one can see the following paragraph:

> Since a tuple imposes certain constraints on the minimum vertex cover sought, one needs to be careful that the constraints imposed by the creation of a tuple do not conflict with the conditions imposed by other operations of the algorithm.
>
> The other operations that do impose constraints on the minimum vertex cover sought are the creation of (other) tuples, the struction operation, and the general folding operation.
>
> For example, the general folding operation assumes that when we are looking for a minimum vertex cover, we can look for one that either contains the set I or the set N ( I ) in the structure ( I , N ( I )) . This is mainly the reason why the set N ( I ) can be folded.
>
> *If the general folding operation is applied*, then this constraint imposed by the operation on the minimum vertex cover might conflict with the constraints imposed by a certain tuple. Therefore, to be on the safe side, when we decide to apply the struction or the general folding operations, we will invalidate all the constraints imposed by the tuples. That is, *we will basically remove all the tuples*.

So, even when I pre-seed `T` with some structures, they will most likely be removed anyway sooner or later, leaving an empty set and going back to square 1.

# Answer
> 1 votes
The beginning of Section 4 states:

> A tuple, a good pair, or a vertex of degree at least seven, will be referred to by the word structure. The algorithm will maintain a list of structures $\mathcal{T}$, and then it will pick a structure and process it. ... We will assume that the algorithm implicitly updates the structures in $\mathcal{T}$ and their priorities after each operation.

It seems that you shouldn't really think of $\mathcal{T}$ as a parameter, but as a dynamically updated list. As for intuition, I suggest that you read the full paper. Once you understand the proof, you should be able to come up with some sort of intuition.

---
Tags: algorithms, graphs, np-complete, parameterized-complexity, branch-and-bound
---


# Question
Title: Are there more partially recursive functions than and recursive functions?
Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ?

# Answer
> 8 votes
No they have the same cardinality. They have the cardinality $\aleph\_0$. Both sets are infinite in size so we have to compare them based on their level of infiniteness, since as we know there are infinite levels of infinity. Both sets are countably infinite so we say they have the same cardinality.

To expand on this and show why this is the case:

The set of partially recursive functions are infinite by design. Also they are computable, so by the Church-Turing thesis they are solvable by a Turing machine. Since there are only countably infinite Turing machines there can only be countably infinite partial recursive functions.

The same argument can be used on the set of recursive functions.

---
Tags: computability, combinatorics
---


title: What is a forwarding pointer?

text:
# Question
Title: What is a forwarding pointer?
I recently came across the concept of "forwarding pointer" and have not been able to find sources of a precise definition. In my case this was mentioned and briefly (but poorly) explained during a discussion on distributed systems.

Could you elaborate on the concept, its usual context(s) and possible other names by which this is also known as?

# Answer
"Forwarding pointer" is the name of a technique used in garbage collection algorithms when data cells are being moved to a different storage location, either because you are using a copying collection technique such as Cheney's collector, or because you are doing a compaction phase to reduce memory fragmentation. Compaction is usually associated with mark-and-sweep collectors, but it could be used in other contexts, though the care required by forwarding pointers may entail overhead that is more naturally acceptable with mark-and-sweep.

The forwarding pointer replaces the data cell that has been moved, so that any piece of code trying to access that cell through its old address can find the forwarding pointer to the new address. Exactly like a person moving to a new house will leave her new address on the mailbox (or at the post-office) of her old house. Of course, the code and data must be organized so that forwarding pointers may be recognized as such.

As far as I know, this was historically the first widespread use of the concept of forwarding pointer. But the idea of using forwarding pointers can be considered, and has been considered in other situations that require moving data to a different location, for example:

* The concept is used in mobile computing when an agent moves to a different location (agency) and must still receive messages sent to its former location.
* The concept is also used in data-base implementation when the organization and management of data requires moving some part of it to another location.

Basically, ***forwarding pointers* are a way of reorganizing incrementally the storage structures or system organizations without disrupting (too much) on going computations, and avoiding a complete sweep of the system space, by leaving the new address of moved constituents at their former location.**

*(You could have found some of that yourself by searching the web and wikipedia).*
> 6 votes

---
Tags: terminology, programming-languages
---


# Question
Title: Algorithms which are both deterministic and non-deterministic
I'm just starting my second year in computer science and one of my classes briefly touched upon deterministic vs. non-deterministic algorithms. This got me thinking - is there any use for algorithms which return deterministic output for certain inputs, but non-deterministic output for other inputs? Say, something along the lines of

$$ s\leftarrow n\in\mathbb{R}\\ \text{if }s\le 5:\text{ return }2\times s\\ \text{else }x\leftarrow\text{generateRandomNumber()};\text{ return }s\times x $$

This algorithm returns the input, doubled, if the input is less than or equal to five, and otherwise returns it multiplied by a random number (assuming the RNG returns a truly random number and is itself non-deterministic).

So once again, my main question: are algorithms of this nature useful in any practical application? Additionally, what would this class of algorithm be called? Semi-deterministic? Pseudo-deterministic?

# Answer
First of all, your terminology is at odds with computability and complexity theory. What you are asking is whether it makes sense for an algorithm to have both randomized and non-randomized components. A good example are algorithms which have to be unpredictable (say for cryptographic reasons), but for the purpose of testing have to be predictable. In this case, we substitute a pseudorandom number generator for the true (say, physical) random number generator for testing purposes.

That said, the class of algorithms you are describing are just randomized algorithms. Nothing forces a randomized algorithm to use randomization, it's just a possibility in the model, in the same way that a non-deterministic Turing machine can be deterministic, or that a real number can be rational.
> 5 votes

# Answer
Such algorithms certainly exist and are of practical nature. Algorithms that are deterministic for some input instances and non-deterministic for others are still simply called non-deterministic. When I say "practical nature", it should be added that true non-determinism still does not exist in computers. Yet, the study of non-deterministic branching makes sense anyway as it is helpful computational model.

Note that many non-deterministic algorithms for inputs of arbitrary length will work in a deterministic manner on an empty input string. So that is one rather trivial example.

But coming to a more practical example, consider modern SAT (satisfiability) solving. Here, decisions are made seemingly non-deterministic (in reality, there are advanced heuristics to make these) and back-tracked whenever needed (so that a non-deterministic reasoning scheme is still complete on a deterministic computer). To make reasoning more efficient, so-called clause learning and unit propagation are applied, which reduce the number of decisions that the algorithm has to make. There are more simple input instances for which no non-deterministic decision ever has to be made, as unit propagation alone solves the instance already.

The SAT solving case may not be convincing to everyone as I am arguing that essentially, a non-deterministic search algorithm with unit propagation is executed on a deterministic machine by performing decision making and back-tracking. But since you are asking for practical applications of a non-deterministic algorithm (and we do not have "guessing computers"), I think that this is a fair answer. It should be added that the "clause learning" applied nowadays in SAT solving does not fit into this scheme, however.
> 1 votes

---
Tags: algorithms, terminology, nondeterminism
---


# Question
Title: c compiler source code for compiler construction
Could anyone tell me from where could I get the c compiler source code.In particular the lexical analyzer for c.I searched the web but no links show how a compiler is defined.

# Answer
> 1 votes
search the web: "c compiler" source

By the way, You can find source code for any free software or open-source software, and a licence allowing you to use it freely.

C being the implementation language for Unix, I would expect it to have been one of the first pieces of software with available source, and a copyleft licence.

When searching the web for the source code of a piece of sofware, look for these types of licences (without a licence you are not allowed to use the source code anyway). Creative Commons licences will generally do too, and non copylefted free licences such as BSD licences. All these terms are usually useful keywords to find software with source code available.

---
Tags: compilers
---


title: How to show whether $n2^n = 2^{O(n)}$?

text:
# Question
Title: How to show whether $n2^n = 2^{O(n)}$?
show whether $n2^n = 2^{O(n)}$ is true or not.

In my opinion, it's false because O(n) can be n and thus the equality will be wrong, because $n2^n$ grows much faster than $2^n$

# Answer
One way, if you want to prove that $n2^n \in 2^{\mathcal{O}(n)}$, is to show that there exists a $c \in \mathbb{R}$ such that $n2^n \le 2^{cn}$ for all $n$ greater than some $n\_0 \in \mathbb{N}$.

Correspondingly, if you want to show the contrary, then you have to show that such a $c$ does not exist. However, we will see that the statement is true.

Choose $c = 2$, i.e., we ask whether $n2^n \le^? 2^{2n} = 4^n$ for all $n \> n\_0$. We know that $n \le 2^n$ for all $n \in \mathbb{N}$. Therefore, it also holds that $n2^n \le 2^n\cdot 2^n = 2^{2n}$. Hence, we have an upper bound for the function $n2^n$ by choosing $c = 2$. In this case, we can set $n\_0 = 1$, for instance.
> 7 votes

# Answer
The main issue here is to read that awful abuse of notation in the "right" way.

Let me translate:

> Show whether $n2^n \in O(2^{f(n)})$ for some $f \in O(n)$.

That is, we understand

$\qquad\displaystyle 2^{O(g)} := \\{ f \mid f \in O(2^{h(n)}), h \in O(g) \\}$.

Note how, in particular, $c^n \in 2^{O(n)}$ with $f : n \mapsto n \cdot \log\_2 c$ for all $c\>1$.

The rest is mechanical.
> 4 votes

---
Tags: asymptotics
---


# Question
Title: Proving optimality of a dynamic programming algorithm
We have a string $s$ containing $n \leq 100$ bits. The move we can make on it is erasing from $s$ some substring $x$, but only if $x$ is **directly preceded** by $x^R$, where $x^R$ means string $x$ reversed. In other words, we're choosing some even-length palindrome and erasing it's "right half".

The goal is to minimize the length of the word left when no further can moves be done. In example, from a bit word $100110$ we can erase $01$ from the middle, and be left with $1010$ where no moves can be done. However, starting differently, we can reduce the word to a single $10$, which is optimal. I want to compute this minimal length for a given string, for $100110$ it would be $2$.

Now, I have a dynamic-programming algorithm which I know produces right answers (it has been tested a lot), but don't know how to prove it. It computes the best result for every substring of $s$ in increasing length. For those of length $k$, the answer is surely at most $k$. Also, it's obvious that the only strings in which no moves can be done are of form $1010...$ or $0101...$. For some word we're playing on, as it's first bit can never be erased, we know the exact form of a word that will be left from it, the only thing that we lack is it's length. Now, I assumed that for a word $t$, there exist some words $x$, $y$ that $t = xy$, and if we do the optimal operations just on $x$, producing a word $x'$, then just on $y$ producing $y'$, and in the end on the word $x' y'$, we will acquire the optimal result for $t$. The last step is very easy, because we know how words $x'$ and $y'$ look like only knowing it's lengths, so there are only a couple of cases to consider. The complexity of this process is $O(n^3)$ as it spends linear time on each substring of $s$.

If $DP\[i\]\[j\]$ is the answer for a substring $\[i..j\]$, the complete recurrence is as follows:

$$DP\[i\]\[j\] = \min \\{DP\[i\]\[k\] + F(i,k,j) \cdot DP\[k+1\]\[j\] : i \leq k \< j \\}.$$

where

$$ F(i,k,j) = \left\\{ \begin{array}{ll} 1 & \textrm{for $s\[i\] = s\[k+1\]$ and $DP\[i\]\[k\] = 1$}\\ 1 - DP\[i\]\[k\] \mod 2 & \textrm{for $s\[i\] = s\[k+1\]$ and $DP\[i\]\[k\] \> 1$}\\ DP\[i\]\[k\] \mod 2 & \textrm{otherwise} \end{array} \right. $$

what corresponds to the fact that in some cases $y'$ can be erased using $x'$ (possibly in multiple moves) - in those cases $F(i,k,j)$ is $0$, and it's $1$ otherwise. Also note, that if $s\[i\] = s\[i+1\]$ then when dealing with $DP\[i\]\[j\]$ for $j \> i$ at first we initialize $DP\[i\]\[j\] = DP\[i+1\]\[j\]$.

For me, the assumption that $t$ can be split into $x$ and $y$ in a such a way that the mentioned procedure is optimal, is non-trivial. I'm asking for a proof that this assumption can be made, or some different solutions for this problem, either would be nice.

# Answer
Since you're asking how to construct a proof of correctness, I'll give you some tips to get you started. If you do all of these, I think you'll be able to make a lot more progress.

1. As Raphael suggests, make that you can write a recurrence relation for the solution. You don't yet have a recurrence. A recurrence is an equation for $DP\[i\]\[j\]$ that is written solely in terms of $i,j,s$ and other "earlier" values of $DP\[\cdot\]\[\cdot\]$. Your equation involves a variable $k$, but what is $k$? Where'd that come from? It comes out of the blue. How do we choose $k$? You haven't yet given us a formula that computes $DP\[i\]\[j\]$. Until you do that, you can't possibly hope to prove your algorithm correct. In fact, until you do that, you don't even have an algorithm!

Hint: I think you'll find you want to write something like

$$DP\[i\]\[j\] = \min \\{...\text{something}... : k=i-1,i,i+1,\ldots,j-1\\}.$$

You fill in the $\text{something}$ part. In short, I recommend that you formulate your recurrence more accurately.

Hint: try writing out the pseudocode for your dynamic programming algorithm, in standard form. This will force you to write a recurrence for $DP\[i\]\[j\]$.
2. Once you have a recurrence, your next step is to prove that it is correct. Why does it give the correct answer for your problem? Justify why the recurrence is correct. Here you might use proof by induction.

See Raphael's answer, which gives an excellent overview for how to prove a dynamic programming algorithm correct.

I recommend that you review the proof of correctness for a few other dynamic programming algorithms. (Look in a few standard algorithms textbooks; with any luck, they should show you several examples.) You'll see that they have a similar structure, and this should help you structure your proof.
3. One more tip that will be very helpful. You write "I assume (...)". You might try proving that the "(...)" statement is true.
> 2 votes

---
Tags: algorithms, dynamic-programming, strings, correctness-proof, substrings
---


# Question
Title: Assuming finite optimal cost of a specific LP, find an optimal solution directly
> Minimize $\sum^n\_{i=1} c\_i x\_i$ subject to $\sum^n\_{i=1} a\_i x\_i = b$ (a single constraint), $x\_i \ge 0$.
>
> 1. Derive a simple test for feasibility of this problem
> 2. Assuming the optimal cost is finite, develop a simple method for obtaining an optimal solution directly.

For the first part, I have $\sum^n\_{i=1} a\_i x\_i = b \iff \text {sgn}(b)=\text{sgn}(a\_i)$ for some $i \in \\{1,..,n\\}$ or $b = 0$.

I have trouble obtaining this simple method for part two. Could someone help me out here?

I know $ -\infty \< \sum^n\_{i=1} c\_i x\_i$ and $\sum^n\_{i=1} a\_i x\_i = b$.

# Answer
> 1 votes
Hint: Since there are $n+1$ constraints on $n$ variables, there is a solution in which all but one constraint are tight. You can calculate all these solutions explicitly ("on paper"), and choose the best one.

---
Tags: optimization, linear-programming
---


# Question
Title: Computation is effectively computable in theory and in practice
My big question is the following: What is the meaning of a computation being "effectively computable" (EC) in theory and in practice?

In trying to understand these concepts further, I have a couple of sub-questions as well:

1. Is there a relationship between a computation being EC in theory and being EC in practice? (It seems just by taking the usual meaning of the words, EC in practice should imply EC in theory.)
2. Is there an example of a computation that is EC in theory but not EC in practice?
3. How about EC in practice but not EC in theory?

Either explanations or links to where these explanations may be will be helpful.

# Answer
> 7 votes
The only definitions of the term "effectively computable" that I can find online are that the phrase just means "computable" (which is usually taken to mean "Turing-computable"). As such, computability is an absolute concept: either a function is computable or it is not. Are you asking about whether a function that is computable can actually be computed in practice? If so, the answer is clearly no: it's easy to construct families of problem instances that would require more time than the expected lifetime of the sun, for example. For example, take large instances of **EXP**-complete problems: $2^{100}$ exceeds the age of the universe in nanoseconds. (That is, a 1GHz computer that had been running since the beginning of time wouldn't have executed $2^{100}$ instructions yet.)

# Answer
> 1 votes
this question relates to the Church-Turing thesis which asserts that all possible computation is captured by Turing complete functions. there is a historical reference to "effective methods" that goes back in earlier math research. most mainstream computer scientists consider the Church-Turing thesis as unequivocal (and yet not provable, hence its name) as can be seen in \[1\] with many refs, although there is a small minority faction that asserts there is some kind of possible gap, but those assertions are very controversial and largely rejected within the mainstream. there is also some theory of hypercomputation which (roughly) attempts to look "beyond" the Church-Turing thesis. see also \[2\] for a strong argument against any theoretical deviation outside of the Church-Turing thesis.

\[1\] Applicability of Church-Turing thesis to interactive models of computation tcs.se

\[2\] The enduring legacy of the Turing machine. Fortnow, Ubiquity, 2010, December 2010

---
Tags: terminology, computability
---


# Question
Title: Are there hardware lock implementations without test-and-set or swap?
Locks are usually implemented thru test-and-set and swap machine-level instructions. Are there other implementations that do not use these?

Also, can we say that all hardware level solutions to the critical section problem can be categorized into just three, namely, interrupt disabling, test-and-set and swap?

# Answer
Yes, you can implement mutual exclusion with only memory load and store instructions. There is a long tradition of devising successively simpler solutions to this problem.

The earliest version that I know of, called "Dekker's solution", was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., *Programming Languages: NATO Advanced Study Institute*, pp. 43-112, Academic Press, 1968. There have been dozens of solutions since then. I will discuss only a few of the more notable ones.

Lamport, Leslie; "A New Solution of Dijkstra's Concurrent Programming Problem", *Comm ACM* 17(8):453-455, 1974 introduces the "Bakery algorithm" (because it is based on the analogy of people taking numbers to determine the order in which they will be served at the bakery shop). One of the particularly notable features of this algorithm is that it demonstrates that no hardware atomicity at all is required to solve the mutual exclusion problem. Reads that overlap writes to the same location can return *any* value and the algorithm still works. Lamport discusses this a bit in the description of the paper on his home page.

Peterson's solution, Peterson, G.L.; "Myths about the mutual exclusion problem," *Inf. Proc. Lett.*, 12(3): 115-116, 1981, is one that is specifically designed to be easy to understand, and reason about. Finally, a particular favorite of mine is Lamport, Leslie; "A Fast Mutual Exclusion Algorithm," *ACM Trans. Comp. Sys.*, 5(1):1-11, 1987. In this paper Lamport was trying to optimize a solution to the mutual exclusion problem in the (common) case that there is little contention for the critical section. It guarantees mutual exclusion and deadlock freedom, but not fairness. It is (I believe) the first mutual exclusion algorithm using only normal reads and writes that can synchronize N processors in O(1) time when there is no contention. (When there is contention, it falls back on an O(N) test.) He gives an informal demonstration that the best you can do in the contention free case is seven memory accesses. (Dekker and Peterson both do it with 4, but they can only handle 2 processors, when you extend their algorithms to N they have to add an extra O(N) accesses.)

Apparently people who work on the problem of solving mutual exclusion using just memory reads and writes get frustrated by other people's (lack of) understanding of the problem and its solutions. This is demonstrated partly by the title of Peterson's paper ("Myths about the mutual exclusion problem") and partly by a short note that Lamport published in 1991: Lamport, Leslie; "The Mutual Exclusion Problem Has Been Solved", *Comm ACM* 34(1):110, 1991, which Lamport describes somewhat bitterly on his homepage.

So to answer your second question: No. There are many more than three categories of hardware level solutions to the critical section problem (using just loads and stores is one, others involve compare-and-swap instructions, load-linked/store-conditional instructions (using the cache coherence protocol to test for atomicity), and fetch-and-add instructions.) In another sense there's really just *one* category of solutions: those that involve getting a bunch of asynchronous processes to agree on a global order of events.

(Note that this answer is an (extensive) edit of an earlier answer I gave for a very different question.)
> 14 votes

---
Tags: concurrency, synchronization, mutual-exclusion
---


title: Creating a grammar from the language

text:
# Question
Title: Creating a grammar from the language
L = { a^n b^2n a^(n+2) : n\>=1 }

So I'm trying to construct the grammar and I'm getting stuck.Some example strings would be these (spaced out to help demonstrate the patterns):

a bb aaa

aa bbbb aaaa

aaa bbbbbb aaaaa

This is what I have so far....

S -\> aXbbXaaa

XbbX -\> bXbbXb

The first rule says that there will always be an a on the left side, 3 a's on the right, and 2 b's in the middle.

The second rule adds 2 b's to the middle for b^2n.

But I can't figure out a way to get the a's....

Any suggestions? I don't want the exact answer, but rather hints to lead me to a solution. Thanks in advance!

# Answer
Hint: The language is not context-free. So you will need to employ a type of grammar that is more powerful. Context-sensitive grammars can do the job.

If you need guidance in how to build a context-sensitive grammar for such a language, you might want check a context-sensitive grammar for $a^nb^nc^n$.
> 3 votes

# Answer
It should be possible to use an attribute grammar to produce strings in your given language. Chapter 3 of the lecture notes provided here motivates attribute grammars using the language $L = \\{a^n b^n c^n, n \>= 1 \\}$. The second attribute grammar for said language may be of particular interest to you
> 1 votes

---
Tags: formal-languages, formal-grammars, context-sensitive
---


title: How to construct a truth table

text:
# Question
Title: How to construct a truth table
Yes this is a homework problem, but I only need help setting it up, there are 7 parts to the question once I set it up:

> We want to build a function Y = 2X + 3 where X denotes a 3-bit unsigned value(x2x1x0) and Y = y4..y0 is a 5-bit value in hardware. Contruct its truth table where input bits are x2, x1, and x0 and output bits are y4 through y0.

The homework problem then asks for a bunch of other things which I can get. I just don't understand the question, how do you create a truth table based on a function and these input bits?

Should the truth table look something like this?

```
x2 x1 x0 y4 y3 y2 y1 y0
0  0  0  0  0  0  1  1
0  0  1  0  0  1  0  1
0  1  0  0  0  1  0  1
0  1  1  0  0  1  1  1
1  0  0  0  1  0  1  1
1  0  1  0  1  1  0  1
1  1  0  0  1  1  1  1
1  1  1  1  0  0  0  1

```

# Answer
> 1 votes
For each of the eight inputs, you compute the output. You will get a table with eight rows and $3+5=8$ columns, containing the three input bits and the five output bits.

---
Tags: boolean-algebra, digital-circuits
---


# Question
Title: Is it possible to solve the critical section problem with an atomic subtract operation?
In my Operating Systems class, our professor asked us to solve the critical section problem with the following atomic operation:

```
int sub(int &x, int val){
  x -= val;
  return x;
}

```

The homework was already due and nobody in my class could come up with a solution. The professor's solution does not even work. Here it is:

```
int x = 1; //let x be a shared variable between threads
entry(){
  int loop = sub(x, 1);
  while(loop < 0){
    loop = sub(x, 1);
  }
}

exit(){
  x = 1;
}

```

This solution suffers from the fact that the critical section may be very long, and thus x may loop all the way back around to positive values and eventually become zero before another thread calls exit(). I do not believe it is possible to solve the CS problem because this implementation of sub() does not return the original value of x, but the new value with val subtracted. The professor is convinced that it is possible, even though neither he nor the TA could come up with a proper answer.

# Answer
If the number of threads is less than the number of values that you can hold in a memory location, then you can implement a non-overflowing `test-and-test-and-set` operation with `atomic-fetch-and-decrement`.

So, for example, if you have 32-bit integers and less than 4 billion threads the following should work:

```
initialize: x = 0

acquireLock:
  repeat:
    while x != 0:
      # do nothing
    tmp = atomicFetchAndDecrement(x) # (decrements x and returns *new* value of x)
  until tmp == -1

releaseLock:
  x = 0

```

Each thread only decrements the counter once for each time that it sees the counter get reset to 0, so the value of x never becomes smaller than `-numberOfThreads`.

The real value of `fetch-and-increment` is that you can make critical sections that are "fair" in the sense that threads are given the lock in the order in which they first request it. Like this:

```
initialize: nextTicket = 0; current = 0

acquireLock:
  myTicket = atomicFetchAndDecrement(nextTicket)       # (decrements and then returns *new* value)
  myTicket = myTicket + 1                # make up for the weird atomicFetchAndDecrement semantics
  while current != myTicket:
    # do nothing

releaseLock:
  current = current - 1                  # does not need to be atomic, releaser is only writer

```

Again, with 32-bit integers this works as long as the number of threads is less than $2^{32}$.
> 4 votes

---
Tags: concurrency, threads, mutual-exclusion
---


# Question
Title: help understanding formal grammar for subtraction example
I am going through the following document trying to understand a simple grammar for a basic subtraction example (page 4).

The example states that

> Simple arithmetic expressions of arbitrary length built from the subtraction operator '-' and the numerals 0 and 1 can be described by the following grammar:
>
> ```
> E = T "-" E | T
> T = "0" | "1"
>
> ```

I understand *T* is the terminal symbols, but I am having a hard time understanding *E*. What confuses me even more is when it is stated:

> Choosing the other alternative for *E* we might get the derivation...
>
> ```
> E ==> "0" "-" E
>
> ```

How and why is an alternative to *E* include *E*? Likewise, I am having a hard time understanding how *ET* derives "0" or how *EET* derives 1.

Could someone better explain this to me? I would greatly appreciate it to move forward in the document. Maybe with a few examples would be extremely helpful.

# Answer
`T = "0" | "1"` means that if you want a `T` string, `0` or `1` will do.

`E = T "-" E | T` means that if you want an `E` string, a `T` string followed by `-` followed by an `E` string will do, or a lone `T` string will do.

Thus, for example, `1` is a `T` string, and is thus also an `E` string. Hence, `1-1` is an `E` string since it follows the `T "-" E` pattern.

Note that the double quote is just a notational device to distinguish terminal symbols from non-terminal ones.

Can you go on from here?
> 2 votes

# Answer
All in " " included strings are called symbols.

What you now to is to e.g. match a given input using your grammar.

Is `1-0` defined in your language? Lets have a look:

You start with the rule `E` which is your starting symbol (usually the first rule). This rule says that `1` has to match rule `T` and `0` match the rule `E` (they are connected using `-` as defined in the first part). When following the rule `T` we actually see that the symbol `1` is right hand side (`|` stands for or). So lets following the rule `E` for `0`. `E` is another substraction (symbol `-`) or just the rule `T` again. The rule T has the symbol `0` so it matches. This means `1-0` is defined by your grammar.

So far so good. Now what happens if you have multiple `-` like in `1-1-0-1`. Then you need the recursion as defined in rule `E` to match it. Can you see it now?
> 0 votes

---
Tags: formal-languages, formal-grammars
---


title: Permutations in an k-sorted array

text:
# Question
Title: Permutations in an k-sorted array
Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order.

I have a question in my Algorithms assignment which asks to prove the lower bound to sort a $k$-sorted array as $\Omega(n\log{k})$. I was trying to approach this question by using the standard comparison sort proof ($\Omega(n!)$), where we have $n!$ total permutations of the sequence \[$a\_1,a\_2,\cdots,a\_n$\]. My friend told me that there are $k^{(n-k)}k!$ permutations of a $k$-sorted array. I'm finding it difficult to prove the same. How should I go about finding the total permutations of a $k$-sorted array?

Try for $n=5$, $k=2$.

Total permutation is $3\times 3\times 3\times 2\times 1$, First element has 3 possibilities $\\{1,2,3\\}$; second has 4 possibilities $\\{1,2,3,4\\}$, but one position is already taken by the first,so effectively it has $(4-1)$ slots; third has 5 possibilities $\\{1,2,3,4,5\\}$, but first and second are there in one of these two, hence 3 possibilities; Fouth one has 4 slots $\\{2,3,4,5\\}$ and 3 of them are taken? (doubt: because 1st position can also be occupied) , hence 2 , and the last has one.

# Answer
Let $N(n,k)$ be the number of $k$-sorted arrays on $n$ elements. At each position we have at most $(2k+1)$ possible elements, giving an upper bound of $(2k+1)^n$. On the other hand, suppose that we divide $\\{1,\ldots,n\\}$ into $n/k$ blocks of size $k$ (assuming for simplicity that $k$ divides $n$), and apply an arbitrary permutation on each block. All of these arrays are $k$-sorted, showing that $N(n,k) \geq k!^{n/k}$. In total, $$ k!^{n/k} \leq N(n,k) \leq (2k+1)^n \\ \frac{n}{k} (k \log k - k + O(\log k)) \leq \log N(n,k) \leq n \log(2k+1) $$ We conclude that $\log N(n,k) = \Theta(n \log k)$.

For the exact expression, consult a paper of Kløve or the OEIS.
> 1 votes

---
Tags: combinatorics, sorting, permutations
---


# Question
Title: Intuition behind recurrences with growth O(n log n) vs O(n²)
Been trying to get the intuition behind *why* two very similar recurrence relations don't follow a pattern I would expect. They are pretty well known relations:

Relation 1 -

$T(n) = 2T(\frac{n}{2}) + n$

Relation 2 -

$T(n) = 2T(\frac{n}{2}) + n^2$

When sketching out a tree for the first recurrence, the way I was taught to think that at every level of a tree, you are doing some amount of work.

```
Height 1 - do some O(n) of work
Height 2 - do some O(n) of work
Height log(n) - do some O(n) of work

```

Now In my head, If i visualize the work as a sum of all the work done, it seems like its $O(n\log(n))$ of work being done, which according to the master theorem is correct.

However, using the same intuition for the second recurrence is *wrong* as we know the master theorem tells us the answer is $O(n^2)$.

Any reason why the intuition seems to be correct for the first recurrence, and why it is wrong for the second?

# Answer
What you are missing is the big O constants. In the first case, at successive heights you are doing work of $$n, 2\frac{n}{2}, 4\frac{n}{4}, \ldots = n,n,n,\ldots. $$ In the second case, at successive heights you are doing work of $$n^2,2\frac{n^2}{4}, 4\frac{n^2}{16}, \ldots = n^2,\frac{n^2}{2},\frac{n^2}{4}.$$ Since the series $1,1/2,1/4,\ldots$ converges, the total work is only $O(n^2)$.
> 5 votes

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


title: Haskell monad bind operator type

text:
# Question
Title: Haskell monad bind operator type
In Haskell, the Monads type class has the bind operator, which is represented by the symbol `>>=`

The type of such operator is:

```
(>>=) :: Monad m => m a -> (a -> m b) -> m b

```

Why does the function need to be `(a -> m b)`? Why functions the preserve che inner data type `(a -> m a)` are not allowed?

Has this choice been made for some convenience in the language design, or does it have some other reason?

# Answer
Here's a nice, and accessible, blog on why we need the type to have that form.

http://cdsmith.wordpress.com/2012/04/18/why-do-monads-matter/

Also, this blog *motivates* why we want them this why and how they naturally arise in our daily workings :)

Enjoy!
> 4 votes

# Answer
```
(>>=) :: Monad m => m a -> (a -> m b) -> m b

```

> Why does the function need to be (a -\> m b)? Why functions the preserve che inner data type (a -\> m a) are not allowed?

You seem to have missed a basic principle behind type variables: you are allowed to instantiate type variables however you please with concrete types, provided they satisfy the typeclass constraints (here, whatever you choose for `m` must be a `Monad`) and are all correctly kinded (`m` must have kind `* -> *` and `a` and `b` must have kind `*`).

So if you wanted to instantiate `(>>=)`, some possible choices are:

* `(>>=) :: Monad m => m a -> (a -> m b) -> m b`
* `(>>=) :: [a] -> (a -> [b]) -> [b]` (instantiating `m` to `[]`)
* `(>>=) :: Monad m => m a -> (a -> m a) -> m a` (instantiating `b` to `a`)
* `(>>=) :: Monad m => m b -> (b -> m b) -> m b` (instantiating `b` to `a`... this is an equal type to the last one).
* `(>>=) :: Maybe Int -> (Int -> Maybe Int) -> Maybe Int`
* `(>>=) :: Maybe Char -> (Char -> Maybe Int) -> Maybe Int`

One last tidbit that can help understand the "shape" of the types for monad combinators. Look for types of the form `a -> m b` where `m` is a monad. These are called Kleisi arrows. If you were fanciful, you might imagine a different syntax for them, like `a ~> b` meaning "a function from `a` to `b` with side effects allowed by some monad `m`".

Looking at the type of bind, you see a raw `m a` type at the front. This is essentially the same as `() -> m a`: a function which takes "no inputs", and produces an `a` with side effects in `m`. The `m b` at the end is similar.

If we rewrite this type in terms of these Kleisi arrows, we get:

`(() -> m a) -> (a -> m b) -> (() -> m b)`

Rewriting using our 'fanciful' syntax above, it becomes a little clearer:

`(() ~> a) -> (a ~> b) -> (() ~> b)`

If you squint, this ends up looking like function composition: You start off with `()`, do something and get to `a` then do a second thing and get to `b`. Combining those two steps into one, we just start with `()` and get to `b` directly.
> 4 votes

---
Tags: functional-programming
---


title: Using the rules of inferences

text:
# Question
Title: Using the rules of inferences
I know the rules of inferences and logical equivalence but I cannot seem to validate this argument. I rewrote the first premise as $\neg p\vee q$ other from that I am stuck. Any help will be appreciated.

$$ \begin{array}{c} p \to q \\ (q \land r) \to s \\ r \\ p \\ \hline s \end{array} $$

# Answer
> 3 votes
Since $p$ and $p\to q$, we have $q$ by modus ponens.
Since $q$ and $r$, we have $q \land r$ by definition of conjunction.
Since $q \land r$ and $(q \land r) \to s$, we have $s$ by modus ponens.

# Answer
> 1 votes
1. Assume: $((p \implies q) \land ((q \land r) \implies s) \land r \land p)$
2. $(p \implies q)$ ($\land E$ 1)
3. $((q \land r) \implies s) $ ($\land E$ 1)
4. $r$ ($\land E$ 1)
5. $p$ ($\land E$ 1)
6. $q$ ($\mathord{\Longrightarrow} E$ 5,2)
7. $q \land r$ ($\land I$ 4,6)
8. $s$ ($\mathord{\Longrightarrow} E$ 7,3)

Therefore: $((p \implies q) \land ((q \land r) \implies s) \land r \land p) \implies s$

Notations: $\land I$ is the introduction rule of conjunction, $\land E$ is the elimination rule of conjunction. $\mathord{\Longrightarrow}E$ is the elimination rule of implication, i.e. modus ponens.

---
Tags: logic, propositional-logic, logical-validity
---


# Question
Title: Computational equivalences between a calculus and an automaton model
This Wikipedia table (template for "Formal languages and grammars") maps grammar to language to abstract machine for more than a dozen languages.

http://en.wikipedia.org/wiki/Template:Formal\_languages\_and\_grammars

But I miss another relation: Lambda calculus (that can be described syntactically as a certain context free grammar) has the same **computational strength** as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore the correspondence between abstract programming languages and automata further by asking this question.

Are there any similar equivalences between a calculus and an automaton, for finite state machines, and pushdown automata, to start with? (Other examples welcome.)

# Answer
As I said, I am not sure how to answer your question.

However, given the current rephrasing of it, it finally rung a memory bell. I think that, starting sometime in the 1970's, people have been studying what they called program schemes.

A set of slides (in French) I found on the web seems to give a historical perspective on the subject.

Slide 14 is about Iterative program schemes, corresponding to Regular sets. They correspond to computational structures of the form `X=f(X,Y)` and `Y=a`, which are only a functional version of iteration loops.

Slide 15 is about Recursive program schemes, corresponding to Algebraic (also known as Context-Free) languages. They correspond to more complex recursive computation structure, using a stack memory as in early recursive programming langages.

I am not certain that is the kind of correspondance you are looking for, as it correspond (as much as I remember) to the computing power of uninterpreted programs, i.e. the structural aspects of the computationq. But it may be worth reading.

There are many more references, including fairly recent ones, if you serach the web with: *"program schemes"*.
> 1 votes

---
Tags: automata, logic, simulation
---


# Question
Title: Proving correctness of an AVL-Tree colouring algorithm
I came up with the following recursive algorithm to colour the nodes of an AVL tree so that the resulting tree is red-black. The logic is that the algorithm first colours the root and, recursively, the left and right subtrees black. Since it is an AVL tree, if the root has height h, one path to a leaf takes distance h, and another is h-1. If h is odd the two subtrees from the root have heights h-1 (even) and h-2 (odd), with the even subtree having an extra black node, hence to be coloured red.

```
(pseudocode)
colour_tree(root(T)):
r <- root(T)
if r = null:
    return
colour(r) = "black"

colour_tree(right(r))
colour_tree(left(r))

if isodd(height(r)):
    if right(r) != null and iseven(right(r)):
        colour(right(r)) = "red"
    if left(r) != null and iseven(left(r)):
        colour(left(r)) = "red"

```

I am having trouble starting on a proof of correctness for this algorithm. I know that for any tree with height h, there are at least $\lceil (h+1)/2 \rceil$ blacknodes, and intuitively it seems like I'd have to perform induction on the height, but I am not sure where to start. Thanks.

# Answer
> 1 votes
You are recursing structurally, so you might want structural induction, but in AVL trees structural induction and induction on height are similar. You probably want to prove something a bit stronger than you need at the end - perhaps something like "AVL trees with height n return RB trees with black height n, and if n is even then neither child of the root is colored red."

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


# Question
Title: How many structurally different trees can be formed with n nodes?
Is there any exact formula for finding number of structurally different unlabeled trees can be formed with $n$ nodes? I searched a lot and I found some approximation formulas, e.g. here.

# Answer
> 4 votes
Check out A000055. Even if this is not what you want, it is probable that the OEIS has your sequence. The easiest way to look for a sequence in the OEIS is by calculating the first few numbers.

# Answer
> 3 votes
Apparently, no such formula is known. You can find a generating function, recursion, and first 1000 terms at OEIS.

---
Tags: data-structures, combinatorics, trees
---


# Question
Title: Could an alternating approach yield a fairer solution to the stable marriage problem?
With the G-S algorithm solution to the stable marriage problem, the proposers get the best possible stable matches, while the reviewers get the worst possible stable matches. This is because the proposers keep walking down the list from their best preference downwards till the stable solution is found, while the reviewers walk up the list from where they start.

To improve the fairness to both parties, consider an alternating variant of the algorithm, where in each cycle, proposers and reviewers exchange roles (for example, in each cycle, men and women switch between the role of proposer and reviewer). Would this terminate with a stable match? If yes, would the resulting stable match be fairer to both parties than the original G-S algorithm?

# Answer
> 4 votes
The idea of the Gale-Shapley algorithm is to consider the graph of possible matchings (i.e. marriages) and trim edges that cannot happen in a stable matching. Eventually, we cannot trim any more edges, and then we can read from the graph a stable matching, indeed both the man-optimal and the woman-optimal stable matchings. For this view, check out for example the beginning of Section 6.3 in this paper. In your algorithm, you haven't specified how the final matching is generated (though perhaps it follows from the proposal terminology), so it's hard to evaluate the result. However, since the graph you'll get in the end is probably the same as in the symmetric Gale-Shapley algorithm, the usual extraction procedures probably wouldn't produce anything other than the two optimal stable matchings. Perhaps it's best if you gave a complete pseudocode of the algorithm, and also tested it on a few sample inputs.

The stable matchings form a lattice structure, so you might think it helps to take the two optimal matchings and generate something "in the middle". However, since they are the top and bottom elements in the lattice, neither the join nor the meet would produce anything new. Instead, there are ways to generate random stable matchings, and these might be fairer to both parties.

For more information, consult Knuth's *Marriages Stables* (available also in English) and Gusfield and Irving's *The Stable Marriage Problem: Structure and Algorithms*.

---
Tags: algorithms, matching
---


title: Type of a return satement

text:
# Question
Title: Type of a return satement
I'm creating a experimental toy language for my own education purposes (an impure typed Lisp based on Clojure - https://github.com/mikera/kiss)

I think I understand the concept of each expression in the language having a return type.

However some expressions may contain flow control statements that mean that the expression will not return normally, e.g.

* An early function return
* A break within a loop
* A continue / recur within a loop
* A goto (*the horror...*)

I'm not sure how to represent these in my type system. Should such things alter the type of the expression? Or should I have a parallel mechanism that enumerates alternative ways the expression may be exited?

# Answer
> 4 votes
There is hardly a good reason to give a `return` expression a type.

In Benjamin Pierce's book, Types and Programming Languages, he mentions a similar situation: the type of `throw` expressions. Like `return`, a `throw` expression will not produce a value and instead changes the flow of control.

Pierce's comment is that if such expressions is to be given a type at all, a logical choice is , the "bottom" type. The bottom type is a type, but one which is impossible to instantiate. There are no objects of type .

This makes perfect sense for expressions that redirect flow in a program. They don't produce a value at all. So to denote this, we say their type is this "uninhabited"  type. If they *did* return a value, this would violate the one and only property of : that there are no values. We would have done the impossible.

If you come from an object oriented background, you might like to think about  as the "dual" of the `Object` type. (We sometimes call `Object` by the name  in computer science). In a subtype hierarchy, every type is a subtype of . Dually,  is a subtype of *every other type*. This means if I had a value of type , I can up-cast it

# Answer
> 3 votes
The type system in most programming language only tracks the type of values. A type system assigns types to a program; if the desired output from the type system is to characterize values, then the type system must assign types to the language constructs that produce value, i.e. expressions.

For example, in such a type system, the basic rule for function application (with a single argument, no subtyping or other subtlety) is $$ \dfrac{F : T\_1 \rightarrow T\_2 \qquad A : T\_1} {F(A) : T\_2} $$ meaning that if $F$ is an expression that returns a function that returns a value of type $T\_2$ when passed an argument of type $T\_1$, and $A$ is an expression that returns a value of type $T\_1$, then $F(A)$ is an expression that returns a value of type $T\_2$.

With such a type system, only things that have a value have a type. So an expression like `x + 1` has a type, but a statement like `return x + 1;` or `break;` doesn't have a type. For an instruction sequence like `{ foo(); bar(); }`, the type system only cares that each expression that makes up a simple statement is well-typed. All the `return` statements in a function must be applied to an expression whose type matches the function's return type, but it's the expression that gets assigned a type, not the `return` statement.

Type systems can track other aspects. For example, a type system can track flow control. This is not very in programming languages but common in static analysis systems. One limited but well-known example is Java: in Java, the type system keeps track of which exceptions a piece of code can raise. This needs to be tracked not only in expressions, but also in statements. For expressions, the type system tracks both the type of the value and the set of possible raised exceptions; for statements, the type system tracks the set of possible raised exceptions. The type of functions must track the set of exceptions that the function may raise. A simplified rule for function application looks like this: $$ \dfrac{F : T\_1 \rightarrow^{S\_2} T\_2 \uparrow S\_0 \qquad A : T\_1 \uparrow S\_1} {F(A) : T\_2 \uparrow S\_0 \cup S\_1 \cup S\_2} $$ where $A : T \uparrow S$ means that $A$ is an expression that either returns a value of type $S$ or raises an exception in the set $S$, and $T\_1 \rightarrow^{S\_2} T\_2$ is the type of a function that takes an argument of type $T\_1$ and either returns an argument of type $T\_2$ or raises an exception in the set $S\_2$. In such a type system, statements have exception sets but no value types. Here are rules to type-check a simple statement and sequential composition: $$ \dfrac{A : T \uparrow S} {A; \uparrow S} \qquad \dfrac{I\_1 \uparrow S\_1 \qquad I\_2 \uparrow S\_2} {I\_1; I\_2 \uparrow S\_1 \cup S\_2} $$

Tracking local flow control is rare for type systems provided with compilers. (Compilers do flow control analysis internally as part of optimization and machine code generation, of course, but programs are not rejected at that stage, so this is rarely modeled as a type system.) It is more common in systems for slow (if not non-terminating) static analysis that attempt to prove properties such as termination, bounds checking, etc.

A type system can track model local flow control by tracking the continuations for a statement, i.e. what happens next. Unless you're willing to stick to sufficiently restricted (non-Turing complete languages), or to have a non-decidable type system, the type system will have to over-approximate and thus track possible continuations, i.e. what cannot be ruled out to happen next. For example:

* If $A$ is an expression without side effects, its only possible continuation is local return (i.e. the expression is evaluated and its context gets to use the resulting value).
* If $A$ is guaranteed not to terminate, then local return is not a possible continuation.
* The possible continuations of `foo; bar` are:
    + the continuations of `foo` other than local return
    + the continuations of `bar`, if local return is a possible continuation of `foo`
* The possible continuations of `if condition then foo else bar` are the possible continuations of `foo` or `bar`.
* The continuation of a `return` statement is the context of the function call.
* The continuation of `break` is the context of the enclosing loop.
* The continuation of `continue` is the context at the loop body start.
* The continuation of a `goto` is the context of the target label.

This type system would have judgements of the form $A : T \rightsquigarrow C$ and $I \rightsquigarrow C$ where $A$ is an expression, $I$ is a statement and $C$ is a set of continuations.

---
Tags: compilers, type-theory
---


# Question
Title: Two Step Verification. 4 digits vs 6 digits
From a security level standpoint (such as Server, DataBase, Token Code, Authorization, Authentication, etc.) in regarding the Two Step Verification, usually Apple send a total of **4** digits security code vs Google send a total of **6** digits security code. What are the main differences?

# Answer
> 2 votes
The number of digits in such a one-time password is determined by the acceptable risk that an attacker who doesn't receive the verification code will be able to guess it (lucky guess). This risk takes into account several factors:

* the probability that an attacker will be able to guess;
* the negative consequences of an correct guess by an attacker;
* the probability and the negative consequences if the code is too long and this discourages the user to use the service.

For an $n$-digit code, if there is a single valid code and the code is generated at random, then the probability of a lucky guess is $10^{-n}$. That's 1/10,000 for a 4-digit code, 1/1,000,000 for a 6-digit code. These are usually acceptable figures when the one-time code is a second factor (usually complemented by knowing a static password or possessing a physical device); they would be grossly insufficient if the code alone was enough to access a service.

When the code is sent from a remote server to the user's device, there is generally a single valid code which is randomly generated. Some one-time password schemes don't require communication between the server and the user's device, but instead have both sides generate a pseudo-random code in the same way using a shared secret key and a counter. In this case, there are usually several valid codes, to allow for desynchronization between the client and the server; this requires a slightly longer code to compensate for the increased number of possible lucky guesses.

---
Tags: security, authentication
---


# Question
Title: In ID3 algorithm, which attribute to choose if information gains are equal?
In the ID3 algorithm for building a decision tree, you pick which attribute to branch off on by calculating the information gain. What happens if the calculated information gain is equal for two different attributes? Can you choose either attribute as the new branch?

# Answer
Yes. As @Aaron says, it's fine to choose an attribute arbitrarily.

Keep in mind that choosing the attribute with the highest information gain is just a heuristic. It's a local greedy choice. There is no guarantee that making the local greedy choice at each level will necessarily give you a global optimum (i.e., the best possible decision tree); indeed, it might not do so. Instead, it is a heuristic that empirically seems to work pretty well in practice. Resolving ties arbitrarily is in line with that heuristic. There are already no guarantees when using this heuristic, so you're not giving up any theoretical guarantees in this way. The primary focus of this heuristic is to make it efficient to build a decision tree (so you don't have to try all exponentially possible decision trees); resolving ties arbitrarily is in keeping with that focus.
> 6 votes

---
Tags: algorithms, machine-learning
---


# Question
Title: What is the name of the problem? (partitioning graph into three covers)
I was wondering if this problem has a name:

Given a simple graph whose edges are colored red, blue and green, $G=(V,B\cup R\cup G)$, is there a vertex-coloring $c:V\to \\{B,R,G\\}$ such that every edge has an endpoint with the same color?

Also, is this known to be NP-complete?

---

This can also be viewed as a special case of CSP (or a generalization of 2SAT) where each constraint is a disjunction of 2 variables that could take one of three values, and there are no two constraints on the same variables-pair.

# Answer
Your problem can be solved in linear time, by reduction to 2SAT. For each vertex $v$ we will have three variables $v\_R,v\_B,v\_G$ and clauses $\lnot v\_R \lor \lnot v\_B,\lnot v\_R \lor \lnot v\_G, \lnot v\_B \lor \lnot v\_G$. These ensure that at most one of $v\_R,v\_B,v\_G$ is true. For each edge $(v,w)$ labeled $R$, we will add the clause $v\_R \lor w\_R$. If there is a valid vertex coloring in your sense, then it clearly translates to a solution of this 2SAT instance. Conversely, any solution to the 2SAT instance corresponds to a partial coloring in which each edge is incident to a vertex with the same color. Coloring the other vertices arbitrarily, we obtain a valid vertex coloring in your sense.
> 6 votes

---
Tags: algorithms, complexity-theory, graphs, satisfiability, colorings
---


# Question
Title: Source Coding Theorem: what happen when go below N⋅H(x) bits?
I was following the text book by David Mackay: information theory inference and learning algorithms, this could be found online on his website.

I have question on the source coding theorem (emphasis mine):

> **Shannon's source coding theorem** (p81): $N$ i.i.d. random variables each with entropy $H(x)$ can be compressed into more than $N \cdot H(x)$ bits with negligible risk of information loss, as $N \to \infty$; *conversely if they are compressed into fewer than $N \cdot H(x)$ bits it is virtually certain that information will be lost*.

My question is the emphasised part of the above, *what happens when you go below $N \cdot H(x)$ bits*?

There is an example in the textbook (p77), which he shows that, as $N$ increases, the average entropy per symbol approaches $H(X)$, for the risk tolerance between $0\< \delta\< 1$. (So it becomes more flat as indicate on the diagram).

Therefore, $N \cdot H(x)$ is the number of bits you can compress no matter how much risk tolerance you are willing to take. In the theorem above, however, it is saying that information will be lost if you go below $N \cdot H(X)$. My question is, how much information will be lost?

# Answer
For each bit that you compress beyond the entropy limit you lose one bit of information. Keep in mind that this theorem deals with random variables. If you want to know what happens to a specific input then you need a different kind of analysis.
> 2 votes

---
Tags: coding-theory, encoding-scheme
---


# Question
Title: Can file snapshots aid in detecting malware?
I noticed certain programs have a feature that can have a 'snapshot' of a file from a certaim time and compare it to a more recent snapshot of the file. If one's system has a snapshot of a program when 'first' downloaded and it can compare this to the program 'as it is now' and if there are any changes this might indicate the file is corrupt and it could be marked for possible removal. So could this comparison feature be used to determine if a file is corrupt?

# Answer
This is not likely to be very effective in practice. Malware might corrupt the file before you were first able to take a snapshot... or, more realistically, it might corrupt the snapshot you have taken, so that the snapshot matches the current version of the file. It is difficult to defend against that attack.

So, while your idea is not a bad one, it has significant limitations that might render it not terribly useful in practice.

This also assumes that the underlying file is one that should never change. Of course, in practice, for any given file, there are valid circumstances when the file should be allowed to change. So this means you'd need some way to recognize valid, legitimate changes to the file. This starts to get a bit more complex to implement.

You might take a look at Tripwire, which is a system that does something like this -- except it keeps only a cryptographic hash of each monitored file, rather than a full copy of the file.
> 2 votes

---
Tags: security, filesystems
---


# Question
Title: Decremental reachability in a grid graph
Consider an $n$ by $n$ grid graph. For example, the following.

You can of course reach the top left corner from the bottom right. Now consider the graph dynamically with an arbitrary number of edges deleted at each step.

> What is the time complexity of determining whether you can still reach the top left corner from the bottom right after edge deletions?

---

**Further clarification.**

**Queries.** There is exactly one type of query which gives a Boolean output. That is whether there is a path from the top left corner to the bottom right.

**Updates.** An update can delete an arbitrary number of edges greater than $0$.

**Complexity.** Each update is followed by a query. The complexity I am interested in is the amortized time over all updates and queries. The best this could possibly be would be proportional to the number of deleted edges I assume.

---

I found these lecture notes which say you can get $O(\log{n})$ time for planar graphs per individual edge deletion (the Eppstein et al. reference). However this paper supports many more operations than I need, my graph is a special case of a planar graph and my updates are in batches in a sense. The most important difference may just be that I am only interested in the decremental version. I haven't found anything specialized for batched, decremental connectivity in a grid graph.

Is there anything simpler than the Eppstein et al. paper for my special case or alternatively faster than $O(\log{n})$ time per edge deletion?

# Answer
"Optimal decremental connectivity in planar graphs", by Jakub Łącki, Piotr Sankowski demonstrates an algorithm that uses $O(1)$ amortized time per update and $O(1)$ time per query.
> 3 votes

# Answer
By improving on @emab's idea, you can achieve $\Theta(\alpha(n^2))$ amortized time per deletion and query, where $\alpha$ is the inverse Ackermann function, i.e. almost constant.

* Initialize a union-find data structure with an enry for each square of the grid graph and two entries each for the two pairs of outside faces top+right and bottom+left. For an example of $n=3$, the faces $1,2,3,\ldots,9,A,B$ in the diagram below are initialized. Where $A,B$ are the outside faces split by the dashed lines.
* When removing an edge call `union()` on the two squares (or the sqare and $A$ or $B$) separated by that edge.
* To check connectivity, call `find()` on the faces $A$ and $B$. If the results differ, return true, else return false.
> 3 votes

# Answer
Let's call the top-left node as $s$ and the bottom-right node as $t$.

In the square drawing of this graph, there are four sides (left, right, top, bottom).

Let's call two edges connected, iff they share a square or an endpoint (we can determine if two edges are connected or not in $O(1)$).

As you remove the edges from the graph, you maintain a few lists of those edges. that are connected, and see if any of them connect one of the four side pairs:

* top to bottom
* top to left
* left to right
* bottom to right

In the following figure, by dashed red lines, I tried to demonstrate a series of edge removals (if the red dashed line crosses an edge, it means that the edge is removed at some point).

(Algorithm is below figure)

**Algorithm**

```
Component = []
/* Initialize Hit_Sides by 0 */
Hit_Left = []; Hit_Right = []; Hit_Top = []; Hit_Bottom = [];
while ( input >> e; /* there is an edge e to be removed */)
    L = L + {e};
    Component[e] = e;
    if (e hits any side s) then
        Hit_s[e] = 1;
    For each e' in L
        if (e' is connected to e)
            Component[e] = Component[e']
        if (e hits any side s)
            Hit_s[Component[e] = 1;
    For each component c in Component
        if (it hits one of the four disconnecting pairs)
            Output << There is no path from s to t

```

BTW, the following explanation is clear and precise. However, if you use geometrical techniques, you may be able to get some logarithmic algorithm out of it.

---

If you maintain a list of edges that are being removed, you can consider the list of connected ones, and see whether they hit any disconnecting sides (top-bottom, top-left, left-right, bottom-right) and answer to that reachability query in $O(1)$.

In the following figure, red lines illustrate the disconnecting sides:
> -3 votes

---
Tags: algorithms, graphs, data-structures
---


title: Proof of P-Hardness by reduction

text:
# Question
Title: Proof of P-Hardness by reduction
I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?

# Answer
By definition, a language $L$ is P-complete if for every language $M \in P$ there is a logspace reduction $f\_M$ such that $x \in M$ iff $f\_M(x) \in L$. Now suppose that $L$ is P-complete and that for some language $L' \in P$ there exists a logspace reduction $g$ such that $x \in L$ iff $g(x) \in L'$. Then for every language $M \in P$, $x \in M$ iff $g(f\_M(x)) \in L'$, and so $L'$ is P-hard since the composition of logspace reductions is a logspace reduction.

Generalizing, this sort of argument always works as long as the composition of two legal reductions is a legal reduction. This is the case for both polynomial time reductions and logspace reductions.
> 3 votes

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


# Question
Title: Are there any garbage collectors that take into account paging?
Garbage collections have to visit all objects that are alive, so as to find the memory that can be reclaimed. (Having many generations’ just delays this a bit)

All things being equal, it is clearly better to first visit the object that are already paged into RAM, before paging other block in and therefore paging out some object.

Anther possibility is that when the OS wishes to take a page of ram away from the process, the GC is first asked if it has a page that can be given up without needing to be paged out. The GC may be mostly done with moving objects from a page, so can clear that page within the time limit the OS has for needing a page.

Yet, I cannot recall any garbage collector that integrates with the OS paging system that drive the order the GC works in.

# Answer
> 8 votes
As I recall, copy collectors are supposed to be paging friendly, as the tracing by copying tends to improve the locality of pointer references. This has a positive effect on the program (mutator) that will cause less page faults when following links, and will also improve the next collection cycle as tracing will also cause less page faults. The tracing agenda (which pointers should be processed first) can have an impact on the effectiveness for improving data locality. This may be improved by mesuring statistics on the number of access to different pointers in different types of cells.

Now, if you consider a tracing collector in general, you must usually maintain a structure that keeps track of the pointers that have not been traced yet. It may be possible to organize this structure so that all waiting pointers pointing in the same page will be kept together (though that may take more space, in some cases, depending on the available techniques to keep the list of such pointers). A possible policy is then to always trace first the largest set of waiting pointers pointing to the same page, when there is no waiting pointer left to the pages in memory.

Regarding the question in the third paragraph, that was added after I answered, copy collection is again an answer. The OS may reduce the number of allocated physical pages at collection time, since the pages are completely freed. With a mark and sweep collector, the event of a full page beeing free is probably much rarer, thus not worth a specific machanism to be taken into account.

This kind of ideas is natural, and is probably described in some of the papers. But I do not recall it off hand. I think the early papers on Lisp GC contain some of these ideas (such as: should car or cdr be followed first?).

The good news in this role of copy-collection is also that paging is friendly to copy collection since it increases the available storage space. Recall that the copy collector requires in principle twice as much space as used for actual data storage. Now, the effect of paging depends also on the address space of the machine, and the physical memory available. In older computer, physical memory was much less than available address space, so that paging was really a space bonus, allowing policies such as copy GC. Even when physical space is as big as the address space, one might want to share it, so that the process using a GC would have less address space without paging (see paging). These remarks are somewhat superseeded by the use of generational collectors. They generally use copy collection for the young generation precisely because of these qualities, and because the young generation is mostly short lived.

Then you have all the interactions of generational GC with the cache system, that has been discussed in a previous question: Are generational garbage collectors inherently cache-friendly?

For more information on these issue, I would search the web with, for example, the keywords *garbage collection* and *locality*.

# Answer
> 8 votes
Emery Berger, Matthew Hertz & Yi Feng did some work on this.

> Garbage collection offers numerous software engineering advantages, but interacts poorly with virtual memory managers. Existing garbage collectors require far more pages than the application's working set and touch pages without regard to which ones are in memory, especially during full-heap garbage collection. The resulting paging can cause throughput to plummet and pause times to spike up to seconds or even minutes.
>
> I present a garbage collector that avoids paging. This bookmarking collector cooperates with the virtual memory manager to guide its eviction decisions.

This is a video of Emery’s talk on it, and he wrote a paper Garbage Collection Without Paging

For some reasons there does not seem to be much later work on it, or any “real world” usage. At the end of the paper it says *“We are developing a concurrent variant of the bookmarking collection algorithm”*, but I can’t track it down.

CRAMM: Virtual Memory Support for Garbage-Collected Applications looks at changing the OS to make GC create less paging.

Using Page Residency to Balance Tradeoffs in Tracing Garbage Collection

> We introduce an extension of mostly copying collection that uses page residency to determine when to relocate objects. Our collector promotes pages with high residency in place, avoiding unnecessary work and wasted space. It predicts the residency of each page, but when its predictions prove to be inaccurate, our collector reclaims unoccupied space by using it to satisfy allocation requests.Using residency allows our collector to dynamically balance the tradeoffs of copying and non-copying collection. Our technique requires less space than a pure copying collector and supports object pinning without otherwise sacrificing the ability to relocate objects.Unlike other hybrids, our collector does not depend on application-specific configuration and can quickly respond to changing application behavior. Our measurements show that our hybrid performs well under a variety of conditions; it prefers copying collection when there is ample heap space but falls back on non-copying collection when space becomes limited.

---
Tags: memory-management, paging, garbage-collection
---


# Question
Title: Is a very long plain text password harder to crack than a short complicated password?
Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters?

# Answer
Usually when we talk about "hard to find" we are talking about brute force guessing. This is where the attacker just keeps trying different passwords till they find the right one. I'm going to assume we're talking about this model here and not talk about the real world with hashing and rainbow tables and so forth.

Now, there is nothing inherently different about trying a 5-character random string versus trying a 4-word password. They are both equally easy for a computer to plug in and see if they work. Instead, the question is how many guesses you need to find the password, i.e. how hard is it for an attacker to guess your password.

Now, an important question is what the attacker knows about your strategy of picking passwords. We usually want to make the worst-case assumption that the attacker knows our method for picking passwords. Under this key assumption, we can compare the two methods.

If we pick a 5-character password uniformly at random from all strings containing a-z,A-Z,0-9,!@#\\$%^&\*()-\_+={}\[\];:'"|\\,\<.\>/? then we have something like $92^5 \approx 6.6$ billion possibilities. So the attacker has a one in $6.6$ billion chance of guessing it on the first try, and so on.

If we pick 4 random words uniformly from a set of say 500 words, then we have $500^4 = 62.5$ billion possibilities. So in this example, the attacker is worse off trying to guess a 4-word random passphrase than a 5-character random string. Notice that the example is really assuming that we do this random process for picking passwords, i.e. we run a computer program that takes a list of 500 words and (using good randomness!) spits out a sequence of 4 random words.

Also notice that both of these examples assumed that the attacker knows your strategy. If the attacker is first going to try all 4-word passphrases, and then all 5-character strings, then you would rather have a short random string because it will take longer for that attacker to guess. But since you don't know what the attacker knows, you're best off assuming they know what **type** of passwords you use, but they don't know **which one** you picked. And by "type" of password, I really mean a method of **generating** that password, like uniformly random 5-character strings. Thinking about this method, as we did above, tells you how random or hard-to-guess it is.
> 0 votes

---
Tags: cryptography, information-theory, security, entropy
---


# Question
Title: Terminology about the word Function : General vs Computable
I've seen two different concepts referred to by the term "function":

* A small part of a program specified by the composition of constants and other functions as paramaters, such as the "functions" in Lisp
* A set of tuples, as referred to in formal logic, which is not necessarily computable

The first concept is very fundamental to software design. The second concept is very fundamental to formal reasoning. However, a task I've been working on is analyzing software with formal logic, so the conflation of the terms is a bother.

Is there any agreed upon, concise, unambiguous terminology to distinguish these two ideas? I can think of several verbose terms, such as "Computable Function" and "General Function", but imagine having to type that out with the specification of every modular component.

Any references, ideas, or supported opinions are appreciated, thanks.

# Answer
A (mathematical) function $f$ with domain $X$ and range $Y$ is a set of pairs $(x,y) \in X \times Y$ such that for each $x \in X$ there is exactly one pair of the form $(x,y)$; we say that $f(x) = y$.

A computable function $f$ is a function computed by some program.

A function in a programming language is an entity whose exact definition depends on the programming language. For example, in Pascal a function is a subroutine returning a value, in C a function is any subroutine, and in functional languages a function is either a declared subroutine or an "anonymous" function arising as some lambda expression.

Summarizing, the meaning of *function* depends on context. In a mathematical context or in some parts of theoretical computer science (say, complexity theory), a function is an arbitrary mapping; this is also probably the case in programming language theory, but I'm not qualified to say. In software engineering the meaning might depend on context. Computable functions (also known as recursive functions) are always called that.
> 3 votes

---
Tags: terminology, logic
---


# Question
Title: Why does a DFA either contain all or no words $a^k$ if it loops for $a$ in all states?
I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below:

> Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states $q$ of $A$ we have $\delta(q,a)=q$.
>
> Show that either $\left\\{a\right\\}^\*\subseteq L(A)$ or $\left\\{a\right\\}^\*\cap L(A)=\emptyset$.

As far as my understanding of the first part of the problem, the language accepted by $A$ is $L(A)=\left\\{a, aa, aaa, aaaa, aaaa...\right\\}$.

Since, $\left\\{a\right\\}^\*$ represents strings that belong to $L(A)$ including $\varepsilon$, therefore $\left\\{a\right\\}^\*\subseteq L(A)$ is true.

How to show that $\left\\{a\right\\}^\*\cap L(A)=\emptyset$? Doesn't $L(A)$ represent strings generated by $\left\\{a\right\\}^\*$? How can the intersection be $\emptyset$?

# Answer
> 1 votes
Hint: Suppose that $a^k \in L(A)$ for some integer $k$. Consider the initial state $s$ of $A$. From the premises it follows that $\delta(s,a^k) = s$, and since $a^k \in L(A)$, $s$ must be an accepting state. For every integer $\ell$ we have $\delta(s,a^\ell) = s$ and so $a^\ell \in L(A)$.

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


title: The buckets of water problem

text:
# Question
Title: The buckets of water problem
Let's consider the following problem (buckets/pails of water problem) (This problem may be known with different name. If does, please correct me).

Let $B=\\{b\_1,...,b\_n\\}$ be a set of $n$ buckets. Suppose each bucket has a maximum capacity $c\_i \in \mathbb{Z}$. This also can be written as a maxium capacity function $f:B \rightarrow \mathbb{Z}$ such that $f(b\_i)=c\_i$.

Let $g:B \rightarrow \mathbb{Z}$ be a function such that $g(b\_i)$ is the current amount of water in bucket $b\_i$.

Suppose that we can do the following operations.

1.Fill bucket $b\_i$ from tap until its full, i.e. $g(b\_i)=f(b\_i)$.

2.Move water from bucket $b\_i$ to bucket $b\_j$ until $b\_i$ is empty or $b\_j$ is full.

3.Empty bucket $b\_i$.

Now, the problem is given a number $m \in \mathbb{Z}$ to find a sequence of operations $s\_1,...,s\_k$ such that after $s\_k$ we have a bucket with $m$ amount of water, i.e. $g(b\_i)=m$ for some $i \in \\{1,...,n\\}$, or return that such sequence doesn't exist.

My questions are :

1.How to solve this problem? Is this problem NP Hard? If it is NP Hard, why? How to prove this?

2.What about the case when we are interested in the optimal $k$, i.e. we want minimum number of steps?

3.Does this is a well known problem? If yes, what is the known name for the problem and what good references exists for this problem?

I want to note that I fully understand the case of $n=2$, and I am interested in the generalization of $n$ buckets instead of just $2$. The $n=2$ case described in https://mathoverflow.net/questions/5800/generalization-of-the-two-bucket-puzzle.

Edit: I now know how to prove that this is NP Hard problem. I want to know if there is an efficient algorithm for solving this (maybe some pseudo polynomial algorithm).

# Answer
> 8 votes
The problem is NP-hard, by reduction from SUBSET-SUM. Given a multiset of numbers $x\_1,\ldots,x\_n$ and a target $T$, consider $n$ buckets with capacity $C=x\_1+\cdots+x\_n$, initially filled with $x\_1,\ldots,x\_n$, and ask whether you can obtain a bucket filled with exactly $T$. You can prove by induction that all buckets are always with filled either with $C$ or with the sum of some (possibly empty) subset of the $x\_i$s.

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


# Question
Title: How can an algorithm have exponential space complexity but polynomial time complexity?
For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback problems". It is said that it runs in polynomial time but uses exponential space in a dictionary.

```
insert F_q into Q and into D;
while Q is not empty do
  remove any set F from Q;
  output F;
  for each uG-successor F′ of F do
    if F′ is not contained in D
      insert F′ into D and Q;
    fi
  od
od

```

How can this be? Does an exponential number of insert operations to the dictionary not inevitably imply exponential time?

# Answer
This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes:

> Observe that the number of minimal, and even minimum solutions, can be exponential in the size of the graph; Fig. 1 gives an example. Therefore, the total running time of any enumeration algorithm cannot be expected to be polynomial in the size of the graph.

The paper goes onto explain the concept of polynomial delay,

> However, certain enumeration algorithms for other combinatorial problems work with polynomial delay, i.e., the algorithm performs at most a polynomial number of steps before the first and between successive outputs.

What's polynomial isn't the entire runtime of the algorithm, its the time between successive outputs. Since the algorithm can output an exponential number of items, the total run time can quite easily be exponential.

When it comes to memory, the paper states:

> Note that memory requirements are polynomial for graphs with a polynomial number of MFVS, but potentially exponential for the general case.

Memory goes exponential if we have an exponential number of outputs. But in that case, there is an exponential amount of time passing to fill up that amount of memory as well.

Put another way, memory is exponential because we are measuring memory usage over the entire enumeration process. Time is polynomial because we are only measuring time between two outputs.
> 11 votes

# Answer
What they probably mean is that the domain of the dictionary has exponential size. This is not a problem since you can implement the dictionary using a hash table. If the program runs in time $T$ then the hash table would have size $O(T)$ and all operations have expected time $O(1)$.

Note, however, that using a hash table we only get a *randomized* algorithm; if you want a deterministic algorithm then you might lose some $\log T$ factor in the running time (say using some self-balancing binary tree), but it will remain polynomial.
> 2 votes

# Answer
You're correct that *on a Turing machine*, any algorithm that uses space $f(n)$ must use time $f(n)$ to move the tape heads far enough to access that space. However, models of computation that allow random access to data held in memory don't necessarily have that property.
> 0 votes

# Answer
Splitting calculations into space and time is one way to describe the behavior of the equation. What this is saying is that the calculations do not need to actually compute over the full size of the data to compute the result. This is maybe reasonable since you only need to locate a single vertex in each cycle.

didn't read the full algorithm but probably it has something to do with

Say you have a clique of size N. That queue could approach N! in size, but you may not actually need to computer over the full N! edges to find the solution
> -1 votes

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


# Question
Title: When are binary trees better than hashtables in real world applications?
I am currently bushing up on my data structures and basic algorithms, part of that is the Binary Tree. I do understand the algorithms, and how to implement a binary search tree and such. I do so how smart it is that we can do lookups in O(log n) time.

I am however having a hard time finding an example of when I would use a binary tree, where a hash tables would not do the same/better job. I have been doing some searching around and found that it is used for 3D graphis, something about what items are to be displayed, i do however have a hard time relating to this.

Can any one give me an example where it would be better to user a binary tree over a hash table?

# Answer
Hash tables can only tell you if an element is present or not.

Here are somethings you can do with a binary tree that you can't do wiht a hash table.

* sorted traversal of the tree
* find the next closest element
* find all elements less than or greater than a certain value

See this wikipedia article on K-d trees for an example of a real world data structure that makes use of the special properties of binary trees. http://en.wikipedia.org/wiki/K-d\_tree
> 14 votes

# Answer
One application domain where binary trees are better, or more easily adjustable than certain alternatives, are persistent data structures (which are often used in (purely) functional programming).

A persistent data structure is a data structure that preserves the previous version of itself when it is modified. (Data structures that do not have this property are called *ephemeral*.) One benefit of this kind of data structure is that it allows sharing of parts of the data structure - since the structure itself is guaranteed not to change, it is safe to share it freely between other data structures and even threads without worrying about it changing. Another *subjective* benefit is that these data structures are easier to reason about.

Conceptually, you could have an immutable data type that is a list of numbers, e.g., $L\_1 = \\{3,4,5\\}$. Then you could introduce a new value that adds two numbers to the front of this list: $L\_2 = cons(1,cons(2,L\_1)) = \\{1,2,3,4,5\\}$. What happened to $L\_1$? Nothing - $L\_1 = \\{3,4,5\\}$, still. Did $L\_2$ copy those three elements and put it into its own list, then? Ideally not - the values in list $L\_1$ belongs to $L\_2$, also:

$ \overbrace{ 1, 2, \underbrace{3,4,5}\_{L\_1} }^{L\_2} $

There are data structures that are more well-suited for implementing persistent lists like the one above. In the same vein, binary trees are more well-suited for implementing persistent data structures with certain properties, than other data structures or strategies. And the structural sharing shown in the example with the two lists carry over to binary trees - you can imagine that several *versions* of a tree can share sub-trees that they have in common.

Like I said, some data structures are easier to amend to be persistent. You mention hash table, which is typically (if not even necessarily) an ephemeral data structure. It seems less obvious how one can adjust a common implementation strategy for a hash table to be persistent. Consider that a hash table is often implemented with an array (specifically, arrays that are implemented as a continuous part of memory). Arrays are nice since they provide random access to elements, which is an important property since you ideally want to have $O(1)$ average access to elements in the hash table. But arrays aren't that nice when it comes to building persistent data structures. The gist of it is that, while you can make an immutable array data type, by the nature of arrays, you risk having to do a lot of copying - If the aforementioned List type was implemented with arrays, you would risk having to create a whole new array with five elements, instead of sharing part of it. And what if you want to modify something in the middle of the array? The most obvious - and seemingly unavoidable - answer is, again, *copying*.

Persistent data structures do not avoid having to do copying, in general. But certain data structures make copying less frequent. This is a desirable property when you demand that a data structure has to be immutable.
> 11 votes

# Answer
A binary tree has many applications, especially if we include all binary trees and not just binary search trees. Heaps are implemented as binary trees where the top most element is either a min or max value of all elements, which is very useful for a scenario that calls for a priority queue.

Hashmaps are very efficient in a set type of operation where one is simply checking for existence of an element. But they are weaker when it comes to performing non-existence checking operations on ordered or sorted data. Furthermore, while it would be possible with tweaking of the hash algorithms, binary trees seem to better support the notion of partial key searches. For example, one could try to use a binary tree of strings to answer which words begin with "an". Granted a trie would be a better data structure for that type of scenario.
> 4 votes

---
Tags: data-structures, trees, binary-trees, applied-theory
---


# Question
Title: What is the runtime of the following code?
Can you explain to me how you get the Big O notation for the runtime of the following snippet of code?

```
for x = 1 to n
{
    y = 1
    while y < n
       y = y + y
}

```

Can you explain the steps on how you get the big O notation for it? Also why doesn't it matter if there a bunch of statements inside a for loop when calculating the big O notation? Wouldn't the number of operations increase as n gets larger if there are more O(1) statements inside the for loop? Help would greatly be appreciated.

# Answer
> 2 votes
Hint: First of all, since the code in the loop doesn't depend on $x$, the running time of the code is $\Theta(n)$ times the running time of the code inside the outer loop. Second, the running time of the code in the inner loop is $\Theta(\ell)$, where $\ell$ is the number of iterations of the while loop, which is the number of times you need to double $1$ until you reach or exceed $n$. Perhaps you can find a formula for $\ell$.

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


# Question
Title: Is this a good approach for first attempt to create my own language and compiler?
I want to try to create my own very simple programming language and it's compiler or interpreter.

The programming language I use is Java.

My idea was to create a compiler which will compile source code of my created language to some kind of intermediate code (nothing binary or complex, just plain text), and then have another program (a kind of virtual machine or interpreter) which will execute this intermediate code in Java.

For example, the 'programmer' types: `write "hi world"`. The compiler turns it to some intermediate code like `w-hi world`. The VM/interpreter program reads this intermediate code and executes `System.out.println("hi world");`

My question is:

Is this approach common with programmers who want to try to create a simple language for the first time? **Is this a good way to start?**

*I searched this site and came across questions on this subject, but the answers were more complex and technical than what I'm looking for.*

# Answer
> 2 votes
That sounds like a fine way to start, and you'll become familiar with the issues involved.

*How's it going?*

At a certain point, consider learning more about programming language implementation techniques from

It's also worth investigating libraries to use such as parser generators, although some people swear by the recursive descent parsing approach as easier to build, also good at generating helpful error messages.

Another tip: It's easier to implement a programming language in a language like Clojure than Java. (Clojure is a modern Lisp dialect that's hosted on Java.) E.g. your intermediate representation could be a list of Clojure forms. They handle reading & writing as readable text, and you can construct & interpret (eval) them quicker and easier than text.

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


title: Whats the name of this search game?

text:
# Question
Title: Whats the name of this search game?
I am struggling in finding the name of this game (in order to find research papers related to it in the literature).

Given an initial word $X$ and a target word $Y$, what is the minimum number of (letter) flips needed for $X$ to reach $Y$ assuming $X$ and $Y$ having the same number of letters, we flip only one letter each time and such sequence(s) of flips exist.

That is, there is a sequence $A\_1\rightarrow A\_2\rightarrow \dots\rightarrow A\_n$ where $X=A\_1$ and $Y=A\_n$ and every thing in between is a correct word (i.e. has a meaning in a given dictionary).

For instance, $X=Pork\rightarrow Park\rightarrow Dark=Y$

Yes; I do not have the minimum knowledge in games.

# Answer
> 2 votes
I think you are referring to Hamming Distance. See http://en.wikipedia.org/wiki/Hamming\_distance.

As for a game, having the extra condition that intermediate modifications must be real words is the Word Ladder. See http://en.wikipedia.org/wiki/Word\_ladder.

---
Tags: board-games, search-problem, computer-games
---


title: How to vocalize hexadecimal numbers?

text:
# Question
Title: How to vocalize hexadecimal numbers?
When I want to vocalize a hexadecimal number like 0x41, so I say "forty one in hexadecimal", "four, one in hex" or what? Or do you always have to calculate and say "65 in hexadecimal notation"? I feel like that would complicate communication if I just want to tell someone what numbers I see on the paper in fornt of me, so he can write them down for example.

# Answer
The best way is to read out the digits and then say "hex(adecimal)". Don't say "forty-one hex" because "forty" means four times ten, whereas the four in 41h stands for four times sixteen. Don't say "sixty-five in hex" because then the person you're talking to doesn't know if you mean "The decimal number sixty-five, only written out in hex, i.e., four-one-hex" or "The number six-five-hex, i.e., one hundred and five decimal."
> 1 votes

---
Tags: terminology
---


# Question
Title: How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?
I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1).

> (a) Describe an algorithm that sorts an input array $A\[1 \ldots n\]$ by calling a subroutine $\texttt{SQRTSORT}(k)$, which sorts the subarray $A\[k + 1 \ldots k + \sqrt{n}\]$ in place, given an arbitrary integer $k$ between $0$ and $n - \sqrt{n}$. How many times does your algorithm call $\texttt{SQRTSORT}$ in the worst case?

*Note: To simplify the problem, assume that $\sqrt{n}$ is an integer. Your algorithm is **only** allowed to inspect or modify the input array by calling $\texttt{SQRTSORT}$; in particular, your algorithm must not directly compare, move, or copy array elements.*

> (b) Prove that your algorithm from part (a) is optimal up to constant factors. In other words, if $f(n)$ is the number of times your algorithm calls $\texttt{SQRTSORT}$, prove that no algorithm can sort using $o(f(n))$ calls to $\texttt{SQRTSORT}$.

and,

> (c) Now suppose $\texttt{SQRTSORT}$ is implemented recursively, by calling your sorting algorithm from part (a). For example, at the second level of recursion, the algorithm is sorting arrays roughly of size $n^{\frac{1}{4}}$. What is the worst-case running time of the resulting sorting algorithm?

*Note: To simplify the analysis, assume that the array size $n$ has the form $2^{2^{k}}$, so that repeated square roots are always integers.*

---

**My Attempt:**

For part (a), I come up with a *probably* brute-force algorithm behaving like the $\texttt{BubbleSort}$, except that it treats $\frac{\sqrt{n}}{2}$ of consecutive elements as a single one in $\texttt{BubbleSort}$. The number of calls of $\texttt{SQRTSORT}$ is at worst:

$$1 + 2 + \ldots + 2 \sqrt{n} = 2n + \sqrt{n} = \Theta(n)$$

For part (b), $\sqrt{n}$ is a trivial lower bound: Any reasonable algorithm must have done something on each element, consuming $\sqrt{n}$ calls of $\texttt{SQRTSORT}$.

---

**My Questions:**

> 1. How to show whether my solution is asymptotically optimal or not?
> 2. Do you have better algorithms with lower complexity, say, $\sqrt{n} \lg n$ or $n^{\frac{3}{4}}$. Actually, I am looking for the *optimal* one.

# Answer
Hint for part (b): Consider the statistic $r(\pi) = \sum\_i |i-\pi(i)|$. Running SQRTSORT can reduce $r(\pi)$ by at most $n$, while $r(n(n-1)\ldots1) = \Omega(n^2)$.

Hint for part (c): I get a running time of $O(n^2\log^{O(1)} n)$.
> 1 votes

---
Tags: algorithms, complexity-theory, algorithm-analysis, time-complexity, sorting
---


title: Two's complement overflow

text:
# Question
Title: Two's complement overflow
I know that in the case of a 16 bit word, if we have x - 115 in decimal, the smallest x that would cause overflow would be (32767 + 115 + 1)= 32883 because it would represent a number that is larger than the largest positive integer we could represent in a 16 bit word. However, I was wondering what would the largest value of x be? would it be (2^16)? which would cause 2 carries after the addition. Or would the largest x be a number that would only result in 1 carry alone?

# Answer
You get overflow if the result is larger than the maximal integer, in this case 32767. You get underflow if it is smaller than the minimal one, in this case -32768. (In the context of floating-point operations, *underflow* happens when a non-zero number is rounded to zero.)
> 1 votes

---
Tags: arithmetic
---