# Question
Title: Proving correctness of an iterative Fibonacci algorithm
One of the questions in the problem sets that I'm struggling in is this specific number that asks me to prove an iterative Fibonacci algorithm. The algorithm is written below:

```
function fib(n)
    if n = 0 then
        return(0)
    else
        a = 0; b = 1; i = 2;
        while i <= n do
            c = a + b
            a = b
            b = c
            i = i + 1
    return(b)

```

The way too prove correctness, according to my professor was to make sure that there are these three steps:

1. Initialization - the loop invariant must hold true prior to the first iteration
2. Maintenance - the loop invariant must hold true after an iteration
3. Termination - the loop invariant must hold true when the loop terminates

The loop invariant I've chosen is `a <= b` since I find this to be true for steps 1 through 3. First of all, I'm not sure if this is a valid loop invariant and this is the only observation I saw since `i <= n` isn't always true for inputs `n` that are natural numbers.

Assuming that I've chosen the correct loop invariant, I need to answer the proof by doing three steps so for this number I plan to answer it this way

1. Initialization - before the start of the loop `a` is assigned a value of 0 while `b` is assigned a value of 1 which starts the Fibonacci sequence. `a <= b` holds true prior to the start of the loop
2. Maintenance - during the loop, another variable `c` is added such that it is equal to the sum of `a` and `b`. After which, `b` is assigned to variable `a` while `c` is assigned to `b` thus making the invariant `a <= b` true during the iteration.
3. Termination - the loop ends when `i > n`. Before `i` is incremented, the procedures in the maintenance step is still done, thus the loop invariant still holds true

For my questions, is my loop invariant `a <= b` correct? And are the three statements I mentioned above sufficient to prove the correctness of an iterative Fibonacci algorithm?

# Answer
> 0 votes
The condition $a \leq b$ is a loop invariant, but it captures very little of the operation of the loop. A better loop invariant is $$ a = F\_{i-2} \text{ and } b = F\_{i-1}. $$ This clearly holds just before the loop. The loop sets $a' = b = F\_{i-1}$, $b' = a+b = F\_{i-2}+F\_{i-1}=F\_i$, $i' = i+1$, from which it is easy to prove that it maintains the loop invariant. When the loop has finished, we must have $i = n+1$, and so $a = F\_{i-2} = F\_{n-1}$ and $b = F\_{i-1} = F\_n$.

There is a weak point in this argument: How do we know that $i = n+1$ at the end of the loop? We can fix this by strengthening the loop invariant to $$ a = F\_{i-2} \text{ and } b = F\_{i-1} \text{ and } i \leq n+1. $$ This holds just before the loop since $n \geq 1$ (assuming $n \geq 0$, a precondition that needs to be added to the entire function). It is maintained during the loop since at the beginning of each iteration $i \leq n$. Finally, after the loop we have $i \leq n+1$ and $i \> n$, which forces $i = n+1$ since $i$ is an integer.

---
Tags: algorithms, algorithm-analysis, proof-techniques, correctness-proof, loop-invariants
---


# Question
Title: Prove by reduction EVEN TM is undecidable
```
Reduction from ATM.
Assume that EVEN TM is decidable with decider MT.
We now show how to build, given a ⟨M, w⟩ a machine description ⟨M'⟩ that satisfies the following faithfulness condition.
If M accepts w then M' accepts every even-length string
If M does not accept w then M' does not accept every even-length string
M':
On input x
 If x is an **odd-length** string then accept
 Else simulate M on w and answer what M answered.
Obviously M' satisfies the faithfulness condition.
Here is a decider for ATM.
On input ⟨M, w⟩
1. Build ⟨M'⟩
2. Run MT on input ⟨M'⟩
3. Answer what MT answered.

```

So I have this solution the the problem, what I don't understand is why ⟨M'⟩ checks for odd length first then accepts right away? this doesnt make sense to me

# Answer
> 2 votes
The idea is that for this reduction, we want the resulting TM to give us exactly the answer to $A\_{TM}$, and the focus here isn't M' but much rather what happens when we call the decider (which you call MT) on M' instead.

To go through this in detail, bear in mind the reduction is considered valid if we can someone manage construct a machine that can decide $A\_{TM}$ which we know derives a contradiction. Consider the one that you provided:

1. Let's say that D(M') accepts. This means that M' doesn't accept any odd inputs at all, so that means we need to feed M' even inputs for it to accept. This also means that when given an even input $x$, it'll always discard $x$ and run M(w) instead, so it must be that M(w) always accepts. Which means we can know that $\<M,w\>$ $\in A\_{TM}$, or that M will halt on w.
2. Now the opposite direction. Let's say that D(M') rejects. This means that M' doesn't accept when any even input. But if that's the case, this must mean that M(w) doesn't accept at all, this should follow from the same idea as (1).

So as an overview, we're saying, assuming that we can decide $EVEN\_{TM}$, it would then be possible construct a decider for $A\_{TM}$. The important thing to note here is that the focus is on: (a) creating a new machine M' for the decider **based on** the inputs to $\<M, w\>$ for $A\_{TM}$, and (b) making sure that the decider accepts M' **if and only if** $\<M, w\> \in A\_{TM}$ to derive a contradiction.

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


# Question
Title: Deterministic algorithm to find number of collisions
Let $h:U \to\[m\]=\\{0,1,\dots,m\\}$ be hash function, which can calculate $h(u), \forall u\in U$ in $O(1).$

Let $D \subseteq U$ be a subset of size $n.$

I'm looking for a deterministic algorithm, efficient as possible, to find the number of collisions of $h$ on $D$

I thought to start operating $h$ on all elements in $D,$ place the results in an array and work with that, but not sure how to continue.

Any help is appreciated.

# Answer
> 2 votes
You could hash all of the elements of $D$, sort them, and then count duplicates. Sorting brings all duplicates next to each other, so a linear scan lets you count the number of duplicates. The running time will be $O(|D| \log |D|)$.

If you don't insist on a deterministic algorithm, you could place elements of $D$ into a hashtable, using $h$ as your hash, and then count the size of each hash bucket. If the hash function is any good, then there is a sense in which the expected running time is $O(|D|)$ (e.g., if the elements of $D$ are random and the hash function is sufficiently good) -- but the worst case is $O(|D|^2)$.

---
Tags: algorithms, data-structures, hash
---


# Question
Title: how does cpu read 32 bit word from memory
I'm interested in how does cpu read 32 bit word from memory .If the processor has 32 bits of address space then it can address 4,294,967,295 locations (or 4 gb) Does this mean that each location has 32 bits.?

# Answer
Address Space and Word Size are indeed two different things. If my processor has an $n$ bit address space, then it can address $2^n$ addresses. Note that this is merely the number of addresses and is **not $2^n$ GB**.

The word size of a memory refers to the size of the smallest addressable unit of the memory. In other words if my processor has an $n$ bit address space and a word-size of $b$ bytes, then my processor can address $2^n$ locations each of which are $b$ bytes long.
> 2 votes

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


# Question
Title: Can three regular languages be concatenated?
I can't seem to find anything about this and I wonder if I'm asking a silly question.

> If you have three languages $L\_1=\\{a,b\\}, L\_2=\\{c,d\\}, L\_3 =\\{e,f\\}$, can they be concatenated?

If yes, would you concatenate the first two and concatenate the result to the third one or would you concatenate it as $\\{ace, ade, acf, adf, bce, \ldots\\}$? And what if one of the languages only contained the empty word $ε$?

# Answer
Concatenation is associative: $$ (L\_1L\_2)L\_3 = L\_1(L\_2L\_3) = \\{w\_1w\_2w\_3 : w\_1 \in L\_1, w\_2 \in L\_2, w\_3 \in L\_3\\}. $$ We denote the common value by $L\_1L\_2L\_3$.

A class of languages closed under concatenation of two languages is also closed under concatenation of three or more languages, as a simple induction shows.

The "zero" element for concatenation is the empty language $\emptyset$, which satisfies $L\emptyset = \emptyset L = \emptyset$. The "one" element for concatenation is the language consisting of only the empty word $\\{\epsilon\\}$, which satisfies $L\\{\epsilon\\} = \\{\epsilon\\}L = L$.
> 3 votes

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


# Question
Title: How do NFA's make program design any better when converted DFA form can't remember original states?
Here is some content from the book by Peter-Linz I read

> "Consider a game-playing program where the machine needs to make the decision for the next move \[say for tic-tac-toe\]. Since there are multiple moves possible, we deterministically choose each move and evaluate the move and opt for the best one. Even though the selection process was deterministic and there were many possible moves, the final move made was a single one and was chose as best move while hiding all the tried move-computations from the opponent. \[Here we assume that the evaluation process of each possible move was hidden from the opponent\].
>
> Hence only one choice was made and opponent is given a illusion such that the move was non-deterministic."

My question is: if an NFA is translated to a DFA for implementation purpose ,how does the DFA make(remember) the correct transitions to the states defined in the original NFA(the game)? My confusion stems from the fact that when an NFA is translated to an DFA it's states get mixed up.

Suppose in a simple game below ,Player is at center position and he wins if he moves leftwards:

if the above DFA is implemented it surely finds a winning state on a "m"(move),but how does it decide whether it was right or left move?

# Answer
> \[i\]f the above DFA is implemented it surely finds a winning state on a "m"(move),but how does it decide whether it was right or left move?

In the example you gave, it can't. The nondeterministic transition from the start state occurs when a "move" is made. That's all you can possibly know; the machine can't determine whether the winning move was left or right, because those aren't allowed possibilities.
> 1 votes

# Answer
There's something called a Buchi powerset construction which describes what you're looking for.

To give an intuition on how it works, it's kind of like this: Given an NFA, we know if has finitely many states, and at any step of the computation, multiple states can be "active" as a branch at any time. To determine the next step, it's like observing each how each branch reacts to the next symbol in the input.

So, construct each state in the DFA as a subset of the states in the NFA. Then, add a transition from a subset to another subset based on how each of the active states in that subset react to the next symbol in the

To demonstrate the transitions between sets let's say I design an NFA as follows:

It has 3 states {$q\_1, q\_2, q\_3$} and the transition function works like this,

$\delta(q\_1,a)=\\{q\_2,q\_3\\}$

$\delta(q\_2,b)=\\{q\_1\\}$

$\delta(q\_3,b)=\\{q\_2\\}$

It's an artificial example without accepting states, it's just to show how the transition works.

So as an NFA, if it starts on $q\_1$ and we gave it "ab" as an input, then the sequence of set of states that the NFA goes through is: $\\{q\_1\\}, \\{q\_2,q\_3\\}, \\{q\_1,q\_2\\}$ .

it's the same as just making these sets into a state for a DFA like so:

DFA has states: $\\{q\_a, a\_b, q\_c\\}$, letting $q\_a$ represent $\\{q\_1\\}$, $q\_b$ represent $\\{q\_2,q\_3\\}$ and $q\_c$ represent $\\{q\_1,q\_2\\}$

$\delta(q\_a,a)=q\_b$

$\delta(q\_b,b)=q\_c$

It's quite tedious to go through the entire $2^n$ states so usually after something like that sort of construction you can try to minimise it using a DFA minimisation algorithm or just by considering which states are useless and what transitions can be shortened after.
> 0 votes

