# Question
Title: Is the set of CFGs that contain all odd and even length words Turing-decidable?
$ALLEVEN\_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^\*$} = {(M): ($\Sigma\Sigma$)\* ⊆ L(M)}

$ALLODD\_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd length in $\Sigma^\*$} = {(M): $\Sigma$($\Sigma\Sigma$)\* ⊆ L(M)}

Is $ALLEVEN\_{CFG} \cap ALLODD\_{CFG}$ Turing Decidable?

I thought that this was yes because ALLEVEN would produce strings that are only even in length. ALLODD would produce strings that are only odd in length. The intersection would then be producing strings that are both even and odd in length, which is nothing. This means that we can reduce the problem to $E\_{CFG}$ which is a decidable.

However, my professor says that $ALLEVEN\_{CFG} \cap ALLODD\_{CFG}$ is exactly $ALL\_{CFG}$ which is not decidable. I am not sure how he reached the conclusion that it is equal to $ALL\_{CFG}$.

# Answer
The problem is that you interpret e.g. "grammars that generate all even length strings" as "grammars that generate *only* all even length strings", which is wrong. If you look at it this way, the intersection you are looking for is grammars that generate all even length strings *and* all odd length strings, i.e., grammars that generate all of $\Sigma^\*$
> 8 votes

# Answer
$ALLEVEN\_{CFG} \cap ALLODD\_{CFG} = \\{G$ is a CFG grammar $\mid\ L(G)$ includes all strings of odd length and even length in $\Sigma^\* \\}$. This is because a $G$ that belongs to both sets will have to satisfy the conditions of both the sets.

which really means

$ALLEVEN\_{CFG} \cap ALLODD\_{CFG} = \\{G$ is a CFG grammar $ \mid\ L(G)$ is $\Sigma^\* \\}$.

If your teacher means $ALL\_{CFG}$ to be $\\{G$ is a CFG grammar $\mid\ L(G)$ is $\Sigma^\* \\}$ then he is correct.

The set $ALL\_{CFG}$ is definitely undecidable, refer undecidable problems related to CFG.
> 1 votes

# Answer
> I am not sure how he reached the conclusion that it is equal to $\mathrm{ALL}\_{\mathrm{CFG}}$.

By simple logic. You have two languages defined by predicates like so:

$\qquad G\_P = \\{ \text{CFG } G \mid \forall\\, w \in \Sigma^\*.\ P(w) \implies w \in L(G) \\}$.

Then,

$\qquad\begin{align\*} G\_P \cap G\_Q &= \\{ \text{CFG } G \mid \bigl\[ \forall\\, w \in \Sigma^\*.\ P(w) \implies w \in L(G) \bigr\] \\ &\hspace{2.5cm}\land \bigl\[ \forall\\, w \in \Sigma^\*.\ Q(w) \implies w \in L(G) \bigr\] \\} \\ &= \\{ \text{CFG } G \mid \forall\\, w \in \Sigma^\*.\ P(w) \lor Q(w) \implies w \in L(G) \\}. \end{align\*}$

Since in your case $P$ is "has even length" and $Q$ "has odd length", and every word has either even or odd length, every $G$ in the specified set has to contain all words.
> 1 votes

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


# Question
Title: Counterexample for equality in Quantified Boolean Formula
I'm looking for a counterexample for the following (false) equality. It should exist.

$n$ is an *odd* integer.

$f(x\_1, x\_2 .. x\_n)$ is a boolean expression in 3 CNF form with boolean variables x.

$A = \exists x\_1 \forall x\_2 \exists x\_3 \forall x\_4 ... \forall x\_{n-1} \exists x\_n: f(x\_1..x\_n)$

Note that the exists and forall are alternating and that the expression begins and ends with exist.

$B = \forall x\_2 \forall x\_4 \forall x\_6 .. \forall x\_{n-1} \exists x\_1 \exists x\_3 .. \exists x\_n : f(x\_1..x\_n)$

Somehow I have a flawed proof that implies $A=B$. I'm looking for a simple counterexample, a 3 CNF formula with few variables, so I can find the flaw in my proof.

# Answer
> 2 votes
The equality is correct for $n=1$, so let's take $n = 3$. Let $f(x\_1,x\_2,x\_3) = \[x\_1 \neq x\_2\]$. Statement $B$ states that for every $x\_2$ there exists $x\_1 \neq x\_2$, which is correct. Statement $A$ states that there exists $x\_1$ which is different from all $x\_2$, which is incorrect.

---
Tags: boolean-algebra
---


# Question
Title: Compare phase and magnitude spectrum results of 2 Images
I have read that from Fourier transform we obtain magnitude and phase spectrum. The magnitude spectrum tells you how strong are the harmonics in a image and the phase spectrum tells where this harmonic lies in space.

I have used Matlab to compute the magnitude and phase spectrum of the 2 grayscale images of babies using `fftn` function, but the all spectrum are difficult to understand.

Can anyone please explain the features given in 1st paragraph by comparing the spectrums of both images of babies?

**1.phase spectrum**

and

**2.magnitude spectrum**

**(If you have results other than in Matlab, explaining with your method is also okay)**

```
image1=imread('D:\baby1.jpg');%Read colour image
image1=rgb2gray(image1);%covert colour image into Gray scale

image2=imread('D:\baby2.jpg');%Read colour image
image2=rgb2gray(image2);%covert colour image into Gray scale

figure,
subplot(1,3,1);
imshow(image1);
title('Gray scale Image of Baby1');

%Apply Fourier transform on Gray scale image
fft1=fftn(image1);
fft1=log(1+fftshift(fft1));%Use log function for scaling

%Find the magnitude spectrum
magnitude1=abs(fft1);
subplot(1,3,2);
imshow(magnitude1,[]);
title('Amplitude Spectrum 1');

%Find the phase spectrum
phase1=angle(fft1);
subplot(1,3,3);
imshow(phase1,[]);
title('Phase Spectrum 1');

figure,
subplot(1,3,1);
imshow(image2);
title('Gray scale Image of Baby2');

%Apply Fourier transform on Gray scale image
fft2=fftn(image2);
fft2=log(1+fftshift(fft2));%Use log function for scaling

%Find the magnitude spectrum
magnitude2=abs(fft2);
subplot(1,3,2);
imshow(magnitude2,[]);
title('Amplitude Spectrum 2');

%Find the phase spectrum
phase2=angle(fft2);
subplot(1,3,3);
imshow(phase2,[]);
title('Phase Spectrum 2');

```

# Answer
The images are mostly noise with a recognizable cross in the middle, that means that there is nothing in the image that repeats. The first image however shows some patterns (circles), not just the cross, those are probable the wall on the top-left which has some repeating pattern on it.
> 1 votes

---
Tags: image-processing, fourier-transform, signal-processing
---


# Question
Title: How do I interpret this divide and conquer algorithm for removing duplicates in a list?
Consider the following divide and conquer algorithm to remove duplicates in a list. The text is in French.

What is the meaning of the variables $c1, c2, d1, d2$? Why are only the variables $c1, d1$ compared?

# Answer
> 1 votes
As wvxvw suggested, the dot notation is a shorthand way of separating the head and the tail of a list, as in LISP or ML. For example, if we have a list $L=\langle\\,4,7,8\\,\rangle$ then we can write $L$ as $c\_1.c\_2$ where $c\_1=4$ and $c\_2=\langle\\,7,8\\,\rangle$.

The function $\Delta$ takes two sorted lists, $c\_1.c\_2$ and $d\_1.d\_2$ and recursively produces a list without duplicates. For instance, we might have $$\begin{align} \Delta(\langle\\,6\\,\rangle,\langle\\,3,5,6\\,\rangle) &=\langle\\,3,\Delta(\langle\\,6\\,\rangle,\langle\\,5,6\\,\rangle)\\,\rangle&\text{by rule 3}\\ &=\langle\\,3,5,\Delta(\langle\\,6\\,\rangle,\langle\\,6\\,\rangle)\\,\rangle&\text{by rule 3}\\ &=\langle\\,3,5,6,\Delta(\varnothing,\varnothing)\\,\rangle&\text{by rule 2}\\ &=\langle\\,3,5,6\\,\rangle \end{align}$$ This is where the real work is done. The function $SD$ uses $\Delta$ by splitting the original sorted list $\langle\\,s\_1,s\_2,\dotsc,s\_n\\,\rangle$ into two: the odd-indexed part, $\langle\\,s\_1,s\_3,s\_5,\dotsc\\,\rangle$ and the even-indexed part, $\langle\\,s\_2,s\_4,s\_6,\dotsc\\,\rangle$ and applies $\Delta$ to them, to remove duplicates. For instance, $$\begin{align} SD(\langle\\,3,3,3,5,6,6\\,\rangle&=\Delta(SD(\langle\\,3,3,6\\,\rangle),SD(\langle\\,3,5,6\\,\rangle))\\ &=\Delta(\langle\\,3,6\\,\rangle,\langle\\,3,5,6\\,\rangle)&\text{since $SD$ removes dups}\\ &=\langle\\,3,5,6\\,\rangle \end{align}$$ as we saw above. It's worth noting that the arguments to both functions must be in sorted order. To see why, trace the action on, say, $\langle\\,3,4,2,3\\,\rangle$.

# Answer
> 0 votes
In addition to the explanation by Rick Decker, here's an implementation of this algorithm in Python:

```
def merge(left, right):
    result = []
    while left and right:
        small, big = min(left, right), max(left, right)
        result.append(small[0])
        left, right = ((left[1:], right[1:])
                       if small[0] == big[0]
                       else (small[1:], big))
    return result + [x for x, y in zip(right, right[1:] + [None])
                     if x != y]

def remove_duplicates(candidates):
    if not candidates or len(candidates) == 1:
        return candidates
    return merge(remove_duplicates(candidates[1::2]),
                 remove_duplicates(candidates[::2]))

```

---
Tags: algorithms, notation, divide-and-conquer, lists
---


# Question
Title: How can we use the FPTAS for problem B to solve problem A
Given an optimization problem A which is NP-complete, and can be polynomially reduced to another optimization problem B which is also NP-complete. If we use an FPTAS to solve the reduced problem B' (A $\rightarrow$ B = B'), then under what rules can the solution obtained from solving with the FPTAS be directly associated with a solution to problem A?

For example, Problem A is shortest Path problem and Problem B is knapsack Problem.

# Answer
You need a stronger guarantee on the reduction, that it be approximation preserving. Not all reductions are approximation preserving. An extreme example is given by Min Vertex Cover and Max Independent Set. The complement of a vertex cover is an independent set, and so there are simple NP-hardness reductions between these problems. However, while Min Vertex Cover has a 2-approximation algorithm, Max Independent Set cannot be approximated to within $n^{1-\epsilon}$ for any $\epsilon \> 0$ unless $\mathsf{P=NP}$.
> 3 votes

# Answer
You don't necessarily have to focus only on an FPTAS, and not even on positive results. The key idea is an approximation-preserving reduction: if you reduce problem A to problem B, then an $\alpha$-approximation algorithm for B implies a $f(\alpha)$-approximation for A, where $f$ is some function. Now observe both of the following are true: if A is hard to approximate, so is B. Also, if you can approximate B, you can also approximate A.

