# Question
Title: Worst-case input for median-of-medians with groups of size 3
Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a recurrence of:

$$\begin{align\*} T(n) & \leq T(n/3) + T(2n/3) + O(n)\\ & = O(n \log n) \end{align\*}$$

However, this assumes that there exists an input which would always split the recurrence in the worst possible case. I am not convinced that this input always exists.

**Question**: Is there a general procedure to create a worst-case input for the median-of-medians algorithm with $k=3$ for an input of any length $n$?

If it helps, you can assume $n$ is of some particular format and that we are always searching for the exact median (as opposed to querying the $i$-th order statistic). You can also assume that the algorithm groups elements deterministically (e.g. incrementally group 3 elements).

---

You can choose any deterministic implementation if it helps, here is one for reference. Given an input array $A$ of $n$ distinct elements and query $i$ for the $i$-th order statistic, the $\mathrm{SELECT}(A, i)$ procedure is as follows:

1. Divide $A$ into $\lfloor \tfrac{n}{3} \rfloor$ groups of length $3$.
    * We can do this by putting $\\{a\_1, a\_2, a\_3\\}$ as group $G\_1$, then $\\{a\_4, a\_5, a\_6\\}$ as group $G\_2$, and so on...
    * If $n \neq 3k$ then we can create one more group with the remaining 1 or 2 elements.
2. Find the median of each group $G\_i$ and store them in a list $M$.
    * We can do this by creating $M = \[\mathrm{med}(G\_1), \mathrm{med}(G\_2), \ldots \]$.
3. Recursively call this function to get the median of medians $x = \mathrm{SELECT}(M, \lfloor \tfrac{n}{6}\rfloor)$.
4. Partition $A$ about $x$ into $A\_1$ and $A\_2$.
    * Let all elements in $A\_1$ be less than $x$. (Assume order is retained)
    * Let all elements in $A\_2$ be greater than $x$. (Assume order is retained)
5. If $i = |A\_1| + 1$ return $x$
6. If $i \< |A\_1| + 1$ return $\mathrm{SELECT}(A\_1, i)$.
7. If $i \> |A\_1| + 1$ return $\mathrm{SELECT}(A\_2, i - |A\_1| - 1)$.

---

The biggest issue I am having for constructing a worst case input, is that we need $A$, $M$, and $A\_1$ or $A\_2$ to exhibit worst-case behavior. Since $M$ is nested in $A$ and $A\_1$ or $A\_2$ are subsets of $A$, getting all of this coordinated is very difficult.

---

Additional Notes:

We can always show that the initial recurrence will split into a problem of size $n/3$ and $2n/3$, perhaps we can also do this for the next level down, however I doubt it can be done consistently for levels below. This is relevant and important, because if you can show that our second recurrence will in fact be on something less than $2n/3$, then we have a linear time algorithm! This is because we'd get a recurrence:

$$T(n) \leq T(n/3) + T(\alpha n) + O(n)$$

Where $\alpha \< 2/3$ thus, by the uneven split theorem this must be linear a la $T(n) = O(n)$.

# Answer
> 8 votes
Whether or not the median-of-medians algorithm with groups of size 3 runs in linear time is an open problem as said in \[1\] (while they proposed a variant running in linear time). I checked some follow-up papers and no one has a progress on showing the complexity of this algorithm. I believe it still remains open now.

---

\[1\] Chen, K., & Dumitrescu, A. (2015, August). Select with groups of 3 or 4. In *Workshop on Algorithms and Data Structures* (pp. 189-199). Springer, Cham.

---
Tags: algorithm-analysis, recursion, open-problem
---


title: pure function in C

text:
# Question
Title: pure function in C
There does not seem to be a canonical definition of "pure function", but the widespread language-agnostic understanding seems to be a function that

* has no side effects
* produces a value that is completely and uniquely determined by its explicit arguments

This appears to beg a question when the arguments are themselves mutable, especially if they are passed by the value of a reference. To take one example, suppose I pass an array `x` to a function in C -- say it sums an array of int. For thinking about the purity of the function, how am I supposed to understand what has been passed? If I have a C understanding of it (forgive me for errors; I don't really speak C) then I have just passed a pointer, and whatever happens to be pointed to is a side-effect of the runtime behavior of the program. Yet for any given array of int, the function behaves in a fully predictable way, which seems pretty pure. So can a C function take an array as an argument and still be pure? (I want a language-agnostic answer, not a reference to the gcc docs.)

# Answer
> 4 votes
When you pass a pointer (or an array, which decays to a pointer) in C, the exact details don't matter for function purity. What really matters is that *you're given a way to access the object*. This is the same as when any object is passed to a function in Java or Python.

There's no one correct universal definition of function purity, but ignoring these implementation details seems the most sensible: a function taking a pointer can be pure, as long as it doesn't mutate the object pointed to. In C, this can even be ensured, by making the argument a "pointer to const": this is what happens by default when you pass a double-quoted string (that is, a `const char *`, a reference to an immutable array of characters).

# Answer
> -2 votes
C and Python these are not the purely pure functional programming languages. But you could expect to write functions with much less side effect as far I know :) something is better than nothing in the context of C python, etc which are not purely functional programming platform. For more, you could read this article about a purely functional algorithm in a non-purely functional language like python http://scottlobdell.me/2016/02/purely-functional-red-black-trees-python/

comments are welcome for further discussion.

---
Tags: functional-programming
---


# Question
Title: Finding $t$, $r$ and $w$ in Cache - Direct Mapping
I had a question in my past System Architecture exam and I am not sure how to solve it.

Question was this:

> Consider a 16-bit addressable memory and a direct-mapped cache sized 64 bytes. MAR is 10 bits and a block in memory is 8 bytes sized. Find $t$, $r$ and $w$ (they are Tag, cache index, and block offset respectively.)

Can you show steps of solution of this and such questions? Should I divide cache size by 2 since it is 2 byte addressable? Thanks.

# Answer
> 1 votes
I think i found out the solution, may be helpful for others reading this.

The size of a block is 8 bytes. And the memory is adressed with 2 bytes. So each block contains 4 words (considering 1 adressible unit = 1 word).

4 = 2^2, Then $w$ = 2 bits

Since cache has a size of 64 bytes which is 2^6, than $r$ \+ $w$ must be 6.

$r$ \+ $w$ = 6, $w$ = 2 so $r$ = 6-2 = 4 bits

Lastly the MAR is 10 bits so the length of RA ($r$ \+ $w$ \+ $t$) must be 10.

$r$ \+ $w$ \+ $t$ = 10, $r$ \+ $w$ = 6, then $t$ = 10 - 6 = 4 bits .

So the RA distribution will be like:

```
+----------------------------------------+
| t = 4 |       r = 4      |    w = 2    |
+----------------------------------------+

```

---
Tags: computer-architecture, cache
---


title: What is language density used for?

text:
# Question
Title: What is language density used for?
If we have a langage $L$ over an alphabet $\Sigma$, then we can defined the density function of $L$ as :

> $$ p\_L(n) = | L \cap \Sigma^n | $$

I am wondering why it’s useful to study this function and what informations it gives on $L$.

Moreover, we can then defined the entropy of $L$ as :

$$E\_L(n) = \frac{1}{n} \log p\_L(n) $$

Once again I am wondering what information does this function reveal about $L$. Moreover, is there any way to think intuitively what the entropy of a language really represents?

Thanks you !

# Answer
> 6 votes
The number of words of given length in a language is a very natural parameter. Here are some examples to pique your interest:

1. The density of $(1+01)^\*$ is the Fibonacci sequence.
2. The density of a regular unary language is eventually periodic.
3. The density of a regular language is of the form $\Theta(n^k \lambda^n)$ for some integer $k \geq 0$ and real $\lambda \geq 0$.

The parameter $E\_L(n)$ measures the entropy per character of a random word of length $n$ in $L$, chosen uniformly at random. For example, if $L$ consists of all binary words containing $\lfloor pn \rfloor$ ones (where $n$ is the length of the words), then $E\_L(n)$ converges to $h(p)$, the binary entropy function.

# Answer
> 4 votes
Density is what you get when you want a measure for the size of infinite languages. We can't quantify that by just taking their number of elements, which is the same for all infinite languages: (enumerable) infinity.

Still, we have an intuition about the relative sizes of infinite languages. For instance, about the language of all even strings over a given alphabet, we say it contains half of all strings over that alphabet, so intuitively, the former is half the size of the latter. Similarly, we can say that whenever $L\_1 = L\_2 \cup L\_3$, the size of $L\_1$ is at least that of $L\_2$ and the size of $L\_3$, and it is their sum when $L\_2$ and $L\_3$ are disjoint.

We want a notion of size for which this holds even for infinite languages. The answer is to consider size not as equal to the total number of strings in the language, but as the proportion of strings of each length that is in the language:

$ \displaystyle \delta(L) \mathrel{\mathop{=}\limits\_{\scriptsize D}} \sum\_{n \in \mathbb{N}}\frac{ | \\{ w \in L \mid |w| = n \\} | }{ | \\{ w \in \Sigma^\* \mid |w| = n \\} | } = \sum\_{n \in \mathbb{N}}\frac{ p\_{\scriptsize L}(n) } { 2^{|\Sigma^\*|} } $

but the density function $p\_{\scriptsize L}$ grows exponentially, like the denominator, so we may wish to use the proportions of their logarithms instead:

$ \displaystyle \delta'(L) \mathrel{\mathop{=}\limits\_{\scriptsize D}} \sum\_{n \in \mathbb{N}}\frac{ \mathbb{log}\\, p\_{\scriptsize L}(n) } { \mathbb{log}\\, 2^{|\Sigma^\*|} } = \frac{1}{ |\Sigma^\*| } \sum\_{n \in \mathbb{N}} \mathbb{log}\\, p\_{\scriptsize L}(n) $

# Answer
> 4 votes
$E\_L(n)$ describes how many bits of information you get from a string of length $n$, assuming it belongs to the language.

For many languages the function would be a rather smooth function in $n$. There are of course languages where the language only contains strings of even length, for example, in which case $E\_L(n)$ isn't even defined for odd $n$.