# Answer
You asked:

> my question is if NFA is translated to DFA for implementation purpose

I think that the premise of the question is not correct, since it is clearly stated by the author (at least according to your question) that:

> Since there are multiple moves possible, we **deterministically** choose each move and evaluate the move and opt for the best one.

So from the outset it is clear that any Non-determinism is just a result of abstracting the Deterministic Finite machine. So in this particular case, the conversion (loosely stated) is from a DFA to an NFA and not otherwise.

Coming to your question specifically, the DFA and NFA have different states altogether. The states from an NFA (say $S\_n$) are used to construct the new states for the DFA (say $S\_d$) and once they have been constructed, the DFA only tends to $S\_d$. There is no need for the DFA to remember $S\_n$ and the associated transitions.

Thus to sum it up, the DFA does not make transitions to the states $S\_n$. It only makes transitions between the various states $S\_d$.
> 0 votes

# Answer
In this particular example, the problem is that the transition labels are just "move". This violates the idea that the NFA represents a **language** that we are interested in if we later want to find out which move was the right one. Hence the NFA to DFA translation makes little sense in this case.

A simple solution would be to label every transition in the NFA by the last move taken by one of the two players, and then determinizing the NFA would retain this information.

(This is, if I get your question right. If you study games, you normally model your game as as *game*, rather than an NFA).
> 0 votes

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


# Question
Title: Efficiently compute parallel matrix-vector product for block vectors?
I have $P$ processors, each having a different vector $v\_p$ of size $N$, $p=1, ..., P$. I now want to compute the matrix-vector product $$w = (E\otimes I\_N)v$$ in parallel, where $\otimes$ is the Kronecker product, $v = (v\_1, ..., v\_P)^T$ is the stacked vector consisting of all local vectors $v\_p$, $E = (e\_{pj})\_{p,j}\in\mathbb{C}^{P\times P}$ some dense matrix and $I\_N$ is the identity matrix of size $N\times N$.

So, to do this, each processor $p=1, ..., P$ has to compute $$w\_p = \sum\_{j=1}^P e\_{pj} v\_j$$ and for this, all $P$ vectors $v\_p$ have to be sent to all $P$ processors.

Now, $N$ is pretty large (say, $10^8$), in particular much larger than $P$ (which is only 10-100) and so large that $NP$ (the size of $w$ and/or all vectors $v\_p$ together) does not fit into each processor's memory. Also, sending all these vectors $v\_p$ in an all-to-all fashion seems pretty hard on the network.

Is there a standard and/or particular efficient way to compute this sum for a general matrix $E$? What would be the complexity of this approach?

Any help, suggestions or links to publications are appreciated!

# Answer
You can do this as a parallel sum. You want to compute

$$w\_i = \sum\_{j=1}^P e\_{ij} v\_j,$$

where processor $j$ has the vector $v\_j$.

One way to do this is to have each processor compute $e\_{ij} v\_j$ locally. Then, use a binary tree to compute the sum. In particular, processor 1 sends $e\_{i1} v\_1$ to processor 2, which computes the sum $e\_{i1} v\_1 + e\_{i2} v\_2$; processor 3 sends $e\_{i3} v\_3$ to processor 4, which computes the sum $e\_{i3} v\_3 + e\_{i4} v\_4$; and so on. Then, processor 2 sends $e\_{i1} v\_1 + e\_{i2} v\_2$ to processor 4, which computes the sum $e\_{i1} v\_1 + e\_{i2} v\_2 + e\_{i3} v\_3 + e\_{i4} v\_4$; and so on. Repeat until you have computed the final sum. Basically, this is just parallel sum of some vectors (parallel aggregation).

This requires sending $\Theta(NP)$ data over the network, and $\Theta(\log P)$ rounds of communication. Each processor only needs memory for $\Theta(N)$ data. So, it looks like it meets all your requirements. It may still be hard on the network, but that seems unavoidable given what you are trying to compute. You'll do this $P$ times, to compute $w\_1,\dots,w\_P$, so in total it will require $\Theta(NP^2)$ data on the network, $\Theta(P \log P)$ rounds of communication (though they can be parallelized down to $\Theta(\log P)$ if the network is fast enough), and $\Theta(N)$ space on each processor.
> 0 votes

---
Tags: algorithms, parallel-computing, matrices, numerical-algorithms, multiplication
---


# Question
Title: Why is the unit of image size not Pixel²?
If you calculate the area of a rectangle, you just multiply the height and the width and get back the unit squared. Example: 5cm * 10cm = 50cm²

In contrast, if you calculate the size of an image, you also multiply the height and the width, but you get back the unit - Pixel - just as it was the unit of the height and width before multiplying. Example: What you actually calculate is the following: 3840 Pixel * 2160 Pixel = 8294400 Pixel

What I would expect is: 3840 Pixel * 2160 Pixel = 8294400 Pixel²

Why is that the unit at multiplying Pixels is not being squared?

# Answer
The width of an image is being measured in a discrete 2 dimensional space.

The image is 3840 pixels across. This means there is a horizontal band of 3840 pixels (which are each 2 dimensional regions) that cross the space. We aren't using pixel as a unit of measurement -- we are actually counting things called pixels.

When we measure how tall it is, we measure 2160 pixels in a vertical band to the top of the image. Again, pixel isn't a unit of measurement, it is a thing we are counting.

If you take a grid of things that is 3840 wide and 2160 tall, you end up with 3840\*2160 of them. This is counting.

We could *also* describe the image as 3840 pixel\_widths wide and 2160 pixel\_heights tall, and modify those *distances*. Then we'd get 3840\*2160 (pixel\_width * pixel\_height) area. This is an area calculation.

These happen to have the same numerical value because `pixel_width*pixel_height = pixel_area`, and X pixels have an area of X pixel\_area.

A difference between these calculations appears when you have non-square pixels and you rotate. Something 10 pixel\_widths wide rotated 90 degrees may not be 10 pixel\_heights tall. At the same time, the rotation should preserve area (up to rounding).

The ratio between width and height on a pixel is called its aspect ratio. CRTs often had an effective aspect ratio of 1.11 if I remember correctly.
> 7 votes

# Answer
Because "pixel" isn't a unit of measurement: it's an object. So, just like a wall that's 30 bricks wide by 10 bricks tall contains 300 bricks (not bricks-squared), an image that's 30 pixels wide by 10 pixels tall contains 300 pixels (not pixels-squared).
> 239 votes

# Answer
I have a different answer from other folks: pixel *is* the correct unit for areas, and you *do* need dimensional analysis. The discrepancy is that the pixel in "3840 pixels wide" is not the same unit as the pixel in "the display has 8294400 pixels". Instead, "pixel" is a natural-language abbreviation for different units at different times, and it takes some context and judgment to expand the abbreviation appropriately.

The unabbreviated form is "3840 pixel-widths wide x 2160 pixel-heights tall = a bazillion pixel-areas" (and one "pixel area" is definitionally equal to "pixel-width * pixel-height" for rectangular pixels).

N.B. it is frequently assumed that pixel width and pixel height are equal (as in the CSS discussion in the other answer), and even without that assumption the above assumes that pixels are rectangular -- and these assumptions are often but not always true!
> 122 votes

# Answer
# A pixel is already a two-dimensional object

In your example, you specify *centimeters* as a contrasting example. *Centimeters* are a unit of length, which is by nature a one-dimensional measurement. When measuring areas, we need to talk about *square centimeters*, which defines the unit as a two-dimensional quadrilateral with right angles and equal length sides = 1cm. When discussing volume we then talk about *cubic centimeters*, which defines the unit as a three-dimensional, six sided prism with squares for sides, the length of each side = 1cm.

Since a pixel is an abstract concept, and not a strict unit of measure, it makes sense for it to exist purely as a two-dimensional object. When you're measuring something like screen resolution, you could consider the measurement to include an implied *pixel widths*. *ex: 1920 pixel widths x 1280 pixel widths*

As an interesting note, there is a three-dimensional pixel, called a *voxel*, which is defined as a three-dimensional prism with a pixel for each face.

@KlaymenDK Had a great note, which is that pixels are so abstract and context sensitive that they are not necessarily square. This pushes their class further from 'unit of measure' and into 'count of objects' territory.
> 44 votes

# Answer
As others have said it's because pixel is an object. If you'd like to think of it in terms of units, the equation is technically `3840 pixel-heights * 2160 pixel-widths = 8294400 pixels` (where you can think of a pixel as `1 pixel-height * 1 pixel-width`)
> 16 votes

# Answer
Pixels are weakly typed units. Just like `1` can be coerced into an integer, floating-point value, or string in a weakly typed language, a "*pixel*" is coerced into whatever unit makes sense in context.

If we were to more strongly type the unit, we'd probably have several:

1. pixel-width;
2. pixel-height;
3. pixel-diagonal; and
4. pixel-area.

As you correctly point out, if we assume that pixels are squares, then$$ \left\[\text{pixel-area}\right\] = {\left\[\text{pixel-side}\right\]}^2, $$such that it'd make more sense to speak of *square-pixels* when discussing image size in terms of *pixel-sides*.

The thing's just that, if we're talking image size, then a "*pixel*" is meant to be coerced into a *pixel-area*, not a *pixel-side*.

### Note: Pixels are units

A ***unit*** is literally anything we use to express measurements of some sort. Sure pixels are objects, but so are other units - there's no conflict there. For example, in the US, we still measure lengths in *feet*.

Object-defined units of measurement were the historical norm, so there's nothing unusual about pixels being object-defined units. Just, there're obvious shortcomings to such definitions, so in recent history standardization efforts have been made. For example, *feet* are now more formally defined than as a person's foot's length.

That said, the same is happening to the *pixel* unit:

> A **device-independent pixel** (also: *density-independent pixel*, *dip*, *dp*) is a physical unit of measurement based on a coordinate system held by a computer and represents an abstraction of a pixel for use by an application that an underlying system then converts to physical pixels.
>
> -"Device-independent pixel", Wikipedia
> 12 votes

# Answer
You may want to look at this in another way:

$$3840\\, \frac{\mathrm{px}}{\mathrm{scanline}}\times2160\\, \mathrm{scanline}=8294400\\,\mathrm{px}.$$

I.e. treat pixels as two-dimensional objects, much like bricks in a wall, and just count them along the display width and height.
> 6 votes

# Answer
A pixel on a screen is like a block in your city. You don't say *I love the houses on this city block²* since block is by definition *itself* the square, not the side of the square.
> 4 votes

# Answer
Pixel are a discrete unit you want to know the count of. Practically, it is like counting potatoes in several bags. Use the other length as plain number, so eg. 1600\*900 Pixels, but not 1600 Pixels\*900 Pixels. Leaving one number without unit yields Pixels as expected (instead of Pixels-squared) and is mathematically correct.
> 3 votes

# Answer
Technically a pixel is not a unit of measurement. In optical design pixels are measured in radians. In photogrammetry, particularly when performing interior orientation, pixels are measured in millimeters. For example, if you have a sensor with 5micron pixels and you talk about a line of pixels 1000 wide, those pixels are not 5mm wide by 1mm or 0mm tall. They are 0.005mm tall. Pixels are inherently 2 dimensional, sort of. When you include tonal information pixels are actually 3 dimensional. 4th, 5th, or 6th dimensional pixels are, of course, voxels. Within the realm of hyperstacks, each nth dimension is defined and can decompose into into its constituent pixels across any dimensionality.