For example, consider an instance $(G,k)$ of chromatic number. Suppose there is a polynomial-time algorithm that, given $(G,k)$, constructs an instance $(G',k')$ of problem X. Moreover, suppose it holds that the size of $G'$ is linear in the size of $G$, $k' = k$, and $(G,k)$ is a YES-instance of chromatic number iff $(G',k')$ is a YES-instance of X. Now, any algorithm approximating problem X is also an approximation algorithm for chromatic number. But in fact, it is known chromatic number cannot be approximated within a factor of $n^{1-\varepsilon}$ for any $\varepsilon \> 0$ (unless P = NP). Thus, the same is true for problem X.
> 3 votes

---
Tags: complexity-theory, np-complete, optimization
---


# Question
Title: What is the appropriate means of bias field in image processing?
I want to do image segmentation. In (Li, C. et al, 2011) article about A Level Set Method for Image Segmentation I saw that the authors use bias field estimation. I searched a lot but I couldn't understand the meaning of bias field...What is the appropriate mean of bias field?

# Answer
> 3 votes
Bias field is magnetic based inhomogenity in results of MRI, which comes from magnetic settings, patient position etc.
This term has no standard definition in terms of image processing.
Essentialy this is smooth, low frequency, gradiented signal, which covers valuable data.
In terms of MRI this is just artifact and very often when somebody says that image will be preprocessed or will get rid of artifacts, bias field is included (naming it simply - noise from equipement).

---
Tags: image-processing
---


# Question
Title: Relation between Hamming distances of columns and rows
You're given a $0-1$ $n\times n$ matrix such that for every distinct columns $C\_i$ and $C\_j$, $d\_H(C\_i,C\_j)\gt 2t$ for some $t$. What could be said about the Hamming distances of the rows? It it true for instance that there are two distinct rows $R\_k$ and $R\_l$ that satisfy $d\_H(R\_k,R\_l)\lt n-t$?

# Answer
> 1 votes
The condition on the columns implies that $2t \< n$. Suppose that the condition on the rows is not satisfied. The rows therefore form a code of minimal distance at least $n-t \> n/2$ of size $n$. The Plotkin bound implies that unless $n-t$ is extremely close to $n/2$, such a code cannot exist. If $t$ is very close to $n/2$, however, the columns form a code of minimal distance close to $n$, which is again ruled out by the Plotkin bound (except perhaps for very small $n$).

I'll let you fill up the details and check for which $n$ this argument works.

---
Tags: combinatorics, information-theory
---


title: Dividing bins into segments

text:
# Question
Title: Dividing bins into segments
This may be a question with a well known answer, but I've been thinking on it for two days, and can't quite come up with a satisfactory answer.

Consider the problem of dividing $p n$ bins numbered $1$ through $pn$ into $p m + 1$ segments by placing $pm$ balls. If we let $k = pn - pm \bmod pm+1$, then we can show that we may attain a placement of the $pm$ balls such that there are exactly $(pm+1) - k$ segments of empty bins of length $\lfloor \frac{pn-pm}{pm+1} \rfloor$ and $k$ segments of empty bins of length $\lceil \frac{pn-pm}{pm + 1} \rceil$.

Here's the tricky question: can we accomplish this task while ensuring that there are exactly $m$ balls in each interval $\[(j-1)n + 1, jn\]$, for $j \in \\{1, 2, \dots, p\\}$?

Every concrete example I work through answers in the affirmative, but I can't seem to get an algorithmic way of doing it, or mathematical proof that one such arrangement exists.

For particular examples, it always seems to work. See an example below with $p = 2,$ $n = 7,$ $m = 2.$

1| |X| | |X|1|X| | |X| | |

where 1 denotes the beginning of a new 'period', and | denotes the 'wall' of a bin, and X denotes a ball. Note that 1 and | both denote 'walls' of bins.

# Answer
> 2 votes
For $0 \leq i \leq pm+1$, define $$ x\_i = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor. $$ We put ball $i$ in bin $i$ for $1 \leq i \leq pm$. The length of the $i$th space (for $1 \leq i \leq pm+1$) is $$ x\_i - x\_{i-1} = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor - \left\lfloor (i-1) \frac{pn+1}{pm+1} \right\rfloor \in \left\\{ \left\lfloor \frac{pn+1}{pm+1} \right\rfloor, \left\lceil \frac{pn+1}{pm+1} \right\rceil \right\\}, $$ so your first condition is satisfied (the spaces are as equal to each other as possible).

For your second condition, we need to verify that $1 \leq x\_1,\ldots,x\_m \leq n$, $n+1 \leq x\_{m+1},\ldots,x\_{2m} \leq 2n$, and so on. It's clearly enough to verify that $x\_{Cm} \leq Cn$ for $1 \leq C \leq p$ and that $x\_{Cm+1} \> Cn$ for $0 \leq C \< p$. For the first condition, we have $$ x\_{Cm} = \left\lfloor Cm \frac{pn+1}{pm+1} \right\rfloor \< Cm \frac{pn+1}{pm+1} + 1 = \frac{Cpmn + Cm + pm + 1}{pm+1} \\ \< \frac{Cpmn + Cn + pm + 1}{pm+1} = Cn+1, $$ using your implicit assumption $m \< n$. For the second condition, $$ x\_{Cm+1} = \left\lfloor (Cm+1) \frac{pn+1}{pm+1} \right\rfloor \geq (Cm+1) \frac{pn+1}{pm+1} = \frac{Cpmn + Cm + pn + 1}{pm+1} \\ \geq \frac{Cpmn + Cn + pm + 1}{pm+1} = Cn+1, $$ using $Cm + pn \geq Cn + pm$, which follows from $(p-C)(n-m) \geq 0$.

---
Tags: discrete-mathematics, packing
---


title: Efficient flood filling (seed filling)

text:
# Question
Title: Efficient flood filling (seed filling)
I am referring to the algorithm that fills a white area of arbitrary shape in a binary digital image, starting from a given white pixel, using the Moore (8 neighbors) or Neumann (4 neighbors) connexity rules.

There are well-known solutions to this problem, such as recursion on the immediate neighbors, or the scanline approach. The former takes 4/8 tests of the neighbor color per pixel, and the latter takes a little less as when a straight run of pixels is processed, one backward test is saved per pixel. I have heard of an article possibly published in 2006, which is based on outline following, but have no reference for it.

(Whether the actual implementation uses the recursion stack or an allocated array is not relevant for this question. Nor is the "fixed-memory" requirement for which solutions have been proposed.)

My intuition tells me that better could be achieved by avoiding the repetition of some neighbor tests. In an extreme case, you can fill a square starting from the middle and spiraling until you reach the boundary with just one test per pixel, as you know that all pixels inside the spiral have been filled.

So my question: do you know of any theoretical study on the required number of neighbor tests per pixel for flood filling ? (The question can be rephrased in terms of graph theory as a connected component labeling problem.)

# Answer
> 3 votes
Following comments by @EvilJS which restarted a bibliographic search, here is relevant material that improves upon the initial algorithm by Alvy Ray Smith, which I called "scanline" in the OP.

It seems that the number of pixel visits was lowered from 2 to 1.5 in the worst case. It also seems that the minimum achievable rate depends on the topology of the filled area. The '85 article by Fishkin & Barsky is the most theory-oriented resource.

* Computer Graphics And Geometric Modelling : Implementation & Algorithms Max K. Agoston , Springer (2005), ISBN 10: 1852338180 ISBN 13: 9781852338183. *See 2.4 Fill Algorithms.*
* Smith, A. Ray, Tint Fill, Computer Graphics, Vol 13, No 2, Aug 1979, 276-283 (SIGGRAPH 79 Conference Proceedings).
* Fishkin, K.P., and Barsky, B.A., “An Analysis and Algorithm for Filling Propagation,” Proc. Graphics Interface 1985, 203–212.
* Fishkin, Ken, “Filling a Region in a Frame Buffer,” in \[Glas90\], 278–284.
* Heckbert, Paul S., “A Seed Fill Algorithm,” in \[Glas90\], 275–277.
* \[Glas90\] is Glassner, A.S., editor, Graphics Gems, Academic Press, 1990.

---
Tags: graphs, algorithm-analysis, efficiency, image-processing
---


# Question
Title: Does Every Recognizable language has a subset not Recognizable?
Does every Turing Recognizable language has a subset which is not turing recognizable? i can give some examples but can't prove in general

# Answer
No, finite languages don't have subsets which aren't Turing recognizable. However, infinite languages (Turing recognizable or not) always have subsets which are not Turing recognizable, simply because they have uncountably many subsets, but there are only countably many Turing recognizable languages.
> 6 votes

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


# Question
Title: Do correlated inputs imply existence of efficient communication protocols?
Suppose that I have 2 parties Alice and Bob. Alice gets an input $X$ and Bob gets input $Y$ where $X, Y$ are $n$-bit strings. In the classic communication complexity world, computing a function such as disjointness of $X$ and $Y$ requires $\Omega(n)$ bits assuming the input distributions of $X$ and $Y$ are chosen to be "hard".

Now suppose that we know that $H(X | Y) = k$ and $H(Y | X) = k$, for $k \<\< n$. Is it always possible to derive an efficient deterministic communication complexity protocol (that computes a given function $f$) and has communication complexity at most $O( H(X | Y) \cdot H(Y | X) )$ ?

If the answer to the above question is no, is there an easy counterexample, i.e., a function that requires a high amount of communication despite correlated inputs?

One approach I was thinking about is that, since Alice knows $X$ and $H(Y | X)=k$, we could in advance fix an enumeration $E\_X$ of the possible choices of Bob's input $Y$, given $X$. Clearly, the choice of a specific $Y=y$ from $E$ can be described using $k$ bits. But this doesn't seem to help at all: Bob doesn't know $X$, so he doesn't know which enumeration $E\_X$ is used by Alice (and vice versa).

# Answer
Deterministic communication complexity depends only on the support of the input distribution (the "promise"). Even if $H(X|Y),H(Y|X) \< 1$ the distribution $(X,Y)$ could have full support, so the $\Omega(n)$ bound still holds.
> 2 votes

---
Tags: algorithms, coding-theory, communication-complexity
---


# Question
Title: Finding the minimum sum path between two vertices in an undirected weighted graph
What algorithm would I use for finding the minimum-weight path between two vertices in an undirected weighted graph?

Dijkstra is for shortest path, but I need path with the minimum sum of the weights. Would Prim's or Kruskal's algorithm do this? Is a brute force method required? There are millions of nodes and edges.

# Answer
When looking at weighted graphs, "shortest path" usually means "minimal weight path". Dijkstra's algorithm is used for finding the shortest (minimal weight) path between nodes in a directed graph with non-negative weights, however, if there are negative weights it could fail. Bellman-Ford algorithm is used for the same purpose for graphs with negative weights (and has a slower runtime).

So in your case you need to:

1. Transform your graph into a directed graph (by duplicating each undirected edge $ (u, v) \in E$ into two directed edges $(u, v)$ and $(v, u)$ with the same weight)
2. Choose one of the above algorithms based on the existence of negative weights in the graph
> 0 votes

---
Tags: graphs
---


title: What type of knapsack problem is this?