$E\_L(n)$ together with the logarithm of $|\Sigma|$ tells you how likely it is that a random string is in $L$. Usually people try to create strings in a language (that's what programmers usually do), and a low entropy means small mistakes are more likely to get caught.

Which is a good thing, because usually a string in the language $L$ has some semantics, and when I wanted to create a string that is supposed to be in L and has semantics $X$, and a make a small mistake using one or two wrong symbols, I want to be told that my string is not in $L$, and not produce end up with a string in $L$ with the wrong semantics.

If a language has very high entropy, so that *most* random strings are in $L$ (but with probably very different derivations), it is very hard to find errors because *anything* could be in $L$.

---
Tags: formal-languages, word-combinatorics
---


# Question
Title: Closest k points - performance on large lists
Very similar to this

**Problem formulation:** Given a list $L$ of n points with GPS coordinates and a second list $Q$ of $m$ points, find the $k$ (let's say 3) closest points on $L$ for each element on $Q$.

**Aditional constrains:** Assuming that both $L$ and $Q$ are very large, and performance is an issue. We can also assume that $Q$ is much larger thant $L$. Preprocessing can be performed, but has to be robust to updates on lists $L$ and $Q$ (*ergo*, it can't be be very performance heavy).

**Problem extensions:** If we can't have preprocessing, because the updates on $L$ and $Q$ are very common, what would be the solution?

If you can also point me out to implemented solutions on R or Python it would be great!

# Answer
> 1 votes
I think what you are trying to do is a kind of SPATIAL JOIN. A similar question has been answered here, albeit with a fixed size radius for returned points instead of asking for $k$ closest points.

I would suggest using a spatial index $L$. Then you can perform $k$-nearest neighbor queries on the index for each point. The complexity would be about or $O(|Q| * k * log |L|)$. I did some performance test of different spatial indexes here (Figure 28) with 2D and 3D datasets, you should be able to get around 100,000 $k$-nearest neighbor searches per second (on an index with 10,000,000 points). Some of these spatial indexes have updates rates of up to 1,000,000 updates per second, see Figure 40 in the same document. Especially quadtrees and the PH-Tree have high updates rates.

Not sure that it matters, but the PH-Tree uses internally z-curves (Morten order), which means that the ordering of elements uses z-order and is independent of insertion/deletion order. However, also note that the PH-Tree does *not* support duplicates, there can be only one point at any given coordinate.

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


title: Lower bound on $1^k+2^k+\dots+n^k$

text:
# Question
Title: Lower bound on $1^k+2^k+\dots+n^k$
I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.)

Now I want to find a lower bound on the expression I got. Specifically, I want to prove that

$$ 1^k + 2^k + \dots + n^k = \Omega(n^{k+1}). $$

# Answer
> 7 votes
You can estimate your sum from below by $$ 1^k + \cdots + n^k \geq \sum\_{m=\lceil n/2 \rceil}^n n^k \geq \frac{n}{2} \cdot \left(\frac{n}{2}\right)^k = \Omega(n^{k+1}). $$ It is even easier to see that $1^k + \cdots + n^k \leq n^{k+1}$, and so $1^k + \cdots + n^k = \Theta(n^{k+1})$.

You can get better bounds by approximating the sum with an integral: $$ \frac{n^{k+1}}{k+1} = \int\_0^n x^k \\, dx \leq 1^k + \cdots + n^k \leq\int\_1^{n+1} x^k \\, dx = \frac{(n+1)^{k+1}-1}{k+1}. $$ This shows that $$ 1^k + \cdots + n^k = \frac{n^{k+1}}{k+1} + O(n^k). $$

There is also an exact formula, known as Faulhaber's formula.

---
Tags: asymptotics
---


title: Modelling regex replacement via a DFA

text:
# Question
Title: Modelling regex replacement via a DFA
I wish to model the following common construction in code via a finite state automaton for the purposes of static analysis:

```
s = <string matching regex R1>
t = s.replace(<regex R2>, <string matching regex R3>)
# What is the set of possible strings of t?

```

More formally, given DFAs $R\_1$, $R\_2$, and $R\_3$, I want to find some automaton $R\_o$ that is the result of replacing substrings of $R\_1$ that are accepted by $R\_2$ by some string that is accepted by $R\_3$.

Unfortunately, while the literature seems to discuss this, I am unable to pin down a precise implementation of this operation. In addition, I am having trouble even defining the set of strings that $R\_o$ should accept. Does there exist an algorithm to solve this problem? Is it even solvable in general?

# Answer
> 0 votes
Depending on the exact semantics of the `replace` operation (regarding multiple matches, overlapping matches, etc.), it can likely be modelled as a finite-state transducer. The set of possible values of `s` can be modelled as a regular language. It is known that the application of a finite-state transducer to a regular language gives you another regular language, and there are standard algorithms for computing it, using the product construction.

---
Tags: finite-automata, regular-expressions, static-analysis
---


# Question
Title: How to cluster images based on meta-information in tags
**Context and Motivation**

I have researched online for an algorithm (independent of a programming language AND in the context of Machine Learning) that accepts images as inputs with the expectation that individual images contain tags in the form of semi-structured information (for example, in the JSON format) that identify physical objects inside each image.

My goal is to find a clustering algorithm that will cluster objects based on common occurences of strings (i.e. physical objects described by a word, for example 'tree', 'mountain', 'airport' etc) contained in the tags about the images AND NOT on the input features of individual images contained in the pixels.

**Question**

My question is a binary question (Yes / No) - has such an algorithim been studied in published papers? If yes, can you refer me to a source or a list of sources that explores, explains, discusses, codes AND/OR contains instructions on how to implement the algorithm?

**Input:**

A set of images with semi-structured tags identifying physical objects in each indiviual image.

**Output:**

A set of clusters where images are grouped based on commonly occuring objects in the images.

Thanks and appreciation in advance.

# Answer
> 1 votes
Yes, this has been studied, but the images seem to be completely irrelevant.

What you have is a set of texts, and you want to cluster them based on similarities. You simply want to do text clustering. A very simple way to start is to create a vector that represent each of the words. Suppose that you have 1000 words. Sort them, and you have a 1000 dimensional vector. Now, each text (metadata) is represented by a vector with a 1 in position $i$ if the $i$th word is in the text and 0 otherwise.

Do clustering on these vectors as you normally would, you can easily start of with $k$-means clustering.

---
Tags: algorithms, clustering
---


# Question
Title: Boolean expression for sum bit of full adder
The Boolean expression I find on the internet for the sum bit of a full adder is A xor B xor Cin. Does't this expression exclude the A=1,B=1,Cin=1 situation? When that happens, the sum bit is also 1, isn't it?

Thank you very much.

# Answer
1 xor 1 xor 1 = 1, so this is correct in that case as well.
> 1 votes

---
Tags: logic
---


# Question
Title: Proof for Unusual QuickSort Partition Scheme
TL:DR I wrote code for a QuickSort variant. It seems a bit off from original QuickSort. Can anyone tell me why and how this works? Is it a quicksort?

---

The following is code I wrote for a middle pivot quicksort for a high school class of AP CS.

It works for some reason. I've also found a few versions that are same or similar to this. But I'm not sure if this is the same thing as the Hoare implementation scheme. I've tried to analyze it but found out it was quite different from the quicksort I knew of -\> which takes form of: elements smaller than piv | piv ~ piv | elements greater than piv. But this one acts like elements not greater than piv | elements not less than piv. Elements that are equal to the pivot can end up anywhere in between. But it works. Is this even quicksort?

```
public static void middlePivSort(int[] a, int start, int end) {
    if(start < end) {
        int i = start - 1;
        int j = end + 1;
        int m = start + (end - start) / 2;
        int v = a[m];

        while(true) {
            while (a[++i] < v);
            while (v < a[--j]);

            if (i >= j) break;

            swap(a, i, j);
        }

        middlePivSort(a, start, j);
        middlePivSort(a, j + 1, end);
    }
}

```

# Answer
> 3 votes
Welcome to the fascinating world of sorting algorithms!

Apparently, you get the terminologies the other way around.

What you have implemented is none other than the classic/standard/conventional version of quicksort by Hoare partition scheme.

The version of quicksort that you knew of, "which takes form of: elements smaller than piv | piv ~ piv | elements greater than piv", is probably a variation of quicksort using a variation of Lomuto partition scheme that is good at sorting arrays with many repeated elements.

**Exercise 1.** Will your code still be correct if the line `int m = start + (end - start) / 2;` is changed to `int m = start;`?

**Exercise 2.** Will your code still be correct if the lines `int m = start + (end - start) / 2; int v = a[m];` is changed to `int v = (a[start] + a[end]) / 2`? .

---
Tags: quicksort
---


# Question
Title: Finding an unambiguous grammar of a language provided by a CFG
I'm working through 'Intro to Automata Theory, Language and Computation' 2nd edition by Hopcroft, Motwani & Ullman.

In section 5.4, exercise 5.4.3 I am tasked with finding an unambiguous grammar for the language of this Context-Free Grammar (where epsilon is the empty string):

$$S \rightarrow aS | aSbS | \epsilon$$

I'm having difficulty describing this grammar formally, but I realize the number of a's is greater than or equal to the number of b's. And the string will always begin with an a (except for the empty string).

I have attempted to break the grammar into two parts to remove the ambiguity. After a few brute force attempts, I decided to distinctly have a variable generate only a's and the other variable generate an equal amount of a's and b's.

$$S \rightarrow A | B | \epsilon$$ $$A \rightarrow aA | a $$ $$B \rightarrow BB | aAbA | ab$$

The key part is when a re-write of B to a sentential form when an A occurs, only more a's can be generated in the string.

My question is does the new grammar I created generate the same language as the previous grammar? If not, what would be the correct grammar? I realize determining if two CFG are equivalent is undecidable; but I have no method of determining if I am correct.

# Answer
> 1 votes
First, let us show that the original grammar generates the language $L$ of all words in which in every prefix, there are at least as many $a$s as $b$.

A simple induction shows that every word generated by the grammar satisfies the property. In the other direction, let $w$ be a non-empty word in $L$. We consider two cases:

1. Some prefix of $w$ has exactly as many $a$s as $b$s. Write $w = axby$, where $axb$ is the shortest prefix with this property. This choice guarantees that $x \in L$. Also, $y \in L$. Hence we can generate $w$ using the rule $S \to aSbS$.
2. In every prefix of $w$, the number of $a$s exceeds the number of $b$s. Hence $w = az$, where $z \in L$, and we can generate $w$ using the rule $S \to aS$.

Every word $w \in L$ can be written (uniquely) as $w\_0 a w\_1 a \cdots a w\_\ell$, where $w\_i$ is a word in $L$ in which the number of $a$s is the same as the number of $b$s. Indeed, $w\_0$ is the longest prefix of $w$ in which the number of $a$s is the same as the number of $b$s; $w\_0 a w\_1$ is the longest prefix of $w$ in which the number of $a$s exceeds the number of $b$s by 1; and so on.

Suppose that $T$ generates unambiguously the language $L'$ of all words in $L$ in which the number of $a$s is the same as the number of $b$s. Then we can generate $L$ itself unambiguously using the productions $S \to T a S \mid T$. The language $L'$ can be generated unambiguously using $T \to aTbT \mid \epsilon$.

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


title: Are Huffman codes self-synchronizing?

text:
# Question
Title: Are Huffman codes self-synchronizing?
A code is *(statistically) self-synchronizing* if, given that the transmitted string is long enough, the receiver is guaranteed to eventually synchronize with the sender, even if bit flips or slips have occurred.

Do Huffman codes have this property in general? In case not, is there a criterion for testing if a Huffman code is self-synchronizing or, equivalently, is there a modified construction of a Huffman code which guarantees self-synchronization?

# Answer
Assume 256 symbols, each with probability 1/256. The Huffman code words will be all 256 possible eight-bit sequences, and there is no synchronisation at all.

To find if a Huffman code is self-synchronising:

```
Let S = {}
For each code c:
    For 1 ≤ m < length (c)
        Let s be the last m bits of c
        As long as s has a code c' as prefix
            Remove prefix c' from s
        If s is not empty and not in S
            Add s to S.

Loop:
    If S is empty the the code is self-synchronising.
    Let T = {}
    For each s' in S, and code c:
        Let s be s' concatenated with c
        As long as s has a code c' as prefix
            Remove prefix c' from s
        If s is not empty and not in T
            Add s to T.
    If T = S then the code is not self-synchronising
    Let S = T and loop.

```
> 2 votes

---
Tags: coding-theory, huffman-coding
---


title: How do I model line comments in a CFG?

text:
# Question
Title: How do I model line comments in a CFG?
Assume we want to define a context free grammar of say a programming language, where on each line everything after the character # until the end of line is considered a comment and should be ignored. How to express that in a context free grammar?

# Answer
Can just treat comments as whitespaces.
> 0 votes

# Answer
Without multi-line statements, it's rather simple; assuming `line` is the non-terminal for well-formed line, change its right-hand-side appearances to

```
line (# .*)?

```

(borrowing regular expression syntax for brevity).

Otherwise, if you explicitly handle line breaks, replace occurrences of the line-break token `CRLF` (or so) similarly by

```
(# .*)? CRLF

```

If line breaks remain implicit, one chance you have left is make it part of the lexer; don't only skip whitepace, but also `(# .*)? [\r\n]`. You can also create a token `COMMENT` for that and place it in all places of the grammar where it may appear. This strategy doesn't work for nested multiline comments, though, a common problem in older languages.
> 3 votes

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


# Question
Title: Is there any model of Game of Life compatible with hypercomputation?
I found a question in Mathematics Stack Exchange which asks a very similar question

(https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-life)

It asks whether there are Game of Life models with 3 or more dimensions and if there are Game of Life models related to hypercomputation, but the answers seem to refer to the first question and ignore the second.

So, if I am not wrong, and that is the case, then:

Is there any specific model of Game of Life (Or Cellular Automata in general) that can perform hypercomputation (i.e a Hypercomputational model of Game of Life and/or Cellular Automata)?

And also, Is there any specific model of a hypercomputational Game of Life/Cellular automata that has been applied to physics? That has proposed a cosmological/physical model of the universe based on these Cellular Automata? (Like some sort of Zuse's thesis: https://en.wikipedia.org/wiki/Calculating\_Space)

# Answer
Cellular automata can be simulated with an ordinary Turing machine, so they don't have any more power than an ordinary Turing machine -- they can't perform "hypercomputation".
> 1 votes

# Answer
If you want to introduce Hypercomputation in CA, one way could be going "meta". So for example an Hypercomputer could execute a CA where every cell contains states that are uncomputables by traditional TMs. For what concern the physics part, someone (I am aware for example of Gerard Hooft) suggested a superdeterminisic theory where the basic working of reality is in fact a CA.
> 0 votes

---
Tags: turing-machines, game-theory, cellular-automata, hypercomputation
---


# Question
Title: Determining an appropriate number of buckets for a hash function
I would like to select an appropriate number of buckets in my hash table for this scenario:

A hash table with collision resolved is required to hold about 10000 records. Each record is to be indexed by the 2-character initials of the customer's name, transformed into integers using the mapping: A=01, B=02,..., Z=26. It is expected that on average no more than 8 comparisons is made every time a search is requested.

How would you select an appropriate number of buckets for a division hash function, and a multiplication hash function, based on this scenario?

# Answer
> 1 votes
The number of buckets in a hash structure will almost always be *on the order of* the number of items in the hash structure.

The phrase *"on the order of"* is intentionally imprecise. That means you could have twice as many buckets as items. Or two times as many items as buckets. But the two values (bucket count and item count) are generally correlated in a linear (not exponential) manner, within a factor of 10.

If the hash function is fairly good, and the number of buckets is prime, then anywhere up to one item per one bucket will result in a median search depth of one and an average search depth just over one. Generally, because the relative cost of a bucket is small, it makes sense to maintain a ratio of buckets to items that is greater than 1, but only minimally so.

Your description of your solution is confusing, because you have 10,000 records identified by initials, but only 676 combinations of initials (26 x 26). It is likely that you are layering complexity onto complexity in a vain attempt to save clock cycles and RAM, both of which you are likely to waste as a result of the inherent complexity of your solution. A smart guy named Donald Knuth once said: "Premature optimization is the root of all evil (or at least most of it) in programming." I'm almost certain you are well down that path already, and I suggest that you back out of that choice.

# Answer
> 1 votes
Two letters from a name are an extraordinarily bad hash code. There are only 576 possibilities, but letters are not random (you will find very few names with initials Z. Z.). With 10,000 records, I'd expect easily 100 records with the same hash code. There is no way on earth you can get the expected number of comparisons below 20 with this hash code.

Take a decent hash code, calculated from *all* characters in the name. Then you want something like 15,000 to 20,000 slots. 8 comparisons on average is something I would consider extremely high / unacceptably high.

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


# Question
Title: How much does C# gain from its value types
C# makes an distinction between value types and reference types contrast to Java where all (except primitives types) are of reference semantics. The design decision, as I understand it, is mainly to make small objects more cache friendly, that is, for efficiency reasons.

my question is;

1. is there any study on how much efficiency gain does C# make by this design choice, based on evaluating real world projects.
2. Assuming the answer to the first question is that there is a measurable efficiency gap, will things change when JIT compilers come into play?

# Answer
Swift does the same thing (having both value types and reference types). I'm sure there are efficiency studies, performed by the people implementing the Swift compiler.

But the difference between reference types and value types goes a lot deeper. What you need to look at is things like mutability, semantics when passing parameters, and so on. I don't choose reference vs. value types for micro efficiencies, but for the semantics.

So your assumption "the design decision is mainly to make small objects more cache friendly", is firstly wrong, and secondly I strongly doubt it makes things more cache friendly.
> 2 votes

---
Tags: programming-languages, efficiency
---


# Question
Title: How to check for ambiguous grammar if you don't know the string
Let's say I have a CFG grammar $G$ which describes some rules for language generation. How can you tell that grammar can generate ambiguous results for a string if you don't know that string? I know how to check for ambiguity when you're given a particular string but what about the cases when it's not? Is there any algorithm to do this?

# Answer
You cannot tell that a context-free grammar is ambiguous, since the problem is undecidable. This can be proved by a straightforward reduction from the Post correspondence problem, for example. What this means is that there is *no* algorithm that, given a context-free grammar, decides whether it is ambiguous or not.
> 4 votes

# Answer
My answer is this, you can not check for ambiguity if no string is given, because there is no algorithm till now to check for ambiguity.
> -1 votes

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


# Question
Title: Find an algorithm to write a given word with this broken keyboard
I am submitting this interview question I have recently found

> Imagine you have a computer keyboard that has all the letters mismatched
> example:
> \- typing q gives you a
> \- typing w gives you b
> all 26 letters in the alphabet are there, but typing one letter will give you another one
>
> Restriction: you need to type a word every time, not go character by character
>
> The goals are
>
> * find an algorithm to write a given word with this keyboard
> * estimate its complexity
> * identify the approach limits

**NOTES**

* The restriction means it is not possible to type a single char and observe the result, it is necessary to input a whole word before observing the result

# Answer
> 0 votes
This is my approach

# Analysis

This implicitely means finding the button to char mapping the keyboard follows

As it is stated, the problem can be of an arbitrary complexity as we have no prior information about this transfer function, in fact it could be

* random or have a random component
* stateful, so the result could depend on the history

Let's however start focusing on a simple subset of transfer functions which have the following features

* deterministic
* stateless

We can model this as follows, in Haskell terms

`f :: Char -> Char`

However there is an additional problem regarding this function: it is possible any char we need is not represented, i.e. there is no input for that function so that we obtain the desired char as output

This makes the problem essentially equivalent to a linear search so it's `O(N)` with `N` number of possible input chars for the transfer function hence buttons on this keyboard

# Strategy

The additinal restriction which requires to input a word and not single chars, to observe the output, does not affect the complexity: it is sufficient to identify a set of non overlapping words covering the whole input domain so to get a complete knowledge

At the end of this procedure, we will be able to solve the problem or decide it can not be solved because some chars are not representable

---
Tags: algorithms
---


# Question
Title: What is parallel virtual machine (pvm) and how it's different from mpi (message passing interface)
I am learning beowulf cluster. And I want to know what is pvm and how it's work and there is any difference between mpi and pvm

# Answer
> 2 votes
In fact, MPI and PVM are very different. However, they have the same objective, that is achieving data/message exchange between processors, thus enabling distributed/parallel computation.

---

MPI is the acronym for *Message Passing Interface*. It is a well-known message-passing standard, which defines the syntax and semantics of a core of library routines to exchange data between processors. Therefore, MPI is not a technology itself, but just the definitions of how to exchange data. However, MPI implementations exist in several programming languages (e.g., C, C++, FORTRAN, Python, and R), and those implementations are usually refereed simple as MPI. This fact may cause confusion since both the technology and the standards definition have the same name.

---

On the other hand, PVM is a free software (released under both the BSD License and the GNU General Public License) which enables data exchange between processors, in the same way as the MPI implementations. PVM consists of a run-time environment and library for message-passing, task and resource management, and fault notification.

---

You may have a look at some studies that compare both MPI and PVM. Please, see the links below.

http://wwwmayr.informatik.tu-muenchen.de/konferenzen/Jass04/courses/2/Papers/Comparison.pdf

https://www.researchgate.net/profile/James\_Kohl2/publication/2612922\_PVM\_and\_MPI\_A\_comparison\_of\_features/links/0c960528b9401cec40000000/PVM-and-MPI-A-comparison-of-features.pdf

http://wwwmayr.informatik.tu-muenchen.de/konferenzen/Jass04/courses/2/Talks/Elts.ppt

---
Tags: parallel-computing, clustering
---


# Question
Title: How does the cpu know which process to wake?
In general, my understanding is: the cpu is executing a process/thread until either it is interrupted, the scheduler kicks it out, or it's waiting for something else (I/O for example), when it's put in different queues (ready, waiting, etc). (Correct me if I'm wrong)

My question is, when one process is waiting information from another process (I guess, sleeping until a signal for it has been received). How does the cpu know how to wake that process? When it receives the signal will it be attempting to wake up all the processes with it? Is it marked somehow which processes are expecting which signals? What if the interrupt doesn't have this process id, but a general message to which the process is the only one waiting for it?

I've been trying to find a concrete response and read: https://learning.oreilly.com/library/view/operating-system-concepts/9781118063330/10\_chapter03.html#chap3 https://medium.com/cracking-the-data-science-interview/how-operating-systems-work-10-concepts-you-should-know-as-a-developer-8d63bb38331f

Thanks in advance!

# Answer
> 2 votes
**TL;DR**
The CPU doesn't know anything. The operating system (OS) knows it all.

---

The CPU is rather a stupid machine that activates one instruction at a time, without knowing what that instruction "means" nor to which program it "belongs". To the CPU eyes there is only a single program that runs (maybe, up to interrupts that "jump" to the interrupt service routine and then goes back to THE PROGRAM.

The program that does the magic and allows us running multiple programs "at the same time" over a single CPU is the OS. The OS keeps a list of processes that are ready to run, with all the information needed -- their priorities, their memory regions, the point in the code where they stopped, etc.

Every now and then a timer interrupt is received causing the scheduler (which is part of the OS) to run. The scheduler registers the process that was currently running as "stopped" and chooses one of the waiting processes, restoring its meta-date (stack, etc.), and jumps to the point where that process stopped last time.

This gives you the illusion of running multiple processes simultaneously. But at the bottom of it, there is only one program that runs -- the OS -- and it gives priority to (or, calls) user loaded programs.

Regarding your question about inra-process communication. Again, this is usually done via methods provided by the OS. When a process waits for a signal it calls an OS method that registers this process awaits a signal and blocks the processes, allowing other processes to run. When the other process needs to send data to the first processes it uses a OS method that records the data and its destination, and (eventually) awakes the destination process. From the point of view of the first process it got blocked on a OS function which returns only when new information arrives.

---
Tags: cpu, multi-tasking
---


title: micro programming and hard wiring

text:
# Question
Title: micro programming and hard wiring
I have a question about the details of microprogramming and hard wiring in CPU architecture.

in hardwiring, we write a code the compiler translates it to the ISA. then ISA is run in the hardware.

in microprogramming, we write a code the compiler translates it to the ISA(which is much more complicated than the ISA in hardwiring)then a device(I don't know the name) translates it to the hardware language.

am I correct?

# Answer
> 1 votes
Not Exactly. The microcode is a layer "below" the ISA and the Hardware-level functionality. That is, when you write some machine code like MOV or ADD or MUL (which are part of the ISA), the microcode translates it into multiple simpler activities (e.g., "move info from A register to B register. ADD this registers. Load from the Memory. etc.). These simple activities eventually perform the instruction you coded.

For instance, think of the MUL instruction that can be micro-coded as multiple add and subtract, like in done in elementary school.

---
Tags: cpu
---


# Question
Title: Optimal prefix-free binary code with several codewords already assigned
The classic Huffman algorithm, as Wikipedia states, finds an optimal prefix-free binary code with minimum expected codewords length, given a set of symbols and their weights. Now, suppose codewords for some (but not all) symbols are already assigned (maybe in a suboptimal way). How should we assign remaining codewords to the remaining symbols so as to minimize the minimum expected codewords length, assuming that there exists at least one binary sequence such that none existing codewords have it as their prefix, and neither of the existing codewords is its prefix?

# Answer
> 1 votes
## "Ordinary" Huffman is suboptimal

Let's call a symbol "free" if it has not yet been assigned any codeword. Here's an easy counterexample to the optimality of running the ordinary Huffman algorithm on the set of free symbols:

Suppose we have three symbols $a, b, c$, with frequencies $0.5, 0.25, 0.25$, of which $b$ and $c$ are free; $a$ has already been assigned the codeword $00$. Then the unique minimum-size tree in which $b$ and $c$ -- the lowest-frequency free symbols -- are siblings is

```
  /\
 / /\
a b  c

```

with expected codeword length $0.5\*2 + 0.25\*2 + 0.25\*2 = 2$, which is strictly greater than that of either of the two trees in which they are not siblings:

```
  /\        /\
 /\ c      /\ b
a  b      a  c

```

which each have expected codeword length $0.5\*2 + 0.25\*2 + 0.25\*1 = 1.75$.

---
Tags: coding-theory, huffman-coding
---


# Question
Title: Complexity of many constant time steps with occasional logarithmic steps
I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant.

Is it possible for this task to ever take amortized constant time, or is it impossible because the logarithm will eventually become greater than $k$?

If an upper bound for $n$ is known as $N$, can $k$ be chosen to be less than $\log{N}$?

# Answer
> 8 votes
If every $k$th operation takes $O(\log n)$ time, then the best bound you can get on the amortized complexity is $O(1 + \frac{\log n}{k})$. This follows from the definition of amortized complexity.

---
Tags: algorithm-analysis, runtime-analysis, amortized-analysis
---


title: Hardness of FNP vs Choice of Verifiers

text:
# Question
Title: Hardness of FNP vs Choice of Verifiers
A (T)FNP problem is induced by a NP language, say $L$. Usually in the notion of verifers, we define $L=\\{x:\exists y,V(x,y)=1\\}$, where $V$ is a poly-time verifier. The function version would be finding the certificate $y$ (if exist).

However, the choice of verifier could be arbitrary, for example, the verifier for $HAM-PATH$ problem could be

1. Determinig whether the computation path of TM configurations is valid and reaches accepting state. (The Cook-Levin way).
2. Determine whether a path of input graph is Hamiltonian. (The natural way)

In order to make this definition "natural", we should probably show that, undere these different choice of verifier, the definition remains equivalent, i.e. the problem do not suddenly become harder/easier just because we introduce a different verifier.

> **So here's my question:** Is the choice of verifier independent with hardness of its functional problem? How do we justify this?

# Answer
> 1 votes
No (unless $P=NP$). Consider a language $L$ that is in $P$, say, $L$ is the language of prime numbers.

Suppose $V\_1$ works as follows: $V\_1(x,y\_1)$ ignores $y\_1$ and checks directly whether $x$ is prime, and if so, outputs 1; otherwise it outputs 0.

Suppose $V\_2$ works as follows: $V\_2(x,y\_2)$ interprets $x$ as a 3CNF formula and checks whether $y\_2$ is a satisfying assignment for it; then it checks whether $x$ is prime; and if both are true, it outputs 1, otherwise it outputs 0.

Both verifiers define the same language, namely, $L$.

However, given $x$, the problem of finding $y\_1$ that's accepted by $V\_1$ can be solved in polynomial time; but the problem of finding $y\_2$ that's accepted by $V\_2$ is NP-hard. So, assuming $P \ne NP$, those two function problems have different hardness.

---
Tags: complexity-theory, search-problem
---


# Question
Title: Search a sorted array that ends with zeros in O(log n) time
I have an array of size $m$, $\[1,1,2,2,3,4,5,...,f,0,0, \cdots,0\]$, where the first $n$ elements $1,1,2,2,3,4,5,\cdots, f$ are sorted.

If I make a binary search including the 0's I get $O(\log(m))$.
I'm trying to make the algorithm better and to get complexity of $O(\log(n))$ with no success.

I thought maybe something with medians?
Any idea will be great.

# Answer
> 7 votes
Here is a simple algorithm to solve the problem as in Yuval's comment.

### Algorithm

**Input**: A positive number $w$ and array $A$ of $m$ numbers, $A\[0\],\cdots, A\[m-1\]$. The first $n$ numbers of $A$ are non-decreasing positive numbers and the rest are 0s.

**Output**: An index $k$ such that $A\[k\]=w$ or -1 if $w$ is not an element of $A$.

**Procedure**:

1. Check elements at index $1,2,4,8,\cdots$, until a zero is found or the index overflows. Let the index thus found be $p\_0$. Let $p$ be the smaller of $p\_0$ and $m-1$. Note $n\le p\lt 2n$.
2. Consider 0 as greater than all positive numbers so that $A\[0\], A\[1\], \cdots, A\[p\]$ becomes a sorted array. Conduct a binary search for $w$ on that array. If $w$ is found, return the index; Otherwise, return -1.

### Algorithm analysis

Step 1 checks at most $\log\_2(2n)=1+\log\_2 n$ elements. Step 2 checks at most $\log\_2(p+1) + 1 \le 2 + \log\_2n$ elements. So the time-complexcity of the algorithm is $O(\log n)$.

This problem is a variation of the classic problem of searching sorted, unbounded/infinite lists. The algorithm above is a simple variation of the exponential search explained in this Wikipedia article. You are encouraged to take a look at that article for more intriguing variations. For example, a basic version of Bentley and Yao's algorithms checks elements at index 2, 4, 16, 256, 65536, $\cdots$ first.

### Exercises

**Exercise 1**. (One minute or two) Assume that $w$ might not be positive and the first $n$ element of $A$ might not be positive instead. Adapt the algorithm slightly so that it still works.

**Exercise 2**. (One minute or two) Improve the algorithm so that it runs in $O(\log k)$ time where $k$ is the smaller of $n$ and the index of the first element in $A$ that is no less than than $w.$

**Exercise 3**. Let $B$ be a sorted array of $n$ distinct elements, one of which is $w$. Devise an algorithm that finds $w$'s index in $O(\min(k, n-k))$ time, where $k$ is $w$'s index.

---
Tags: algorithms, complexity-theory, data-structures, search-algorithms
---


# Question
Title: Kolmogorov randomness for Pseudo random number generator
I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable. So would appreciate any help or guidance for this subject matter.

# Answer
> 1 votes
You can't. Kolmogorov complexity is not computable. See, e.g., https://en.wikipedia.org/wiki/Kolmogorov\_complexity.

---
Tags: pseudo-random-generators, kolmogorov-complexity
---


# Question
Title: Find a node with maximum distance from query node in a tree
I solved this problem from codechef: problem link

and now I want to change it a bit. Instead of find out the distance between node $u$ and $v$ I want to answer $k$ queries of the form: find node $u$ to which distance from node $v$ is maximum but I'm not able to see fast enough algorithm for it. I think that heavy light decomposition is still my best option. Do you have any ideas?

Finding node to which distance is maximum in this way is $O(n)$ but the challenge here is that I have to answer to $k$ queries so the total complexity is $O(nk)$. I believe that this can be done in $O((n+k)\log n)$.

# Answer
> 2 votes
Start from any node and find (say, with a BFS) a farthest node from it; call it $u$. Then start from $u$ and find a farthest node from it; call it $v$. Nodes $u$ and $v$ achieve the absolute maximum distance in the tree.

Now with 2 more BFS, find the distances of all nodes from $u$, and the distances of all nodes from $v$. At this point you are ready to answer the queries: for each queried node $z$, the most distant node is either $u$ or $v$, depending on which has the larger distance. This solves your problem in $O(n + k)$ time.

# Answer
> 0 votes
Let's say your $k$ queries are in the following order $\\{v\_1, v\_2, \ldots v\_k\\}$. For $v\_1$, we will have no information so we simply do a DFS and determine the furthest node $u$ and return it. Consider $v\_1$ to be the root of this DFS tree. For each of $v\_1$'s children $\\{u\_1, u\_2, \ldots\\}$ we will also keep track of the deepest node in the subtree rooted at $u\_i$. Let's call this $d(v\_1, u\_i)$. Note that the maximum distance node from $v\_1$ is:

$$d(v\_1) = \max\_i d(v\_1, u\_i)$$

At this point, it is important to note that for the query $v\_2$, we can retain a lot of information from $d(v\_1, u\_i)$ if the path to the furthest node from $v\_2$ includes $v\_1$. Let's assume w.l.o.g. that $v\_2$ is in the subtree rooted at $u\_j$ in the DFS tree of $v\_1$. We will again do a DFS for the deepest node in the DFS tree of $v\_2$, however when we hit $v\_1$ we can stop and we only need to retain the distance $\delta(v\_2, v\_1)$. Now we compute $d(v\_2)$ as:

$$d(v\_2) = \max \\{ \max\_i d(v\_2, y\_i) , \ \delta(v\_2, v\_1) + \max\_{i \neq j} d(v\_1, u\_i) \\}$$

This idea can be repeated for the rest of the queries where $v\_i$ relies on the information from the queries of $\\{v\_1, v\_2, \ldots v\_{i-1}\\}$. At query $v\_i$ we can describe the work as follows. Consider the DFS tree rooted at $v\_i$, the "search" work done at any subtree rooted at $\\{v\_1, v\_2, \ldots v\_{i-1}\\}$ is constant based on our precomputed values. We need only care about the work done before we reach these nodes. Here is an example analysis where we consider the query $v\_{i+1}$ is in the "middle" of the largest remaining subtree.

1. First query takes $cn$ and splits the tree into trees $T\_1$ and $T\_2$ of size $n/2$ each.
2. Second query takes $cn/2$ and splits $T\_1$ into trees $T\_3$ and $T\_4$ of size $n/4$ each.
3. Third query takes $cn/2$ and splits $T\_2$ into trees $T\_5$ and $T\_6$ of size $n/4$ each. At this point we have 4 trees: $\\{T\_3, T\_4, T\_5, T\_6\\}$.
4. This goes on and on.

If we assume $k = 2^\ell - 1$, then we get the summation:

$$T(n) = \sum\_{i = 0}^{\ell-1} 2^i\frac{n}{2^i} = O(\ell \cdot n) = O(n \log k)$$

---

As a side note, much of the work will depend on the ordering of the queries. For instance if we have a linked list of edges: $\\{(v\_1, v\_2), (v\_2, v\_3), \ldots\\}$ and we assume the query order is $\\{v\_1, v\_2, \ldots v\_k\\}$ then:

1. First query takes cn, and splits the tree into trees $T\_1$ and $T\_2$ of size $1$ and $n-1$ each.
2. Second query takes c(n-1), and splits $T\_2$ into trees $T\_3$ and $T\_4$ of size $1$ and $n-2$ each.
3. Third query takes c(n-2), and splits $T\_4$ into trees $T\_5$ and $T\_6$ of size $1$ and $n-3$ each.
4. This goes on and on.

We get the final complexity is:

$$T(n) = \sum\_{i = 0}^k c(n-i) = O(nk)$$

However, if we order the queries as $\\{v\_k, v\_{k-1}, \ldots v\_1\\}$ then:

1. First query takes cn, and splits the tree into trees $T\_1$ and $T\_2$ of size $k-1$ and $n-k + 1$ each.
2. Second query takes c(k-1), and splits $T\_1$ into trees $T\_3$ and $T\_4$ of size $k-2$ and $1$ each.
3. Third query takes c(k-2), and splits $T\_3$ into trees $T\_5$ and $T\_6$ of size $k-3$ and $1$ each.
4. This goes on and on.

We get the final complexity is:

$$T(n) = cn + \sum\_{i = 0}^{k-1} c(k-i) = O(n + k^2)$$

Even with an ordering of $\\{v\_k, v\_{k/2}, v\_{k/4}, v\_{3k/4}, \ldots\\}$ we could get a complexity of $O(n + k \log k)$. So the complexity very much depends on the ordering of the queries. If we assume the queries are random then this is still okay and we can get $O(n \log k)$. If we can re-order the queries then we can greedily pick the node that splits the tree closest to in-half and continue. This should give approximately $O(n \log k)$, though I have no proof and will not work through it here.

---
Tags: algorithms, graphs, trees
---


# Question
Title: Binary strings such that the sum of 0's is not equal to twice the sum of 1's
Construct a context-free language for $L=\\{w\in \\{0,1\\}^\* \mid n\_0(w)\not= 2n\_1(w)\\}$. Here $n\_b(w)$ is the number of $b$'s in $w$.

I can construct a CFL in the case $n\_0(w)=2n\_1(w)$, but I have no idea how to construct it when they are not equal, considering that CFL is not closed under complement operation.

# Answer
Distinguish $n\_0(w) \< 2n\_1(w)$ and $n\_0(w) \> 2n\_1(w)$. That is, in your grammar for $n\_0(w) = 2n\_1(w)$ either generate extra $0$ or (in a separate half of the grammar) extra $1$.
> 2 votes

---
Tags: context-free
---


title: State Transition Diagrams for XOR

text:
# Question
Title: State Transition Diagrams for XOR
I have found two different versions for State Transition Diagrams for XOR.

I'm confused as to why one has 2 states and the other has 3. What are the implied states in each please?

Are they both functionally equivalent? Are there situations where one is more appropriate than the other?

# Answer
> 2 votes
On the left you have a DFA that accepts the language of all strings over $\\{0,1\\}$ in which the XOR equals 1.

On the right you have a Mealy machine in which each output is the XOR of the two recent inputs (the first output is always zero).

---
Tags: finite-automata, boolean-algebra
---


# Question
Title: Use dynamic programming to merge two arrays such that the number of repetitions of the same element is minimised
Let's say we have two arrays `m` and `n` containing the characters from the set `a, b, c , d, e`. Assume each character in the set has a cost associated with it, consider the costs to be `a=1, b=3, c=4, d=5, e=7`.

for example

```
m = ['a', 'b', 'c', 'd', 'd', 'e', 'a']
n = ['b', 'b', 'b', 'a', 'c', 'e', 'd']

```

Suppose we would like to merge `m` and `n` to form a larger array `s`.

An example of `s` array could be

```
s = ['a', 'b', 'c', 'd', 'd', 'e', 'a', 'b', 'b', 'b', 'a', 'c', 'e', 'd']

```

or

```
s = ['b', 'a', 'd', 'd', 'd', 'b', 'e', 'c', 'b', 'a', 'b', 'a', 'c', 'e']

```

If there are two or more identical characters adjacent to eachother a penalty is applied which is equal to: `number of adjacent characters of the same type * the cost for that character`. Consider the second example for `s` above which contains a sub-array `['d', 'd', 'd']`. In this case a penalty of `3*5` will be applied because the cost associated with `d` is `5` and the number of repetitions of `d` is `3`.

I need to design a dynamic programming algorithm which minimises the cost associated with `s`.

Does anyone have any resources, papers, or algorithms they could share to help point me in the right direction?

# Answer
> 3 votes
Here is an algorithm that computes the minimum cost that is about as simple as possible and as fast as possible.

1. Count the total number of each character in $m$ and $n$. Let them be $c(a), c(b), \cdots$ respectively. Let $x$ be one of $a,b,\cdots$ such that $c(x)$ is the maximum.
2. Let $\sigma$ be the sum of all $c(i)$ where $i$ goes through $a, b, \cdots$ except $x$.
    1. If $c(x)\le 1 + \sigma$, return 0.
    2. Else return $p(x)(c(x) -\sigma))$, where $p(x)$ is the penalty associated with $x$.

The time-complexity of the algorithm is $O(\ell)$, where $\ell$ is the sum of the length of $m$ and the length of $n$.

Since the algorithm above is simple and clear, there is no need to apply the heavy machinery of dynamic programming.

### Exercises

Here are two exercises that prove the correctness of the algorithm above.

**Exercise 1.** If $s(x)\le 1 + \sigma$, design a procedure to produce a merged array that does not have adjacent pairs of the same letter.

**Exercise 2.** If $s(x)\gt 1 + \sigma$, then any merged array must have at least $s(x) -\sigma$ $x$s each of which is adjacent to another $x$. Design a procedure to produce a merged array that has no other penalties except for $s(x) -\sigma$ $x$s.

---
Tags: algorithms, dynamic-programming, subsequences, bioinformatics
---


title: Intuition for “run” function of monads

text:
# Question
Title: Intuition for “run” function of monads
I'm learning about monads, I understood why they are useful, I understood in general what bind, join, return do.

I also looked at basic usage examples for the basic reader / writer / state / list / maybe monads.

Still, being a beginner, I still don't feel I have a grip on what the "run" function means in general. It does not seem to have a generic signature like the above functions, and I don't get it if it's definable / makes sense for all monads.

# Answer
> 2 votes
Short answer:

**There isn't a run-function for all monads, and its use is evaluating data structures.**

Medium answer:

Certain monads build data structures that will be evaluated afterwards. Let's say we want to build our own IO monad (I'll need to use GADT notation, basically I just talk about inhabitants and their specific types):

```
data SimpleIO a where
  PutStr :: String -> SimpleIO ()
  GetLine :: SimpleIO String
  Bind :: SimpleIO a -> (a -> SimpleIO b) -> SimpleIO b
  Return :: a -> SimpleIO a

```

Like this, we can build a few IO actions, like one that just reads a string and prints it: `Bind GetLine PutStr`does exactly that. However, our monad doesn't do anything: We don't know how to execute those actions, so we need some kind of conversion function:

```
runSimpleIO :: SimpleIO a -> IO a
runSimpleIO (PutStr x) = putStrLn x
runSimpleIO GetLine = getLine
runSimpleIO (Bind x f) = x >>= f
runSimpleIO (Return x) = return x

```

This is some kind of run function, it uses the monad-made structure to make use of it. It definitely isn't unique though: You might as well write a run function `SimpleIO a -> Maybe a`. That's nothing defined within the monad, but more of an interpretation.

---
Tags: functional-programming
---


# Question
Title: Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?
I was reading this article and was wondering if there is any finite set of higher-order functions like map, fold or filter such that they could empower a language to be Turing complete even without having explicit constructs for recursion or iteration. Obviously the higher-order functions would be implemented with recursion or iteration, but the requirement is that recursion or iteration could not be directly exposed to the programmer. That is to say, recursion or iteration can be baked in a finite set of pre-defined, built-in higher-order functions, but the language must not have an explicit construct for iteration or recursion. The set of higher-order functions can be arbitrarily large, but must be finite.

Alternatively, if the answer is no, which is the biggest set of problems that could be computed by such a language? Is that set a known set (eg. equivalent to pushdown automaton)?

# Answer
> 3 votes
A functional language such as (a fragment of) Agda has:

* inductive types (lists, trees, numbers, etc.)
* higher-order functions
* structural recursion (a generalization of `fold` and `map`)

However, such a language is not Turing complete. If we add the fix-point operator, which is a higher-order function

```
fix_t : (t -> t) -> t

```

then we can use that to implement general recursion and we have a Turing-complete language. Conversely, in Turing-complete functional language it is possible to implement `fix_t`, at least in the case `t = nat`.

So the obstruction to Turing completeness of functional languages is whether they can implement the fixed-point operator. (Partial combinatory algebras from another answer to this question also have the fixed-point operator.)

# Answer
> 0 votes
Have you heard about combinatory logic? It somewhat works like this, introducing three combinators ($\approx\\,$functions) $S$, $K$, and $I$. Together with an infinite set of variables, those are turing complete using the following evaluation rules:

$(((Sx)y)z)$ evaluates to $((xy)(xz))$.

$((Kx)y)$ evaluates to $x$.

$(Ix)$ evaluates to $x$.

where $(xy)$ is $x$ applicated to $y$.

For example, we can define the natural numbers in a quite simple way:

$0 =\_{def} (KI)$, $succ =\_{def} (S((S(KS))K))$

Addition isn't that difficult then: $add =\_{def} S(KS)(S(K(S(KS)K)))$ (I omitted parentheses such that $XYZ = ((X Y) Z)$).

When evaluating, you will see how those terms work and what simple systems still are capable of.

---
Tags: programming-languages, functional-programming, turing-completeness
---


# Question
Title: How can i prove this asymptotic comparison?
This is an exercise that's part of my assignment, but it is optional and flagged as a "challenge". I would like to discuss its solution:

Prove that: $$ 27\log{n} + \sqrt{n} = \theta(\sqrt{n})$$

Clearly this is correct, because the dominant term ($\sqrt{n}$) is present in both sides. But i wasn't able to give a mathematic explanation why it's correct.

# Answer
When it comes to instances like this, I prefer to think about conceptually "promoting" and "demoting" lower order terms.

For instance, if we wanted to upper bound:

$$f(n) = 32 + 11 \log\_2 n + 5 n + 2 n^2$$

We know (by intuition or limits) that $n^2$ is the fastest growing term here. Thus, we should be able to bound $f(n)$ by $n^2$. By this, I mean we can find some constant $c$ such that $f(n) \leq c n^2$ for all $n \geq n\_0$ (where $n\_0$ is some initial starting value for $n$ where this inequality holds true). Note, that this is preciesly the definition of Big O.

> *Promoting* lower order terms of $f(n)$ \- Consider we can represent each lower order term by a constant $c\_0$ times some function $h\_0$ of $n$ (e.g. $c\_0 \cdot h\_0(n) = 11 \cdot \log\_2 n$). For each lower order term, we will *promote* $h\_0(n)$ to the highest order function of $n$, call it $h^\*(n)$ and leave the constant the same.

Consider the lower order terms of our example: $\\{32,\ 11 \log\_2 n,\ 5n\\}$ and the highest order term $2 n^2$. The promotions will go as follows:

$$\begin{align\*} 32 & \mapsto 32 \cdot n^2\\ 11 \cdot \log\_2 n & \mapsto 11 \cdot n^2\\ 5 \cdot n & \mapsto 5 \cdot n^2 \end{align\*}$$

Let's assume $n\_0$ is the first value of $n$ for which all lower order functions of $n$ are less than or equal to the highest order function of $n$. In our example we have:

$$\begin{align\*} 1 & \leq n^2 & \forall n \geq 1\\ \log\_2 n & \leq n^2 & \forall n \geq 1\\ n & \leq n^2 & \forall n \geq 1 \end{align\*}$$

Thus we have found our $n\_0 = 1$. Now we can replace the lower order terms in $f(n)$ with their promoted counterparts to get:

$$\begin{align\*} f(n) & = 32 + 11 \log\_2 n + 5 n + 2 n^2\\ & \leq 32 n^2 + 11 n^2 + 5 n^2 + 2n^2 & = 50 n^2 \end{align\*}$$

With this he have found our $c = 50$. Thus we can conclude:

$$f(n) \leq 50 n^2 \quad \forall n \geq 1 \quad \implies f(n) = O(n^2)$$

> For *demoting* lower order terms we simply remove them from the equation to get:

$$\begin{align\*} f(n) & = 32 + 11 \log\_2 n + 5 n + 2 n^2\\ & \geq 2n^2\\ & = 2n^2 \end{align\*}$$

Thus we can conclude:

$$f(n) \geq 2 n^2 \quad \forall n \geq 1 \quad \implies f(n) = \Omega(n^2)$$

Then we clearly get:

$$f(n) = O(n^2) \land f(n) = \Omega(n^2) \implies f(n) = \Theta(n^2)$$

---

Typically, most of these operations are simple enough to just conclude $f(n) = \Theta(n^2)$ in one fatal sweep, though it does always help to determine $c$ and $n\_0$ explicitly when you need to. Clearly, the $c$ we find here is a loose upper bound and you could usually restrict it further if you needed to.

At this point I am assuming you have a summation of functions that are monotone non-decreasing. You must be a bit more careful when you have decreasing lower order terms, but these are usually not a big problem.
> 2 votes

# Answer
Since it seems to be an unfulfilled clause in this discussion, let me add a quick proof that the following equations hold:

$ log(n) \leq \sqrt {n} $ for all $n \geq n\_0$, where $n\_0$ is some constant.

proof by L'Hospitals rule:

$$\lim\_{n\to \infty } \frac{\log(n)}{\sqrt{n}} = \frac{\frac{1}{n}}{\frac{1}{2\sqrt{n}}} = \frac{2\sqrt{n}}{n}=\frac{2}{\sqrt{n}} \rightarrow 0$$

similarly:

$$\lim\_{n\to \infty } \frac{\sqrt{n}}{\log(n)} = \frac{\frac{1}{2\sqrt{n}}}{\frac{1}{n}} = \frac{n}{2\sqrt{n}}=\frac{\sqrt{n}}{2} \rightarrow \infty$$

We proved $\lim\_{n\to \infty } \frac{\log(n)}{\sqrt{n}}$ is $0$, which means essentially $ log(n) \< \sqrt {n} $ for all $n$ sufficiently large, and also that $\lim\_{n\to \infty } \frac{\sqrt{n}}{\log(n)}$ is $\infty$ therefore does not exist.
> 2 votes

# Answer
Find $c$ and $n\_0$ for $\Omega$ and then find other $c$ and $n\_0$ for $O$. This way, you prove that the function is both $\Omega(\sqrt n)$ and $O(\sqrt n)$, therefore, it is $\Theta(\sqrt n)$.

EDIT: I am changing the answer to get a bound from the well-known inequality $\log x \< x$ for $x \> 0$.

For $\Omega$: use that $\log n \ge 0$ for $n \ge 1$, which implies that $27 \log n \ge 0$ and then $27 \log n + \sqrt n \ge \sqrt n$. Therefore, you have $c = 1$ and $n\_0 = 1$.

For $O$, notice that $\log n = \log(\sqrt n \sqrt n) = 2\log \sqrt n$.

Then, using that $\sqrt n \> 0$ for $n \ge 1$ you have $\log \sqrt n \< \sqrt n$, thus

$$27 \log n + \sqrt n \le 27 \cdot 2\sqrt n + \sqrt n = 55 \sqrt n.$$

Thus, you have $c = 55$ and $n\_0 = 1$.
> 0 votes

---
Tags: time-complexity, asymptotics, landau-notation, big-o-notation
---


title: Generalized geography game graph

text:
# Question
Title: Generalized geography game graph
I'm studying the Sipser textbook for my theory of complexity class. In a part of the book (i.e., Space Complexity chapter), for showing that Generalized Geography game is PSPACE-complete, the author has given an argument to model this game with TQBF problem (which is proven to be PSPACE-complete).

In a step of the argument, he has tried to construct a directed graph by using the definitions of TQBF problem (universal and existential quantifiers). What he has come up with is the following graph:

I have some questions about this graph:

1. I, actually, don't get it why the diamond structure has been used for showing choice possibilities of player $x\_i$. Couldn't we use a simple structure like what we do on binary trees?

2. How would it be if we use a hexagon shape instead of diamond for showing choices of $x\_i$?

# Answer
Your graph based on a binary tree would have exponential size (it would require at least $2^k$ nodes), which is probably no good for the reduction; an exponential blow-up in the size of the problem instance isn't ok.

Yes, you could use a hexagon instead of a diamond. I don't see any advantage, but it would also provide a valid reduction.
> 1 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Find the bitwise AND of a subarray closest to given number
It was a question I was asked in an online assessment for a company.

Please help me in this question-

> Given an array, $A$ of size $N$ and an integer $P$ , find the subarray $B = A\[i \dots j\]$ such that $i \leq j$ and compute the bitwise value of subarray elements i.e say $K = B\[i\] \mathbin{\\&}B \[i+1\] \mathbin{\\&} \cdots \mathbin{\\&}B\[j\]$.
>
> Output the minimum value of $|K-P|$ among all values of $K$.
>
> Size of array: $1 \leq A.\mathrm{size} \leq 100000$
>
> $0\le A\[i\]\le 10^8$

I could only think of brute force.

# Answer
> 2 votes
Let f (i, j) = AND ($A\_i, A\_{i+1}, ..., A\_{j-1})$ for $0 ≤ i \< j ≤ n$. $f (i, j)$ has the property that whenever $i ≤ i' \< j' ≤ j$, $f (i, j) ≤ f (i', j')$.

We also have $f (i, j)$ = AND($(f (i, k), f (k, j)$) for any $0 ≤ i \< k \< j ≤ n$.

Because of these properties, we get an algorithm slightly better than brute force as follows:

Keep track of the optimal solution so far, initialising with f (0, 1). For 0 ≤ i \< n: If $a\_i ≤ P$ then check if f (i, i+1) is a better solution. Otherwise, find the largest j such that f (i, j) ≥ P; it may be that j = n. Check if f (i, j) is a better solution. If j \< n then check if f (i, j+1) \< P is a better solution.

How to find the largest j in O (log n), making the total time O (n log n):

We start by building some tables, calculating all f (i, i+2) for even i, f (i, i+4) for i multiple of 4, f (i, i+8) for i multiple of 8. This is done in O (n) since there are about n values which can each be calculated with a single AND operation.

To find the largest j, we start with j = i+1, f (i, j) = a \[i\]. If j \< n is odd then we can calculate f (i, j+1); if the result is ≥ P then we replace j with j+1, which makes j even. Then if j \< n is an odd multiple of 2 we can calculate f (i, j+2); if the result is ≥ P then we replace j with j+1, which makes j a multiple of 4, and so on. This ends with j being a multiple of $2^k$ for some k. Now we try to increase j by $2^{k-1}$, $2^{k-2}$, ..., 4, 2, 1 if the increased j is ≤ n, and f (i, j) ≥ P. The total cost is O (log n) operations.

# Answer
> 0 votes
It is a nice question, because the problem is so useless that nobody has encountered it in practice, and it tests your ability to come up with algorithms on the spot.

You can use brute force with shortcuts. Let d = minimum of abs (P - K) found so far, then the AND of a subarray must be between max (P - d, 0) and P + d). To have a start value, find the single value k = A\[i\] closest to P, and the best solution so far is A \[i:i\].

The AND of a subarray only gets smaller if you add more array elements. So you do the brute force thing, starting with A\[0:0\], A\[0:1\], ... A \[0..n-1\], updating d if you have an improved value, and stopping when the AND is less than P-d. Let's say A\[i:j-1\] is \> P-d but A\[i:j\] isn't, then you set i=j and decrease i as long as A\[i+j\] \> d. You work out the details.

Note: This is obviously $O(n^2)$ but might be better. Hard to prove. And I suspect it is reasonably good for random data. It may not be an appropriate question for an online assessment, but better as an interview question where you can watch what the candidate does.

---
Tags: algorithms, bit-manipulation
---


# Question
Title: Name for multiset with fractional amounts?
What do you call a set which accepts multiples of the same element, even in fractional amount? Is there even an established for this?

Example from a video game about production chains:

For a carpenter to run at full capacity, you need: 1 carpenter 1 sawyer 0.5 woodcutter 0.25 forestry

And knowing the fractional amount is important to know for example that you can build only 1 forestry to feed 4 carpenters.

There is the "multiset", but definitions I've read all say elements must have an integer count. I've search for keywords like "multiset fractional amounts", "multiset fractional multiplicity", but didn't find anything .

There is the "knapsack" that turned out on occasion, but the problem's definitions also say the elements must have an integer count?

Am I just approaching this the wrong way??

(I'm a 1st year undergrad student in a computer science/programming degree)

# Answer
I don't know a standard name for this, but what you've described is representable as a function into $\mathbb{R}$.

For your example, if $X$ is the set of your things then you can represent your 'fractional multiset' as a a function $f : X \to \mathbb{R}$ such that

$$ f(x) = \begin{cases} 1 & x = \text{carpenter}, \text{sawyer} \\ 0.5 & x = \text{woodcutter} \\ 0.25 & x = \text{forester} \\ 0 & \text{otherwise} \end{cases}. $$

If you're looking for a way to implement this in a programming language, if you need to store only finitely many things then you could use a map/dictionary data structure. For example in java you could use some implementation of `Map<X, Float>`

As for what to call this, "fractional multiset" sounds fine as long as you explain it in whatever context you're using. Alternately you could just refer to it as a "size/measurement function".
> 3 votes

---
Tags: terminology, sets
---


# Question
Title: Check whether a directed, rooted spanning tree is actually some shortest-paths tree in $O(V + E)$ time
Given a directed graph $G = (V, E)$, with all edge weights being non-negative, someone has written a program that he/she claims implements Dijkstra's algorithm.
For a fixed starting vertex $s$, the program produces $v.d$ (*shortest distance from* $s$) and $v.\pi$ (*immediate predecessor in the shortest path*) for each vertex $v \in V$.

> **Question:** How to check whether the $d$ and $\pi$ values match those of some shortest-paths tree of $G$ in linear time (i.e., $O(V + E)$)?

---

*My attempts:*

1. Feed the $d$ and $\pi$ values into a running instance of our *real* Dijkstra algorithm and check if some step would go wrong.
The key point here is how to reduce the running time of the *real* Dijkstra algorithm from $O(E \log V)$ to $O(V + E)$, taking advantage of the existing $v.d$ and $v.\pi$ values.
2. To check the triangle inequality condition: For all edges $(u,v) \in E$, we have $d(s,v) \le d(s,u) + w(u,v)$.

> **Question:** However, is the triangle inequality condition a sufficient one for some directed, rooted spanning tree to be a shortest-paths tree?

# Answer
> 1 votes
**Hint:**

1. This question is telling us to find an algorithm in $O(V+E)$ which immediately suggests us some kind of search in the graph, i.e, DFS.
2. Using $\pi$ we should be able to build a candidate tree $T$ rooted in $s$ to test if it's shortest-path tree.
3. In each shortest-path tree, we have that for every $v \in V(T)$, $v \neq s$, the equality $d(\pi(v)) + w(\pi(v), v) = d(v)$ holds.

# Answer
> 0 votes
We can prove this in a similar way to how you prove Bellman-Ford has converged. Let $d(v)$ be the distance from root to $v$ in this rooted spanning tree and let $\delta(v)$ be the shortest distance from $s$ to $v$ in the graph. If $d(v) = \delta(v)$, then attempting to relax all edges in $E$ should not change anything. When I say "relax" I mean, invoke the triangle inequality:

```
relax(u, v):
  if d(v) > d(u) + w(u,v):
    d(v) = d(u) + w(u,v)
    pi(v) = u

```

If, at any point, a relaxation changes $d(v)$, then clearly the spanning tree path is not the shortest. This makes sense intuitively, but we can prove it formally.

**Claim**: If $d(v) \> \delta(v)$ for some node $v$, then some node $v'$ on the true shortest path from $s$ to $v$ has value $d(v')$ such that $d(v') \> d(u) + w(u,v')$ for some edge $(u,v') \in E$.

**Proof**: By induction on the number of nodes $n$ in the shortest path from $s$ to $v$.

**Base Case**: When we have $n = 2$, then we have one edge in the shortest path $s \rightarrow v$. Thus, the true shortest path has distance $w(s,v)$. If $d(v) \> \delta(v)$ then:

$$\begin{align\*} d(v) &\> \delta(v)\\ & = w(s,v)\\ & = d(s) + w(s,v) \end{align\*}$$

**Inductive Case**: Assume the claim holds for the first $n-1$ nodes on the shortest path $\\{s, u\_1, u\_2, \ldots, u\_{n-2}, v\\}$. We now prove it holds for the addition of $v$ to the shortest path.

If the claim holds for this whole path, then either some node prior to $v$ in the path triggers the if condition, and the claim holds by induction. Otherwise, we have for all nodes $u$ prior to $v$ that $d(u) = \delta(u)$ and $d(v) \> \delta(v)$. Now we need only prove that $d(v) \> d(u\_{n-2}) + w(u\_{n-2}, v)$:

$$\begin{align\*} d(v) &\> \delta(v)\\ & = \delta(u\_{n-2}) + w(u\_{n-2}, v) & \text{by construction of the shortest path}\\ & = d(u\_{n-2}) + w(u\_{n-2}, v) \quad \square \end{align\*}$$

Thus, after running the relaxation step on all edges, you should have your answer.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Can CNF with an input string be evaluated in logarithmic space?
I have been trying to solve satisfiability of

{$\<c, w\>$ | $c$ is a CNF and $w$ is a binary string which satifies the $c$}.

As first looks to me, it is satisiable in linear time ($O(n)$) since $w$ has lenght $n$.

I tried thinking about whether the space complexity of this problem can be reduced to logarithmic order. But couldn’t end up with an acceptable reason so far. Well, my first thought is the following:

Considering that CNF $c$ is composed of conjuction of some clasuses, it’s possible to write every clauses’s result (0 or 1) to the working tape and after reading the entire string, evaluate those 0’s and 1’s (which correlates with the CNF’s clauses). But this won’t result in a logarithmic space complexity anyway and I think it would be of $O(n/k) = O(n)$ where $k$ is the number of clauses.

Is there an optimize way of solving this in logarithmic space?

# Answer
> 2 votes
Yes, you can decide this language in logarithmic space, using the following algorithm:

* for each clause in the CNF:

+ do a linear scan of $w$ to see if one of the literals in the clause is satisfied; if not, reject
* if you got through all the clauses without rejecting, accept

What's the space complexity? Well, there are at most $n$ clauses, so we need at most $\lg n$ bits to store the loop counter to keep track of which clause we're currently on. We also need to store the current clause; there are at most $n$ variables in the formula, so we need at most $3 (1+\lg n)$ bits to store the clause. Therefore, we need at most $O(\lg n)$ bits in total of space.

Of course, the running time is not optimal (it is $O(n^2)$ or so), but that doesn't matter, as we're only counting space complexity.

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


# Question
Title: Proving $L = \{\langle M, w, n \rangle$ : $M$ accepts $w$ within $n$ steps $\}$ is decidable
> Show the following problem is decidable: Given $w\in \Sigma^{\*}$, $n\in \mathbb{N}$, and a Turing machine $M$, does $M$ on $w$ halt within $n$ steps.

My Thoughts:

I am new to proving results like these with Turing machines, so I'm often not sure what is "legal" or "not legal" with a Turing machine. For example, my textbook often gives "high level" descriptions of Turing machines doing a computation instead of formally step by step. This is the way we are expected to describe Turing machines in class, but it often leaves me unsure if I'm being rigorous enough in my description.

---

My Attempt:

Construct a Turing machine $M'$ the following way:

$M'$ = "On input $\langle M,w,n \rangle$:

(1) Represent $n$ on the tape by $n$ consecutive $1$'s

(2) Simulate $M$ on $w$

(3) Each "execution" of the transition function is followed by a mark on one of the $1$'s

(4) If $M$ enters an accepting state, accept; Otherwise, reject if $M$ enters a rejecting state or after all of the $1$'s are marked."

---

My main concern is step (1) of the algorithm. I'm really unsure if that can be done. I'm also not sure how $n$ is represented as a string for the input $\langle M,w,n \rangle$. Am I able to choose how it's encoded?

Thank you for your time and feedback.

# Answer
> 3 votes
1. This is not a problem. You have an infinite tape, so you can store whatever you want on it.
2. Depending on how explicit your proof should be, consider a few edge cases for defining your transition function:

a.) How does your TM recognize, if all n 1s are gone? The complexity of this depends on the alphabet of the TM, if $|\Sigma| \> 2$ it should be easy, else you have to work out a few details.

b.) After you've marked one of the 1s - how do you get back to the next step of your computation?

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


# Question
Title: Why does it take so long to prove optimality when warm-starting from optimal solution
So I'm solving bigger instances of some binary-linear-program using cplex. The formulations of the problem I am using is integer friendly, meaning nearly all of my instances can be solved at the root node. Additionally I have a pretty good heuristic for calculating solutions. The heuristic is quite fast and nearly always gives the globally optimal solution.

When combining cplex with the heuristic I do not achieve the performance gains I expected. I feed the globally optimal solution to cplex as a "warm-start-solution", but it still takes quite some time for cplex to proof its optimality (cplex chooses the dual-simplex for the relaxation).

I might lack some theoretical understanding, but why can't the dual-simplex just build a basis for the supplied optimal solution and show that there is nothing else to do?

# Answer
An IP-solver can use relaxations of variants of the integer program (that is, the linear program where the integrality constraints are dropped) among other steps to compute the final solution.

For these individual relaxations, the solver can indeed efficiently verify that it has an optimal basis. However, solving a relaxation is only a subproblem of solving the original IP. Therefore, even if you give an optimal solution to the original IP, this does not (necessarily) directly correspond to a basis in a relaxed LP, and the solver has to inspect other solutions than checking a basis.

---

There is one case in which providing an IP solution does allow for a fast check of optimality: when the relaxation of the IP is guaranteed to have the same solution as the original IP. (This is the case when the matrix describing the IP is *totally unimodular* or equivalently when the solution space is an *integral polyhedron*)

However, it is unlikely that the solver will be able to detect when this is the case. So, you will have to do that by some other means, and if the relaxed solution indeed solves the IP, you can let the solver solve the relaxed instance, and then the LP solver can quickly verify if your solution is optimal.
> 2 votes

---
Tags: optimization, integer-programming
---


# Question
Title: Are the two LTL properties $GF(\psi_1 \land F\psi_2 )$ and $GF(\psi_2 \land F\psi_1 )$ equivalent?
Is $GF(\psi\_1 \land F\psi\_2 )$ equivalent to the property $GF(\psi\_2 \land F\psi\_1 )$?

Attempt:

In the first property each state must eventually see $\psi\_1$ and $\psi\_2$, in the second property as well each state must eventually see $\psi\_1$ and $\psi\_2$, as such the two properties must be equivalent. Is this correct?

# Answer
You are right, but you should prove it. Here's a proof sketch:

*Proof setup:*

> Suppose that $GF(\psi\_1 \land F\psi\_2)$ is true and assume towards a contradiction that $\neg GF(F\psi\_1 \land \psi\_2)$.

*Observations:*

> Then there exists a state $s\_1$ in which $\neg F(F\psi\_1 \land \psi\_2)$, which means that every state $s\_2 \> s\_1$ has $\neg(F\psi\_1 \land \psi\_2)$, which means that for every state $s\_2$, either $\neg F\psi\_1$ or $\neg \psi\_2$.

*Contradiction:*

> But since $GF(\psi\_1 \land F\psi\_2)$, there exists a state $s\_3 \> s\_2$ such that $s\_3 \vDash \psi\_1$ and a state $s\_3 \> s\_2'$ such that $s\_3' \vDash \psi\_2$, which is a contradiction.

The other direction is identical.
> 2 votes

---
Tags: logic, formal-methods, linear-temporal-logic
---


# Question
Title: Isomorphism problem on bounded degree digraphs
By Babai & Luks (1983), it was proved that graph isomorphism problem is tractable on bounded degree graphs. However, I could not find any result when the graph is edge directed.

Is isomorphism problem tractable (or GI-complete) on edge-directed graphs with bounded degree?

# Answer
You can reduce graph isomorphism on directed graphs to graph isomorphism on undirected graphs. I think it's possible to build a reduction that preserves the bounded-degree property.

For instance, I think the following should work. Replace each directed edge `u --> v` with the following gadget:

```
u --- a --- c --- v
      |
      b

```

where `a`, `b`, and `c` are fresh new vertices (different ones for each edge).

Next, we'll add some edges to make sure that the isomorphism makes original vertices like `u`, `v` map to other original vertices (not to the new vertices). Add a new vertex `A` (just one), and connect `A` to each of the `a`'s; to do this in a way that preserves bounded edge degree, use a binary tree. Finally, add a long path `A --- A' --- A" --- A"' --- ...` with n+3 new vertices, where n is the number of vertices in the original graph. Add a new vertex `B`, connected to a path of n+2 new vertices, and connect it to the `b`-type vertices as above; and add a `C`, connected to a path of n+1 new vertices, connected to the `c`-type vertices.

Apply this transformation to both directed graphs, to get two undirected graphs. Now I think any isomorphism of the resulting undirected graphs corresponds to an isomorphism of the original directed graphs. In particular, the isomorphism must map the two n+1 paths to each other; so it must map the two `A`-type vertices to each other; so it must map `a`-type vertices to other `a`-type vertices; and similarly, `b`-type to `b`-type and `c`-type to `c`-type. Thus vertices of the original directed graph must be mapped to vertices of the other original directed graph. The mapping must preserve the direction of the edges, due to the asymmetry in the gadget above.
> 3 votes

---
Tags: reference-request, graph-isomorphism
---


# Question
Title: SVM with a priori information about class probabilities
Given are two 2-d sets, each with its own bivariate normal distribution. I need to build an SVM classifier. The a priori probabilities of each class corresponds to the size of its set (20/50 for the first and 30/50 for the second one). I am quite confused about the way to implement the knowledge about set structure and a priori probability of classes. Any ideas appreciated.

(If your idea is supported by some R packages it would be very nice.)

# Answer
> 1 votes
SVM doesn't take into account that prior knowledge about the distribution of the classes, so if you want a classifier that takes advantage of that, you'll need a different classifier.

In particular, if you know the distribution of each class and the priors (class balance), you can use Bayes rule to classify each point directly, without needing any fancy classifier. This is the optimal (most accurate) way to classify, is not hard to implement, and doesn't require any training set.

If you know that each class has a bivariate normal distribution but you don't know its parameters (mean and covariance matrix), you can use the training set to estimate these parameters, then use Bayes rule.

---
Tags: probabilistic-algorithms, classification, svm
---


# Question
Title: defining a programming language grammar for doing arithmetic
I'm studying programming language design, and I've been taught the grammar below which lets you write basic math expressions.

```
Exp ::= Num | Exp Op Exp
Op ::= + | - | * | Div
Num ::= Digit | Digit Num
Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

```

According to the lecturer things like 1 - (2 -3) are not valid as it can't generate expressions with brackets and it can't do -1 because it can't start with -1.

While I understand the first one, the second is a little harder to understand.

Also could you show me how I could modify the above grammar to add the ability to group operations, and start with a -1?

Finally, I'm told that a grammar is a set of symbols, rules, and an initial symbol? But I'm struggling to find more info on what an initial symbol is/should be.

# Answer
With `Num` you can only generate digits, so the only choice left is (starting with `Exp`) to produce `Exp Op Exp`. However, `Exp` and `Op` must both produce at least one symbol each (i.e., producing the empty word is not allowed). Hence, even if you replace `Op` with `-`, you get `Exp - 1` and `Exp` must produce another valid expression (or number), so you cannot get `-1` on its own.

> Also could you show me how I could modify the above grammar to add the ability to group operations, and start with a -1?

There are several ways of doing so. Check out, for instance, how Java does it (the "Expression3" there is roughly equivalent to your `Exp`).

> Finally, I'm told that a grammar is a set of symbols, rules, and an initial symbol? But I'm struggling to find more info on what an initial symbol is/should be.

The initial symbol is an arbitrary non-terminal symbol. Read more here on what terminal and non-terminal symbols are.
> 0 votes

---
Tags: formal-grammars, syntax, syntax-trees
---


# Question
Title: backpropagation algorithm seems to be forcing output values to middle than extremes
I have been playing around with artificial neural networks lately, specifically with the prospect of trying to replace the contrastive divergence algorithm with some type of evolutionary metaheuristic technique (i have been working with PSO) to do unsupervised pre-training, but I have come up against some issues when trying to implement the backpropagation algorithm to then fine-tune the connection weights to create a classifier.

I am using a reduced version of the MNIST dataset consisting of just the '0's and '1's to try and develop a binary classifier than is capable of distinguishing between the two different classes.

The output of my network is two visible nodes that are supposed to output \[1 0\] if the data is classified as a '0' and \[0 1\] if the data is classified as a '1'

before learning with the backpropagation algorithm i have about a 30% classification error using the quadratic error, and as i perform the supervised learning, the error gets pushed towards 12.5% but stays there as if there was an asymptote.

I thought this was showing that it was improving the classification, however when i examined the output of the network, it was just showing that with each iteration, the activations of the output nodes were moving closer to \[0.5 0.5\] before settling there.

before backpropagation was applied it was giving output values of \[0.75 0.2\] (for example) - and any attempts to train it using backpropagation just pushed those values toward \[0.5 0.5\] rather than amplifying the difference.

can anyone offer any insight as to why this might be happening? is this a common problem when training neural networks? or does it just sound like an implementation bug? i have implemented my backpropagation algorithm in a similar fashion to that which is found here.

# Answer
I have run into a similar issue when trying to train a neural network with hidden layers for regression. My network simply learned to always predict the mean of all target values in the training set.

In my case, the problem was missing input normalization (my input data had values in the 100,000s) in combination with sigmoid units: The easiest way for the network to reduce the loss function (mean squared error) was to simply set the weights in the early layers to very small values and the output unit's bias to the data's mean value.

After that, the network was stuck and no amount of training seemed to change anything, since the absolute gradient values were too small.
> 1 votes

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


# Question
Title: how do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates
How do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates?

# Answer
> 1 votes
The nice thing about small Boolean circuits like this, is there are only a few possible inputs.

With two input wires, there are $2^2=4$ possible inputs to your circuit: $00, 01, 10, 11$. You can test each one and write down its output. Then compare that to the XOR gate's outputs.

If the two line up, then the circuits are equivalent! And if they're not, something has to be adjusted.

# Answer
> 0 votes
Just write down what the output of every circuit is. In the first example, the left circuit is X = NAND (a, b), top middle is Y = NAND (a, X), bottom middle is Z = NAND (X, b), right = NAND (Y, Z).

Substitute everything into the eqation for the right circuit, then use Boolean algebra.

---
Tags: logic, boolean-algebra
---


title: Symmetry of NP completeness

text:
# Question
Title: Symmetry of NP completeness
To show that some problem X is NP-complete, we usually show that it is in NP and that an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem like SAT.

At the same time, informally, the NP-completeness definition usually says that solving any single NP-complete problem implies a solution to *all* NP-complete problems.

If both statements above are correct, then the above "proof approach" (showing that "solving X" $\implies$ "solving SAT") also somehow implies that an efficient algorithm for SAT implies an efficient algorithm for X. In general reductions are not symmetric, so why is this the case here?

# Answer
> \[...\] an efficient algorithm for deciding X implies an efficient algorithm for deciding some known NP-complete problem like SAT.

**Be careful with this!** In the context of NP-completeness we work with *many-one reductions*, not *Turing reductions*. This means you are *not* allowed to assume the existence of an efficient algorithm for $X$; this is too strong an assumption since it would allow you arbitrary access to the algorithm deciding $X$. Rather, you must *reduce SAT to an instance of $X$*. In fact, it is irrelevant whether $X$ can be solved efficiently or not (or even solved at all!). This establishes *NP-hardness*; for NP-completeness you also need to show $X \in \textbf{NP}$.

Note it is only *once you have established NP-hardness of $X$* that you can say the existence of an efficient algorithm for $X$ implies the existence of an efficient algorithm for SAT (or any problem in NP). However, this is only an *implication* of the NP-hardness of $X$, *not* the actual requirement for $X$ being NP-hard.
> 3 votes

# Answer
> At the same time, informally, the NP-completeness definition usually says that solving any single NP-complete problem implies a solution to all NP-complete problems.

Correct, only it implies a solution to any NP problem, yours is a weaker statement. To be precise, a polynomial time solution to an NP-complete problem implies a polynomial time solution to any NP problem.

> If both statements above are correct, then the above "proof approach" (showing that "solving X" ⟹ "solving SAT") also somehow implies that an efficient algorithm for SAT implies an efficient algorithm for X.

Yes, only the fact that "solving SAT"⟹ "solving X" is already true as per your first statement (a consequence of the Cook-Levin Theorem), and the result stands independent of this reduction. You might want to take a look at Karp and Cook reductions, as others have pointed out, as NP-completeness is usually defined in terms of Karp reductions, so "solving A" ⟹ "solving B" where B is NP-complete does not necessarily mean A is NP-complete in the sense of Karp reductions.
> 1 votes

---
Tags: np-complete, reductions
---


# Question
Title: Finding an interval in a binary search tree that contains a point
I have a binary search tree where nodes are non-overlapping intervals. I'm given a point, and I need to determine which interval the point belongs to (if any). This is easy to do because I can compare against the low and high of each interval and descend either left, right, or exit.

Is it possible to only compare against the low, or the high, or some kind of median to reduce the number of comparisons in the average case? I know the optimal lower bound would be O(lg n) but in many cases the max of a predecessor is very close to the min of a node, which seems redundant.

I'm wondering if there is a way to branch more aggressively at first and make small adjustments along the way. Potentially determining the next step based on which direction we branched previously.

I could not find any literature on this. Interval trees don't quite match this setup and almost all other resources relate to overlapping intervals.

What would be an optimal algorithm to find an interval?

# Answer
> 4 votes
You can't find a better algorithm for your problem using comparisons, because a lower bound of $\Omega(\log n)$ can be proven for these setings (proof below).

What you can do is some minor optimizations; if each node in your tree saves the end of the rightmost segment and the beginning of the leftmost segment, by adding $2$ comparisons to each query, you can immediately decide $x$ is outside any segments when it becomes out of bounds. These comparisons do not increase your overall complexity, but they also don't improve it.

---

Let us consider the data as $n$ disjoint line segments. Or to be formal, $I = \\{(i\_1,j\_1),\dots (i\_n,j\_n) \\} $

Suppose given a query $x$ we wish to determine in which interval $(i\_t,j\_t)$ our query $x$ is located at, or whether no $ 0 \leq k \leq n$ exists s.t $x \in (i\_k,j\_k)$.

Since your algorithm performs comparisons, it can be represented as a decision tree; a node represents a comparison $x : q$; the left child are the comparisons you would make if $x \< q$ and the right child the same for $x\>q$.

Note that since in your case, your values $q$ are medians, if $x=q$ you can finish your algorithm (and $x$ belongs to that segment).

Let's denote the decision tree $T$.

Some observations about $T$:

$\bullet$ $T$ MUST have at least $n+1$ unique leaves; one for each segment $(i\_t, j\_t)$ and one that represents the decision that $x$ belongs to no segment.

$\bullet$ Each inner node $v$ of $T$ has three children ($=, \<, \>)$

$\bullet$ A trenary tree of height $h$ has at most $3^h$ leaves; $3^h \geq n+1 \rightarrow h \geq \log\_3{(n+1)} \geq \log\_3{n}$

Since $\log\_3{n} = \Omega(\log n)$, we proved a lower bound for comparison based search, and thus any search as described by your algorithm must perform at least $\log n$ queries.

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