To think about this more concretely (pun intended) if you have a cinder block wall and the blocks are 9x18 inches then a 10x10 block wall will be 90x180 inches or 10 blocks wide and 10 blocks tall. I suppose that if you had a 1000x1000 block wall you could say that you had a megablock but then there would need to be a base2 / base10 debate.

Bottom line, those pixel dimensions might be convenient integers when stored in an image file but in the real world a single pixel can have any number of dimensions greater than 2 and have sizes of any precision.
> 1 votes

# Answer
It happens when you multiply units. Pixel is not a unit. You can do that with Pixel per Inch etc. but not with the pixel alone.
> -2 votes

---
Tags: terminology
---


# Question
Title: What does it mean "given a NFA and its accepted language L build the DFA that accepts L*"?
Supposing we have either a NFA or a DFA with accepted language $L$, what is $L^\*$? And how can I build an automaton that accepts it?

# Answer
$L^\*$ is the Kleene closure of $L$. This is the language of all strings that can be made by taking a finite number of (not necessarily different) strings from $L$ and concatenating them. More formally,

$$L^\* = \\{\varepsilon\\}\cup\\{w\in\Sigma^\*\mid \exists k\geq 1\\,\exists w\_1, \dots, w\_k\in L \text{ such that } w = w\_1\cdot\dots\cdot w\_k\\}\\,.$$

Or, if you prefer, for $k\geq 1$, let $$L^k = \\{w\_1\cdot \dots \cdot w\_k\mid w\_1, \dots, w\_k\in L\\}$$ and then $L^\* = \\{\varepsilon\\}\cup L^1 \cup L^2 \cup L^3 \cup\cdots\\,$.

As for how to produce an automaton that accepts that, I suggest you think about it some more yourself, now that you know what it is you're trying to do. A hint would be to use nondeterminism to "guess" where the words $w\_2, \dots, w\_k$ begin.
> 0 votes

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


# Question
Title: Edge removal to convert a non-planar DAG to a planar DAG while maintaining reachability?
Is there an algorithm that removes edges to convert a non-planar DAG to a planar DAG while maintaining reachability? For example, the graph $G$ below is non-planar:

but, by removing certain edges to produce $G'$, it can be made planar but every vertex still has the same transitive closure (meaning vertex $t$ is reachable form vertex $s$ in $G'$ iff the same is true in $G$)