text:
# Question
Title: What type of knapsack problem is this?
I need to choose the highest value combination of items given a specific set of constraints. These constraints are:

1. Exactly 6 items from group A and 2 items from group B must be selected.
2. Items in group A and group B count towards the same maximum weight.
3. No item can be selected more than once.
4. No more than 2 items of the same 'color' can be selected (there is always exactly 2 of each color in group A and 1 of each color in group B).

Example data set:

**Group A**
Item - Weight - Value - Color
A01 - 32 - 59 - Teal
A02 - 31 - 65 - Teal
A03 - 29 - 57 - Red
A04 - 27 - 16 - Red
A05 - 25 - 07 - Orange
A06 - 25 - 20 - Purple
A07 - 24 - 06 - Orange
A08 - 23 - 39 - White
A09 - 22 - 20 - White
A10 - 21 - 23 - Purple
A11 - 21 - 31 - Blue
A12 - 20 - 16 - Green
A13 - 20 - 17 - Blue
A14 - 19 - 45 - Green
A15 - 18 - 22 - Black
A16 - 18 - 14 - Yellow
A17 - 17 - 08 - Yellow
A18 - 17 - 22 - Gray
A19 - 16 - 13 - Black
A20 - 16 - 26 - Gray

**Group B**
Item - Weight - Value - Color
B01 - 36 - 85 - Teal
B02 - 33 - 39 - Red
B03 - 31 - 48 - Purple
B04 - 30 - 28 - Orange
B05 - 29 - 71 - White
B06 - 24 - 65 - Blue
B07 - 23 - 64 - Green
B08 - 22 - 61 - Yellow
B09 - 21 - 36 - Black
B10 - 20 - 27 - Gray

Max weight = 200

---

I'm not necessarily looking for a solution to this problem. I have found all sorts of ways to solve many variations of problems that seem very similar to this, but none seem quite right. If I just knew what to look for, I'm sure I'd be able to find an example and figure out the rest from there.

The closest I've been able to get is an 0/1 multi-knapsack (or maybe multi-dimensional knapsack?) problem. Does anyone have a better description of this problem? Thanks in advance!

Edit: Oh, bonus question, if anyone has any recommendations for languages which are particularly well suited to this type of problem (I was thinking python for itertools), I'd greatly appreciate it.

# Answer
Multi-dimensional knapsack seem appropriate. The additional dimensions are `1 if item is in group A, else 0`, `1 if item is in group B, else 0`, `1 if item is green, else 0`, ... The maximum weights of additional dimensions are 6, 2 and then 2 for each color.

The condition that there must be *exactly* 6 items from group A could be forced by an additional dimension `-1 if item is in group A, else 0` and maximum weight of -6. However, this is awkward.
> 1 votes

---
Tags: algorithms, dynamic-programming, knapsack-problems
---


# Question
Title: Register images from a camera which has undergone pure forward translation
Images are taken by a DSLR camera, always set at a particular Focal length. The scene contains objects with varying distance to the cameras. Since the camera has undergone translation, homography no longer applies. Thus looked into Epipolar Geometry for pure translation. I know a very close estimate of the displacement of the camera (in between images, say Image 1 taken at x and Image 2 taken at x+d). Is there anyway to find the transformation that maps Img1 to 2 or vice versa to accomplish image registration (need to do image differencing after) ? Can the fundamental matrix and the displacement be used to transform an image to another ? I am using OpenCV for my implementation.

# Answer
> 1 votes
Without knowing a decomposition of the scene into objects and the depth of each object (distance to each object), it's not possible to achieve what you want. A very-close object will be affected much more by the translation than a very-distant object.

---
Tags: image-processing
---


# Question
Title: Why does this statement evaluate to 176?
```
int y = 10;
int z;
z = (++y * (y++ + 5)); // Evaluates to 176

```

According to me this should evaluate to 180. Please provide an explanation as well which relates to precedence and associativity.

# Answer
> 0 votes
Here's a link to how increment works.

Here's how the above problem evaluates:

```
z = (++y * (y++ + 5)); // Beginning expression
z = (11 * (y++ + 5)); // y -> 11, 11 is used as a value
z = (11 * (11 + 5)); // 11 is used as value, y -> 12
z = (11 * 16); // Evaluation
z = 176; // Evaluation

```

---
Tags: java
---


# Question
Title: Implicit complexity and interpretation of total languages
In implicit complexity theory we construct languages that characterize what can be computed in various complexity classes. One major result is Bellantoni and Cook where they show that $FP$ can be characterized by such a language (called system $B$).

I have the following beliefs about system $B$

* System B can encode all functions which can be computed in polynomial time
* All terms in System $B$ normalize in polynomial time
* Because all System $B$ terms normalize (in any amount of time) System $B$ is total
* Because all System $B$ terms normalize in polynomial time System $B$ can interpret System $B$

I have the following beliefs a computability as well

So I seem to believe contradictory things now; namely that System $B$ is total and that System $B$ is not total. Writing out like this makes me realize that the error is almost certainly in the last line of my beliefs about System $B$. So it must be the case that System $B$ can't interpret itself but I don't actually understand why this is the case. Is there a program input pair such that interpreting it takes greater than polynomial time? Further still System $B$ is just one such system among all characterizations of complexity classes on which I could apply this faulty reasoning so the answer should not be specific to System $B$ but to all such implicit characterizations of complexity classes.

# Answer
As concluded via non-direct means in discussion interpreting a polytime program cannot be done in polynomial time in general. The following example shows this directly.

The trick is that for the interpreter to run in polynomial time there must be an polynomial that bounds the running time for *every* input. This pretty obviously isn't going to hold for System-$B$ because a small constant increase in program size can increase the order of the polynomial that bounds it by a constant amount. The trick you can fall into (and I indeed fell into) is to think that because for each program the running time is bounded a polynomial that the interpreter will run in polynomial time which is pretty embarrassingly obviously false when you write it out like this. It's running time on certain inputs will be bounded by some polynomial but that's the case for any program that always terminates.

So say there is a program, $I$ in System-$B$ that interprets System-$B$ and has running time in $O(n^k)$. Say I had another program, $P$, that ran in $O(n^K)$ with $K \> k$. We could speed up P to $O(n^k)$ by simply running it though the interpreter first. So suddenly you have a huge speed up on $P$ that you shouldn't be able to get. In general $I$ could speed up any program slower than it.

I don't have a proof there is no $k$ such that every polytime function can be computed in $O(n^k)$ but it seems fairly obviously the case.
> 2 votes

# Answer
> If a language can interpret itself then it is not total

I take this to mean that if there is a universal machine for a class in the class itself, the class can not be total (i.e. there have to be non-total functions in the class). What you probably have in mind is that the class can not be the class of *all* total computable functions since we know that one to be not recursively enumerable.

However, that does not say anything about any other set of total functions.

For instance, all polynomial-time TMs can be simulated by a single polynomial-time TM. Assuming computable enumerations $M\_i$ of all TMs and $p\_j$ of the polynomials; both exist. Now consider the following machine `UPM` (universal polynomial machine):

```
UPM(<i,j>, n) :
  simulate M_i(n) for p_j(n) steps
  if the computation halts
    return M_i(n)
  else
    return 0
  end

```

This machine clearly exists (i.e. the described function is computable). Computing $p\_j(n)$ and simulating $M\_i(n)$ takes only polynomial time (some polynomial effort per simulated step) in $n$ and the size of the $M\_i$ (effectively $|\langle i,j \rangle|$), so `UPM` is a polynomial-time machine itself.
> 1 votes

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


# Question
Title: Closure under reversal of regular languages: Proof using Automata
I have been studying the closure properties of regular languages, referencing the book *Introduction to Automata Theory, Languages, and Computation* by John E. Hopcroft and Jeffery D. Ullman.

Under the topic of Reversal, they have tried to prove that the regular languages are preserved under the reversal of closure. They have stated the following (for a regular language $E$):

> $E = E^{\*}\_{1}$. Then $E^R = (E^{R}\_{1})^\*$

I wasn't able to get their justification so I took the following approach:

1. Tried to take up an example, say $E\_{1} = 01^{\*}$
2. Draw an NFA that accepts the regular expression $E\_{1}$
3. Draw AN NFA that accepts the Kleene's closure of $E\_{1}$, i.e. $E = E\_{1}^\*$
4. Convert the NFA into a DFA, and reverse the DFA into an NFA to get $E^{R}$.
5. Reduce the NFA of step 4 to a DFA again.

This is my work regarding the same:

Now for the right hand side, i.e. $(E^{R}\_{1})^\*$,

1. Created an NFA that accepts $E\_{1}$ and reducing it to DFA
2. Created an NFA that accepts $E\_{1}^{R}$ by reversing
3. Created an NFA that accepts $(E^{R}\_{1})^\*$ by taking the Kleene Closure, and then reduced it to a DFA.

This is my work for the second half:

However, the two DFAs I get at the end are not similar. Can anyone help me with the error I might be making?

Plus, how can we prove the same in a way other than DFA/NFA construction?

# Answer
You are asking two questions. I will only answer the second one. Recall that $L^\* = \bigcup\_{n=0}^\infty L^n$. I will show that $(L^k)^R = (L^R)^k$, and then it easily follows that $(L^\*)^R = (L^R)^\*$.

To show that $(L^k)^R = (L^R)^k$, notice that: $$ (L^k)^R = \\{ (w\_1\ldots w\_k)^R : w\_1,\ldots,w\_k \in L \\} = \\ \\{w\_k^R \ldots w\_1^R : w\_k,\ldots,w\_1 \in L \\} = \\ \\{z\_k \ldots z\_1 : z\_k,\ldots,z\_1 \in L^R \\} = (L^R)^k. $$ If you want to be more formal, you can prove this by induction on $k$. The crucial observation is $(xy)^R = y^R x^R$, which you can also prove by induction if you want to be very formal.
> 4 votes

# Answer
A proof using the definitions of the operators, as given by Yuval, is the way I would also approach this. As for the question of possible mistakes in your automata, there are two:

* In the first construction, at the very end you mark state $Z$ as accepting, when it shouldn't be.
* In the second construction, when going from $E^R$ to $(E^R)^\*$, you add an $\epsilon$ transition to $B$ from the (non-accepting) state $Y$ rather than from $Z$.
> 2 votes

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


# Question
Title: Prove that the Kolmogorov complexity function cannot be approached from below
How would one go about proving that Kolmogorov function $K(x)$ cannot be approached from below by any computable function?

After some research it seems I must show the function $K(x)$ is not lower semi-computable.

Instead, I can do this by showing $-K(x)$ is not upper semi-computable

Intuitively it seems that $K(x)$, the length of the smallest program computing $x$, can always get smaller, but could be approached using a convergent function... but this is clearly not the case, so I'm obviously a bit lost.

I would be very grateful if someone could explain how I might approach such a proof. I'm more interested in the approach, I might encounter similar questions in an upcoming exam.

Thanks a lot.

# Answer
> 3 votes
We can computably approach $K(x)$ from above by trying all programs. Since $K(x)$ is not computable, we cannot computably approach it from below — otherwise it would have been computable.

---
Tags: computability, computation-models, information-theory, kolmogorov-complexity
---


