title: Why can't CPU access secondary memory

text:
# Question
Title: Why can't CPU access secondary memory
I have read in my subject "Operating Systems" that CPU can't access secondary memory. Any program that is stored on secondary memory is executed once its retrieved from secondary memory to primary memory. Is this true? If the CPU can't execute code directly out of secondary memory, why not?

# Answer
There *are* CPUs that can execute programs directly from secondary memory. (I'm kind of surprised at you not being able to simply search this: e.g.http://www.analog.com/media/en/technical-documentation/application-notes/EE363v01.pdf)

That being said, many CPUs cannot. It generally boils down to access speeds and/or I/O type. Secondary storage (flash, etc) can be slower and/or have more latency than RAM, and for a simple CPU (i.e. embedded system or similar, generally) the CPU may not be able to wait the length of time necessary to do an instruction fetch. (Or rather, it may assume that an instruction fetch will complete in cycles as opposed to having a mechanism to wait until the instruction is actually fetched)

Also, unless you have memory-mapped I/O or a proper MMU you'll need explicit support by the CPU to issue the I/O instructions required, which increases the complexity of the CPU and may increase the critical path, limiting the speed of the CPU. (If you have a MMU you can just have a page fault handler that fetches the appropriate page from secondary memory on first access)

An elaboration:

Ultimately, a CPU has to be able to read the data for its next instruction. This is generally only a few bytes at most. However, many devices only support block-level access (e.g. 512 bytes, etc) of larger block sizes than the instruction size. Note that this includes many forms of RAM! (For instance, if you have DDR ram (64 bits transferred at a time) and an instruction set that isn't always 64 bits wide) There are a couple of ways to deal with this mismatch: you can fetch the block and toss away the data you don't need for that instruction, you can fetch the block into a small sliding window of the next few instructions (throwing away the rest of the block) so you only need to do a fetch every few instructions, or you can fetch the entire block into a buffer. Fetching every instruction is slow, and in particular is latency-sensitive. It also wastes memory bandwidth that could be otherwise used for DMA, for instance. Fetching into a sliding window can faster, but substantially more complex. It also introduces latency variations (if you have unpredictable branches you may not be able to keep the window filled, for instance) And fetching the entire thing limits you and requires a lot of die space for the buffer (you need to have a buffer at least as large as the block size), and is prone to problems (e.g. what happens when an instruction overlaps two blocks? There are a lot of edge cases.)
> 2 votes

# Answer
The CPU reads directly from primary memory (RAM). To read data from secondary memory (primarily disk), it is first read into primary memory.

Secondary memory is organized into *blocks*, and data is transferred from/to primary memory a block at a time. Thus to do the above, space must be allocated first, and then the correct commands given to the specific device (devices do differ in the exact incantations required to have them do the specified dance) to transfer data. This is too complex (and too time consuming) to have it done transparently by the CPU.
> 0 votes

---
Tags: operating-systems
---


# Question
Title: What is the name of this code transformation that uses associativity of addition?
I am learning about compiler optimization technique and there is a technique that use associativity of addition to transform code.

For example, consider the following expression:

```
(a + b) + ((c + d) + e)

```

It can be transformed into:

```
a + (b + (c + (d + e)))

```

Does anybody know the name of this transformation?

# Answer
> 1 votes
According to LLVM it is called "Reassociate expressions" and uses the flag "-reassociate"

According to here:

> `-reassociate`: **Reassociate expressions**
>
> This pass reassociates commutative expressions in an order that is designed to promote better constant propagation, GCSE, LICM, PRE, etc.
>
> For example: `4 + (x + 5) ⇒ x + (4 + 5)`
>
> In the implementation of this algorithm, constants are assigned rank = 0, function arguments are rank = 1, and other values are assigned ranks corresponding to the reverse post order traversal of current function (starting at 2), which effectively gives values in deep loops higher rank than values not in loops.

---
Tags: terminology, compilers, program-optimization
---


# Question
Title: Converting maximization to minimization in aproximation algorithms
Suppose algorithm *A* is given for a maximization problem and we are asked to show that it is a 1/2-approximation algorithm.

As you know it is enough to show

Sol \>= 1/2 OPT

What I need to know is, is it true to assume this problem as a minimization one and prove

Sol \<= 2 OPT

Or is there any correspondence between these two?

# Answer
> 4 votes
One connection is that maximizing some function $f$ is the same as minimizing its reciprocal $1/f$. You can use this to convert between maximization and minimization.

The general problem of maximizing a function $f$ under some constraints can be very different from the corresponding minimization problem (of the *same* function $f$). A case in point is MIN-CUT versus MAX-CUT. Whereas MIN-CUT is in P, MAX-CUT is NP-hard to approximate better than some constant.

---
Tags: algorithms, optimization, approximation
---


# Question
Title: Is the language of TMs that decide some language Turing-recognizable?
Is the language

$\qquad L=\\{ \langle \text{M} \rangle \\; | \\; \text{M is a Turing machine that decides some language} \\}$

a Turing-recognizable language? I think it's not, as, even if I am able to tell somehow that a Turing machine halts for some input there are still infinite strings to check for. Similarly I think that this problem is not even co-recognizable. Am I right? If yes is there a more precise proof ?

# Answer
This language is usually known as TOT, the language of machines computing total functions. It is $\Pi\_2$-complete, and in particular is neither recognizable nor co-recognizable.
> 6 votes

# Answer
Of course, this depends on what you exactly mean.

Do you mean, all the machines that decides a **specific** language? e.g., $$ L = \\{ \langle M \rangle \mid M \text{ decides the language } A\\}$$

then, it depends on the language $A$. For instance, if $A=HP$, the halting problem, then $L$ is clearly decidable (i.e., it is empty).

But if you mean, **any** language, i.e., that $M$ is a decider, $$ L = \\{ \langle M \rangle \mid M \text{ halts on all inputs } \\}$$ then $L$ is not recognizable, see Yuval's answer.
> 7 votes

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


# Question
Title: Question about proof of Kannan's Theorem
The wikipedia page (here) assumes the existence of some $L \in \Sigma\_4 - SIZE(n^k)$. How can one show that such a language exists?

This is related to a homework question, I'd prefer some hint to the answer. Using the hierarchy theorems, we can find some language $L \in SIZE(n^{k+1})$ for which $L \not \in SIZE(n^k)$. I doubt all such languages would be in $\Sigma\_4$, but maybe some of them with a special property may be?

It seems we could just as well take something in $\Sigma\_3$. Could we maybe take the language $L$ decided by the smallest such circuit? So then we could make a sentence like

$x \in L \iff \exists C\_n $ such that for $\forall$ circuit families $C'\_n \exists x'$ so that $C\_n(x) = 1$ and $(|C'\_n| \> |C\_n|$ OR $C'\_n(x') != C\_n(x'))$?

But it seems like this choice depends on $|x|$.

# Answer
Following your way:

Let us denote by $C\_{n,s,i}$ the i'th $n$ inputs, $s$ size circuit (relative to the lexicographic ordering of the strings describing such circuits), Then:

$x\in L \iff \exists i \hspace{1mm} \phi\left(C\_{|x|,|x|^{k+1},i}\right)\forall j\<i : \neg \phi\left(C\_{|x|,|x|^{k+1},j}\right)\land C\_{|x|,|x|^{k+1},i}(x)=1$.

$\phi(C)$ is a formula which states that $C$ cannot be computed by an $n^k$ size circuit, and can be written as a $\Pi\_2$ statement (as you did in your original post).

The idea is the same as yours, trying to decide some language in $SIZE(n^{k+1})\setminus SIZE(n^k)$. The only addition is using the lexicographic ordering and forcing minimality. This way we force that for any length $n$ string, the quantification over the circuit index $i$ yields the same circuit.

After grouping the quantifiers (and moving $\forall j\<i$ right after $\exists i)$ you get a $\Sigma\_4$ formula.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Memory address of variable after reassignment
When a local variable is reassigned a different value/object, does its position/address change in the stack?

# Answer
"Local variable" is a concept in the source language. Some target languages have the concept (e.g. virtual machines with dictionary-based scopes), but many do not. Since you're using Java, let's look at the JVM.

A local variable cannot be accessed by other methods (e.g. you can't pass a variable by reference like you can in C++ or Fortran), and cannot be accessed by other threads. This gives a Java compiler (and a JVM implementation, for that matter) a lot of freedom about what to do with it.

JVM code has two "local" areas where it may store data: the *operand stack* and the *local variable array*. If you want to read along, this is covered in section 2.6 of the JVM specification. As the names suggest, the operand stack is organised like a stack (mostly push and pop-type operations), and the local variable array is organised like an array (dereference-type operations).

The JVM is designed so that a compiler can emit code where every local variable has one exactly entry in the local variable array. To use the value, the compiler would emit code to transfer a value from the local variable array to the stack (the instruction is called "load"; there are variants for variables of different types, but we'll ignore this complication for now), and to write a value to the variable, there is a corresponding "store" instruction which transfers a value from the stack to the local variable array. Section 3.2 of the specification covers this.

The reason why the JVM is designed with this in mind is that it allows for very simple compilers. However, this is not the only possible way to generate code for the JVM.

A local variable cannot be accessed by another method (e.g. you can't pass it by reference like you can in C++), or on another thread. So the compiler has a lot of freedom about what it can do with one.

If a variable is extremely short-lived, for example, it may not need an entry in the local variable array. Consider, for example:

```
for (int i = 0; i < 10; ++i) {
    int x = f(i);
    g(x,x);
}

```

A simple way of compiling the body of this loop might be something like this.

```
// x = f(i);
iload i    // push i onto the stack
invoke f   // pop the argument, call f, and then push the return value on the stack
istore x   // pop the stack and store the value in local variable x
// g(x,x);
iload x    // This probably doesn't need to be explained, right?
iload x
invoke g

```

(Note that this isn't actually JVM bytecode. The JVM uses slot numbers in the bytecode stream, not names, and also has different "invoke" instructions depending on what "f" actually is; it might be a static method, or an interface method, or one of a number of other things. Nonetheless, this should give you the basic idea.)

The variable x doesn't really need to be stored in the local variable array. When this method calls the method f(), the return value is pushed onto the operand stack. Invoking the method g() requires two values to be on the top of the operand stack, representing its arguments. The JVM has an instruction (called "dup") which duplicates the value on the top of the operand stack, so the body of this loop could be compiled as:

```
iload i
invoke f
dup        // Duplicate the top value on the stack
invoke g

```

In fact, in this simple example, the compiler may not need to allocate local storage for i, either.

There are lots of other possibilities. The compiler might reuse local storage slots for local variables whose lifetimes don't overlap, or it might assign different locations to the same variable for different parts of the code; this is known as live range splitting. In a sense, the distinction between the operand stack and the local variable array when compiling for the JVM is very like the distinction between registers and the stack when compiling for a physical CPU, and many of the same ideas carry across.

Now, there are a few reasons why a compiler might not want to go to all this trouble.

First off, it can be a lot of work. Optimal register allocation is a formally unsolvable problem, although for some reasonable definitions of "optimal" it's NP-complete. Nonetheless, for stack machines like the JVM, very simple techniques work in practice.

Secondly, chances are good that if this is performance-critical code, it will be JIT-compiled anyway, and so many of these optimisations will be done by that part of the JVM implementation.

Thirdly, it complicates debugging. If a variable can be stored in more than one location, then the debugger needs to know where to find the value any point in the program. If the reason why you're optimising local variable storage is to reduce the size of the class file, chances are good that it won't help, because what you gain in the number of instructions you will probably lose in debugger metadata.

This is one reason why software projects often use "debug builds" during development.

One final thing: I've been talking about basic types like integers here, but one additional complication in optimising the storage of local variables is how it interacts with the garbage collector, since the garbage collector needs to know what heap objects are referred to by local variables.

Garbage collection is a more advanced topic, and you didn't ask about it, so I won't go into the details. It doesn't affect how a Java compiler would compile to JVM bytecode, but it may affect the design of the JVM implementation. Once again, a local variable can't be accessed by other methods or other threads, so this gives the JVM implementation a lot of freedom on how it can let the garbage collector know what is live and what isn't.
> 3 votes

---
Tags: stacks, memory-allocation
---


# Question
Title: Does entangling 100 qubits require a 2^100 X 2^100 Hadamard gate?
Suppose I have 100 qubits that I want to entangle and put into superposition. To do so I construct a Hadamard gate to do this. By definition, the Hadamard is going to be a 2^100 X 2^100 matrix - which is huge.

How does one go about actually performing this operation? The size of the Hadamard matrix is exponential relative to the number of qubits (ie 2^100 X 2^100). Is there a way to perform this operation without actually making this huge matrix? Or can we only work with a 'small' number of qubits at once?

Follow up question: does using 100 4x4 Hadamard gates (one for each qubit) do the same thing as using a single 2^100 x 2^100 Hadamard gate? If so, how do these qubits become entangled?

# Answer
It does require that, but you get it for free.

When you apply a 2x2 gate to a single qubit, the gate you are applying to the $n$-qubit system that qubit is in is automatically $2^n$ x $2^n$. If you apply an $H$ to the third qubit out of six, then the operation you applied to the six qubits is $I\_2 \otimes I\_2 \otimes H \otimes I\_2 \otimes I\_2 \otimes I\_2$. That's a 64x64 matrix; exactly what you needed.

So performing a Hadamard transform on $n$ qubits is actually very easy, even though some very large matrices are being thrown around if you think about what's happening in that way. Just independently hit each qubit with the usual single-qubit $H$ gate.

Note that Hadamarding each qubit doesn't entangle them, though. It puts them in a superposition, but the state still factors. If you want to entangled all the qubits, you could instead hit one of them with a Hadamard then use Controlled-Nots to toggle each of the other qubits based on that Hadamard'ed qubit.
> 5 votes

---
Tags: quantum-computing
---


# Question
Title: Why do we use Insertion Sort in the Bucket Sort?
Bucket sort is a linear-time sort.

1. Why do we use insertion sort in it? We know that insertion sort takes $O(n^2)$ time.
2. Why can we not use any linear sort inside it?
3. As we see, when in each bucket we use insertion sort $O(n^2)$. How is bucket sort's total complexity $O(n)$?
4. Why do we not use a $O(n \log n)$ sort such as merge sort or quick sort?

# Answer
> 2 votes
If each bucket has $O(1)$ things, then insertion sorting the buckets takes time $O(n)$.

As a more practical matter, the algorithm you use to sort small lists of things should be chosen because it's fast at sorting small lists of things, not for its asymptotic performance on large lists of things. And insertion sort seems to be the popular choice for this task.

An implementation of bucket sort that produces buckets with many elements should indeed use some other method (e.g. bucket sort again) to sort the buckets.

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


# Question
Title: Is showing two different derivations enough to prove that a CFG is ambiguous?
I'm wondering, is showing two different ways to derive the same word enough proof to show that a context-free grammar is ambiguous?

For example:

**O** = start symbol
**Non-terminal** = {O}
**Terminal** = {r, s}
**Productions** =
O -\> r
O -\> Or
O -\> sOO
O -\> OOs
O -\> OsO

There are two different derivations for the word rsrrs:

O -\> OOs -\> OsOOs -\> rsOOs -\> rsrOs -\> rsrrs
O -\> OsO -\> rsO -\> rsOOs -\> rsrOs -\> rsrrs

# Answer
> 2 votes
As Rick says, this is very close. The key is to show that there are two different parse-trees for the same word in the grammar.

What you have is okay, but presenting it as a linear derivation isn't enough. For example, consider something similar to what you did, but slightly different:

$O \rightarrow OOs \rightarrow OsOOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs $

At face value, these are two different derivations. However, if you look closely, you see that they only differ in the order that we expand the different terminals of the same intermediate word. So this is NOT a valid proof that the grammar is ambiguous.

However, if we look at your original example using parse-trees, we can see that it still holds:

```
O
|
O--O--s
|  |
r  s--O--O
      |  r
      r

```

And the second tree:

```
O
|
O--s--O
|     |
r     O--O--s
      |  |
      r  r

```

This shows that these are actually different parses: we use a different production from the initial $O$ symbol, so we know that they are different.

An equivalent way to do this is to use the linear derivations like you do, but always put them in "left-derivative" form, where you only ever expand the left-most non-terminal. So your derivations would become:

$O \rightarrow OOs \rightarrow rOs \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs$

$O \rightarrow OsO \rightarrow rsO \rightarrow rsOOs \rightarrow rsrOs \rightarrow rsrrs $

In this case, there's a 1:1 correspondence between left-derivatives and parse trees, so if there are two distinct ones, you know the grammar is ambiguous.

For the "bad" example I gave, both derivations give the first parse tree, so it's not a valid proof that the grammar is ambiguous.

---
Tags: context-free, formal-grammars, ambiguity
---


# Question
Title: Sorting an unordered pile of items into drawers with minimal drawer movements
A while ago, I was doing my laundry late at night. When I brought my laundry back to my dorm, I started to put it away.

My wardrobe is set up as follows:

* My drawers are categorized by the type of clothing they hold, and I'm very particular about that; this means I can't put t-shirts in my pants drawer (otherwise I'll be too flustered over it to sleep). Of course, I know this categorization, and I know which drawer is which even in the dark.
* I have $N$ pieces of clean laundry, and $M$ drawers arranged vertically (with the drawer at the top being $D\_0$)
* I can open and close drawers as I see fit, but if drawer $D\_i$ is open, I can't put any clothes in drawer $D\_{i+1}$ (because it's blocked by $D\_i$).
* All of my drawers are already closed when I enter the room.
* When I finish, I have to close all open drawers.

Considerate gentleman that I am, I don't want to wake up my roommate (this was a college dorm, so we slept in the same room). I resolved to not turn on the lights and make as little noise as possible.

This means that I have to put away my laundry under the following constraints:

* I can't see into my laundry bag, so I only know what I grab as soon as I pull it out.
* Opening and closing a drawer makes noise. Pulling items out of my laundry bag, or actually putting them in the drawer, does not.
* I can only put away one item of clothing at a time; I can't fold like clothes and put them in piles (and then put those piles away) because the floor's too dirty and there's no space on the furniture within reach of me.
* I can put an item of clothing back in my bag and take out another, but the one I take out next could be the one I had just put back in (remember, I have no control over what I pull out of the bag).

**Given this, I have three questions:**

* How can I put my laundry away while opening and closing the drawers as few times as possible?
* Has anyone else thought of this problem or something similar?
* Does this problem have any practical applications?

# Answer
> 4 votes
How about the following:

1. Go through your bag; fold and stack items for drawers $D\_i$ and $D\_{i+1}$, $i \in 2\mathbb{N}$, in/on drawer $D\_i$ (which you open on demand).

Make sure you have the items for $D\_{i+1}$ on top; that may require quite some reordering pancake-style, but you don't seem concerned about such operations.

Note that there is always enough room (two drawer heights) to do this, assuming the drawers are roughly equal and your clothes fit into them as it is.
2. For each open drawer $D\_i$,

* pick up the stack for $D\_{i+1}$ (and put in the bag, if necessary),
    * close $D\_i$,
    * open $D\_{i+1}$,
    * put the stack in there, and
    * close $D\_{i+1}$.

This algorithm requires $2M$ drawer movements if all drawers get clothing, so it is worst-case optimal.

It will waste some movements if there are items for $D\_{i+1}$ but not $D\_i$; if *only* odd drawers get items, we execute twice the drawer movements necessary. Since this is the worst that can happen, we still have a $2$-approximation.

---
Tags: algorithms, optimization, sorting, randomized-algorithms
---


# Question
Title: Proving that picking odd-numbered symbols can create the universal set from a non-regular language
Let's define the following operations:

$odd(string) = $ odd characters of $string$, $even(string) = $ even characters of $string$

Now say we have some language $L$, we will then define the following languages:

$odd(L) = \\{odd(w): w \in L\\}$, $even(L) = \\{even(w): w \in L\\}$

Need to prove that there exists a non-regular language, $L\_N$, such that $odd(L\_N)$ and $even(L\_N)$ are both regular languages.

I thought of a few examples that might produce obvious regular languages with $odd$ and $even$, one of which was the language:

$L\_1 = \\{w \in \\{a,b\\}^\*: |a|\_w = |b|\_w\\}$, where $|x|\_w =$ # of $x$'s in the string $w$

I know how to prove that this is non-regular, and upon inspection of a lot of values of $odd(L\_1)$ and $even(L\_1)$, it appears both produce the language $\\{a,b\\}^\*$ which is obviously a regular language. Don't really know how I could prove that equality though.

# Answer
You want to show that $\operatorname{odd}(L\_1) = \\{a,b\\}^\*$. This is a set equality claim, and you show it the way you can approach any such claim:

1. Show $\operatorname{odd}(L\_1) \subseteq \\{a,b\\}^\*$.

That's trivial.
2. Show $\operatorname{odd}(L\_1) \supseteq \\{a,b\\}^\*$.

Let $w \in \\{a,b\\}^\*$. Can you construct $w' \in L\_1$ so that $w = \operatorname{odd}(w')$?

> You only need to fix symbol counts, so brute force works: $w' = w\_1 \overline{w\_1} \cdots w\_n \overline{w\_n}$ with $\overline{x}$ the "inverse", i.e. it maps $a$ to $b$ and vice versa.

Thus, $w \in \operatorname{odd}(L\_1)$. Since $w$ was chosen arbitrarily, the claim follows.

A similar proof works for $\operatorname{even}(L\_1)$.
> 5 votes

---
Tags: formal-languages, regular-languages, proof-techniques
---


title: NFA diagram for a*

text:
# Question
Title: NFA diagram for a*
I would like to know whether we could replace the second image with first image since the second image contains less transitions and states than first image even though everyone uses second image to show construction of (a\*).

# Answer
> 4 votes
Yes, the two automata are equivalent: both accept the language $a^\*$.

However, if you're just interested in the language $a^\*$, there's no reason to use either of those two automata. The langauge $a^\*$ is accepted by the automaton that has a single state, which is the start state and is accepting. The single transition is an $a$ transition from the state to itself. If this automaton receives any number of $a$'s (including zero), it is in the accepting state; if it receives any other character, it rejects because there is no transition.

So, what *is* the point of the first automaton in the question? Why would you ever use a four-state NFA with $\lambda$-transitions to accept something that a one-state NFA can do? The point is that the automaton is designed to be used as a "subroutine" in an inductive translation of regular expressions to NFAs, via what are called generalized NFAs. In an ordinary NFA, every transition is labelled with a single symbol from the alphabet (or with $\lambda$, if you're allowing that kind of transition); in a generalized NFA, each transition is labelled with a regular expression. To convert the regular expression $R$ to an NFA, you start with the automaton with two states: a start state, an accepting state and a transition between them labelled $R$. You then recursively replace transitions labelled with regular expressions with automata whose transitions are labelled with simpler regular expressions.

The construction shown in the first diagram is used to replace an edge labelled $R^\*$ with an automaton whose edges are labelled with the simpler regular expressions $\lambda$ and $R$. Note that $R$ is (slightly) simpler than $R^\*$: it has one operation fewer.

In general, the second diagram can't be used to replace a transition labelled $R$, because "other than $R$" is shorthand for the regular expression that matches exactly the strings not matched by $R$. Since we don't usually include negation in the definition of regular expressions, this means that "other than $R$" can be some horribly long regular expression that isn't simpler than $R^\*$, because it contains many more operations. This would break the recursive scheme: we're trying to make things simpler all the time but this step would make things more complicated. Trying to prove that you always get to an ordinary NFA where every transition is labelled by a single symbol (the simplest possible regular expression!) would now be very difficult.

Even if you did allow negations in your regular expressions, you wouldn't be done yet. In that case, you've removed an edge labelled $R^\*$ but introduced one labelled $\neg R$. This has the same number of operations, so it isn't simpler. Again, it's going to be difficult to prove that you always end up with an ordinary NFA. Also, you're going to need to design an automaton that replaces an edge labelled $\neg R$ with ones with simpler labels.

If it's not appropriate to write "other than $R$" for a general regular expression, why is it OK to write "other than $a$"? Well, that's just a shorthand for "I'm too lazy to draw a separate transition for each symbol $b\in\Sigma\setminus\\{a\\}$." That's just an abbreviation, whereas writing "$\neg R$" on an edge subtly hides potentially vast complexity.

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


title: Choosing a random bit from a bitmap

text:
# Question
Title: Choosing a random bit from a bitmap
Since, I don't have strong algorithmic background my question may sound a litlle odd. Please correct me, if so.

I have quite a large bitmap (~100 Million bits) (e.g. `100100101001010001001...010010`). The bitmap is just an example, it doesn't have to start with `1` or end with `0`.

Now, I need to choose *randomly* any `0`-bit from the bitmap and retrieve it's position. Memory is not an issue in my case, I can maintain a few copies of the bitmap, if necessary. But the acceptable complexity of the algorithm would be linear or `O(n lnn)` in the worst case. Couldn't you advice a direction to move to? I'll appreciate any advices or refernces to some related resources.

# Answer
> 9 votes
There is a simple $O(n)$ algorithm using the technique of *reservoir sampling*. Keep a currently selected element $x$ (initially, none). Go over all bits in the file in order. When seeing the $m$th zero, put it in $x$ with probability $1/m$. You can show (exercise) that the final contents of $x$ is a uniformly random zero from the file.

If you are allowed preprocessing, you can store the locations of all zeroes in a new file, and then choose a uniformly random zero in $O(1)$ by choosing a uniformly random position in the list.

Practically speaking, we expect bitmaps to contain a decent fraction of zeroes – say at least 1%. This suggests querying uniformly random locations in the file until you reach a zero. The expected runtime of this algorithm is at most 100 random queries.

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


# Question
Title: How do I sort these elements in O(n) time?
So let's say I have an array of elements where each of the values can range from 0 to $n^2-1$. I'm trying to make an algorithm to sort this array in O(n) running time and I was thinking of using radix sort. The run time of radix sort is O(d(n+N)) or O(dn) if n is really large. So how can I modify radix sort so that it runs in O(n)?

EDIT: I don't think you guys understand this. The amount of elements in the array is n but the ACTUAL value for each element can range from 0 to n^2 - 1. So if we have an array with 10 elements in it then the largest the element can be is 99 and the smallest it can be is 0 but there will still be 10 elements in the array.

# Answer
If you want to implement this on a RAM with integer math (ie. a real computer if your n is smaller than $2^{32}$), you can have a look at Upper bounds for sorting integers on random access machines. The authors show that integers in the range \[0,$n^c$\] can be sorted in $O(n(1 + \log c))$. Word RAM models add some loglog factors to that runtime.
> 2 votes

# Answer
$d$ is presumably the number of digits, and you need $d = O(1)$.

Since the number of digits of a number $m$ in base $b$ is $1 + \lfloor \log\_{b} m \rfloor $, you solve to get $b \approx m^{1/d}$.

Using base $n^2$ is too ambitious, but base $n$ or base $\sqrt{n}$ is fine, for example. (or better, pick the next larger power of $2$)

That is, rather than binning numbers based on their individual bits, you should bin them based on $\frac{1}{k} \log\_2 n$ consecutive bits, for some integer $k \in O(1)$.
> 1 votes

# Answer
I really doubt anyone can sort an array within O(n) unless infinite memory is given. However, if you know the range of numbers and have sufficient memory to store all of them, then you can hash the array (take mod by $n^2$) and store them in a intermediate array of size ($n^2$).You can use another intermediate array of same size to store repetition (if you have repeated elements in original array.). All this can be done in single pass causing O(n). And on second pass iterate over the intermediate array and place them in original array one by one.
> -1 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting, arrays, radix-sort
---


# Question
Title: Which addressing modes permits relocation without any change whatsoever in the code?
An exercise problem stated that :

Which of the following addressing modes permits relocation without any change whatsoever in the code?

1. Indirect addressing
2. Indexed addressing
3. Base register addressing
4. PC relative addressing

---

Somewhere it explained as :

**Base register addressing :** In this mode , content of base register is added to the address part of the instruction to obtain effective address . A Base register is assumed to hold a base address and the address field of the instruction gives a displacement relative to the base address with a base register , the displacement values of the instruction do not have to change only the value of the base register requires updating to reflect the beginning of a new memory of constant .

Hence , option (3) is true .

---

I found another explanation too , which stated that base addressing mode and relative addressing mode are suitable for relocation at run time .

---

My question is :

Which addressing modes permits relocation without any change whatsoever in the code?

> > Can you explain it in a formal way, please?

# Answer
> 6 votes
Code relocation can be done whenever addresses are not directly specified in the program (absolute), but are relative to some variable or other modifiable source.

In the 2 modes that you correctly specified as able to support relocation of code and data, the effective address is calculated based on the value loaded in another register.

For 3), base addressing, a register points to the base of the structure and the effective address is obtained by computing an offset from the base. The base address register can be loaded at run time to point to the base of the structure so the code doesn't have to be modified.

For 4), PC relative, the effective memory address is obtained by computing an offset from the current PC. No matter where the code is loaded in memory, the offsets are always the same so the code needs no modification.

Now the other 2 selections are a little more tricky. 1. Indirect addressing. This supports relocatable code since the effective address is determined based upon the contents of the initial load. Code and data can move but with a data structure containing pointers to the code and/or data being at a fixed address. For example, the operating system may define that a pointer to the system's CPU database is always located at address 80002000, but the CPU database can be loaded at any address. You COULD argue that the entire program is not relocatable because the pointers are at fixed locations, but really relocation is the one of the purposes of this addressing mode.

2. Indexed Addressing. This depends upon a bit more definition of the term. If you mean indexed ABSOLUTE mode, then no, I wouldn't consider this to be a mode that supports relocation. In this case the effective address of data is based on an offset from a literal fixed address (ex: 1000 + R5). In order to relocate this data (or code) the literal address would have to be changed in the code. If it's indexed relative to a base register, then yes it supports code relocation since the base register can be loaded at run time.

---
Tags: computer-architecture, operating-systems
---


# Question
Title: Would you ever use a skip list over a treap?
Skip lists are taught as a standard of the undergrad CS curriculum at many major universities. However, from my reading\* I can't find any practical situation where you would use a skip list over a treap. Also they have the same asymptotic performance for all the main operations.

As a result this left me wondering:

> Should you ever choose a skip list over a treap?

\*A few web links that suggest that treaps are faster in practice or a just very fast in practice.

http://pinporelmundo.blogspot.co.uk/2011/06/skip-lists-compared-with-treaps-and-red.html https://stackoverflow.com/a/16009599/2179021 https://stackoverflow.com/a/18303163/2179021

and here is a link suggesting that skip lists are almost never useful

https://www.quora.com/Why-arent-skip-lists-used-more-often-instead-of-balanced-trees

# Answer
here is an extensive 13 page analysis of considerations in this area including empirical analysis. coders sometimes ask for "one size fits all" answers. of course "best" implementation depends on the actual "forces" applied on the implementation. a single implementation may even behave ("dramatically") differently on different amounts of data and different conditions. for some data structures there is no significant difference and either can be acceptable.

raw performance is not the only factor. factors might involve how hard it is to implement/ test the structure vs whether it is already implemented etc. and this paper also considers caching considerations effect on performance. this research finds that skip lists have good variable-node-size performance (ie not all nodes have same size) and paged skip lists outperforms B+-trees in their case.

see p7 and fig6 p 10.

> The AVL tree is the best performing fixed-node-size data structure, and the paged skip list is the best performing variable-node-size data structure. Moreover, the gap between the cache-conscious data structures and their counterparts is growing, as shown by the 100 cycle memory latency configuration. The paged skip list outperforms the sequential search B+-tree by 12% on the Intel processor.
> 1 votes

---
Tags: data-structures, efficiency
---


# Question
Title: Basic requirements for Integrality gap examples
I have the following question about giving a series of examples of range spaces for my Hitting Set problem that establish a lower bound for the integrality gap (IG).

IG is the supremum of ratio of the optimum for natural integer linear programming (ILP) formulation of Hitting Set to the optimum for its (mean ILP) LP-relaxation taken over all range spaces corresponding to my problem.

There are lots of algorithms where solution for LP-relaxation is rounded to some feasible solution of ILP which is not far from optimum. IG gives the lower bound of multiplicative factor to which rounding procedure could worsen the optimum for LP with respect to the goal function.

Specifically, do I need to provide any polynomial algorithm for generating those series of example range spaces (giving the gap lower bound) ? if yes, then what are the parameters with respect to which my algorithm should be polynomial in ? I'm interested in this because by claiming some gap lower bound I provide educated lower bound for approximation algorithm performances which are based on aforementioned LP-relaxation.

# Answer
No, there is absolutely no need for the gap instances to be efficiently constructible. It is perfectly fine even to give some pure existence proof, say using diagonalization or probabilistic techniques.

The reason is that the integrality gap examples rule out certain kinds of algorithms. Specifically, suppose that an algorithm solves the LP and then rounds it, and suppose that the way you prove the approximation guarantee is by showing (for a minimization problem) that rounding increases the value of the solution by at most a factor $C$. If there is an integrality gap of $\alpha$ then you know that $C \geq \alpha$. So no algorithm with this kind of analysis can result in an approximation ratio better than $\alpha$.

If I remember correctly there are some rare cases in which the way you analyze your algorithm is a bit different, and then you can go beyond the integrality gap, but unfortunately I can't think of any; if you're interested ask a separate question.

It is meaningful to consider an integrality gap even for different relaxations, for example for the semidefinite relaxation or for some LP or SDP hierarchy. The requirements are the same only you're comparing the integral optimum to the value of some more complicated program. The consequence is that an algorithm which proceeds by solving that program and then rounding can't given an approximation ratio better than the integrality gap (unless it does some rare hocus pocus as mentioned above).

Chlamtac and Tulsiani have written a nice survey on integrality gaps, which you might want to browse. It describes many complicated methods for constructing integrality gaps.
> 3 votes

---
Tags: algorithms, complexity-theory, integer-programming
---


# Question
Title: Image Comparison tuned to Human Perception
Say I have two systems that take the same drawing commands and starts drawing on their respective platforms (i.e. HTML Canvas). After this is done, I want to save and compare these two images to ensure that they are perceptually the same, even though the shapes and colors may be very slightly off (non-perceptible differences).

I tried using perceptual hashes, but unfortunately it does not seem sensitive enough for this task. So for example, if you set 1000 pixels all black (for an image that is 1920x1080) on one and compare it to the other, it will be very obvious perceptually but the pHash algorithm will still return a 100% match.

I tried using nearest neighbor averaging for all pixels. Basically, for each pixel, I averaged its value with that of a number of its neighbors and set this value back to the pixel. This seems to work well with shapes that have hard edges and straight lines, because it only takes a very small localized change for it to be perceptibly different. For long curves, this is not so good since there can be moderate changes throughout the entire curve with it still being considered perceptually the same.

Does there exist an algorithm that can handle perceptually small changes in many possible shapes/curves? Should I use multiple algorithms to handle this task?

# Answer
> 2 votes
Unfortunately there is not likely to be any good general algorithm for this. Human perception is *extremely* complex. The best you can do is find algorithms that will sometimes recognize two images as perceptually similar, but there will inevitably be some pairs of images that humans would classify as perceptually similar but your algorithm won't detect as similar.

Your best bet is probably to try to find out exactly what minor differences tend to be introduced by these particular platforms, and then try to devise an algorithm that is tuned to those particular kinds of differences -- you'll probably have better luck than that than with any general algorithm.

One very simple algorithm is to align the two images (e.g., using SIFT/SURF/etc.), add a bit of Gaussian blur to the two images, downscale, and then compare using a L2 norm. Another simple algorithm is to align the two images with SIFT/SURF/etc., and then compute a metric based upon the number of inliers vs outliers in the feature points (how well the set of feature points from the first image match up with the set of feature points from the second image). However, it's hard to know how well this will work for your particular application, without knowing the details of the differences that tend to arise in your situation.

---
Tags: algorithms, image-processing, computer-vision, graphics
---


# Question
Title: Why translating a program from one high-level programming language directly into another is difficult?
I am looking for a better explanation (research level, papers) to answer:

**Why translating a program from one high-level programming language directly into another is difficult?**

Note: When I say difficult I don't mean "hard" - i.e. I am not taking about computational complexity here simply because I am unaware of such results, but you are very much welcome to correct my ignorance.

I understand that at the core of the argument can say something like one-to-one mapping for such translation simply does not exists.

In general, I am not comfortable with terminology used in my own question.

We know from text books: *Low-level language* \- each command or object of the language has one-to-one mapping to CPU commands (e.g. Assembler). All other languages are *High-level*.

Is there a way to reformulate the question into FSA formalism like with regular languges, or some other formalism. But I don't think Church–Turing thesis can help here - it is not about computability or existence of a proof.

PS

My motivation is very simple - I want to discuss/answer how difficult is such a problem for example in translating PHP to Java. Please note that direct translation is indeed a mapping of language commands or objects (e.g. HipHop does not qualify).

---

Probably any **pragmatic solution** would be indirect translation, i.e. in order to (partially) convert a program P written in high-level language A into a high-level language B:

1. (complexity lowering) convert codebase of program P from A to low or inter-mediate level language C
2. (shared codebase) resue parts of converted codebase of program P by calling commands in low or inter-mediate level language C from high level language B

# Answer
The task *is* simple. Here are two naive strategies.

Say we want to compile from A to B.

1. Pick a language C for which you have a compiler A $\to$ C and an interpreter for $C$ in $B$.

Create a new program in B that includes the compilate (in C) as string and the code of the interpreter.
2. Compile code in A to machine code or intermediate language. Translate line by line to B.

Both give horrible programs -- but you did not require anything fancy.

The more theoretical answer is: we know that effective (i.e. Turing-computable) compilers exist between any two Turing-complete languages, since such define nothing but an admissible numbering.
> 3 votes

# Answer
here are two examples of scientific literature on porting projects, the 1st is a large Phd thesis that includes much detail on the intricacies/ difficulties, many of which would apply to different projects, its a C++ to java analysis for a large software system. the difficulties that would be encountered with porting tends to vary by project/ language and is oriented around the rationale for the port. often porting is to achieve better performance, and then the challenge is actually achieving it.

you also mention PHP to Java. a description of a similar project of converting Ruby (also a dynamic scripting language) to Java that happened at Twitter may be useful. there are a huge variety of porting projects that occur and it would be difficult to make generalizations. there is much more literature on eg attempting to compare language performance on standard problems etc.
> 2 votes

# Answer
I think that when doing the translation, you're going to encounter two main difficulties (read: things that could require lots of work):

1. High level languages tend to have lots of features. And even if two languages have a similar feature, they tend to work slightly differently. So, for each feature in the source language (and possibly for each edge case of that feature), you will need to find translation to the target language.

For example, PHP is dynamically typed, Java statically typed. So, to translate from PHP to Java, you would somehow need to simulate PHP's dynamic typing in Java.
2. Languages often come with large standard libraries/frameworks/runtimes, which often aren't completely written in the language itself (so you can't just use the translator on them).
> 1 votes

# Answer
A Simple example of this is trying to show equivalence in C to OCaml.

The features of pointers are not even a language feature in OCaml, and Pattern matching of OCaml is not a feature of C.

This is a simplistic example, but the fundamental semantics of the languages are different.

There are many languages that a 'simple' translation will suffice: Java \<=\> C#, or Scheme \<=\> Lisp.

We can show they are all equivalent to a Turing machine, but this does not give you a practical translation.
> 0 votes

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


# Question
Title: Is there a term for the common semantics of global variables, static local variables, and fields?
I'm working on a graph representation of software for a static analysis project, and I'm finding a distinction that I have no name for between different types of variables.

On one side of the division, we have local variables and parameters, which are not subject to modification by other threads during the execution of a method. For these variables, static single assignment form is valid.

On the other side of the division, we have global variables, fields, and C/C++ static local variables, which can be modified by other threads, meaning static single assignment form is not necessarily valid, as the variable may be modified by a separate thread during the execution of the method.

Is there any existing term for this division?

# Answer
One standard term is "shared mutable state".

Let's unpack that. "State" is any place to store data: e.g., a variable or object. "Mutable" means that the data can be modified. "Shared" means it is shared among multiple threads. Thus, shared mutable state is state that is visible to multiple threads and can be modified by multiple threads.

Usually, immutable state is not a concern: even if it can be read by multiple threads, no one can write to it, so there is no potential for data races or concurrence problems.

Usually, non-shared state is not a concurrency concern: there's only a single thread that can read or write it, so we don't have to worry about concurrency -- merely single-threaded-correctness.

Note that this also helps clarify how we should think about a case that wasn't mentioned in your original question. What about state that can only be written by a single thread, but can be viewed by multiple threads? That's shared mutable state. And that's exactly the right classification, because such state *can* cause concurrency problems: if you're not careful, it can cause data races and other issues, so it's only right that it be lumped together with other kinds of shared mutable state.

(For instance, in your question you write that "local variables... are not subject to modification by other threads during the execution of a method". This is true, but it doesn't go far enough. The relevant fact about local variables is that they can't be modified *or* read by other threads. Also, this highlights that not all local variables qualify: for instance, if you take the address of the local variable and pass that pointer to another thread, the local variable now becomes shared mutable state and is a concurrency problem.)
> 2 votes

# Answer
As Wandering Logic already mentioned in the comments, the most obvious distinction in your case is thread-local storage vs non-thread-local storage.

In general, the specification of your programming language of choice should have a section about storage duration and visibility of variables. For C++ the rules are rather complicated. You can have a look at this summary.
> 1 votes

---
Tags: terminology, typing
---


# Question
Title: Finding a target vector through applications of a binary operator
Let $\mathbb{X} = \mathbb{N} \cap \[0, 255\]$. I am given three vectors in $\mathbb{X}^3$ which I will denote by $v\_i = \[x\_i, y\_i, z\_i\]^T$ for $i \in \\{1, 2, 3\\}$. Now we have a binary operator $\bigoplus$ defined by $w = u \bigoplus v = \lfloor0.9 \cdot u\rfloor + \lfloor0.1 \cdot v\rfloor$, where $u$ and $v$ are in $\mathbb{X}^3$. Given a target vector $t \in \mathbb{X}^3$, the goal is to find a sequence of applications of $\bigoplus$ starting only with vectors $v\_1, v\_2, v\_3$ that yield $t$. We are also given a promise that such a sequence of applications exists. How quickly can I find this sequence? It is worth noting that $\bigoplus$ is non-commutative and closed on $\mathbb{X}^3$. In my case, I am given specific values for $v\_1, v\_2, v\_3,$ and $t$: $$\begin{align\*}v\_1 &=\[150, 0, 255\] \\ v\_2 &= \[255, 150, 0\] \\ v\_3 &= \[0, 255, 150\] \\ t &= \[62, 63, 184\]\end{align\*}$$

The obvious thing to try was a memoization / search approach where we keep a data-structure containing each vector seen so far (initially containing only $v\_1, v\_2, v\_3$) and recursively apply the operator on each pair of vectors stored in my data-structure until the target is found. However this appears to be much to time consuming as the number of possibilities grow super quickly. Is there any better approach that one might try? It doesn't help that there appears to be little structure - For example, starting with our three vectors, there appears to be many combinations that we cannot even form.

I am also interested in knowing what happens if we are not given the promise that $t$ can be obtained from a series of applications of $\bigoplus$ on our three vectors. If we are not given such a promise, is there any easy way to at least determine if such a sequence exists (even though finding it might be difficult)?

# Answer
> 1 votes
Here is a simple solution that I suspect will be fast enough. Use breadth-first search on a graph where the vertex set is $X^3$. In other words, each possible vector $w \in X^3$ is a vertex. The vertex $w$ has 6 edges out of it going to $w \oplus v\_1$, $w \oplus v\_2$, $w \oplus v\_3$, $v\_1 \oplus w$, $v\_2 \oplus w$, $v\_3 \oplus w$. Now use BFS to find the shortest path from $v\_1$ or $v\_2$ or $v\_3$ to $t$. This can be done by initially marking $v\_1,v\_2,v\_3$ as visited and having distance 0, initializing the queue to contain $v\_1,v\_2,v\_3$, and then running BFS until you reach the goal vertex $t$.

Why does this work? Define $d(v,w)$ to be the distance from $v$ to $w$, i.e., the length of the shortest path from $v$ to $w$ in this graph. Define $d(w) = \min(d(v\_1,w),d(v\_2,w),d(v\_3,w))$. Note that any path of length $d$ corresponds to an expression that uses $d$ applications of the $\oplus$ operator, and vice versa. Therefore, $d(t)$ -- the distance to the goal vertex $t$ -- represents the minimum number of applications needed to reach $t$, and the corresponding path yields an expression that evaluates to $t$ using the minimal number of applications of $\oplus$.

How efficient is this? BFS run in time linear in the number of vertices plus the number of edges. Here we have $2^{24}$ vertices and $6 \times 2^{24}$ vertices. Therefore, in the worst case we perform something like $c \times 6 \times 2^{24}$ basic operations, where $c$ is a small constant. The performance in practice might be better than that, as there might not be any need to visit all possible vertices. The memory requirements are relatively limited. You can store the set of visited vertices in a 2MB bitmap; thus, checking whether a vertex has been visited before can be done by a single random-access lookup in this bitmap. You can store the queue in a single array of maximum size $3 \times 2^{24}$ bytes, i.e., 48MB; this is not very large large, and locality of access will be excellent. So I expect this algorithm to complete within seconds.

---

If this is not fast enough, it is probably possible to optimize it further using various techniques. For example, here is one candidate. Define $x-v = \\{w \in X^3 : v \oplus w = x\\}$ and $P(x) = \\{v \in X^3 : \exists w \in X^3 . v \oplus w = x\\}$. Define $S\_j = \\{w \in X^3 : d(w)=j\\}$ and $T\_k = \\{w \in X^3 : d(w,t)=k\\}$. Now you could consider an optimized iterative deepening algorithm, as follows:

* For $d=1,2,3,\dots$:

+ For $k=\lfloor d/2 \rfloor, \lfloor d/2 \rfloor + 1, \lfloor d/2 \rfloor -1,\lfloor d/2 \rfloor +2,\dots,d,1$:

    - Set $j=d-k$. For each $v \in S\_j$:

        * If $v \in P(t)$ and $t-v \cap T\_k \ne \emptyset$, then choose any $w \in t-v \cap T\_k$ and output $v \oplus w$ and halt.

We can compute the $S\_j,T\_k$'s using the technique above (BFS). The trick here is to use a clever data structure to store $T\_k$. If we store $T\_k$ in an octree or k-d tree, then testing whether $t-v$ has any intersection with $T\_k$ is a stabbing query: we are given a $10 \times 10 \times 10$ cube and want to know if there's any point of $T\_k$ that falls within the cube. This lookup can be done efficiently when $T\_k$ is stored in an octree or k-d tree or similar data structure (basically in $O(\log |T\_k|)$ time or so).

This requires more complex data structures, so I'm not sure that it will be worth it to implement. It's not clear whether the resulting solution will be faster or slower than simple BFS, but if simple BFS is too slow, this is another approach you could try.

---

This finds the sequence that evaluates to $t$ and uses the *minimal* possible number of applications of $\oplus$. If you just want any sequence (not necessarily minimal), it might be possible to find it faster. For example, you could use best-first search, where the "goodness" of a vertex is measured by its $L\_{\infty}$ distance to $t$.

---

An aside: your operator $\oplus$ is not associative, but it is "almost so". In particular, $(u \oplus v) \oplus w$ is in general not equal to $u \oplus (v \oplus w)$ (due to the rounding), but it will be "close". Ignoring rounding, $$\begin{align\*}(u \oplus v) \oplus w &= 0.81 u + 0.09v + 0.10w\\ u \oplus (v \oplus w) &=0.90 u + 0.09 v + 0.01 w,\end{align\*}$$ so (again ignoring rounding) their difference is $0.09 u - 0.09 w$, which is in $\[-23,23\]^3$. Rounding might make it a bit larger, but not too much.

It might be possible to use this property to gain some additional speedup -- though I have not identified a specific way yet.

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


# Question
Title: How are Neural Networks made so general?
After reading this blog about Deep Neural Networks learning about selfies I'm struck by how generic the network in question is.

In short: I'm thinking of trying to write something vaguely similar for solving cryptic crosswords, but I can't fathom how to make the general algorithms it uses generic enough that it can develop them ?

A contextual example from the blog is how the network 'understands' filters? Would I need to teach the network about tokenizing the input around keywords, or is that something the network has to 'figure out'? How do I 'seed' the operations the network can perform?

# Answer
> 3 votes
Neural nets don't "understand", they are trained. Despite the fancy term, a neural net is simple a regression model on steroid - often high-dimensional. It's a bunch of weights (vectors) connected in a graph, with an input side and some updating rule (for example, gradient descent).

You'll need a lot of labeled data for the training set. The neural net is trained by feeding these input and telling it about the supposed output, and it readjusts its weights in the regression model.

Apart from that it's a blackbox - kinda magical. But you can't use a neural net trained to recognize selfies to do cryptography (or anything else).

# Answer
> 2 votes
there is some deep academic research on AI/Machine Learning applied crossword solvers, eg contained in the following paper. the basic effective systems utilize large databases of clue-answer pairs combined with dictionaries. an IR "Information Retrieval" system is built to take a given crossword clue and generate "candidate answers". these are further processed eg with part of speech analyzers to generate different "near" answers and constraint solvers guarantee words fit the current constraints eg other letters already known. the systems somewhat use "trial-and-error" just like humans. it is known/ observed that a lot of crossword puzzles reuse clues in minor variations so these systems have some degree of success just "working from memory" and not necessarily utilizing complex rules.

> Automatic resolution of Crossword Puzzles (CPs) heavily depends on the quality of the answer candidate lists produced by a retrieval system for each clue of the puzzle grid. Previous work has shown that such lists can be generated using Information Retrieval (IR) search algorithms applied to the databases containing previously solved CPs and reranked with tree kernels (TKs) applied to a syntactic tree representation of the clues. In this paper, we create a labelled dataset of 2 million clues on which we apply an innovative Distributional Neural Network (DNN) for reranking clue pairs. Our DNN is computationally efficient and can thus take advantage of such large datasets showing a large improvement over the TK approach, when the latter uses small training data. In contrast, when data is scarce, TKs outperform DNNs.

you use the word "understand" in your question. that is a more general question in AI about whether systems that succeed at given AI tasks have demonstrated "understanding". it generally verges on philosophy and there is a sizeable "parallel" philosophical debate about how closely AI is to "real intelligence". much of this started with Turings test in the early 1950s. CS researchers generally take a pragmatic/ empirical, behaviorist stance on this. one can measure human performance on objective tests, and machine performance, and just compare numbers and avoid the far deeper questions *(for now)* of what constitutes "understanding".

another recent successful system that uses AI but not NNs and is very similar to the crossword "clue/answer" dynamic is Watson built by IBM for the jeopardy game, and decisively beat the best human player(s) at the time. it uses technology called DeepQA which is basically/ roughly an IR and post-processing system, in the vein of expert systems.

# Answer
> 1 votes
> I'm struck by how generic the network in question is.

That's exactly the point of a convolutional neural network: it is intended as a general architecture for solving machine learning problems in computer vision, so you don't have to craft a customized architecture for each new computer vision problem you run across.

However, convolutional neural networks are focused on computer vision kinds of problems. The "convolutional" part makes sense in that domain, where we expect that there is some kind of "spatial symmetry" in images (a banana in the upper-left corner of an image looks the same as a banana in the lower-right corner, and the two should often be treated similarly). The same is probably not going to be useful in other domains, such as solving crossword puzzles.

Therefore, I would not recommend a *convolutional* neural network for your application. Instead of looking to computer vision and trying to crib off what they are doing, I suggest you spend some more time learning about the fundamentals of machine learning and deep learning; that will probably help you more.

For crossword puzzles, you will probably achieve much more success by building a customized algorithm that is designed specifically for that particular problem, rather than by trying to use some machine learning algorithm. Deep learning is not "fairy dust" that can magically solve every problem in computer science. They are good for very specific tasks (supervised classification, where you have a huge training set), but not everything; solving cryptic crosswords does not sound like one of the things I'd expect deep neural networks to be especially useful for.

---
Tags: machine-learning, neural-networks, pattern-recognition
---


# Question
Title: Why does the Toffoli gate output c XOR (a AND b) instead of just a AND b?
The Toffoli gate takes in three inputs and gives out three outputs, and is often referred to as the quantum AND gate.

It takes in a,b,c and gives out a, b, c XOR (a AND b).

Why does it do that, instead of just giving out a,b,b AND c? or a,b,(a AND b)?

# Answer
> 0 votes
As the comments said, if it worked like i asked, it would neither be reversible, nor a unitary matrix.

Both things are required for quantum computing!

---
Tags: quantum-computing
---


# Question
Title: How rule 110 would be proven to be universal if the tag system did not exist?
I was reading about Cellular Automata and I read in this question that Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system. Is there another method or information that would still prove the universality of rule 110? In other words, is there another way to to do that without considering tag systems, and if so, can you explain the proof or give a reference to it?

# Answer
More a bunch of references than an answer .... :-)
As said by @vzn in its comment Cook's proof is very complex and required a lot of work; nevertheless the universality of rule 110 renewed the interest on small model of computations.

Among the most notable results was the proof that rule 110 can simulate a deterministic Turing machine efficiently, i.e. with only a polynomial-time slowdown:

Along the direction of a simplified/different proof of the universality of rule 110, you can find some work, e.g.:

For a good survey on universality in cellular automata and other ideas for proving universality:

Finally a *\*personal\** idea on an alternative approach that could be investigated:

* Proving universality of larger CAs (with larger neighbourhood or more states) is much easier and you can even get rid of the intermediate tag-system simulation, so you could investigate if using rule 110 gliders it is possible to simulate an arbitrary larger CA; a slightly similar approach has been used by Nicolas Ollinger and Gaétan Richard in A Particular Universal Cellular Automaton to prove the universality of colliding particles systems (they prove that a particular system can simulate an arbitrary CA)

And don't forget that instead of working on a different proof for rule 110 universality, you can work on the *open problem* regarding rule 54 ... is it (weakly) universal ? :-)
> 7 votes

---
Tags: computability, reference-request, proof-techniques, turing-completeness, cellular-automata
---


# Question
Title: Can big-step semantics express evaluation order?
Can you express evaluation order using big-step semantics?

For example, in a simple language consisting of only `if t then t else t` and `true` and `false`, we can decide to only step a `if then else` to one of its branches if its branches are already values.

Can big-step semantics express the same thing?

# Answer
No, you cannot express evaluation order using big-step semantics.

Borrowing from Benjamin Pierce: big-step semantics is a multi-step evaluation relation that directly formulates the notion of "this term evaluates to that final value". So it cannot impose the kind of evaluation order you describe.

Also keep in mind what the horizontal bar represents. Again borrowing from Pierce: If we have established the statements in the premise(s) listed above the line, then we may derive the conclusion below the line. It would not make sense to impose an ordering on the premises to draw the conclusion.
> 3 votes

---
Tags: programming-languages, type-theory
---


title: Palindrome of fixed length

text:
# Question
Title: Palindrome of fixed length
We know that general palindromes cannot be decided by a DFA.

Howeve if you restrict to case of even length palindromes, does a DFA need exactly $2^{2k}$ states where $2k$ is length of palindrome the language needs to accept?

I get this as lower bound from Myhill Nerode aplication.

From answers below, my lower bound is wrong. What is the correct bound from Myhill Nerode?

How do you show the upper bound?

# Answer
> 3 votes
Imagine we build the DFA from top to bottom to recognize palindromes of length $2k$. As usual, we'll use the states to "remember" the input seen so far. The DFA will consist of three parts:

1. The states needed to represent the $2^k$ possible choices for the first $k$ characters. This will be a complete binary tree of depth $k$ with $2^k$ leaves and so will need $2^{k+1}-1$ nodes in total.
2. The states needed to process the remaining $k$ inputs. This will consist of $k-1$ layers, each of which contains $2^k$ nodes for a total of $(k-1)2^k$ nodes. For example, suppose we had $k=3$ and after part (1) we were in state $q\_{011}$, i.e., having seen input $\mathtt{011}$. Then on input $\mathtt{0}$ we would transition to the fail state, since $\mathtt{0110}$ could not be part of a 6-character palindrome. If, on the other hand, we saw $\mathtt{1}$ we would change to a state on the next level, since the current input $\mathtt{0111}$ could be part of a palindrome.
3. Finally, we add an accept state and a reject state, with the appropriate transitions from the accept state to the reject state on either 0 or 1 and similarly from the reject state to itself on a 0 or a 1.

We will have $2^{k+1}-1$ states in stage (1), $(k-1)2^k$ states in stage (2) and the two states in stage (3) for a total of $(2^{k+1}-1)+(k-1)2^k+2=(k+1)2^k+1$ states.

It's not hard to use a Myhill-Nerode argument to show that the states are pairwise distinguishable and so this DFA is minimal.

# Answer
> 0 votes
If your alphabet is 0,1, and you want to recognize a palindrome of size exactly $k$ you need $2^k$ states to store which string makes up the first half of your palindrome.

```
{} - {0} - {00}
  \    \ {01}
   \ {1} - {10}
       \ {11}

```

Then you need to mirror that tree there to consume the last read input. The edges are labeled with the last character in the left state. Missing edges lead to fail. The right empty state is accepting.

```
...{00} - {0} \
...{01} /       {} - fail
...{10} - {1} /
...{11} /

```

So I get $2\*2^k$ plus a failure state. If you want to recognize all palindromes up to size $k$, you can nondeterministically guess $k$. You can work out if making that NFA deterministic produces the bound you stated in your question.

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


# Question
Title: Schaefer's dichotomy theorem and reformulating 3-literal clauses
Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would be very unlikely in that it would imply P = NP? I ask because I know that there are some types of problems involving 3-literal-clauses which can be transformed into equivalent 2-sat/Hornsat clauses. I'm thinking specifically of 2-or-3 SAT which can be solved by 2-sat/anti-Hornsat clauses or 1-or-3 SAT which can be solved using affine clauses.

# Answer
Schaefer's dichotomy theorem doesn't purport to claim anything about what transformations might be possible / not possible.

However, as Yuval says, we don't need Schaefer's theorem. We already know that 3SAT is NP-complete. Therefore, we know that if there is a polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT instance, then P = NP. Put another way, if P $\ne$ NP (as many researchers suspect to be the case), then there is no polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT instance. Put yet another way, finding such a transformation that provably works is at least as hard as proving that P = NP.

The same holds for a transformation to any other set of formulas that are known to have a polynomial-time algorithm for testing satisfiable (e.g., the conjunction of Horn clauses).
> 4 votes

---
Tags: complexity-theory, np-complete, satisfiability, p-vs-np, 2-sat
---


# Question
Title: What's the difference between a "dead" and "empty" state?
In computational theory, I came across both deterministic and non-deterministic finite state machines but I heard someone said there are no dead states in deterministic machines. I thought dead and empty states were the same. What I noticed is that empty states are represented by a special symbol called an empty set ∅. What's exactly the difference?

# Answer
> 2 votes
That ∅ in the figure is just the name of that particular state in that machine.You could name it "cpx" if you want.

The figure is an example showing conversion from NFA to DFA. The conversion algorithm builds the DFA states from subsets of NFA states.The state named ∅ indicates that this state represents a particular subset of the states of the NFA, namely the empty set.

So, the symbol is just for the viewer to understand the significance of that particular state in the machine.

# Answer
> 1 votes
As calmyoursenses writes, in one sense, the state labelled $\emptyset$ in the output of the powerset conversion is just a particular state in the DFA it outputs.

On the other hand... It's also true that this particular state has some special properties. $\emptyset$ always has the special property that every outgoing transition from it goes back to itself, and that it is a non-accepting state. Therefore, one could plausibly say that the state labelled $\emptyset$ (in the output of the powerset construction) will always be a dead state. In other words, one could plausibly argue that the state labelled $\emptyset$ in the output of the powerset construction will always be a dead state. However, the converse need not hold: there can be other dead states in the output of the powerstate construction.

Note that all of this is specific to the kind of DFA output by the powerset construction. If you take some other DFA, there need not be any set labelled $\emptyset$ (there's no reason to expect such a label to exist, or to expect states to be labelled by sets).

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


# Question
Title: Unrestricted grammar for the language of strings whose length is not $2^n$
The following exercise is inspired by an old exam question (note that this is not the question):

Let us define a single-letter alphabet $\Sigma = \\{a\\}$ and the language $L = \\{ w \in \Sigma^\*: |w| = 2^n, n \in \mathbb Z\_+\\}$. (In other words, $L = \\{a^2, a^4, a^8, \ldots \\}$.) What is an unrestricted grammar for $L$?

I thought of a solution using binary number representation. Consider the grammar:

$S \rightarrow 10TaX$
$T \rightarrow 0T | \epsilon$
$0a \rightarrow aa0$
$0X \rightarrow X$
$1a \rightarrow a1$
$1X \rightarrow \epsilon$

$\epsilon$ signifies the empty string. Using the first two production rules, we can produce a string of the type $10^naX$, for example $100aX$. One route here to get rid of the non-terminal symbols is $100aX \Rightarrow 10aa0X \Rightarrow 1aa0a0X \Rightarrow 1aaaa00X \Rightarrow 1aaaa0X$ $\Rightarrow 1aaaaX \Rightarrow \ldots \Rightarrow aaaa1X \Rightarrow aaaa = a^4$.

Assuming that this solution is correct, one interesting thing about it is that by modifying the third production rule to $0a \rightarrow a^k0$ one can get a restriction-free grammar for strings of length $k^n$ instead. But maybe there is a cleaner solution, so I am interested in seeing other examples of unrestricted grammars for the language.

However, here comes the actual question: the existence of an unrestricted grammar for $L$ only proves that it is recursively enumerable. Therefore I would like to ask for an **unrestricted grammar of $\overline{L}$** (then we have one proof that $L$ is a Turing-decidable language).

Edit: In case the question here is unclear, please read the discussion in the comments.

# Answer
> 2 votes
1. Your method is correct to generate $L$. But if you change the rule to $0a \to a^k0$ then the language you generate is $L^{'}=\\{a^k,a^{k^2},a^{k^3}....\\}$ ( $k \>2$) .
2. You can show that language $L$ is indeed decidable. One way is to give an algorithm that halts on every input in $\sum^{\*}$ and gives the correct result. Following is the approach
(1) If the input is empty reject.
(2) If not empty , check if there are even number of 'a' or odd. If only one 'a' is there accept. If odd 'a' ( \> 1 ) are there reject.
(3) If even 'a' are there, go back to starting of input and cross off alternate 'a' from beginning to end of input. Go back to step (2).
The algorithm accepts the string $a$ in addition. You can always modify the above algorithm, keeping a special check that if the input is 'a' reject.

# Answer
> 2 votes
As I show here by giving a context-sensitive grammar for $L$, it is actually in CSL. Since CSL is closed against complementation, this answers your question.

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


title: Canonical representation of programs

text:
# Question
Title: Canonical representation of programs
I'm working on some compiler software, and I'm looking for information on canonical forms for expressing software, algorithms, mathematical expressions (including predicate logic), etc. I assume canonicalization is generally intractable, but NP algorithms and more-constrained problems (e.g. pure functions) are also interesting. Normal forms may be useful too. My goal is not to be able to represent and manipulate all programs, but some of them (the trivial ones).

# Answer
> 1 votes
The brief survey contained in this paper might be of interest:

J. Swan, Z. A. Kocsis, and A. Lisitsa. 2014. The 'representative' metaheuristic design pattern. In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO Comp '14). ACM, New York, NY, USA, 1435-1436. DOI=http://dx.doi.org/10.1145/2598394.2609842.

It discusses the existence of canonical forms for various forms of representation (groups, rings, boolean functions etc) and in particular normal forms for the lambda calculus using $\beta$-reduction as a rewrite rule.

# Answer
> -3 votes
this general area fits into the concept/ subarea of intermediate representations/ IRs. here are some basic overviews/ surveys/ refs to start. another related area with large theory is bytecodes. there is some analysis of "canonicalization" of IRs but it is possibly or probably not a major focus in compiler design because, as you say, its undecidable in general. the more practical/ common approach is apparently a "normalizing" or "best-attempt/ heuristic streamlining" of the IRs. a technique that has seen major applied advancement in recent times is just-in-time compiling eg in Java hotspot/ Javascript (v8 engine).

---
Tags: algorithms, normal-forms
---


# Question
Title: Why is Minimum $k$-cut NP hard when $k$ is specified as part of the input?
As you know a set of edges whose removal leaves $k$ connected components is called a $k$-cut. The minimum $k$-cut problem asks for a minimum weight $k$-cut.

For $k=2$ this problem is **P**.

*Vazirani* in his book says for any fixed $k$ when $3 \le k$ it is **NP-hard** and When $k$ is specified as part of the input this problem is also **NP-hard**.

I would like to know what difference does it make when $k$ is specified as part of the input? and why is it **NP-hard** in this case?

# Answer
> 4 votes
First, be careful what Vazirani actually says. On page 38, it is written that:

> "The minimum $k$-cut problem is polynomial time solvable for fixed $k$; however, it is **NP**-hard if $k$ is specified as part of the input."

(In particular, the claim you make about being NP-hard for any fixed $k \geq 3$ holds for a different problem, namely *minimum weight multiway cut*). Indeed, Wikipedia states this is the case as well: for any fixed $k$, you can solve the minimum $k$-cut problem in $O(n^{k^2})$ time. In other words, when $k$ is fixed, you have polynomially many ways of removing $k$ edges. So why does it matter if something is part of the input or fixed then?

When $k$ is fixed, it is *not* part of the input. The problem is this:

> (Minimum $k$-cut.) *Input:* A graph $G$. *Question:* Is there a $k$-cut?

So the problem is defined for every fixed value of $k$. We have minimum 2-cut, minimum 3-cut, minimum 4-cut, and so on. In contrast, the problem could be this:

> (Minimum cut.) *Input:* A graph $G$, an integer $k$. *Question:* Is there a $k$-cut?

Now, it is possible for $k$ to depend crucially on the size of the graph. This way a naive brute-force won't give you a polynomial time algorithm. Another example is given in this question of ours in the context of finding cliques.

---
Tags: algorithms, optimization, approximation
---


# Question
Title: Why is the intersection of CFL and RL not always RL?
Suppose M is a CFL and N is aa RL. Then wouldn't the language generated by the intersection of M and N contain strings, some of which are accepted by both DFA and PDA? So if they are accepted by a DFA as well, then why is the generated language not an RL?

# Answer
> 5 votes
Let $C=\\{0^n1^n\mid n\ge 0\\}$, a known CFL. Let $R=\\{w\in\\{0,1\\}^\*\\}$, a known regular language. Then $C\cap R = C$, which is not regular.

# Answer
> 3 votes
Being *a* set of strings accepted by some DFA is not the same as being *the* set of strings accepted by a DFA.

It is true that, if $M$ is context-free and $N$ is regular, then $M\cap N$ is a set of strings, all of which are accepted by some DFA – the automaton that accepts $N$ must accept all strings in $M\cap N$. However, to say that $M\cap N$ is regular is something stronger: $M\cap N$ is only regular if it is *the* set of strings accepted by some DFA, i.e., if there is a DFA that accepts every string in $M\cap N$ and rejects every string not in $M\cap N$. The automaton that accepts $N$ accepts every string in $M\cap N$ but also accepts every string in $N\setminus M$. Therefore, unless $N\subseteq M$, the automaton that accepts $N$ also accepts a bunch of strings that aren't in $N$. So, just knowing that $N$ is regular (so there's an automaton for it) isn't enough to show that $M\cap N$ is regular.

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


title: Daily Applications of Type Theory

text:
# Question
Title: Daily Applications of Type Theory
I want to understand type theory but I have to know first how I can apply it. Could there be more non-obvious applications of type theory aside from in type systems in programming? Could there be other applications, let's say in personality profiling and the likes?

# Answer
> 11 votes
Because of the Curry-Howard correspondence, types can be interpreted as propositions, and propositions as types.

As a result of this, type theory is applicable to literally any field that uses formal logic for its proofs. This can be circuit verification, real analysis, symbolic logic, geometry, etc.

For instance, some automated proof checking tools work using this principle: they check the validity of the proof by type-checking a particular term in some type system. The LF proof checker is based on this approach, as is HOL Light. As an example application, proof-carrying-code used LF to check proofs of memory-safety of untrusted code. The benefit of using this kind of proof-checker is that the implementation can be very simple, and thus we can gain high assurance that the implementation is correct. See, e.g., the following paper:

Foundational Proof Checkers with Small Witnesses. Dinghao Wu, Andrew W. Appel, Aaron Stump. PPDP 2003.

# Answer
> 10 votes
You may be interested in the work on Ceptre, a result of the PhD research of Chris Martens, which uses type theory for interactive storytelling. Quoted below is the thesis abstract:

> Interactive storytelling weaves together deep computational ideas with humanity's rich history of story and play, providing an important context for tools and languages to be built. At the same time, formal specification languages offer a palette of representation and inference techniques typically reserved for the analysis of programming languages and complex deductive systems. This thesis connects problems in the interactive storytelling domain to solutions in formal specification.
>
> Specifically, we examine narrative from a structural point of view and observe that alternative narrative paths play a complementary role to simultaneous interacting timelines. Linear logic provides the representational tools necessary to investigate this structure, and by extending the correspondence to proofs and proof construction, we find a suite of computational possibilities. We present three efforts toward realizing those possibilities: (1) the use of linear logic programming to generate narratives; (2) a new programming language for authoring interactive narratives, games, and simulations; and (3) techniques for stating and proving design-level program properties.
>
> We find that linear logic programming, enriched with a minimal extension to its logical semantics, enables a wide range of programming idioms and domain encodings. As evidence, we give five case studies, including social simulation, combat-based adventure games, and board games. To support reasoning about design correctness, we present techniques for stating and proving program invariants, as well as a decidability proof for automatically checking those invariants for a large fragment of the language.
>
> These findings show that linear logic is a fruitful representation language to serve as the basis for modeling and executing interactive worlds, and they invite future investigations on using proof-theoretic methodologies for creative systems.

# Answer
> 9 votes
There has been interesting uses of type theory in linguistics. See for example the linguistic works of Chung-chieh Shan or Christian Rétoré.

Quoted below is the description of Rétoré's book on categorial grammars:

> This book is a contemporary and comprehensive introduction to categorial grammars in the logical tradition initiated by the work of Lambek. It guides students and researchers through the fundamental results in the field, providing modern proofs of many classic theorems, as well as original recent advances. Numerous examples and exercises illustrate the motivations and applications of these results from a linguistic, computational and logical point of view. The Lambek calculus and its variants, and the corresponding grammars, are at the heart of these lecture notes. A chapter is devoted to a key feature of these categorial grammars: their very elegant syntax-semantic interface. In addition, we adapt linear logic proof nets to these calculi since they provide efficient parsing algorithms as exemplified in the Grail parser. This book shows how categorial grammars weave together converging ideas from formal linguistics, typed lambda calculus, Montague semantics, proof theory and linear logic, thus yielding a coherent and formally elegant framework for natural language syntax and semantics.

The following quote is in the introduction of Shan's Linguistic Side Effects book chapter:

> This paper relates cases of apparent noncompositionality in natural languages to those in programming languages. It is shaped like an hourglass: I begin in §1 with an approach to the syntax-semantics interface that helps us build compositional semantic theories. That approach is to draw an analogy between computational side effects in programming languages and what I term by analogy linguistic side effects in natural languages.
>
> > This connection can benefit computer scientists as well as linguists, but I focus here on the latter direction of technology transfer. Continuations have been useful for treating computational side effects. In §2, I introduce a new metalanguage for continuations in semantics.
> >
> > > The metalanguage I introduce is useful for analyzing both pro- gramming languages and natural languages. For intuition, I survey the first use in §3, then point out the virtues of this treatment in §4.
>
> Turning to natural language in §5, I describe in detail how this perspec- tive helped Chris Barker and I study binding and crossover, as well as wh-questions and superiority. I have also used continuations to study quantifier and wh-indefinite scope, particularly in Mandarin Chinese, but there is only room here to sketch these further developments, in §6.

# Answer
> 7 votes
An interesting article that explain applications of dependent types, is the The Power of Pi, that shows how Agda can be used to solve interesting problems.

Another good example is the use of dependent types to resource control. A good example is the file management API of Effects of Idris. For instance, the function for reading a line from a file has the following type

```
readLine  : { [FILE_IO (OpenFile Read)] } Eff String

```

which specifies that this function is only applicable if there's a file opened. The list in braces indicates which effects are available. In this case, we have that this function requires the effect of having a file opened for reading.

More information on Effect library can be found here.

One more application is the use of dependent types for concurrency as reported in the following article by the creator of Idris.

# Answer
> 3 votes
as mentioned in jmite's answer, higher order logic/ type theory in circuit/ hardware/ electronics verification has been around for decades and is now so routine that its not even noticed/ regarded so much as an "application" after an apparently major transfer effort in the ~1990s although its still an active area of research. there is also a lot of application of Coq and its type logic in particular to circuit/ hardware/ electronics verification all the way from low level gate logic to much higher level/ order structures/ subsystems. here are a few key refs

---
Tags: type-theory, applied-theory
---


# Question
Title: Research work on computational models for a "specific" person's behaviors
Is there active research work on creating computational models of a "specific" person's behaviors (general behaviors, emotions, actions...)? What are some references for such research? I tried google and scopus and did not have much luck.

I have worked on modeling movement behaviors of pedestrians in crowd (for my PhD work), but I am planning to work on the simulation of general behaviors of individuals (based on the historical data of their actions and behaviors).

I am more inclined to use machine learning methods than detailed mathematical models.

# Answer
this is a broad area now overlapping with big data and (mass) surveillance technology. here are a few refs with scientific elements/ angles/ leads/ papers/ books etc. and reference to a new field of "social physics"
> 1 votes

---
Tags: machine-learning, artificial-intelligence, simulation, pattern-recognition, agent-based-computing
---


title: [Graph Problem algorithm]

text:
# Question
Title: [Graph Problem algorithm]
I am new here . Please forgive me if there is anything wrong in that I am going to write . So , my question is about one problem given in last round of codeforces , pretty easy to handle it , but I do not understand the other players\` solutions .

THE PROBLEM :

We have a convex polygon and numbers it's vertices 1, 2, ..., n in clockwise order. Then starting from the vertex 1 , we draw a ray in the direction of each other vertex. The ray stops when it reaches a vertex or intersects with another ray drawn before. We repeat this process for vertex 2, 3, ..., n (in this particular order). And then we put a walnut in each region inside the polygon. What is the minimum number of jumps we have to perform in order to collect all the walnuts?

I think the answer is equivalent to find the number of all those distinct regions / faces of that graph .

How could the answer be : $(n-2)^2$ .

# Answer
It is just a counting problem. Here is my brief analysis and see if it makes any sense to you.

A key observation is to notice the answer is equal to the number of rays plus 1. Here is an explanation: Initially, there is 1 walnut on the polygon and no ray. Then, each extra ray will separate a region into two and thus increase the total number of walnut by 1.

What remains is to count the number of rays.

First of all, NONE of vertices can shoot itself. Then, I separate all vertices into three groups:

1. For Vertex 1. It CANNOT shoot rays to vertices 2 and N because of immediate neighborhood.

Then, the polygon has been triangulated and each region can be studied separately. Now, NONE of the remaining vertices can shoot ray to vertex 1 (because they have been shot by vertex 1 already).

2. For vertices 2 and N. Vertex 2 CANNOT shoot ray to vertex 3, and vertex N CANNOT shoot ray to vertex N-1 (because of immediate neighborhood too).
3. For vertices 3, 4, ... up to N-1. They CANNOT shoot ray to the TWO NEIGHBORING VERTICES.

At the end, the answer is

$1+Ray\_{v\_1} + Ray\_{v\_2, v\_N} + Ray\_{V-\\{v\_1,v\_2,v\_N\\}}\\ = 1+1\times (N-3)+2\times(N-3)+(N-4)\times(N-3)\\ = (N-1)\times(N-3)+1$

which is equivalent to $(N-2)^2$

Notice that the formula may not make sense when $N\<5$, but you can memorize it.
> 2 votes

---
Tags: graphs, combinatorics
---


# Question
Title: A variant of the vertex cover problem on trees
Consider the following variation on the vertex cover problem: given a tree on $n$ vertices, we are asked to calculate minimum size of a multiset $S$ such for each edge $(u,v)$ in the tree at least one of the following holds:

* $u\in S$,
* $v\in S$,
* there are at least two vertices in $S$, each of which is adjacent to $u$ or $v$.

Since $S$ is a multiset, a vertex may be in $S$ multiple times.

My hunch is the following. First of all, we take into consideration the following fact: in optimal solution each vertex is in $S$ at most twice. So we can traverse tree in post-order and calculate results for the three cases where a vertex is not in the optimal $S$, it's in once and it's in twice.

Unfortunately I can't link relations between subproblems and I'm not sure if this idea would be correct.

Hints or references are both welcome. Many thanks.

# Answer
Define $f(v,r,s)$ to be the minimum size of a multiset $S$ that covers the entire tree rooted at $v$, such that $S$ contains exactly $r$ copies of $v$'s parent and exactly $s$ copies of $v$.

Then you can express $f(v,r,s)$ in terms of the values $f(w\_i,s,t\_i)$, where the $w\_i$'s are the children of $v$. If the tree is a binary tree, there are only $9=O(1)$ cases you need to consider and at most $2\times 3=O(1)$ terms in the recursive expression for $f(v,r,s)$. The case analysis gets a bit ugly, but it's all $O(1)$.

Therefore, you get a $O(n)$ time algorithm for this problem, if the tree is guaranteed to be a binary tree. I don't know what happens for general trees of unlimited degree.
> 3 votes

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


# Question
Title: Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it?
Is the language $\\{a^{n^2-1} | n \in \mathbb{N}\\}$ context free? and how to prove it? I think it is, but I could not find a way to prove it by using push down automaton or any other way.

# Answer
> 1 votes
A unary language (a subset of $a^\*$) is context-free iff it is regular. This is a special case of Parikh's theorem. It is not too hard to show that a unary language $L$ is regular if and only if there exist $n,m$ such that for all $N \geq n$, $a^N \in L$ iff $a^{N+m} \in L$. See if this condition holds for your language.

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


# Question
Title: Upper bound on the number of triangles in a planar graph
For any $n \geq 4$, I was able to prove that every Apollonian network has $3n - 8$ triangles. An Apollonian network is a planar graph defined by recursively subdividing a triangle by three smaller triangles (adding a new vertex inside the face and connecting it to all three vertices). Now I am trying to prove a similar statement for arbitrary planar graphs. In particular, I am trying to show that every planar graph has at most $an + b$ triangles, for some constants $a$ and $b$, where the goal is to make the constants as tight as possible. The result I showed implies that we need $a \geq 3$ and $b \geq -8$ This is an assignment question, so I would only like a hint please. I believe that I should be able to prove that no planar graph has more triangles than an Apollonian network, but unsure how to proceed.

# Answer
> 1 votes
Presumably you have to show that if you triangulate an arbitrary planar graph then you get an Apollonian network. Then you have to show that the triangulated graph contains more triangles than the original one. This will complete the proof.

---
Tags: graphs, mathematical-analysis, planar-graphs
---


# Question
Title: Does classification of a problem also require the algorithm used?
Just learnt that a problem in computer science can be divided into the following categories

```
Polynomial problems
NP problems
NP hard problems
NP complete problems

```

based on how long it takes to run the program

For example, suppose there is a problem P that can be solved with two algorithms say A1 and A2 where,

```
A1 is polynomial in nature,
A2 is non-polynomial

```

According to me, if P is solved using A1, then P is a polynomial problem and if P is solved using A2, then it must be an NP problem.

Am I right?

In other words, is it fair enough to say that classification of a problem does also require the algorithm that is being used to solve it?

# Answer
> 1 votes
No. The classification of problems into complexity classes is based on the amount of resources *required* to solve the problem, not the resources that some programmer decides to use. If you have a smart algorithm that solves a problem in polynomial time, and a dumb one that uses exponential time, the problem itself is in polynomial time because it *can* be solved within that resource bound.

---
Tags: algorithm-analysis, p-vs-np
---