Is there an algorithm to do this for any general DAG (or return an error if it's not possible)?

My use case is that I'd like to use Thorup's algorithm for reachability, but it only works on planar graphs.

# Answer
> 3 votes
Yes, there's a nice algorithm for this. Compute the transitive reduction, then check whether the result is planar.

Why does this work? The transitive reduction is the graph with the smallest number of edges, that has the same reachability relationships as the original graph. It is also unique. Moreover, any other graph with the same reachability relationships must include all the edges in the transitive reduction (plus possibly some others). Thus, if the transitive reduction isn't planar, no other graph with the same reachability relationship will be planar (as adding more edges to a non-planar graph can never make it planar).

---
Tags: graphs, planar-graphs
---


# Question
Title: Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree
I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this?

I know that a full node has 2 children.

# Answer
Well, an induction proof consists of a base case and an induction step. For trees that is usually *structural induction*, based on inductive ways trees are built.

The *base case* considers the smallest binary tree, which cannot be composed further. Show that one has the Property.

The *induction step* argues that the Property is true for any tree $T$ assuming the Property holds for its subtrees $T\_{\textrm{left}}$ and $T\_{\textrm{right}}$. That assumption is called the *induction hypothesis*.

There is another approach, induction based on the number of (full) nodes, called *natural induction*. Base case has a single full node. Induction step argues Property is true assuming Property holds for any tree having less full nodes.
> 4 votes

---
Tags: proof-techniques, trees, binary-trees, induction
---


title: Partially diagonalizing a matrix

text:
# Question
Title: Partially diagonalizing a matrix
Suppose I have an $n\times n$ matrix. I would like to keep an $m\times m$ subblock undiagonized, while keeping the rest diagonized. Is there any algorithm for this?

More precisely, I mean using unitary matrix $U$ to realize

$$ U^\* \pmatrix{ A & B \\ C & D } U = \pmatrix{A' & 0 \\ 0 & D' } $$ where submatrix $A'$ is diagonal, and $D' \approx D$.

# Answer
> 3 votes
In general $U$ will only be unitary if your composed matrix is hermitian. I will answer the more general problem that the matrix is partially diagonalizable: $$U^{-1} \begin{pmatrix}A & B \\ C & D\end{pmatrix} U = \begin{pmatrix}A' & 0 \\ 0 & D'\end{pmatrix}.$$ The diagonal matrix $A'$ contains the eigenvalues on its diagonal. You must already know them and their corresponding left and right eigenvectors. Now let $U\_\text{eig}$ consist of the right eigenvectors and $V\_\text{eig}$ consist of the left eigenvectors as columns. Then choose $$U=(U\_\text{eig}|V\_\text{eig}^\perp)$$ where $\perp$ denotes an orthogonal complement (a basis of the null space).

Proof: Say, you have a matrix $U$ represented by $(U\_\text{eig}|U\_\text{rem})$ that partially diagonalizes your matrix. Then split its inverse like so: $V = (V\_\text{eig}|V\_\text{rem})$ with $U^{-1} = V^T$. We know that $V\_\text{eig}$ contains left eigenvectors as columns. It holds $$I = U^{-1}·U = V^T·U = (V\_\text{eig}|V\_\text{rem})^T · (U\_\text{eig}|U\_\text{rem}).$$ Separated: $$ \begin{array}{cc} I = V\_\text{eig}^T · U\_\text{eig} & 0 = V\_\text{eig}^T · U\_\text{rem} \\ 0 = V\_\text{rem}^T · U\_\text{eig} & I = V\_\text{rem}^T · U\_\text{rem} \end{array} $$ The equation $0 = V\_\text{eig}^T · U\_\text{rem}$ means that $U\_\text{rem}$ is an orthogonal complement to $V\_\text{eig}^T$. You may not know the precise content of $V\_\text{eig}$, but orthogonality to $U\_\text{rem}$ is invariant under change of the basis or re-ordering of columns. Thus for your computation you can choose any left eigenbasis for your selected eigenvalues.

---
Tags: linear-algebra
---


# Question
Title: prove every language got a language that is harder
I am prety stuck over here:

> prove or disprove that every $L$ got $L'$ s.t $L'\geq L$ and for every $L''\geq L$
>
> $L''\ngeq L'$
>
> basically it means L' is the hardest...

my intuition tells me that this is correct, but I cant prove why. I tried to prove using counting but got stuck:

1. we got $\aleph\_0$ pairs of functions that we can use in the reduction for both ways
2. we got $\aleph$ languages so there must be a language that got a function to compute the redaction in one way and doesnt got a function for the reduction to the other way

Its feels terribly incorrect any help will be appreciated

EDIT: I just realized that I didn't write the question correctly please read it again.

# Answer
> 2 votes
The halting problem for a class of machines that can decide $L$ is always harder than $L$. You already know this when $L$ is computable and the proof of the more general result is essentially the same. For every $L$, you need to think of a class of machines that can decide $L$.

---
Tags: computability, reductions, undecidability
---


# Question
Title: NFA string acceptance with loop of epsilon transitions
I am writing an algorithm to test whether a NFA accepts or not a string, and there is a case in which I don't know how the algorithm should behave namely:

How should the algorithm behave? Should it stop and understand that no string is accepted or should it run for infinite time?

# Answer
An algorithm for testing whether an NFA accepts a string has the following specification:

* Input: NFA $A$ and word $w$
* Output: Yes if $A$ accepts $w$, No if $A$ doesn't accept $w$

In particular, the algorithm must always terminate. What algorithm you use is up to you.

---

One way to overcome the problem of $\epsilon$-loops is to compute, for each prefix of $w$, the set of states that the NFA can reach. To this end, for every state $q$ we define $N\_\epsilon(q)$ as the set of states reachable from $q$ via (possibly zero) $\epsilon$-transitions. You can compute $N\_\epsilon(q)$ using a graph traversal algorithm such as BFS/DFS.

Given a word $w = \sigma\_1\ldots \sigma\_n$, we define the set of states $R\_i$ reachable after reading the first $i$ letters as follows:

* $R\_0 = N\_\epsilon(q\_0)$.
* For $i = 1,\ldots,n$, $R\_i$ is the union of $N\_\epsilon(q')$ for all $q' \in \delta(q,\sigma\_i)$ and all $q \in R\_{i-1}$.

The NFA accepts $w$ iff $R\_n \cap F \neq \emptyset$, that is, if $R\_n$ contains an accepting state.

---

In your example, $N\_\epsilon(1) = N\_\epsilon(2) = \\{1,2\\}$. The fact that the graph induced by the $\epsilon$-transitions contains directed cycles is not problematic at all for this approach, since we only care about which states are reachable from which.
> 1 votes

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


# Question
Title: Given that f(n)>0 and constant c>0 Prove that f(n)+c = O(f(n)) or provide a counter-example if it's false
**Question:**

Given that f(n)\>0 and c\>0

Prove that f(n)+c = O(f(n)) or provide a counter-example if it's false.

**My Effort to solve:** \begin{eqnarray\*} f(n) + c \space \leq \space d\cdot&f(n)\space for \space all\space n \geq n\_0\space and \space d\>0\\ \end{eqnarray\*} So i believe there can be found some large d that satisfies this equation, but i am not sure about it.

# Answer
> 2 votes
This is false. A counterexample is $f(n)=1/n$ and $c=1$.

If $f(n)+c=O(f(n))$, then there exists $n\_0\>0$ and $d\>0$, for any $n\>n\_0$, $f(n)+c\le df(n)$, or $1/n+1\le d/n$. But let $n=\max\\{n\_0+1,d\\}$, the inequality fails obviously, a contradiction.

In fact, any $f(n)$ and $c$ such that $f(n)\to 0$ ($n\to\infty$) and $c\>0$ are sufficient.

---
Tags: asymptotics
---


# Question
Title: Are the No Free Lunch theorems useful for anything?
I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here, because I have not found a good discussion of it anywhere else.

The NFL theorems are very interesting theoretical results which do not hold in most practical circumstances, because a key assumption of the NFL theorems is rather strong. This assumption is, roughly speaking, that the performance of an algorithm is averaged over all problem instances drawn from a uniform probability distribution. In realistic applications the problems an algorithm typically encounters are NOT drawn from a uniform distribution, and are instead drawn from what is likely a very interesting and complicated distribution specific to the general problem setting.

So, while the NFL theorems are quite interesting results, do they have any practical implications? Or are they merely theoretical results?

**EDIT**: By practical implications, I mean novel or improvements over existing algorithms, improved hyper-parameter selection, and things of that nature. I would even be interested to learn of NFL-inspired theorems that do apply to realistic search/optimization/learning problems.

# Answer
> 4 votes
A practical implication is that there is no silver bullet: we shouldn't expect any single optimization method to be perfect for all problems. Rather, we should try to design optimization methods that are tailored to the problem we're trying to solve.

For instance, if you want to use local search, you'll probably need to define a neighborhood relation (a set of moves that makes "small" changes to the current solution) that is informed by the problem domain. See, e.g., https://cs.stackexchange.com/a/88016/755 for a recent example of this here on this site.

A practical implication is that machine learning won't work if there is no structure at all on the space of possible models/hypotheses. Instead, we need some kind of prior that makes some models more likely than others.

Often, we assume a prior that assume "simpler" models are more likely than complex one's (Occam's razor: all else being equal, the simpler explanation is more likely to be true). This leads to use of regularization in machine learning, as it effectively applies Occam's razor to candidate models. So, you can think of the NFL theorems as providing some kind of theoretical justification for regularization or theoretical understanding that helps us see what the role of regularization is and provides some partial explanation for the empirical observation that it seems to often be effective.

You could characterize these as "NFL theorems tell us some directions that won't work", which arguably has value as it helps us avoid wasting time on something that won't work and helps point us towards directions that are more likely to work.

---
Tags: optimization, machine-learning, search-algorithms
---


# Question
Title: Shift Organization algorithms (Constraint Programming + Marriage problem)
I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition:

Daily shifts must be covered by workers, who are divided in three groups:

* Trainees (Nt = 2)
* Regulars (Nr = 3)
* Experts (Ne = 7)

The organization constraints are:

* All shifts must be covered
* A Trainee must always cover a shift with an Expert
* Workers covering Friday must also cover Sunday
* Nobody can cover two shifts in a row
* Nobody works more than M shifts every D days

The process should maximize the following output:

* Workers get shifts assigned based on their preference
* Experts work as less as possible, only covering unassigned gaps
* Number of shifts are evenly distributed

My initial idea is to write a branch and bound algorithm to generate all possible combinations allowed by the constraints. I would then score each solution for each worker based on their preferences, and run a marriage algorithm to get the best combination.

The main problem is that the number of combinations is too (damn) high. Without constraints, there would be 6\**30 (~1e24) possible arrangements. I know most of these will be bound, but currently I'm generating at a pace of ~1e8/minute.

I'm wondering if there are any heuristics I could apply to improve the process. Any ideas here? How does this whole thing sound?

Thanks!

---

Sample code to generate combinations:

```
def get_combinations(population, base, spots):
    if len(base) == spots:
        yield base
        return

    for candidate in population:
        combo = base + (candidate, )

        if is_viable(combo, population, spots):
            yield from get_combinations(population, combo, spots)

population = {'t1', 't2', 'n1', 'n2', 'n3'}
get_combinations(population, tuple(), 30)

```

# Answer
> 1 votes
Turns out this problem is pretty hard to solve and is still under active research. This paper (2004) describes the state of the art.

---
Tags: algorithms, optimization, combinatorics, constraint-programming, branch-and-bound
---


title: Lower bounds on regret

text:
# Question
Title: Lower bounds on regret
In "regret" styled analysis over $T$ steps of an iterative algorithm $\\{x\_i \in F \\}\_{i=1}^T$ (where $F$ is some feasible set) being given the sequence of loss functions $\\{ f\_i\\}\_{i=1}^T$ one defines the regret $R\_T = \sum\_{i=1}^Tf\_t(x\_i) - \min\_{x \in F} \sum\_{i=1}^T f\_t(x)$ Most typical analyses assume that the $f$s are convex.

Is this notion of "regret" lower bounded? Or under what conditions is it lower bounded?

I guess "minimizing the regret" does not make sense because one can always have an "Oracle" access to the sequence of points $x^\*\_i$ such that $x^\*\_i = \min\_{x \in F} f\_i(x)$. Then for this sequence for $x^\*$ points the regret is only at most $0$.

# Answer
> 1 votes
There are many different models in which regret minimization makes sense. One particular model is Gaussian density estimation. Takimoto and Warmuth, in their paper The minimax strategy for Gaussian density estimation, give a tight analysis which includes both an upper bound achieved by a particular algorithm and an almost matching lower bound proved using the adversary method. There are probably many more such analyses out there.

---
Tags: optimization, online-algorithms
---


# Question
Title: Algorithm - Checking if an unconnected graph is cyclical
I have an algorithm for finding if there is a cycle in a connected graph by depth first path creation of a graph until there is a duplicate in the path. Beside simply starting this algorithm at all possible points for an unconnected graph, how can I find if an unconnected graph is cyclical in good time and in a simple way?

# Answer
As part of the cycle checking, you already need to keep track of which vertices have been visited. So just restart at the first unvisited vertex each time you exhaust a component.
> 1 votes

# Answer
Another option is to count the number of connected components using some graph traversal algorithm such as DFS or BFS, and compare it to the number of vertices and edges. If a graph has $n$ vertices, $m$ edges, and $c$ connected components, then it is acyclic iff $m = n - c$.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Why does the negative reward function in LQR encourage convergence to the origin?
I was reading Stanford's CS 229 materials on **Linear Quadratic Regulation** (LQR) (Lecture note 13, YouTube Lecture 18, around minute 36), and it mentions that:

> \[...\] the quadratic formulation of the reward is equivalent to saying that we want our state to be close to the origin. For example, if $U\_t = I\_n $(the identity matrix) and $W\_t = I\_d$, then $R\_t = -\Vert(s\_t)\Vert^2-\Vert(a\_t)\Vert^2$, meaning that we want to take smooth actions (small norm of $a\_t$) to go back to the origin (small norm of $s\_t$).

Why is that? Why the norm of the origin is smaller? $s\_t$ for any time point are just a vector of n dimension which can take any value, right?

# Answer
Minimizing $s^TUs=s^Ts=\\|s\\|^2$ minimizes the distance from the origin, because the norm of a vector is its Euclidean distance from the origin:

$$\\|s\\|= \sqrt{s\_1^2+s\_2^2+\dots+s\_n^2} = \sqrt{(s\_1-0)^2+(s\_2-0)^2+\dots+(s\_n-0)^2}$$
> 0 votes

---
Tags: optimization, machine-learning, dynamic-programming
---


# Question
Title: Machine Learning and Neural Networks for High School Students
I hope this question is appropriate for this forum.

In this summer I am giving a 3-day workshop on machine learning and neural networks for advanced and very enthusiastic high school students which all know at least one programming language.

Typically a day consists of 2 hours lecture in the morning and later the students should solve a given problem (with help, of course).

For the first day we are going to sove a simple pixel counting problem in a picture (Or do you know any simpler interesting example)

For the second and third day I wanted to give them a more challenging problem: Consider the set of binary $3\times 3$ matrices. One can imagine every matrix as a chessboard like picture where every $1$ corresponds to a black field and every $0$ to a white field. The objective is to count the connected components.

I allready produced the matrices and computed a neural network. It seems to work (training set 50%), however I am not an expert in machine learning so my solution is most likely not good!

**So my questions are:**

> Has anybody allready computed a neural network for the problem above and is willing to share his data?
>
> Do you know similiar problems accessible for high school students which are better suited for this occasion?

# Answer
For high school kids, I think the most important goal is to make sure they're impressed by what they've accomplished. To do that the task needs to be inherently useful. Classic things like the XOR problem or pixel counting aren't going to do the trick, because you're relying on the students to connect the dots and realize that this means you can build it into something cool. You need them to build a system

* that does something cool,
* which can't easily be accomplished with a handbuilt algorithm,
* that seems to behave intelligently.

A few ideas:

* Make an environment where agents play a game. Something like tic-tac-toe or rock-paper-scissors is probably best. At the end of the course, you can let the agents that the students have made battle each other in a tournament.
* Create a simple a-life environment with 2D creatures with simple sensors and joints. Let students create the neural network for the creatures, so they learn to walk. You can also let them evolve the network topology when creatures mate.
* A car driver. Again, this is best with an artificial environment, but you can probably get a dataset somewhere too. This is an example from Tom Mitchell's machine learning where they did this with an actual car and a human driver for the network to learn from.
> 7 votes

# Answer
For the second question, I think it is interesting to do some work on face recognition from Tom Mitchell's *Machine Learning*. (There are available code framework and image data for downloading)

The dataset is small and you don't need to do much code work except parameter tuning. You can even train variant networks for expression, pose, user and eyes classification. I tried to classify users with this framework and it produced a very accuracy result. So you can have a try!
> 5 votes

# Answer
NNs are fairly complicated to understand. Your class might be better off starting with a simpler ML algorithm, like a Monte Carlo simulation of a genetic algorithm. Virtually any optimization problem is suitable for a genetic algorithm. Genetic algorithms work by combining a large set of possible solutions in random ways to find good solutions, so there's no math or feedback functions, very easy to understand what it's doing and how it works.

An example problem might be training a tic-tac-toe playing AI. In that case, the genome would represent the tic-tac-toe board and the desired move. "Players" compete directly against each other in successive generations. Losers don't get to breed. Winners breed the next generation of players.

It should be relatively easy to get convergence and demonstrate that generation 0 is terrible while generation 1 million is nearly optimal.
> 5 votes

# Answer
here is one classic ML question that is easy to understand and interpret, the so-called "two spiral separation" problem and lends itself to many different approaches eg NNs as one of the early approaches. two separate intertwined spirals are given in 2d and the classification task is: given an (x, y) pair, determine which spiral it belongs to. this paper can serve as a moderately recent survey.
> 3 votes

# Answer
How about teaching them how to create a Neural Network model for computer viruses. Find sample computer viruses of a particular file type (pdf, exe, etc.), as well as benign uninfected files of the file type. Train the models, and now you can determine with some level of confidence if a file is infected with a computer virus or not.
> 3 votes

# Answer
Being a high school student, I had the exact same problem at one point in time - however, through guidance from older peers, I managed to gain a solid understanding.

To rectify this issue, I decided to compile a learning path for high school students: kjaisingh/high-school-guide-to-machine-learning

Do let me know if you have any questions or suggestions to this, and best of luck!
> 1 votes

---
Tags: machine-learning, neural-networks, education
---


# Question
Title: Find the best set of triples of objects, using each object at max one time
I stumbled upon an interesting problem and I'm stuck with it, since I can't find parallels to other problems or algorithms to solve it.

We have a set of objects $O = \\{a,b,c,...,z\\}$, objects can make triples, e.g. $T=(a,b,c)$ $a,b,c \in O$ and we have a set of triples $X = \\{T\_1, ... T\_n\\}$. Each triple is assigned a value $c: X \rightarrow \mathbb{R}$

* not every object has to be in a triple
* an object can be in multiple triples
* there can be triples using the same objects, but in a different order e.g. $(a,b,c),(c,a,b)$

Goal: Find the subset of triples $S \subseteq X$, where $\forall x \in \bigcup S: \exists y \in \bigcup S =\> y =x$ (Every object may appear at most once in the selection) with maximum $\sum\_{T \in S} c(T)$ (maximum value of selection).

Is there a fast way to get the maximum? If not, is there any fast strategy that may produce a good result?

A simple greedy strategy would be to sort the triples descending by value and take a triple into the subset if all of it's objects are unused. This can be done in $O(n \log n)$, but does not produce the optimal result.

# Answer
Your problem is NP-hard. In particular, 3-dimensional matching is a special case of your problem, and 3-dimensional matching is NP-hard -- so your problem is, too.
> 1 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Inserting values at maximal distance from current value
I have the following problem. Given an array A, filled with 0s, we should set some elements to be equal 1, considering such rules:

1. If all elements equal 0,set A\[0\] to 1
2. Next 1 should be set at maximal distance from any other 1s. At this stage it will be A\[size-1\].
3. In case of equal distances, set 1 at the element with equal distance AND with smaller index.
4. At any point of time, any 1 could be set back to 0 at random

Consider an example:

1. 0000000 // initial
2. 1000000 // just first
3. 1000001 // second
4. 1001001
5. 1101001 // all given opportunities have distance 0 to any other 1, so pick up the smallest index
6. 1111001 // again the smallest index
7. 1110001 // we replaced a random 1 with 0
8. 1110101 // at this step we have location with distance 1, so use it!

Input: a sequence of additions/removals of 1s.

Expected output: a sequence of accessed indices at each step.

My question is: how to compute index for a next request? Removals are trivial and it's not interesting (there is some bookkeeping, which is out of the problem's scope), but what about additions? I don't think that you can use dynamic programming or other approaches to compute next index from scratch because of *randomized* removals.