# Question
Title: Why classification represents all computations?
I'm a computer science student taking a theory of computation class. Recently we were taught about what is computable and what is not and about the Turing machine. As I understood (please correct me if I'm wrong) Turing machine could do any computation that is possible to compute. But for all examples in computing, what my instructor takes are classification (deciding whether the input has a certain characteristic or not) problems.

Does being able to classify anything mean you can do any computation? For example, addition subtraction etc? What is the connection between classification and computation in general?

I referred few books but I couldn't find an answer. Please help.

Thank you, PPG

# Answer
First, you're not entirely correct when you say that a "Turing machine could do any computation that is possible to compute". What you're referring to is known as the *Church-Turing thesis* and it's not a statement of fact, but more like a statement of confidence. A better way of stating it would be "Any task that we would agree would be described as 'computation' can be accomplished by a TM". This wouldn't be true or false until we could somehow formalize the part "... we would agree would be described as computation ...".

One reason that we have for being confident in the C-T thesis is that people have come up with many apparently different ways of modeling what we call computation and in every case it has turned out to be the case that anything that these models can do can also be done by a TM.

Take, for instance, addition. While your instructor may not have shown you, it's not difficult to build a TM that when given two (binary, say) representations of integers, produces on its tape a representation of the number that is the sum of the two original inputs. Any text I know of includes examples of such computations and there are literally hundreds of online examples of TMs that can add, subtract, multiply, compare numbers, and do other tasks that we'd call computation.

In a sense, you can do these computational tasks without explicitly showing how as long as you can decide whether an input string was in a language, which is what you mean by "classification". The classification problems you've seen take the form, I suspect, of "Given a language $L$, make a TM that determines whether of not an input string is in the language". These *decision problems* are just disguised forms of what you've described as "computation".

Here's an example: Suppose you had a language, $A$, consisting of all triples, $(x,y,z)$ where $x,y,z$ were binary representations of integers such that $x+y=z$ and you had a TM, $M$, that when given any such triple, could decide whether or not that triple was in $A$ or not. From this TM, you could make another, $M'$, that would do addition. All it would have to do to add $x$ and $y$ would be to try all possible strings $z$ and for each one use $M$ to decide whether $(x,y,z)$ was in the language $A$. Sure, it would take a long time to come up with an answer, but once you hit upon the right $z$, all that $M'$ would have to do would be to write the $z$ it found on its tape.

That equivalence, between classification and computation, gives some justification for the apparent approach your instructor has adopted (though a weak justification, in my opinion). My advice to you would be to search out some examples of computation, like addition, that would give you an idea about the tasks TMs can do.
> 3 votes

# Answer
Turing machines are commonly used to model computation of *functions* like addition and subtraction. The machine finds its input on the tape when it starts running, and it leaves its output on the tape when it terminates. In this way you can model functions directly.

You can also model functions through decision problems (what you call classification problems). Taking as an example addition, consider the decision problem whose Yes instances are triple $\langle x,y,i \rangle$ such that the $i$th bit of $x+y$ is $1$. If you can solve this decision problem, you can add numbers (and vice versa).

Real life computers are *interactive* — then send and receive information from the outside world. This can be modelled using Turing machine with special tapes which can be used to send messages or to receive them, similar to *oracle tapes* which you will learn about later on.
> 2 votes

---
Tags: computability, decision-problem, computation-models
---


# Question
Title: Derivation of implicational propositional axioms
Is there a way to subtract and add properties of axioms to generate new axioms?

For example:

**{L} = {P S K}** // natural deduction

**{P S K} = {P H K I}** // natural deduction

**{S K} = {?}** // constructive logic

**{K I} = {?}**

Where:

**L = ((A -\> B) -\> C) -\> ((C -\> A) -\> (D -\> A))** // Łukasiewicz's axiom system

**P = ((A -\> B) -\> A) -\> A** // Piece's Law

**H = (A -\> B) -\> ((B -\> C) -\> (A -\> C))** // Weak hypothetical syllogism

**S = (A -\> (B -\> C)) -\> ((A -\> B) -\> (A -\> C))**

**K = A -\> (B -\> A)**

**I = A -\> A**

I want to be able to be able to add and subtract axioms such that **P + S + K = P + H + K + I** implies **S** encodes the properties of **H + I**

I'm probably using unjustified assumptions here. For example, I assume you can derive **S** from **H** and **I**, without using **P** or **K**. Ideally, there would be a way to automate the process of constructing and destructing axioms (though it'd probably be NP hard).

# Answer
The natural way to define your addition operation is as *set intersection*. The value of a single axiom is *the set of all models satisfying the axiom*. The sum of several axioms is then the set of all models satisfying all the axioms.

A similar definition is $\mathbf{A} + \mathbf{B} = \mathbf{A} \land \mathbf{B}$, but then you need to interpret equality as logical equivalence. The definitions then become completely equivalent.

However, you can't "cancel" axioms. If you know that $\mathbf{A}+\mathbf{B} = \mathbf{A}+\mathbf{C}$ then all you can conclude is that in the presence of $\mathbf{A}$, $\mathbf{B}$ and $\mathbf{C}$ are equivalent. As an example, let $\mathbf{A}$ be $x=0$, let $\mathbf{B}$ be $y=1$, and let $\mathbf{C}$ be $x+y=1$. In the presence of $\mathbf{A}$, the axioms $\mathbf{B}$ and $\mathbf{C}$ are equivalent, but in general they aren't.

If are are really keen on the cancellation law, you can always take formal sums. It is then true that $\mathbf{A}+\mathbf{B} = \mathbf{A}+\mathbf{C}$ implies $\mathbf{B}=\mathbf{C}$, but at the cost of $\mathbf{A}+\mathbf{B}$ having no other meaning than the formal sum of $\mathbf{A}$ and $\mathbf{B}$.
> 2 votes

---
Tags: propositional-logic, automated-theorem-proving
---


title: Constructive version of decidability?

text:
# Question
Title: Constructive version of decidability?
Today at lunch, I brought up this issue with my colleagues, and to my surprise, Jeff E.'s argument that the problem is decidable did not convince them (here's a closely related post on mathoverflow). A problem statement that is easier to explain ("is P = NP?") is also decidable: either yes or no, and so one of the two TMs that always output those answers decides the problem. Formally, we can decide the set $S :=\\{|\\{P, NP\\}|\\}$: either the machine that outputs $1$ only for input $1$ and otherwise $0$ decides it, or the machine that does so for input $2$.

One of them boiled it down to basically this objection: if that's how weak the criterion of decidability is - which implies that every question which we can formalize as a language that we can show to be finite is decidable - then we should formalize a criterion that doesn't render any problem with finitely many possible answers that's formalizable in this way decidable. While the following is possibly a stronger criterion, I suggested that maybe this could be made precise by requiring that decidability should depend on being able to show a TM, basically proposing an intuitionist view of the matter (which I don't incline towards - nor do any of my colleagues, all of them accept the law of excluded middle).

Have people formalized and possibly studied a constructive theory of decidability?

# Answer
I think the question you are trying to ask is "is computability theory constructive?". And this is an interesting question, as you may see by this discussion on the Foundations of Mathematics mailing list.

Unsurprisingly, it has been considered, since a lot of recursion theory was developed by people with constructive sensibilities and vice versa. See e.g. Besson's book and the venerable Introduction to Metamathematics. It's pretty clear that the first couple of chapters of recursion theory survive moving to a constructive setting with minimal changes: e.g. the s-n-m theorem, Rice's theorem or the Kleene recursion theorems survive unchanged.

After the first chapters though, things get a bit tougher. In particular, the higher levels of the arithmetic hierarchy are usually defined by a notion of truth. In particular, widely used theorems such as the Low Basis Theorem seem to be explicitly non-constructive.

Perhaps a more pragmatic response, though, is that these "paradoxically computable languages" are simply an idiosyncrasy, that can (and have!) been studied at great length, like non-measurable sets of reals, but that once the initial surprise has been overcome, one can move on to more interesting things.
> 7 votes

# Answer
In classical logic, every statement is either true or false in any given model. For example, any first-order statement about natural numbers is either true or false in the "real world" (known in this context as *true arithmetic*). What about Gödel's incompleteness theorem, then? It just states that no recursively enumerable axiomatization of true arithmetic is complete.