My idea is to maintain something similar to an interval tree, where each node correspond to 1, left subtree correspond to an interval to the left side, right subtree to right, but it lacks some important details.

Are there any already known approaches/algorithms to this problem? Or how should I proceed with my interval tree idea?

# Answer
Use an interval tree to store a set of intervals, where you have one interval for each chunk of contiguous 0's. Now to figure out where to put the next 1, you need to find the longest interval in the interval tree. You can keep track of the longest interval in the interval tree by augmenting the data structure: store in each node the length of the longest interval under that node. Each operation can be done in $O(\log n)$ time.
> 2 votes

---
Tags: data-structures, dynamic-programming, binary-trees
---


title: Finding weakest precondition

text:
# Question
Title: Finding weakest precondition
I have the following program

```
x := y + 1;
if (y > 0) then
x := x + y
else x := y + 100;
x := x + y;

```

I want to compute the weakest precondition for getting `{x = y}` by executing this program.

The solution of this problem is the following

```
{(y > 0 & y + 1 + y = 0) | (y = -100)} = {( y > 0 & y = -0.5 | y = -100} = {false | y = -100}
x := y + 1;
{(y > 0 & x + y = 0) | (y =< 0 & y=-100)} = {(y > 0 & x + y = 0) | (y = -100)}
if (y > 0) then
{x + y = 0}
x := x + y
{x=0}
{y + 200 = 0} = {y = -100}
else x := y + 100;
{x=0}
{x+y = y} = {x=0}
x := x + y;
{x=y}

```

Can anyone explain this solution with a breakdown for each line?

# Answer
> 4 votes
Weakest precondition (WPC) can be computed with a procedure that takes your program, as well as the given postcondition (in this case, `x=y`), as inputs, and applies certain rules on how the precondition is computed for each part of the program (e.g. how to compute WPC for an if statement), until it reaches the point of computing the precondition for the whole program. Now, since the program you've given is a sequence of statements, this procedure will compute WPC for each of these statements and effectively start with computing WPC for the last statement and "propagate" WPC back to the first statement in the sequence.

In order to understand computation of WPC, it's good to be aware of some relevant notions like the semantics of the programming language your program is given in, i.e. what each statement means, (for your example the semantics is quite straitghforward), the way the WPC is computed according to rules that depend on the given part of the program and its semantics, and then specific rules on how WPC is computed for the given language. (Some links to useful materials are given at the end.)

Specifically for your program, which we will label for more convenient notation of `P[x..y]`, which designates the program part consisting of lines from `x` to `y`

```
1. x := y + 1;
2. if (y > 0) then
3. x := x + y
4. else x := y + 100;
5. x := x + y;

```

the procedure for computing WPC would be given as

```
wpc(P, x==y) === wpc(P[1..5], x==y) === wpc(P[1], wpc(P[2..5], x==y))

```

where we use `===` for equivalence on the top-level (not be confused with assignments `=` and equality `==` in the language), and in turn

```
wpc(P[2..5], x==y) === wpc(P[2..4], wpc(P[5], x==y))

```

as `P[2..4]` represents the if statement. Now,

```
wpc(P[5], x==y) === wpc(x := x + y, x==y) === x + y == y === x = 0

```

given the rule for handling assignments, `wp(x:=E,R) = R[x ← E]`, which says that, intuitively, in order for some condition to hold after the assignment of `x` is executed, same condition should hold before that assignment, where instead of `x` we have the right-hand side of the assignment, since that will exactly be the value of `x` after assignment is done.

The next step is computing `wpc(P[2..4], wpc(P[5], x==y))`, i.e. `wpc(P[2..4], x=0)`, since based on the WPC computation we discussed above, `wpc(P[5], x==y) === x==0`.