Regarding $\mathsf{P}$ vs. $\mathsf{NP}$, most researchers believe that $\mathsf{P} \neq \mathsf{NP}$, some that $\mathsf{P} = \mathsf{NP}$, and a handful entertain the belief that it is independent of (say) ZFC. Suppose that you're willing to admit that it's in fact *not* independent of ZFC (in the same way that you're willing to admit that ZFC is consistent in the first place). In that case, there is a completely explicit Turing machine that computes your language. The machine searches for proof of either $\mathsf{P} = \mathsf{NP}$ or $\mathsf{P} \neq \mathsf{NP}$ until one is found, and then proceeds accordingly. We can *prove* that this machine accepts your language, even though we still don't know what that language is exactly!

If you're not willing to admit that $\mathsf{P} \stackrel{?}{=} \mathsf{NP}$ is decided by ZFC, then you can still ask whether there is an explicit Turing machine that accepts your language. I leave this mind-boggling question to the interested reader.
> 2 votes

# Answer
(disclaimer, a fuzzy answer to a fuzzy question which maybe fits better on cstheory). constructibility is a "big deal" in theoretical math but it shows up especially in continuous contexts such as the semifamous Banach-Tarski paradox. these paradoxes generally do not seem to have shown up in "more discrete" CS *"so far"*. so what is (the analog/ parallel of) constructibility in CS? the answer seems not so clear. its a concept originating in math research more than CS and the two dont seem to be tied together on this particular crux too much *"so far"*.

one answer is that theory of decidability actually seems to be a variation on constructibility ie it is a strict method of determining which sets are *computable* which appears to be closely connected.

constructibility at heart deals with some issues of "independence from ZFC" and those areas are considered at length in this paper by Aaronson wrt P vs NP, Is P vs NP formally independent?.

its not really shown that "paradoxes" seem to point toward constructibility issues, but one might take that as a rough guide for a rough analogy as in Aaronsons paper where he considers eg oracle results which seem to have some "paradoxical" flavor in particular Baker Gill Solovay 1975 result that oracles exist both such that PA = NPA and PB≠ NPB. other paradoxical like thms are the Blum gap and speedup theorems.

also is it merely a coincidence that CS focuses on "time/ space" *constructible* functions in its fundamental time/ space hierarchy theorems? (which then exclude Blum-like paradoxes almost *"by design"*?)

another answer is that this is under active investigation/ research eg as in this finding. constructibility is known to be tied up with "large cardinals" in math: Winning strategies for infinite games: from large cardinals to computer science / Ressayre.

> Using the large cardinal axiom of “sharps” Martin proved analytic determinacy: the existence of a winning strategy for one of the players in every infinite game of perfect information between two players, provided the winning set of one of the players happens to be an analytic one. I modify and complement his proof so as to obtain a new proof of the Rabin, Buechi-Landweber, Gurevich-Harrington theorem of finite state determinacy: existence of a winning strategy computed by a finite state machine, when the player's winning sets are themselves finite state accepted.
> 1 votes

---
Tags: computability, undecidability
---


# Question
Title: Difference between Dependent type , refinement type and Hoare Logic
I know little dependent type theory. From wikipedia :

> A dependent type is a type whose definition depends on a value.

And from my Type theory course i recall that a dependent type is :

> Family of types indexed by a type.

But i have a confusion regarding dependent types and refinement types and hoare logic.

Because from Depenedent vs refinement type the refinement types looks like a Hoare logic. What more power refinement types gives besides just allowing to state predicated that has to be satisfied (Which looks like nearly same as Hoare Logic)?

What additional thing that dependent type gives in comparison to refinement types ? And is Dependent type more powerful than Refinement types + Sat/Constraint solver.

can anyone clear the air with examples.

# Answer
> 19 votes
There is recent work by Paul-André Melliès and Noam Zeilberger that explores this. In particular the papers Functors are Type Refinement Systems and An Isbell Duality Theorem for Type Refinement Systems. There's also a video of a talk on the first one.

I think there is a lot of confusion around refinement types due to people thinking of *particular* systems as representative which causes goals and details of those particular systems to be attributed to the general idea. The short of it is type refinement systems classify terms that exist independently whereas (non-refinement) types, dependent or otherwise, are part of terms. This may sound familiar and possibly even a bit contradictory.

The potentially familiar and possibly contradictory seeming part comes about if you view types à la Curry (extrinsically) versus types à la Church (intrinsically). When we think of types à la Curry, we think of types as classifying untyped terms that already have meaning. In types à la Church, the only terms that exist are well-typed terms, i.e. the type constraints are part of our syntax. So what I'm saying is that a Curry-style type system is actually a type refinement system refining untyped terms, while a Church-style type system is not a type refinement system. This means that, for example, we can think of the simply typed lambda calculus as either a type refinement system or as a non-refinement type system.

Of course, no one says that our terms have to be untyped terms. We could just as well apply a type refinement system to typed terms, and, historically, this is the context in which refinement types (by that name) arose. However, applications to soft typing illustrate something closer to the situation described above.

So far I haven't said anything about dependent types. The reason is that it is a completely orthogonal concern. I would say the archetypal dependent type systems are usually presented in a Church-style, and thus are not type refinement systems, but NuPRL (based on Computational Type Theory, a variant of the most archetypal dependent type theory, Martin-Löf type theory) is blatantly a type refinement system as I've described. Terms in NuPRL may not even *have* types! Admittedly, the fact that "PRL" stands for "Program Refinement Logic" might be a tip-off too. On the flip side, Refinement Types for ML describes a refinement type system, possibly the origin of the term, which is not a dependent type system in any way.

As for Hoare triples, they are a type refinement system. They are actually used as an example of a type refinement system in the first paper. However, Hoare Type Theory gives something which can be viewed as a non-refinement type system for a language having Hoare triples.

To have an answer about the "power" of different systems, you need to specify a particular (family of) dependent type system(s) and a particular (family of) refinement type system(s). The term "dependent type system" covers a very broad class of type systems, and "type refinement systems" is even broader. Even then, the terms aren't mutually exclusive, so it would not be a comparison between "dependent type systems" and "refinement type systems". However, if by "dependent type system" you are thinking of something like Coq, and for "refinement type system" something like Liquid Types then it is pretty one-sided. Coq is generally viewed as powerful enough to handle virtually all of mathematics in practice; you could literally implement and prove correct a SMT solver within Coq and then use it; and a very close analog to the subset type can be formulated. (NuPRL literally has subset types.) On the other side, SMT solvers are usually restricted to decidable theories where Coq has no such limitation; and many systems like Liquid Types have a limited and non-extensible language for specifying predicates. (Of course, by "dependent type system" you could mean Dependent ML, and by "type refinement system" NuPRL \[which is also a dependent type system\] which would be one-sided in the other way.)

---
Tags: dependent-types, hoare-logic
---


title: Exclusive queue problem

text:
# Question
Title: Exclusive queue problem
There is the exclusive queue problem in The Little Book of Semaphores, which is stated as follows:

Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers, wait in two queues before entering the dance floor. When a leader arrives, it checks to see if there is a follower waiting. If so, they can both proceed. Otherwise it waits. Similarly, when a follower arrives, it checks for a leader and either proceeds or waits, accordingly. Also, there is a constraint that each leader can invoke dance concurrently with only one follower, and vice versa.

The author's solution:

```
leaders = followers = 0
mutex = Semaphore(1)
leaderQueue = Semaphore(0)
followerQueue = Semaphore(0)
rendezvous = Semaphore(0)

def leader_thread():
   mutex.wait()
   if followers > 0:
      followers--
      followerQueue.signal()
   else:
      leaders++
      mutex.signal()
      leaderQueue.wait()

   dance()
   rendezvous.wait()
   mutex.signal()

def follower_thread():
   mutex.wait()
   if leaders > 0:
      leaders--
      leaderQueue.signal()
   else:
      followers++
      mutex.signal()
      followerQueue.wait()

   dance()
   rendezvous.signal()

```

However, I think there is a simpler solution:

```
leader_mutex=Semaphore(1)
follower_mutex=Semaphore(1)
leader_rendezvous=Semaphore(0)
follower_rendezvous=Semaphore(0)

def leader_thread():
   leader_mutex.wait()
   leader_rendezvous.signal()
   follower_rendezvous.wait()
   dance()
   leader_mutex.signal()

def follower_thread():
   follower_mutex.wait()
   follower_rendezvous.signal()
   leader_rendezvous.wait()
   dance()
   follower_mutex.signal()

```

It is quite obvious and very similar to the queue problem solution mentioned in this book, so I wonder why it was not included in the book. Is there something wrong with my solution? Could you prove that my solution is correct?

# Answer
If you suspect that your solution is right, then try to prove it (since we are not dealing with foundations, e.g. how exactly is time represented in our system, the proof will be somewhat informal, but it is still a good way to convince yourself).

Claim 1: No more than one pair of follower and dancer can be at the dance floor concurrently.

This is obvious, since if we have one dancer and one follower dancing then both locks are acquired, and thus no more dancers are able to continue.

Claim 2: If a pair $(f,l)$ is dancing ($f,l$ are follower and leader correspondingly), no other dancers will be able to dance until both $f,l$ are done.

Obviously at least one of the dancers $f,l$ has to finish for others to be able to join (we need to release at least one lock). Suppose $l$ finishes first. More followers cant join unless $f$ is done (lock), so the next dancer has to be a leader. However, the next leader will be stuck waiting for follower\_rendezvous, which will only be signaled when a new follower comes, and for that $f$ must finish dancing as well (to release the lock).

Claims 1,2, together with the observation that a pair of follower and dancer are able to dance concurrently, concludes the proof.
> 2 votes

---
Tags: concurrency, synchronization
---


title: How do computers keep track of time?

text:
# Question
Title: How do computers keep track of time?
How are computers able to tell the correct time and date every time?

Whenever I close the computer (shut it down) all connections and processes inside stop. How is it that when I open the computer again it tells the exact correct time? Does the computer not shut down completely when I shut it down? Are there some processes still running in it? But then how does my laptop tell the correct time when I take out the battery (and thus forcibly stop all processes) and start it again after a few days?

# Answer
> 112 votes
Computers have a "real-time clock" -- a special hardware device (e.g., containing a quartz crystal) on the motherboard that maintains the time. It is always powered, even when you shut your computer off. Also, the motherboard has a small battery that is used to power the clock device even when you disconnect your computer from power. The battery doesn't last forever, but it will last at least a few weeks. This helps the computer keep track of the time even when your computer is shut off. The real-time clock doesn't need much power, so it's not wasting energy. If you take out the clock battery in addition to removing the main battery and disconnecting the power cable then the computer will lose track of time and will ask you to enter the time and date when you restart the computer.

To learn more, see Real-time clock and CMOS battery and Why does my motherboard have a battery.

Also, on many computers, when you connect your computer to an Internet connection, the OS will go find a time server on the network and query the time server for the current time. The OS can use this to very accurately set your computer's local clock. This uses the Network Time Protocol, also called NTP.

# Answer
> 15 votes
If you remove the battery on the motherboard then the computer wouldn't have any way to tell the time.

This is also the case with mobile phones. If you let a phone discharge and then not recharge it for more than a few weeks it will also "forget the time" because the small auxiliary battery is discharged completely and nothing is powering on the real-time clock.

You could try to power on an old mobile phone if you have one and check it yourself to see that it "forgot the time".

This is how the battery looks. https://yandex.com/images/touch/search?text=mobo%20battery&source=tabbar

I had to buy one a few times when mine started to last less then a day. I had to configure the clock everytime i turned on the PC.

# Answer
> 2 votes
When you start Windows, it gains direct access to the memory of the Real Time Clock (RTC) and uses its date and time values to set the computer date and time. Timer interrupts maintain the computer time when Windows is running. A Time Daemon in Windows runs approximately once each hour after the Windows starts. The Time Daemon compares the time in Windows with the time in the RTC. If the two times are more than one minute apart, Windows changes the time and date to match the RTC. You cannot change the time interval for the Time Daemon to run.

If you use a time synchronizing service, such as the TimeServ.exe tool included with the Windows NT 4.0 Resource Kit, the tool updates the time in Windows and the computer's RTC. If the Windows Time Service runs on a Windows 2000 based-computer, the Time Daemon in Windows cannot run approximately one time each hour after the Windows starts.

For more details visit this link:http://msdn2.microsoft.com/en-us/library/ms724936.aspxhttp://msdn2.microsoft.com/en-us/library/ms724942.aspx

---
Tags: computer-architecture, clocks
---


# Question
Title: Is the language of strings with an integer ratio of the number of a's to the number of b's context-free?
Consider the language $L \subseteq \\{a,b,c\\}^\*$, where $w \in L$ if and only if the ratio of the number of $a$'s in $w$ to the number of $b$'s in $w$ is an integer. I've been unable to find a counterexample string in $L$ which I can use to disprove (via a contradiction proof using the pumping lemma for CFLs) that $L$ is a CFL. This suggests that $L$ may be recognized by a nondeterministic PDA.

Now, if $\\#\_a(w) = i\cdot \\#\_b(w)$ for some $i \geq 0$, then I can perfectly match every single $b$ with $i$ $a's$. The problem is that since $i$ can be any nonnegative integer, there are strings in $L$ for which I'd need to match every one $b$ with one $a$, strings for which I'd need to match every two $a$'s with one $b$, and so on. I don't see how a nondeterministic PDA has the capacity to cover all such (i.e., infinitely many) matchings.

# Answer
The language is not a CFL. The string $w$ that is the counter example to the pumping lemma is $a^{(N+1)^2}b^{(N+1)}$ where $N\geq 1$ is the pumping length. The idea is to take the number of $a$'s comparably larger by an order of $N$ to the number of $b$'s. Then if you pump you get strings with $\\#\_a={(N+1)^2+ik\_1}$ and $\\#\_b ={N+1+ik\_2}$ for $i\geq -1$. You would be able to prove that his string does not belong to $L$ for some $i$ and for any $k\_1+k\_2\leq N$.

Or if we take some crazy long string like $w = a^{(2N)!}b^{N+1}$, noting that the pumped string will have $\\#\_a={(2N)!+ik\_1}$ and $\\#\_b={N+1+ik\_2}$ for $i\geq -1$. If $k\_1 = 0$ then we can take $i \> \frac{(2N)! - N -1}{k\_2}$. If $k\_1 \> 0$ then for $i=1$, $\frac{(2N)!+k\_1}{N+1+k\_2}$ is a proper fraction, since $0\leq k\_2 \leq N-1$, $1 \leq k\_1 \leq N$ and therefore $N+1 \leq N+1+k\_2 \leq 2N$ which implies $0\<\frac{k\_1}{N+1+k\_2}\<1$ is a fraction.
> 2 votes

# Answer
You could use Parikh's theorem. Suppose that your language is context-free. Then its commutative image $$ c(L) = \\{(|u|\_a, |u|\_b, |u|\_c) \mid u \in L \\} = \\{ (rn, n, m) \mid r \>0, n \geqslant 0, m \geqslant 0\\} $$ would be a semilinear set of $\mathbb{N}^3$. By projection, the set $R = \\{ (rn, n) \mid r \>0, n \geqslant 0\\}$ would be a semilinear set of $\mathbb{N}^2$. Observe that $$ \\{ (rn, n) \mid r \>1, n \> 1\\} = R \setminus ( S \cup T) $$ with $S = \\{ (n, n) \mid n \geqslant 0\\}$ and $T = \\{ (r, 1) \mid r \>0\\})$. Since $S$ and $T$ are semilinear and since semilinear sets are closed under Boolean operations, the set $\\{ (rn, n) \mid r \>1, n \> 1\\}$ would be semilinear. Thus its projection $\\{ rn \mid r \>1, n \> 1\\}$ would be a semilinear set of $\mathbb{N}$, and so would be its complement $\\{0,1\\} \cup \\{ p \mid p \text{ is prime }\\}$, which is certainly not the case. Thus $L$ is not context-free.
> 1 votes

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


title: First Harshad number with given sum

text:
# Question
Title: First Harshad number with given sum
How can we compute the least Harshad number with given sum of decimal digits $S$? Harshad number in base 10 is any number divisible by sum of its decimal digits.

I think that some kind of dynamic programming should be used. But which one?

Thanks in advance for any ideas.

# Answer
> 2 votes
You solve the following more general problem: find the least number $N$ with sum of digits $T$ such that $N \mod M = R$ (the inputs are $M,T,R$). Initially, $T=M=S$ and $R=0$. Now you go over all possible least significant digits $b$. Using the formula $$ (10n+b) \pmod{M} = 10(n \pmod{M}) + (b \pmod{M}), $$ you reduce the problem to a smaller one, and so on.

The total amount of work appears to be $O(S^2)$, since the number of possible values for $T$ and $R$ is $O(S^2)$. Care needs to be taken with zero digits, however, a detail which I leave you to ponder.

---
Tags: dynamic-programming, number-theory
---


title: Why is (small) $o(n^2) \neq n^2$?

text:
# Question
Title: Why is (small) $o(n^2) \neq n^2$?
We know that $10n^2 = O(n^2)$ but $10n^2 \neq o(n^2)$. What is the underlying principle?

# Answer
> 5 votes
The *underlying principle* is that the definitions of *small o* and *big O* are different.

## Big O definition

$O(f(n)) = \\{g(n) | \exists c \> 0, \exists n\_0 \> 0, \forall n \> n\_0 : 0 \leq g(n) \leq c\*f(n)\\}$

In words:

$g(n)$ is an element of $O(f(n))$ if there exists a $c \> 0$ and a $n\_0 \> 0$ such that for all $n \> n\_0$, $0 \leq g(n) \leq c\*g(n)$

In your example $f(n) = n^2$ and $g(n) = 10n^2$

If we pick $c = 20$, $n\_0 = 1$, you can check that for all $n \> 1$, $0 \leq 10n^2 \leq 20\*n^2$, so $10n^2 \in O(n^2)$

## Small O definition

$o(f(n)) = \\{g(n) | \forall c \> 0, \exists n\_0 \> 0, \forall n \> n\_0 : 0 \leq g(n) \< c\*f(n)\\}$

In words:

$g(n)$ is an element of $o(f(n))$ if for any $c \> 0$, there exists a $n\_0 \> 0$ so that for all $n \> n\_0$, $0 \leq g(n) \< c\*f(n)$.

In your example $f(n) = n^2$ and $g(n) = 10n^2$

If we pick $c = 1$, you can check that there is no $n\_0 \> 0$ so that for all $n \> n\_0$, $0 \leq 10n^2 \< 1\*n^2$

Therefore the condition does not hold and $10n^2 \notin o(n^2)$.

## Informal explanation

$g(n) \in O(f(n))$ if $g(n)$ *grows* slower than or in the same fashion as $f(n)$. $g(n) = 10n^2$ grows in the same fashion (quadratically) as $f(n) = n^2$, so $10n^2 \in O(n^2)$.

$g(n) \in o(f(n))$ if $g(n)$ *grows* **strictly** slower than $f(n)$. $g(n) = 10n^2$ grows in the same fashion and thus not strictly slower than $f(n) = n^2$, so $10n^2 \notin o(n^2)$

NOTE: I've used notation like $10n^2 \in O(n^2)$ because the definitions were actually sets. But in practice, there's accepted notation abuse and $10n^2 = O(n^2)$ is written instead.

---
Tags: asymptotics
---


# Question
Title: The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable?
I have often read that Hindley-Milner extended to allow polymorphic recursion is *undecidable*. However is the term used what is actually meant? Or do people actually mean *semidecidable* when they mention that?

I ask this before I've recently found a paper where such a type system is presented and an algorithm based on the search of a fixed-point allows type inference for the type system. The trick is that you can fix a number $k$ of iterations for the search to maintain decidability of such a type system. If you cannot find a fixed point you can use the usual ML rules to try to type the program disallowing polymorphic recursion.

The authors proved that, given a well-typed expression $s$ there exist $k \in \mathbb{N}$ such that you can type the expression with the correct type limiting the number of iterations to $k$.

Now, I think this implies *semidecidability* of type inference with polymorphic recursion in such a case. If we allow $k = +\infty$ what would happen is that the algorithm would always terminate for well-typed expression, but could not terminate for non-well typed expressions.

Am I correct in this conclusion or is there some hidden issue I didn't understand?

# Answer
> -5 votes
Yes, I was right. People in the field use the term undecidable to mean semidecidable. In fact, it seems like this is done in *most* fields.

# Answer
> 5 votes
The answer you gave is right, but I'd like to stress the relationship between the two terms.

A formal language is **decidable** if and only if there exists an algorithm which correctly accepts or rejects every input in finite time. We also say it's **computable**.

A formal language is **undecidable** if and only if it is *not* decidable.

A formal language is **semidecidable** if and only if an algorithm exists that recognizing an input that is in the language. In particular, all decidable languages are semidecidable! However the halting problem is an example of a semidecidable language that is also undecidable. The complement of the halting problem is not even semidecidable.

We say type inference is undecidable rather than semidecidable (even though both characterizations are true) because the former is usually more relevant.

---
Tags: type-inference, semi-decidability
---


title: implementing simple elvator algoirthm

text:
# Question
Title: implementing simple elvator algoirthm
I want to implement simple elevator algoirthm.

people in different floors orders the elevator and the destination floor they want to get to (so you get a {from,to} alert from different floors).

So I got a simple strightforward solution :

once elevator start going in specific direction (lets say up) it will continue doing so , and serve all request of ppl want to go up (only if at the time they were made they were from higher floor in respect to the elevator) until serving the last one. all the request will be kept in an array, so on each floor you can check if someone wants to go on the same current direction.

In addition ill save in two vars (on for up direction and one for down direction) the highest and lowest points of request - hight floor that somebody wants to go up from there , and lowest floor that sombody want to get to lower floors from there - and the elevator allways will be travling between these two points picking all the ppl that want to go on the same direction.

Does this solution make sense/work ? is there something as simple that make more sense?

I saw some **priorities queue** suggestions while searching in google but didnt really understand what the need of them ..

Thanks for your feedback .

# Answer
> 0 votes
Of course your approach will *work* but the answer to your question: "Does this solution make sense?" is entirely dependent on the situation.

**Priority Queues** are used (e.g.) when you want to serve the passenger whoever's destination floor is closest to the current one. Said passenger will have very high priority. This has a disadvantage that when a passenger wants to go to a floor that is far away from the current one, he will be assigned a very low priority and will be served never/late. This can be solved by increasing the priority for a passenger over time.

**Your approach** has the advantage that there's a maximum waiting time known for all passengers. That is, the time it takes for a person to go to floor 1 when he gets in at floor 2 while the elevator is going up all the way to the penthouse and it stops at all floors along the way. The advantage of knowing this isn't present in the case (or it is at least not easy) in the priority queue approach. But you can imagine that the situation described can be very annoying for the involved passenger since he will have to travel along the full building almost twice to lower just one floor.

**Another approach** I'm thinking of while writing this makes use of priority queues where the priority of going to a floor is the number of people that needs to get in/off at that floor.

In conclusion, I think the advantage of your approach isn't very useful and it has a big disadvantage as well. I would look into priority queues and then define for yourself what priority means. Maybe your priority is to deliver groups of people to floors at once (last approach) or maybe it's to deliver the passenger whoever's floor is closest, (first approach). As said before, deciding if an approach is good depends entirely on the situation.

---
Tags: algorithms
---


title: Incremental compilation over AST

text:
# Question
Title: Incremental compilation over AST
Is incremental compilation ever done based on the AST? That is, the compiler would just regenerate code for the parts of the AST that have changed.

I know that many compilers do incremental compilation on a file-basis, but I don't know about on an AST-basis.

# Answer
The Eclipse Builder infrastructure actually does this, I believe. You might find this link useful.
> 1 votes

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


# Question
Title: How to detect intersecting segments based on length of the segments
As part of a larger problem, I am trying to detect based on the distance matrix which segments intersect in the original 2D space that originated the matrix. I don´t have coordinates (lat/long, x/y or any other for the points).

As an example, on the image below, the answer to the question for the top graph would be: AD, BC. While for the bottom graph would be AC, BD.

The information that we have is just the distance matrix:

DISTANCE MATRIX TOP

$ \begin{align} && A && B && C && D \\ A&& 0 && 1 && 1 && \sqrt{2} \\ B&& 1 && 0 && \sqrt{2} && 1 \\ C&& 1 && \sqrt{2} && 0 && 1 \\ D&& \sqrt{2} && 1 && 1 && 0 \end{align} $

DISTANCE MATRIX BOTTOM

$ \begin{align} && A && B && C && D \\ A&& 0 && 1 && 1 && \sqrt{2} \\ B&& 1 && 0 && \sqrt{2} && \sqrt{5} \\ C&& 1 && \sqrt{2} && 0 && 1 \\ D&& \sqrt{2} && \sqrt{5} && 1 && 0 \end{align} $

I have tried so far to use the triangular inequality and some other (probably) naive geometric knowledge but I can´t figure out what conditions must be met.

# Answer
First assume that you know where $A,B,C,D$ are. In this case, you can write $D$ uniquely in the form $\alpha\_A A + \alpha\_B B + \alpha\_C C$, with $\alpha\_A + \alpha\_B + \alpha\_C = 1$. The tuple $(\alpha\_A,\alpha\_B,\alpha\_C)$ are called the barycentric coordinates of $D$. You can read off which of the segments $Dx$ ($x\in \\{A,B,C\\}$) cross a side of the triangle $ABC$ from the sign pattern of the barycentric coordinates.

It's not particularly difficult to find suitable coordinates either. You can just assume that $A=(0,0)$, $B=(d(A,B),0)$, and $C$ is either intersection point of the appropriate circles around $A$ and $B$. This will then uniquely determine $D$ by intersecting three circles.
> 3 votes

---
Tags: graphs, computational-geometry, euclidean-distance
---


title: Boolean expression logic law confusion

text:
# Question
Title: Boolean expression logic law confusion
I've been trying to attempt a particular question that I need to translate truth table into boolean expression but I'm completely stuck on one point now.

First, I worked it out by using Sums of product by getting X first.

(I did this by taking the inputs with X = 1)

A'B'C'D' + A'B'C'D + A'B'CD + A'BC'D' + A'BCD' + A'BCD +AB'C'D + AB'CD + ABC'D' + ABC'D

= A'B'C'(D'+D) + A'CD(B'+B) + A'BC(D+D') + AB'D(C'+C) + ABC'(D'+D) (Distributive Law)

= A'B'C' + A'CD + A'BC + AB'D + ABC' (Double Complement Law)

\[Currently I'm stuck here and don't know how to proceed\]

# Answer
> 0 votes
If you want to obtain a minimal DNF in this way, it is generally a good idea to follow the Quine-McCluskey algorithm (https://en.wikipedia.org/wiki/Quine-McCluskey\_algorithm). Otherwise, it is easy to get stuck when you use distributivity to combine each term with just one of several possible partners (if you look at your kmap, this would correspond to arranging the $1$ into pairs in such a way that none of them combine into larger blocks).

One other problem with your computation is that you lost the term $A'BC'D'$ when forming pairs (the reason why you still ended up with five pairs os that $A'BCD$ is covered twice).

---
Tags: logic, boolean-algebra, karnaugh-map
---


# Question
Title: How do I simplify this boolean expression?
I have constructed truth tables to prove that: $ABC + ABC'+ AB'C +A'BC = AB+AC+BC$

How do I prove it by simplifying the expression? I know that I can simplify: $ABC + ABC' = AB(C+C')=AB$. However I can't repeat this for $AB'C$ or $A'BC$, to get the answer I desire.

I'm fairly new to boolean algebra and have tried to use the basic identities to figure it out, but can't seem to get there.

# Answer
$ \begin{align} ABC + ABC' + AB'C + A'BC = \\ ABC + ABC + ABC + ABC' + AB'C + A'BC = & & & \text{(2x Idempotency)}\\ AB(C + C') + ABC + ABC + AB'C + A'BC = & & &\text{(Distribution)}\\ AB + ABC + ABC + AB'C + A'BC = & & & \text{(Negation)}\\ AB + (AB + AB')C + (AB + A'B)C = & & & \text{(2x Distribution)} \\ AB + (A(B+B'))C + ((A+A')B)C = & & & \text {(2x Distribution)} \\ AB + AC + BC & & & \text{(2x Negation)} \end{align} $

I'm not proficient at this kind of derivations so please correct any notation/terminology
> 1 votes

# Answer
Idempotency: ABC = ABC + ABC.
> 0 votes

---
Tags: boolean-algebra
---


# Question
Title: Complexity of Independent Set on Triangle-Free Planar Cubic Graphs
I know that **IS** (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and **IS** on triangle-free graphs is also NP-Complete. But how about **IS** on triangle-free planar cubic graphs? Is it still an NP-Complete problem, or there are some polynomial time solutions?

Any ideas or referrences are appreciated, thank you in advance!

# Answer
> 6 votes
Independent Set is $\mathsf{NP}$-hard even for $3$-connected cubic planar triangle-free graphs, as shown in this nice short note.

# Answer
> 4 votes
This paper shows that independent set is NP-complete for triangle-free planar graphs whose maximum degree is at most three (Theorem 2 with $\mathcal{F} = \\{\triangle\\}$). This is almost what you want (you want the graph to be 3-regular), and presumably with some work you could modify the proof to get exactly what you want.

# Answer
> 2 votes
Unfortunately Uehara's proof is wrong. If we consider planar subcubic graphs from Johnson's "Rectilinear Steiner Tree" paper then they could be disconnected and all this stuff with gadgets does not work. Also it does not lead to cubic ($3$-regular) planar graph: when replacing some vertex of degree 2 from the cycle around vertex of degree 1 with the gadget we again have some gadget vertex of degree 2 so the reduction process is infinite.

There is a Mohar's paper Face Covers and the Genus Problem for Apex Graphs that does contain correct proof of NP-hardness of MIS over 2-connected 3-regular planar graphs which involves Kratovchil superresult of NP-hardness of planar 3-connected 3-SAT. I suppose NP-hardness under your setting could be obtained by applying mentioned Mohar's result with Uehara's technique.

---
Tags: complexity-theory, graphs, time-complexity, np-complete
---


# Question
Title: How would I write an if-statement in continuation passing style without an if-statement?
Using continuation passing style, many common language constructs can be written in a simple language with recursion, including loops (using trampolining), exceptions, generators and even function returns. I have found numerous examples of other language constructs, but all examples I have seen use if-statements directly. Noting the power of CPS, I got curious: Can one write an if-statement in CPS without using an if-statement directly?

The naive attempt would be something along these lines:

```
if_cps(condition, true_body, false_body, current_continuation)
{
    if(condition) true_body(current_continuation);
    else false_body(current_continuation);
}

```

but obviously this is a failure, since I used an if-statement directly.

# Answer
OK, so following the advice given by @Andrej Bauer (in the comments to my question) and @Derek Elkins (in his answer), it seems that we can actually do if-statements in CPS!

I will attempt to write out the suggested answer:

The idea is to do booleans in pure Lambda calculus, e.g. using Church encoding. The CPS version would be like this:

```
true(a, b, continuation)
{
    a(continuation);
}

false(a, b, continuation)
{
    b(continuation);
}

if_cps(condition, true_body, false_body, current_continuation)
{
     condition(true_body, false_body, current_continuation);
}

```

To use `if_cps`, we would do like this:

1. Make a closure that captures the variables needed and assign it to `true_body`
2. Make a closure that captures the variables needed and assign it to `false_body`
3. Assign one of the `true` or `false` functions to `condition`
4. Call `if_cps` with the parameters above as well as the continuation.

The `true_body` and `false_body` closures need to be arity one functions, taking the continuation as a parameter.
> 4 votes

# Answer
I think you are over-attributing things to CPS. First, CPS lets you *model* exceptions, generators, and functional calls, but it doesn't create them. For example, modeling exceptions with CPS only gives me exception-like behavior in code that is itself in CPS. I can, of course, use CPS as an implementation mechanism, an intermediate language, for exceptions or generators. Compare this to a language with first-class continuations, e.g. Scheme's `call-with-current-continuation`. With *that*, I could implement exceptions as a library.

Second, recursion gives you loops, not CPS. If you had a language which couldn't express recursion nor had built-in loops, CPS transforming would clearly not change this. You also don't need CPS to express loops as recursion, though it may be useful for things like `break` and `continue`.

To address your specific question, in some sense `if` is part of the definition of booleans. If you want to do anything non-trivial with a boolean, you must at some point use `if`. You could choose a different, non-abstract representation of booleans via their Church encoding, but converting the "native" booleans to this representation would require `if`, and at any rate this would just be word play. While our `if-cps` would not require using `if` in this representation, this would only be because `if` is represented by the identity function in this representation. Or to put it another way, we *are* using this representation's `if`.
> 4 votes

---
Tags: continuations
---


# Question
Title: What is the difference between formal language, regular language and regular expression?
I want to know the difference between these three languages and it would be great if you would give some examples as well.

# Answer
> 8 votes
An *alphabet* $\Sigma$ is a finite collection of symbols. For example, $\Sigma = \\{0,1\\}$.

A *word* over an alphabet $\Sigma$ is a finite sequence of letters from $\Sigma$. For example, $0$, $01$ and $1110$ are all words over $\\{0,1\\}$. The empty word (that is, the empty sequence) is also allowed, and denoted $\epsilon$ (or sometimes $\lambda$).

The collection of all words over $\Sigma$ is denoted $\Sigma^\*$.

A *formal language* over an alphabet $\Sigma$ is a set of words over $\Sigma$. Equivalently, a formal language over $\Sigma$ is a subset of $\Sigma^\*$.

A *regular language* over $\Sigma$ is a formal language over $\Sigma$ which is accepted by some DFA.

A *regular expression* over $\Sigma$ has the following syntax:

1. $\epsilon$ is a regular expression.
2. $\sigma$ is a regular expression for all $\sigma \in \Sigma$.
3. If $r\_1,r\_2$ are regular expressions then so are $(r\_1)^\*$, $(r\_1+r\_2)$ and $(r\_1r\_2)$.

In practice we don't write all the parentheses. Each regular expression denotes some formal language (you will learn this translation in class). It turns out that a formal language is regular if and only if there is some regular expression denoting it.

If you have any more questions, I recommend reading a textbook which covers regular languages, for example Hopcroft and Ullman.

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


# Question
Title: Question on the properties of red black trees
**Problem statement**

Let $T$ be a red black tree and $u$ some internal node of $T$. Suppose that in the left subtree of $u$ we have $n$ nodes. What is the maximum number of nodes that we can have in the right subtree of $u$, before the properties of the red black tree are broken?

**Attempt at a solution**

I was given the answer $O(n^2)$ (past exam sheet question with the answer marked). However, I don't think it's correct, unless I have misunderstood the problem.

According to CLRS the properties of a red black tree are the following:

1. Every node is either red or black
2. The root is black
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Since we are in some internal node $u$, from the properties we infer that all simple paths starting from $u$ and ending in some leaf, should contain the same number of black nodes.

We are given that in the left subtree of $u$ we have $n$ nodes, and our goal is to maximize the number of nodes that we have in the right subtree. It seems natural to assume that the left subtree is a chain containing $n$ black nodes, because in this way, we can make the right subtree of $u$ be a complete binary tree, where every simple path starting from the root of the subtree and ending in some leaf contains exactly $n$ black nodes. And not only that, we can also in the end add red levels of nodes in between black levels, thus increasing the size of the right subtree by 2.

Reducing the black height of the left subtree, will only imply fewer nodes in the right subtree.

So lets find the number of nodes in the right subtree. Essentially we have a complete binary tree of height $n$, so the number of nodes will be:

$S = \sum\_{i=0}^{n-1}2^n$

$-2S = \sum\_{i=1}^{n}2^n$

$S(1-2) = 1 - 2^n$

$S = 2^n - 1$

so the answer is $O(2^n)$. Am I wrong or was there a typo in the exam sheet?

# Answer
> 4 votes
The left subtree cannot be a chain of $n$ black nodes, since it breaks the red-black tree properties.

In the worst case scenario, the left subtree is a minimal black binary tree of height $\log n$, while the right subtree is a full maximal binary tree of height $2\log n$.

The black height of the right subtree must be $\log n$ as well, therefore its maximal total height (including red nodes) is $2\log n$. Since it is a maximal binary tree, it has $ 2^{2\log n} = 2^{\log n^2} = n^2 $ nodes.

---
Tags: algorithms, trees, binary-trees, search-trees, balanced-search-trees
---


# Question
Title: Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?
I just wrote a program that runs the Travelling Salesman Problem using the Nearest Neighbor Algorithm. Afterwards, I started looking into Minimum Spanning Trees (MST).

From my understanding:

The Nearest Neighbor Algorithm traverses a graph starting at one vertex, and then it travels to the next vertex following the edge with the shortest distance (lightest weight) between them.

An MST is a subgraph of the original graph whose vertices are all connected. The total of the edge weights in the subgraph should be as small as possible. You can use Kruskal's algorithm to find MSTs.

As I was looking at the paths taken when implementing the Nearest Neighbor Algorithm, I noticed that it could possibly sometimes return a MST.

**Is the Nearest Neighbor Algorithm a valid algorithm to find a Minimum Spanning Tree?**

It seems like it should be. It's terribly similar to Kruskal's algorithm (from what I have read so far). However, I never see it listed as a possible option for finding MSTs.

Thanks for any help in advance.

**Edit for clarity:**

The Nearest Neighbor Algorithm is described here. From what I read, it works like so:

```
startVertex = vertex V
for (egdes : totalEdges){
    find the edge with the smallest weight connected to vertex V that has    not been visited
}
nextVertex = vertex on the other end of the edge with the smallest weight
move to nextVertex

```

Here is an example:
Each vertex is visited and, looking at the red lines, you get an MST for that graph.

If you do that, you get an MST. My question is, is that a valid way of getting an MST? It seems like it is since it's so much like Kruskal's or Prim's algorithm.

# Answer
Your algorithm starts at some vertex and then always move to the closest vertex that's not been visited so far. That's not guaranteed to find the minimum spanning tree, as the example in your question shows.

First, in a general graph, the algorithm might get stuck: you might end up at a vertex where you've already visited all the neighbours. For example, if you start your algorithm at $D$, it will go to $B$, then $C$ and then it's stuck because it's already visited both of $D$'s neighbours. The set-up of Hamiltonian cycle avoids this possibility by having an edge between every pair of vertices.

Second, even if your graph contains every possible edge, the algorithm can only produce a path, so it won't produce the minimum spanning tree in any graph where the M.S.T. isn't a path. For example, take vertices $\\{1, \dots, n\\}$ with $w(1,i)=1$ for all $i$ and $w(i,j)=2$ for all $i,j\geq 2$. The M.S.T. is all the edges from $1$, and this has weight $n-1$. But your algorithm will find some path that uses only one or two of the weight-$1$ edges, so will have weight $2n-3$ or $2n-4$.
> 4 votes

# Answer
Your algorithm (if I understand it correctly) is known as Prim's algorithm, another algorithm that finds a minimum spanning tree.
> 0 votes

---
Tags: graphs, graph-traversal, minimum-spanning-tree, nearest-neighbour
---


# Question
Title: How to prove that the decidable languages are closed against iteration only by enumerators?
We have the $L\in R$, how can we prove that $L^\*\in R$ only by enumerators?

I try to use induction, but as I understand I wrong...
I'd like to get any help!

# Answer
> 1 votes
I don't really see how to use induction here.

Let's take as an example $L = \\{0,1\\}$. Then $L^\* = \\{\epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\\}$. You probably know how to enumerate $L^\*$. Same thing works if $L = \\{w\_0,w\_1\\}$ for two arbitrary words.

The next step is to handle a language with infinitely many words. Following the earlier convention, I'll just indicate how to solve it for the special in which $L = \mathbb{N}$, and instead of $L^\*$ I will use comma-separated sequences. Here is my enumeration: $$ \epsilon; 1; 2; 1,1; 3; 1,2; 2,1; 1,1,1; 4; \ldots $$ and so on. See if you can figure out a pattern (or if you don't like my pattern, come up with a different one).

---
Tags: computability, closure-properties, enumeration
---


# Question
Title: Achieving better than the theoretical False Positive Rate for Bloom Filters
I implemented a standard Bloom Filter in C++, and tested it on different sizes, with varying values of the ratio ${c = n/m}$ where ${n}$ is the size of the filter, and ${m}$ is the number of elements inserted.

For a Bloom Filter, I created ${k}$ Hash functions, and set the value in the filter for each Hash Index returned. Here's a graph of the results I obtained from my tests:

The problem from the graph is clear, I am getting False Positive rates that are better than the Theoretical value. The theoretical value is based on the assumption that each Hash Index is equally likely, which is:

$ Pr(H(a) = 1)^k = 1 - Pr(H(a) = 0)\\ = (1 - (1 - 1/n)^{km})^{k}\\ = (1 - e^{-k/c})^{k} $

Using $k = c \ln(2)$

$ Pr(H(a) = 1)^{k} = (1 - e^{-\ln(2)})^{k}\\ = (1/2)^{c \ln(2)}\\ = 0.6185^{c} $

All my tests are based on the optimal value of $k = c \ln(2)$, and the theoretical line is a plot of $0.6185^{c}$. My concern is that my False Positive rates are consistently better than the theoretical. Does this mean that my implementation is incorrect, or is it a likely possibility given the large sizes of the Bloom Filters and the efficiency of the hashing algorithm?

I appreciate any guidance on this.

# Answer
The approximation of probability you are calculating is used to give estimated optimal number of hash function used (which is then rounded, $c\*ln(2)$ does not look like integer).

There are many factors that should be considered: the choice of hash functions, data set provided for tests, approximation skew, rounding of approximation and fact that given theoretical bound is asymptotic value, so works better for bigger *n and m*.

I would like to propose paper false-positive rate of Bloom filters, showing how given approximation is incorrect.
Another good resource Thomas Gerbet, Amrit Kumar, C´edric Lauradoux. The Power of Evil Choices in Bloom Filters. (Research Report) RR-8627, INRIA Grenoble. 2014 shows how saturation of filter changes with given data.
> 0 votes

# Answer
Your question includes the equation

$$ (1 - (1 - 1/n)^{km})^{k} = (1 - e^{-k/c})^{k} $$

But that is not actually an equation; it is only an approximation.
> 2 votes

---
Tags: algorithms, data-structures, statistics, bloom-filters
---


# Question
Title: half precision floating point multiplication
A = 0 10011 0011110111

B = 1 00011 0010011000

exponent is 15, mantissa is 10 bits and first bit is implicit. Can somebody please tell me the final answer cause I am having trouble figuring out what is happening with exponent since there are 3 extra zeroes in front of mantissa multiplication. I got that exponent is 7(00111 in binary). Thanks in advance

# Answer
> 1 votes
When multiplying floating points:

1. we add the (real) exponents, to get the output exponent
2. we multiply the two mantissas (remember the implied 1), round and shift as necessary.

So the new exponent is $E=(19-15) + (3-15)= -8$.

The multiplication of the mantissas give $$1.0011110111\_2 \times = 1.0010011000\_2 = 1.01101100111010101$$

taking only 10 digits (rounding down, see here) we get $M= 0110110011$.

The sign is a minus.

So the output is $Out= 1\ 00111\ 0110110011$.

For sanity check, let's convert to decimal and see that it makes sense.

$A = (-1)^0 \times 2^{4} \times 1.2412109\_{10} = 19.8593744$

$B = (-1)^1 \times 2^{-12} \times 1.1484375\_{10} = -0.0002804 $

Then,

$A\cdot B = -0.0055686$

We can convert $Out$ from above to decimal, and get $Out = (-1)^1 \times 2^{-8} \times 1.4248047 = -0.0055656$ and the error is $0.000003 \approx 2^{-18}$ which makes sense (since the real exponent is $2^{-8}$ and we have a 10 digit significand)

---

See also https://oletus.github.io/float16-simulator.js/ for a calculator, and https://en.wikipedia.org/wiki/Half-precision\_floating-point\_format or https://en.wikipedia.org/wiki/Floating\_point for definition and some more explanations.

---
Tags: arithmetic, floating-point
---


# Question
Title: Is there a way to compute time without system clock
I was thinking about any method where we can use RAM I/O speed, to calculate time, let's say for example: RAM transfer rate is 1000 MB/s, so when it's half full (about 500 M Bytes written), by dividing 500 by 1000 we get the time which is epoch + 0.5 seconds so all in all we have three routines:

1. one for writing data (zeros for example) into RAM
2. another one for checking when a specific size is full
3. and the third for calculating time

> Note: Sorry if it sounds stupid, because this is not my study field,

# Answer
You could try to measure time from RAM transfer rates. You'd need to know the precise clock ratio between the RAM and the CPU. There would have to *be* a precise clock ratio; I don't think this is the case on typical PC architectures as the RAM and the CPU have their own clock and I'm not sure the RAM peak transfer rate is a constant.

You'd need to block all other sources of interrupts, because if the CPU is responding to some other interrupt, it may notice too late that the RAM is ready, so it would tend to drift.

The nail in the coffin is that while the CPU is waiting for the RAM, it isn't doing anything else. The same objection goes for anything that requires the CPU to perform computations to obtain the time — a CPU that does nothing but measure the time has no time left to do useful things.
> 5 votes

# Answer
On some video-gaming platforms where the performance characteristics are very rigidly defined and consistent, you can make a very good approximation of elapsed time by counting how many frames have elapsed. For example, if the hardware is designed to refresh the screen every 1/60th of a second, and you are able to detect each time the screen refreshes, you can make a good approximation that 1 second has passed for every 60 refreshes. This allows you to track with decent accuracy the amount of time since the system or application was started; if you punched in the real time when the program started, you could then approximate the real time as long as the program was running.

Some console games measure time based on how many new frames have been drawn, rather than by how many screen refreshes have taken place, and thus you can observe in-game timers actually slowing down if the framerate decreases.
> 2 votes

# Answer
Like you suggest, there would be ways in specific environments to measure time indirectly, but, as the commenters say, most environments would have heavy constraints making this very unwieldy. For example, the moment you have any non-maskable interrupts (not even full multi-tasking), you need to cater for those interruptions.
> 1 votes

---
Tags: operating-systems, clocks
---


# Question
Title: What happens when ε-clos(X) contains duplicate elements? Example: (1+0)*1
I am learning about state machines from the Stanford online cs143 course. Here I have tried to build a nondeterministic finite automaton for the regular expression `(1+0)*1`, but when I attempt to convert it to a DFA I find that the epsilon closure of the initial state A ends up having two outputs for the value `1`, which I imagine would be impossible for a deterministic automaton.

I understand that my NFA differs from the instructors, but I'm unsure of whether or not it is valid. If it is valid, why am I having difficulty converting it to a DFA?

# Answer
Yes, your NFA is correct. You are probably making some mistake during your conversion to a DFA.

Note that after the conversion from the NFA to the DFA, the states will no longer be $S = \\{A,B,C,D,E\\}$. Instead they will be all possible subsets of $S$. So in your case $A$ is not giving two different transitions to $C$ and $E$, instead it is giving one single transition to the state $\\{C,E\\}$
> 2 votes

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