Now, there is again one statement (the if-condition) and one postcondition. (Note that you've written this postcondition two times, once for each branch of the if statement). Without going into all the details, the WPC computation would follow the rule for conditionals, i.e. `wp( E S_1 S_2 ,R) = (E ∧ wp(S_1,R)) ∨ (¬E ∧ wp(S_2,R))`, which guarantees the postcondition is satisfied if either branch is taken, thus the WPC becomes a logical OR between WPCs for each branch computed separately, i.e.

```
wpc(P[2..4], x==0) === (y > 0) & wpc(x := x + y, x==0) | !(y>0) & wpc(x := y + 100, x==0)

```

which is the same as the condition you wrote

```
(y > 0 & x + y = 0) | (y =< 0 & y=-100) === (y > 0 & x + y = 0) | (y = -100)

```

where WPCs for both branches are computed similarly as given before, as both of them represent assignments.

There are many good resources that cover program semantics and generation of verification conditions (including the computation of weakest precondition): some of them are mentioned on Wikipedia, while some courses like the "Program Analysis" course provide good views on the material and might represent a good step to start.

---
Tags: logic, hoare-logic, software-verification
---


# Question
Title: Efficiently compute parallel matrix-vector product for block vectors with FFTs?
Assume I have $P$ processors, each having a different vector $v\_p$ of size $N$, $p=1, ..., P$. I learned in this question/answer that for computing the matrix-vector product $$w = (E\otimes I\_N)v$$ in parallel, where $\otimes$ is the Kronecker product, $v = (v\_1, ..., v\_P)^T$ is the stacked vector consisting of all local vectors $v\_p$, $E = (e\_{pj})\_{p,j}\in\mathbb{C}^{P\times P}$ some dense matrix and $I\_N$ is the identity matrix of size $N\times N$, I can basically do $P$ parallel sums using binary trees.

$N$ is pretty large (say, $10^8$), in particular much larger than $P$ (which is only 10-100) and so large that $NP$ (the size of $w$ and/or all vectors $v\_p$ together) does not fit into each processor's memory.

Depending on the application, the matrix $E$ could be a Fourier or DFT matrix, i.e. computing $$w\_p = \sum\_{j=1}^P e\_{pj} v\_j$$ should be possible using an FFT. For each of the components of the vector $v\_j\in\mathbb{R}^N$, the FFT would not change. Do I still have to do $N$ FFTs or is there a "block-wise" FFT idea/implementation?

# Answer
Let's look at the case where $P=2$, for starters. The FFT can be computed in a divide-and-conquer fashion, where first we compute the FFT of the even-numbered indices, then the FFT of the odd-numbered indices, and then combine them in a simple step (with a single layer of butterfly operations).

So, if the even-numbered indices are stored on one processor and the odd-numbered indices are stored on a second processor, then you could do this in parallel in a natural way, with the first processor doing the FFT on its own data, and the second processor doing the FFT on its own data; the final butterfly step requires only $\Theta(NP)$ data sent over the network.

If the data isn't partitioned that way, then the first step could be to send all the values at even-numbered indices to the first processor and the values at odd-numbered indices to the second processor, then do the above process. In total it will require $\Theta(NP)$ data sent over the network and $\Theta(N \lg N)$ computation ($\Theta(N \lg N)$ computation at each processor to compute the FFT locally).

More generally, if $P$ is a power of 2, you can generalize these ideas in a similar fashion. You send the data to the appropriate processor ($\Theta(NP)$ data sent over the network), then compute the FFT locally at each processor ($\Theta(N \lg N)$ steps of computation at each processor), then combine them with $\lg P$ butterfly layers (requires $\Theta(NP \lg P)$ data sent over the network).

If $P$ isn't a power of two, you can pick the largest power of two that is smaller than $P$, and use that many processor (the remainder are left idle).
> 0 votes

---
Tags: algorithms, parallel-computing, matrices, numerical-algorithms, fourier-transform
---


# Question
Title: Finding (and possibly extracting) source code in heterogenous text data set
I'm looking for a way to recognize and possibly extract source code from text files that may contain only source code, source code mixed with plain text or just plain text without any source code.

There's different source code contained in the data set, just to name a few examples: Java, C, Python, Bash, PHP, Javascript, ...

An example of a mixed file would look something like this:

```
Title
=====

Introduction
------------
dolor sit amet, consetetur sadipscing elitr, sed diam
nonumy eirmod tempor invidunt ut...

Description
-----------
Labore et dolore magna aliquyam erat, sed diam voluptua:

    [.c snippet]

At vero eos et accusam et justo duo dolores et ea rebum.

Proof of Concept
----------------
Stet clita kasd gubergren, no sea takimata sanctus est
Lorem ipsum dolor sit amet.

-- sourcefile.c --

[Full .c source file]

```

The above is only an example and while there might be some files with similar layout, most of them differ quite a bit.

Only looking for one specific language would be preferred, but not required.

My first naive approach when looking for Java source code was to run a simple keyword search using Java keywords, but the results weren't that great. Most java keywords are neither unique to java nor sparingly used in plain text, so what turned up as top results was mostly C files, and of course, this doesn't tackle extraction at all.

I recognize that this is a difficult problem, and I've had no success googling for this topic. The most interesting thing I've found was this paper titled *Extracting Code Segments and Their Descriptions from Research Articles*, but it's not quite relevant since it's much more focused on the *Descriptions* part than it is on the *Code Segments* part.

Is there some kind of algorithm or existing program or library that solves this or a similar problem? Or maybe some kind of neural network flavor?

# Answer
> 2 votes
There are many possible ways you might do this. I'll suggest one.

I suggest you train a classifier to recognize whether a sequence of characters is code or text. Here, the goal is to build a boolean classifier that either outputs "text" or "code". You'll train it only on documents that are entirely text or entirely code (no mixed documents). Build a classifier that not only outputs a classification, but also a confidence (a likelihood value for the chosen classification).

Now, to apply it to mixed documents, run the classifier on all substrings. If a substring $S$ is classified as "code" with high confidence (high likelihood), above some threshold, and there's no superstring $S'$ of $S$ (of length not too much longer than $S$'s length) that is also classified as "code", then output $S$ as one of the code elements from the mixed document. You'll need to select a threshold with a little bit of experimentation.

I suspect this might work nicely. You'll have to try it to see, though.

So, how do you build such a boolean classifier? One simple approach would be to use a simple linear classifier (e.g., SVM or naive Bayes) with features based on bag-of-words on lexical tokens. That alone might suffice (e.g., code tends to have many instances of tokens like "{" and "return", but text doesn't). You could also try bag-of-words on individual characters. If you want to build a more sophisticated classifier, you could train a character-level recurrent neural network (e.g., a LSTM or a CNN); this might achieve higher accuracy, given a large enough training set, but probably will also require a bit more technical knowledge.

---
Tags: data-mining, pattern-recognition
---


title: DFA Infiniteness Testing

text:
# Question
Title: DFA Infiniteness Testing
Why is it that the test for an infinite language on the DFA $M$ has an upper bound of $2n$?

That is to say, when testing for a string of length $k$, why does the theorem say:

$$n \leq k \< 2n$$

I understand the lower bound of $n$ IAW the Pumping Lemma of $|w| \geq n$. I'm just not sure why $2n$ was chosen and I think I'm over complicating it.

# Answer
The upper bound comes also from the proof of the pumping lemma. If you have a DFA with $n$ states, you know that if it accepts a word in length $\ge n$ then the word passes through a circle in the states, thus you can repeat the circle as many times as you like and get an infinite language.

Now, for the upper bound, assume the DFA is infinite, and accepts a word of length $\ge2n$. Now, when you run the word on the DFA, and since the DFA has only $n$ states, there must be a cycle. That cycle must be of length $\le n$. You can now remove a number iterations from that circle such that you will get a word $w$ of length $n\le |w| \< 2n$.

The proof is even easier when you use the pumping length $n$ derived from the pumping lemma. Just show that for a word $w=xyz$ where $|w|\ge 2n$, since $|xy|\le n$ and $|y|\>0$ there exists an $i\in \mathbb{N}$ such that $n\le |xy^iz| \< 2n$.
> 2 votes

# Answer
Let me start with a statement and proof of the theorem.

> **Theorem I.** Suppose that $L$ is a regular language accepted by a DFA with $n$ states. Then $L$ is infinite if and only if $L$ contains a word whose length is between $n$ and $2n-1$.
>
> **Proof.** Let the DFA have states $Q$, accepting states $F$, transition function $\delta$, and initial state $q\_0$.
>
> Suppose first that $L$ is an infinite regular language. Since $L$ is infinite, it contains a word whose length is at least $n$. Let $w = w\_1 \ldots w\_N$ be such a word of minimum length. Let $\alpha\_i$ denote the state of the DFA after reading the first $i$ letters of $w$. Since the DFA only has $n$ states, the sequence $\alpha\_0,\ldots,\alpha\_n$ must have duplicates, say $\alpha\_i = \alpha\_j$, where $i \< j$. As in the proof of the pumping lemma, this implies that the word $z = w\_1 \ldots w\_i w\_{j+1} \ldots w\_N$ also belongs to $L$. By the definition of $w$, we must have $|z| \< n$. Since $|w| = |z| + j-i$ and $j-i \leq n$, it follows that $|w| \< 2n$. By definition, $|w| \geq n$, and so $w \in L$ is a word whose length is between $n$ and $2n-1$.
>
> The other direction follows directly from the pumping lemma. $\quad\square$

Note that in order for $L$ to be infinite, it suffices that it contains a word of length at least $n$. That is, for this direction we don't need the additional condition that the word has length less than $2n$. This shows that the following theorem also holds:

> **Theorem II.** Suppose that $L$ is a regular language accepted by a DFA with $n$ states. Then $L$ is infinite if and only if $L$ contains a word whose length is at least $n$.

Indeed, the proof of Theorem II is much easier, since any infinite language contains a word of length at least $n$, for any $n$. However, Theorem I is stronger, since the criterion it suggests can be checked algorithmically, since there are only finitely many words whose length is between $n$ and $2n-1$ (though there are much more efficient ways to determine whether the language accepted by a DFA is infinite).

We can combine both theorems to obtain a theorem superseding both (that is, stronger than both):

> **Theorem III.** Suppose that $L$ is a regular language accepted by a DFA with $n$ states.
>
> 1. If $L$ is infinite then it contains a word whose length is between $n$ and $2n-1$.
> 2. If $L$ contains a word whose length is at least $n$, then it is infinite.

However, this is not a characterization, that is, it doesn't state an "if and only if" criterion for infinitude.

---

Let us now consider the question of optimality of Theorem III. You mentioned that you are happy with the lower bound of $n$, but in fact this lower bound can be improved, depending on the exact definition of DFA. If you allow the transition function $\delta$ to be partial, then the lower bound is indeed tight:

> **Lemma 1.** For every $n \geq 1$ there exists a DFA over $\Sigma = \\{a\\}$ with $n$ states whose language is finite but contains words of all lengths smaller than $n$.
>
> **Proof.** Let $Q = F = \\{q\_0,\ldots,q\_{n-1}\\}$, and define $\delta(q\_i,a) = q\_{i+1}$ for $i \< n$ (we leave $\delta(q\_n,a)$ undefined). Then $L = \\{\epsilon,a,\ldots,a^{n-1}\\}$. $\quad\square$

If you insist that $\delta$ be total (we call such a DFA *total*), you can improve the lower bound:

> **Lemma 2.** Suppose that $L$ is a regular language accepted by a total DFA with $n$ states. If $L$ contains a word of length at least $n-1$ then $L$ is infinite.
>
> **Proof.** If $L$ contains a word of length at least $n$ then this follows from Theorem II, so suppose that $w = w\_1 \ldots w\_{n-1}$ has length $n-1$. Let $\alpha\_i = \delta(q\_0, w\_1 \ldots w\_i)$. If $\alpha\_0,\ldots,\alpha\_{n-1}$ contains duplicates then $w$ can be pumped as in the proof of the pumping lemma, so $L$ is infinite. Otherwise, $\\{\alpha\_0,\ldots,\alpha\_{n-1}\\} = Q$. Let now $\sigma \in \Sigma$ be an arbitrary symbol. Then $\delta(\alpha\_{n-1},\sigma) = \alpha\_i$ for some $0 \leq i \leq n-1$. It follows that $w(\sigma w\_{i+1} \ldots w\_{n-1})^t \in L$ for all $t \geq 1$ (possibly $w\_{i+1} \ldots w\_{n-1} = \epsilon$), and so $L$ is infinite. $\quad\square$
>
> **Lemma 3.** For every $n \geq 1$ there exists a total DFA over $\Sigma = \\{a\\}$ with $n$ states whose language is finite but contains words of all lengths smaller than $n-1$.
>
> **Proof.** Let $Q = \\{q\_0,\ldots,q\_{n-1}\\}$, $F = \\{q\_0,\ldots,q\_{n-2}\\}$, and define $\delta(q\_i,a) = q\_{i+1}$ for $i \< n$ and $\delta(q\_{n-1},a) = q\_{n-1}$. Then $L = \\{\epsilon,a,\ldots,a^{n-2}\\}$. $\quad\square$

Lemma 2 shows that Theorems I–III can be improved for total DFAs, an improvement which we leave to the reader. Let us now turn our attention to the upper bound.

> **Lemma 4.** For every $n \geq 1$ and $m \in \\{n,\ldots,2n-1\\}$ there exists a total DFA with $n$ states whose language is infinite, contains a word of length $m$, and doesn't contain a word of any length in $\\{n,\ldots,2n-1\\} \setminus \\{m\\}$.
>
> **Proof.** Let $Q = \\{q\_0,\ldots,q\_{n-1}\\}$, $F = \\{q\_{m-n}\\}$, and define $\delta(q\_i,a) = q\_{i+1}$ for $i \< n$ and $\delta(q\_{n-1},a) = q\_0$. Then $L = \\{a^{m-n}, a^m, a^{m+n}, \ldots\\}$. $\quad\square$

This shows, in particular, that $2n-1$ cannot be replaced by a smaller number.

---

What more can be said?

> **Definition.** A set $S \subseteq \mathbb{N}$ is *$n$-total* if every infinite language accepted by a DFA having $n$ states contains a word whose length is in $S$. A set $S$ is *minimally $n$-total* if it is $n$-total and all of its proper subsets are not $n$-total.

As an example, $\\{n,\ldots\\}$ is $n$-total and $\\{n,\ldots,2n-1\\}$ is minimally $n$-total.

> **Open problem.** Characterize all minimally $n$-total sets.
> 1 votes

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


# Question
Title: Time complexity of expanding decimal to new base
There is already a post on this topic on stackoverflow.

Nevertheless, I am asking the question here again, primarily because I do not understand the answer given there, and also because I have some takes on the problem I would like to supplement with.

To reiterate, we have a problem in CLRS which goes like this:

> Show how to sort $n$ integers in the range $0$ to $n^3-1$ in $O(n)$ time.

There seems to be a consensus that we first convert the numbers into base $n$, which ensures that each number is made up of at most 3 digits. Then we can use radix sort to sort the number in $\Theta(3(n+n)) = \Theta(n)$ (the parameter $k$ equals $n$ because we are in base $n$).

What I am concerned with is the cost of converting the $n$ numbers to and from base $n$. Converting back to decimals is $\Theta(1)$ obviously, so $n$ conversions equals $\Theta(n)$. But converting a decimal to another base takes $\Theta(\log n)$, so that the first $n$ conversions to base $n$ would take $\Theta(n\log n)$ time, and break the time complexity of $\Theta(n)$ of the algorithm overall.

I have read that you can view the expansion as a $O(1)$ operation under the RAM model though I do not understand why (probably because I do not understand the difference between the RAM and BIT models in connection to complexities). In the original post the answer given also tries to explain how if integer arithmetic is done in $O(1)$ time, then "... converting a number to base $n$ is basically most significant digit: `x/n`, least significant digit: `x%n`," which I really don't get any of.

# Answer
Let me start with a short introduction on computation models. A (C-like) computation model specifies the inventory of operations, and the cost of each operation. Two popular computation models are the *bit complexity* model and the *word RAM* model, though the latter doesn't really have a canonical description.

In the bit complexity model, all basic operations operate on bits (except for instructions like JUMP, which we ignore here for simplicity), and they all have constant cost. The exact cost of each operation, and the exact repertoire of operations, isn't important (as long as we have a complete set of operations!), since it only affects the running time by a constant factor.

In the word RAM, we associate with each input a parameter $n$ which is a "yardstick" for the input. For example, a function that accepts an array of length $n$ will use the input length as a parameter (but this only works if the array entries are "small" – more on that later). In the word RAM, all basic operations operate on *machine words*. What is a machine word? It is a value which is $C\log n$ bits long, for some constant $C$ depending on the algorithm (we will see that $C$ doesn't really matter shortly). Each operation on machine words takes time $O(1)$. The operations allowed are arithmetic operations (addition, subtraction, multiplication, division with remainder), comparisons, bitwise operations (NOT, AND, OR, XOR), and shifts. Since we can simulate an operation on words of width $C\log n$ bits using $O(1)$ operations on words of width $\log n$ bits (where the constant depends on $C$), the value of $C$ doesn't really matter.

Let us now come back to the definition of $n$. We usually assume that the input consists of $Cn$ machine words of length $\log n$ bits (for some constant $C$ depending on the algorithm), for a total input length of $Cn\log n$ bits. We obtain an equivalent definition by setting $n$ to be the input length in bits, essentially since $\log(Cn\log n) = \Theta(\log n)$.

(We have not touched on the *random access* aspect of the RAM model, and on the uniformity aspect of both models, since these are not relevant here.)

---

Now back to your question. Since your array consists of numbers of length $3\log n$ bits (so we are using $n$ as our yardstick for the word RAM model), we can assume that each of them fits into a single machine word. Packing and unpacking these numbers to base $n$ is very easy:

> **UNPACK**($m$):
>
> 1. $m\_0 = m \bmod n$.
> 2. $m\_1 = \lfloor m/n \rfloor \bmod n$.
> 3. $m\_2 = \lfloor m/n^2 \rfloor$.
> 4. **return** $m\_2,m\_1,m\_0$.
>
> **PACK**($m\_2,m\_1,m\_0$):
>
> 1. **return** $n^2 m\_2 + n m\_1 + m\_0$.

You can see that both operations use $O(1)$ operations, so take $O(1)$ time in the word RAM model. With some care, the implementation can be improved to use $O(d)$ operations for numbers up to $n^d$:

> **UNPACK**($m$):
>
> 1. $m\_0 = m \bmod{n}$, $m = \lfloor m/n \rfloor$.
> 2. $m\_1 = m \bmod{n}$, $m = \lfloor m/n \rfloor$.
> 3. $m\_2 = m \bmod{n}$.
> 4. **return** $m\_2,m\_1,m\_0$.
>
> **PACK**($m\_2,m\_1,m\_0$):
>
> 1. **return** $m\_0 + n(m\_1 + n (m\_2))$.
> 2 votes

# Answer
You pick the right base. If you have numbers in binary representation, and all the numbers are less than $2^{3k}$, then you choose base $2^k$. If you have numbers in decimal representation, and all the numbers are less than $10^{3k}$, then you choose base $10^k$. In both cases, the conversion is trivial.

Now if your n numbers are up to $n^3$, and take up to $3 \log n$ bits, then just the task of moving each item into its right place has to move at least $3n \log n$ bits if no item is in the right place. That factor $\log n$ is usually ignored - in practice, modern processors can move 256 bits in a single instruction, and $n = 2^{85}$ means you are not going to sort that array in your lifetime, so the exact time needed is irrelevant.
> 0 votes

---
Tags: computation-models, radix-sort, base-conversion
---


# Question
Title: Image registration algorithms for images with varying distances
I have two cameras side by side. I'd like to register two images taken from each camera. I think global transformation will not work for this issue since changes of distances between two images for the closer objects are significantly higher. What should I do in this case? I tried to read some papers but I am not sure which one is the perfect match for me. Do you have any suggestions such as "read this paper", "apply this algorithm", "know this and that" etc.

edit: I forgot to say that the project is real-time. Image registration will be implemented in the GPU.

# Answer
Since you need to implement image registration for real-time your should have fast registration algorithm, such as differential total variation (DTV) or binary gradient angle descriptor. However, these methods implement for challenge dataset or multimodal in consideration of your images are mono-modal meanwhile these methods should work perfectly in your case.

Your algorithm should include these steps:

1. Image descriptor to extract the images features.
2. Feature selection: find the most similar features (this step is important to remove outliers which is common)
3. Minimise the distance between the related image features to get the optimal transformation.
4. Apply image transformation on the floating image.
> 1 votes

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


# Question
Title: Encoding a list of numbers using gamma coding
I'm trying to work out how to find the gamma $\gamma -code$ that encodes the postings list (12, 18, 21, 22).

Is the postings list encoded just by a list of the individual $\gamma$-codes for each integer? E.g. for 12 the gamma code is: 0001100, and so the first entry in the $\gamma$-code for the pointing list is just 0001100. Or is there another representation - am I thinking along the right lines?

Thanks in advance for any help!

# Answer
> 2 votes
I'm assuming that you're referring to the Elias gamma code. This code is a *prefix code*, also known as a *self-terminating code*. This means that you can encode a sequence of numbers by simply concatenating the encodings of the individual numbers. Since the code is self-terminating, the concatenated encoding can be decoded into the encodings of the individual numbers.

A prefix code is a code in which no codeword is a prefix of another codeword. This allows you to decode the list as follows. Read bits until you reach a prefix of the encoding which constitutes a codeword. This encodes the first number. Remove and repeat.

Finally, let me stress that the Elias gamma code is a way of encoding numbers using a string of *bits*. When you write 0001100, you should think of it as a string of 7 bits. Eventually these bits will be decomposed into 8-bit chunks (knows as *bytes*) and stored or communicated in this way – as a string of bytes.

---
Tags: information-retrieval
---


# Question
Title: Find number of swap required to club all greater than $k$?
> Given an array of $N$ numbers and a number $K$, Find the minimum number of swaps required to bring all the numbers greater than or equal to $K$ together. Swap here means, swapping value of $array\[i\]$ and $array\[j\]$, where $1 ≤ i , j ≤ N$.

We are also given that:

* $1≤N≤10^5$
* $1≤array\[i\]≤10^5$
* $1≤K≤10^5$

Sample input:

```
5 3

5 2 1 3 4

```

Sample output:

```
1

```

# Answer
> 0 votes
Easy. You get the minimum number of swaps if you find a range that already contains as many items \>= K as possible, and then swap the elements \< K in that range with the elements \>= K outside the range.

You count how many items are \>= K, let's say there are M items \>= K. Obviously O (N).

You examine each range of M consecutive items and count how many items are there ≥ K. Let's say the highest number is m items ≥ K. Easily (maybe not obviously) O (N).

And the answer is M - m.

To actually do the swaps, remember which range had m items ≥ K. Then you iterate through that range until you find an item \< K, and through the remaining numbers until you find an item \>= K, swap them, and repeat this M - m times. Again O (N). Space requirement is O (1).

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


# Question
Title: how applications send tcp data to internet?
What i know is that applications create "socket"(visualized concept for high level programmers),the socket will address the ip addresses and send to internet and forward the feedback data.What i wonder is do applications send tcp packets directly to hardware interface or through another program like firewall?And how exactly the applications send to what program in some operating system like windows or linux?

# Answer
Applications don't deal with TCP packets at all. The operating system presents an interface somewhat similar to the file system and the application just writes data to that interface. The OS deals with organizing that data into packets and sending it across the network. Likewise, received data is handled by giving the application an interface that's similar to reading from a file.

Any local firewalling is done by either an operating system module or a privileged application. In the case of connection filtering, that will check that requested connections are to allowed hosts and ports; in the case of packet filtering, the firewall will inspect the actual data flowing through the connection before it's handed to the application.

Firewalling may also be done by a gateway router. In this case, the standard IP routing system will automatically send all packets via the firewall, which will do its thing before sending them out to the internet.
> 4 votes

---
Tags: computer-networks, os-kernel
---


# Question
Title: Data structure with Median, Min, Max, Delete in $O(1)$ amortized-time
I'm looking for a data structure, in which the operations $Init, Median, Min, Max, Delete$ run in $O(1)$ amortized-time, and $Insert$ should run in amortized-time as low as possible.

I tried to work with Min-Max Fibonacci heaps and pointer to median, but got stuck.

I believe the $Insert$ operation can be done in $O(\log n)$ amortized-time.

Any help is appreciated.

# Answer
It should be possible with everything O (1) amortized if the insertions and deletions are random: If there are n items, try to keep track of the sqrt (n) smallest items, largest items, and items around the median.

If you insert or remove an item within the smallest, largest or median items, that's $O(n^{1/2})$ because you need to insert or remove one of $n^{1/2}$ elements, and happens with probability $O(1/n^{1/2})$, so total O (1).

Whenever you insert or remove one of the elements before the median elements, the range of the "median" elements shifts. When the items that were supposed to be around the median don't contain the median element anymore, you need to find elements around the median again, which should happen in O (n). If insertion / deletions are random, then I think the balance shifts by $n^{1/2}$ only after a large number of insertions / deletions. You'll have to check the maths.

And of course all this only works if insertions / deletions are random. Otherwise you need something significantly more clever.

PS. D.W.'s comment indicates (unless I'm very wrong) that if you can find the median and insert items in O (f(n)) amortized *in the worst case*, then you can sort an array in O (n·f(n)), which means f(n) cannot be better than log n asymptotically *in the worst case*.
> 1 votes

---
Tags: data-structures, amortized-analysis
---


# Question
Title: Poly-time reduction is not antisymmetric
> **Lemma.** *(Transitivity)* "$\leq\_p$" is a transitive relation on languages, i.e., if $L\_1 \leq\_p L\_2$ and $L\_2 \leq\_p L\_3$, then $L\_1 \leq\_p L\_3$.
>
> **Proof.** By definition, there are poly-time functions $f$ and $g$ such that $x \in L\_1 \Leftrightarrow f(x) \in L\_2$ and $y \in L\_2 \Leftrightarrow g(y) \in L\_3$, thus $x \in L\_1 \Leftrightarrow f(x) \in L\_2 \Leftrightarrow g(f(x)) \in L\_3$. Obviously, $g(f(\cdot))$ is poly-time (since $|f(x)|$ is polynomial in $|x|$).

This lemma proves that "$\leq\_p$" is transitive, but how would I prove that it is *not* antisymmetric?

# Answer
By definition, a relation $R$ is antisymmetric if $aRb$ and $bRa$ implies $a=b$. Therefore, to show that $R$ is not antisymmetric, we have to find $a \neq b$ such that $aRb$ and $bRa$.

Specializing this to your case, you have to find two different languages $L\_1 \neq L\_2$ such that $L\_1 \leq\_p L\_2$ And $L\_2 \leq\_p L\_1$. Finding a pair of such languages isn't too challenging, so I leave it to you.
> 1 votes

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


# Question
Title: Incorrect Answer Trying to Find Hamming Distance
```
A 010101
B 110011
C 111000
D 000111

```

The minimum Hamming distance of those code words is 3 as the minimum difference is 3 but the correct answer is 2.

How can I find the correct Hamming distance?

# Answer
> 1 votes
* A 0**1**01**0**1
* D 0**0**01**1**1

There are two bits different (namely the bold ones). So the hamming distance is 2.

---
Tags: algorithms, hamming-code
---


title: Abstractions in call-by-push-value

text:
# Question
Title: Abstractions in call-by-push-value
In "Call-by-push-value: A subsuming paradigm." (Levy, Paul Blain. Springer, Dordrecht, 2003. 27-47) terms of the lambda calculus get split in to values and computations, with the slogan "A value is, a computation does".

What I don't understand is: why are abstractions computations and not values? Intuitively a function does not do anything and can be used as data. It will only do something when applied to something.

# Answer
thanks for your interest in call-by-push-value. The fact that functions (all functions, not just lambda-abstractions) are computations is the main difference between call-by-push-value and call-by-value (where functions are values), and it does seem strange at first. But the mystery is (somewhat) resolved when you see the CK-machine, which is a kind of operational semantics that uses a computation and a stack. In terms of that machine, a function of type A -\> B is a computation that aims to pop a value of type A and then behave as a computation of type B. For example:

```
    print "hello".
    lambda x.
    print "hello again".
    return x

```

is a computation that first prints "hello", then pops x ("lambda" means "pop"), then prints "hello again", then returns x. And actually, the same phenomenon of "lambda" as "pop" is present in call-by-name; that's why call-by-push-value manages to subsume call-by-name.

I hope that helps! I should also say that the origin of call-by-push-value is that it was empirically observed within the models. The slogan was designed to fit the language and not the other way round. But that's just saying probably a less helpful answer, because it's just saying "the language is that way because the models say so".
> 9 votes

---
Tags: lambda-calculus
---


# Question
Title: What are the drawbacks of Normalized Mutual Information clustering evaluation method?
What are the drawbacks of Normalized Mutual Information (NMI) clustering evaluation method? For evaluating what clustering algorithms, is the NMI evaluation method suitable?

# Answer
> 0 votes
It is a matter of preference.

If you come with an information theory background, you'll like NMI better. If you come from a classification background, Rand index is pretty much the "accuracy" that you are used to, but on pairs.

# Answer
> 0 votes
In Comparing Community Detection, whenever the ratio between the number of members and the number of clusters is small the Normalized Mutual Information becomes too high which is called *selection bias* problem. This problem caused by inclination of selecting solutions with more clusters (Amelio et al. 2015)

> For evaluating what clustering algorithms, is the NMI evaluation method suitable?

I think this question incomplete.

---
Tags: machine-learning, clustering, evaluation-strategies
---


# Question
Title: How does this algorithm expressed in pseudo-code work?
On a website it gives you questions and answers for computer science, yet does not explain the answer. I was hoping if someone could explain the pseudo-code (answer) for me, as I do not understand it. Especially the store index part - which is basically the entire pseudo-code. Thank you. ***More specifically:*** line 4, line 8 and why found = False in line 4 means item is found but in line 11 means item not found.

*The question is:*

Write an algorithm expressed in pseudo-code to ask a user for a search item and carry out a linear search on data stored in an array to find that item (6 marks).

*The answer is:*

```
RECEIVE item FROM KEYBOARD
SET found TO False
SET index to 0
WHILE found = False AND index <= LENGTH(store) - 1 DO
  IF store[index] = item THEN
    SET 'Item found' TO DISPLAY
  ELSE
    SET index TO index + 1
  END IF
END WHILE
IF found = False THEN
   SEND 'Item not found.' TO DISPLAY
END IF

```

# Answer
> 1 votes
The algorithm is pretty much straight forward. I'll try to explain this algorithm in basic English here without using pseudo-code.

First you are taking input from the user about the element they need to search for in an array you already have.

Then you are initializing a boolean data type to false(This is used to check whether you have found the element you need or not) and an integer data type to 0(This is used for `index` of the array).

In the next step, you run a while loop till you either reach the end of the array or you have found the number user wants.

You compare each element of an array with the number user wants and if the present element in the array is not the same as the user wants, you increase the value of index by 1. Else, if you have found the number user wanted, you just change the value of boolean data type to `true` and the loop gets terminated at that instant itself.

In the last step, you check whether the value of boolean changed or not. If it is still `false`, you display a message.

I hope this way it was clear.

---
Tags: algorithms, pseudocode
---


# Question
Title: Need to understand signals received vs sent
What is meant by in the following statement (from the paper titled "Implementing Lightweight Threads"):

> As in singlethreaded processes, the number of signals received by the process is less than or equal to the number sent.

Why is the number received less than or equal to the number sent. I don't have enough background in singlethreaded processes I guess.

# Answer
> 1 votes
Suppose I sent you 10 letters. Then the number of letters that you have received is at most 10 (some might still be en route).

The reason that this is stressed is that some of the signals could potentially be received by several threads. The operating system guarantees that each signal is received by at most one thread, chosen arbitrarily among threads which have not masked the signal.

---
Tags: operating-systems, threads
---


# Question
Title: What is the difference between undecidable language and Turing Recognizable language?
I was wondering what is the difference difference undecidable language and Turing recognizable language. I've seen in some cases where they ask:

1. Prove that the language $ A\_{TM} = \\{ \ \<M,w\> | \ M \mbox{ is a Turing Machine accepting } w\\}$ is undecidable.
2. Prove that the language $ A\_{TM} = \\{ \ \<M,w\> | \ M \mbox{ is a Turing Machine accepting } w\\}$ is Turing Recognizable.

Are they the same thing? Can someone elaborate on this issue?

Another one, is the question at hand is known as the halting problem? Or is it different from halting problem?

# Answer
> 3 votes
A language $L$ is *decidable* if there exists a Turing machine $M$ such that:

* If $x \in L$ and $M$ is run with input $x$, then $M$ halts at an accepting state.
* If $x \notin L$ and $M$ is run with input $x$, then $M$ halts at a rejecting state.

(In particular, $M$ always halts.) If no such Turing machine exists, $L$ is *undecidable*.

A language $L$ is *recognizable* (or, recursively enumerable, abbreviated r.e.) if there exists a Turing machine $M$ such that:

* If $x \in L$ and $M$ is run with input $x$, then $M$ halts.
* If $x \notin L$ and $M$ is run with input $x$, then $M$ doesn't halt.

If no such Turing machine exists, $L$ is *unrecognizable*.

A basic fact about these definitions is:

> A language $L$ is decidable if and only both $L$ and $\overline{L}$ are recognizable.

Your language $A\_{TM}$ is one way of stating the halting problem (there are many equivalent ways). It is recognizable but not decidable.

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


# Question
Title: Evaluating the average time complexity of a given bubblesort algorithm.
Considering this pseudo-code of a bubblesort:

```
FOR i := 0 TO arraylength(list) STEP 1
    switched := false
    FOR j := 0 TO arraylength(list)-(i+1) STEP 1
        IF list[j] > list[j + 1] THEN
            switch(list,j,j+1)
            switched := true
        ENDIF
    NEXT
    IF switched = false THEN
        break
    ENDIF
NEXT

```

What would be the basic ideas I would have to keep in mind to evaluate the average time-complexity? I already accomplished calculating the worst and best cases, but I am stuck deliberating how to evaluate the average complexity of the inner loop, to form the equation.

The worst case equation is:

$$ \sum\_{i=0}^n \left(\sum\_{j=0}^{n -(i+1)}O(1) + O(1)\right) = O(\frac{n^2}{2} + \frac{n}{2}) = O(n^2) $$

in which the inner sigma represents the inner loop, and the outer sigma represents the outer loop. I think that I need to change both sigmas due to the "if-then-break"-clause, which might affect the outer sigma but also due to the if-clause in the inner loop, which will affect the actions done during a loop (4 actions + 1 comparison if true, else just 1 comparison).

For clarification on the term average-time: This sorting algorithm will need different time on different lists (of the same length), as the algorithm might need more or less steps through/within the loops until the list is completely in order. I try to find a mathematical (non statistical way) of evaluating the average of those rounds needed.

For this I expect any order to be of the same possibility.

# Answer
> 10 votes
For lists of length $n$, average usually means that you have to start with a uniform distribution on all $n!$ permutations of \[$1$, .., $n$\]: that will be all the lists you have to consider.

Your average complexity would then be the sum of the number of step for all lists divided by $n!$.

For a given list $(x\_i)\_i$, the number of steps of your algorithm is $nd$ where $d$ is the greatest distance between a element $x\_i$ and his rightful location $i$ (but only if it has to move to the left), that is $\max\_i(\max(1,i-x\_i))$.

Then you do the math: for each $d$ find the number $c\_d$ of lists with this particular maximal distance, then the expected value of $d$ is:

$$\frac1{n!}\ \sum\_{d=0}^n{\ dc\_d}$$

And that's the basic thoughts without the hardest part which is finding $c\_d$. Maybe there is a simpler solution though.

EDIT: added \`expected'

# Answer
> 20 votes
Recall that a pair $(A\[i\], A\[j\])$ (resp. $(i,j)$) is inverted if $i \< j$ and $A\[i\] \> A\[j\]$.

Assuming your algorithm performs one swap for each inversion, the running time of your algorithm will depend on the number of inversions.

Calculating the expected number of inversions in a uniform random permutation is easy:

Let $P$ be a permutation, and let $R(P)$ be the reverse of $P$. For example, if $P = 2,1,3,4$ then $R(P) = 4,3,1,2$.

For each pair of indices $(i,j)$ there is an inversion in exactly one of either $P$ or $R(P)$.

Since the total number of pairs is $n(n-1)/2$, and the total number and each pair is inverted in exactly half of the permutations, assuming all permutations are equally likely, the expected number of inversions is:

$$\frac{n(n-1)}{4}$$

# Answer
> 2 votes
Number of swaps \< Number of iterations (in both optimized as well as simple bubble case scenario)

Number of Inversions = Number of swaps.

Therefore, Number of Iterations \> $\frac{n(n-1)}{4}$

Thus, Average case complexity is $\omega(n^2)$. But, since average case cant exceed worst case, we get that it is $O(n^2)$,

This gives us : Average Time = $\theta(n^2)$

(Time complexity = Number of iteration no. of iterations \> no. of swaps)

# Answer
> 0 votes
in this document, the average time complexity of bubble sort reached O(nlog(n))! http://algo.inria.fr/flajolet/Publications/ViFl90.pdf

---
Tags: algorithms, time-complexity, sorting, average-case
---


# Question
Title: Algorithm for exploring a parameter space
I have a research problem which has a general outline as follows:

I have a 2D parameter space, $(\alpha, \beta)$ which serve as initial conditions on some set of partial differential equations. Given values for $\alpha, \beta$ I can integrate this set of PDEs numerically to obtain a result in a 2D phase space $(x,y)$.

Now, suppose I want to work backwards and find the values of $(\alpha, \beta)$, which generate a particular $(x,y)$. I can see a general, crude algorithm as,

1. Choose a random $(\alpha, \beta)$
2. Integrate PDE to obtain $(x,y)$
3. Inspect how close to the desired result we are
4. Adjust $(\alpha, \beta)$.
5. Repeat

I feel like there must be a smart/fast way to do this. Can anyone point me in the direction of some algorithms/resources which may be able to accomplish this goal? Thanks

# Answer
Problem statement: You have a function $f:\mathbb{R}^2 \to \mathbb{R}^2$ where you know how to compute $f$ but not $f'$. Given $(x,y)$, you want to find $(\alpha,\beta)$ such that $f(\alpha,\beta)=(x,y)$.

One approach is to use mathematical techniques for black-box optimization. Define $g:\mathbb{R}^2 \to \mathbb{R}$ by

$$g(\alpha,\beta) = \\|f(\alpha,\beta)-(x,y)\\|^2,$$

i.e., the squared L2-norm of how far off the answer is. Then your goal is to find $(\alpha,\beta)$ that minimizes $g$. Such a minimum will be a solution to your original problem.

The minimization problem could be solved using gradient descent, Newton's method, or some other iterative method.

The iterative methods will often require you to be able to compute the gradient of this function. The gradient can be computed in a black-box way by using

$${\partial g \over \partial \alpha}(\alpha,\beta) = {g(\alpha+\epsilon,\beta) - g(\alpha-\epsilon,\beta) \over 2\epsilon}$$

where $\epsilon$ is a sufficiently small number, and similarly for ${\partial g \over \partial \beta}$.

This method assumes that $f$ is a "nice" function: e.g., continuous and differential and doesn't change too quickly, if you make small changes to its inputs.
> 1 votes

---
Tags: algorithms
---