# Question
Title: When does an extendible 1:1 p.c. function have a 1:1 computable extension?
A partial computable function $\varphi\_e$, defined on a c.e. set $W\_e$, is called extendible if there exists some computable function $f$ which extends $\varphi\_e$, i.e. $\varphi\_e(W\_e) = f(W\_e)$.
My question is what are the conditions for a p.c. function $\varphi\_e$ to have an injective extension.

So far I have found some necessary conditions:

1. Obviously, $\varphi\_e$ itself should be injective.
2. $|\overline{W\_e}| \leq |\overline{\varphi\_e(W\_e)}|$. Because $f(\overline{W\_e})$ should have no intersection with $f(W\_e) = \varphi\_e(W\_e)$, so $f(\overline{W\_e}) \subseteq \overline{\varphi\_e(W\_e)}$.
This rules out $\varphi\_e(x) = x/2$, defined on even numbers. And also any other surjective partial function.

I couldn't manage to find a sufficient condition yet.

# Answer
Here is an example of an extendible, non-injectively-extendible p.c. function $\psi$ which nonetheless satisfies your conditions *(and I think indicates in general that any sufficient condition will be quite complicated)*:

Let $\langle\cdot,\cdot\rangle$ be your favorite computable bijection $\mathbb{N}^2\rightarrow\mathbb{N}$. We define $\psi$ as follows *(with the role of "$2^k$" being merely to control the range of $\psi$, and consequently show that just demanding that the range be "small" won't yield a sufficient condition)*:

* Suppose $k$ is even. Let $a\_k, b\_k$ be the unique natural numbers such that $k=2\langle a\_k,b\_k\rangle$. We define $\psi(k)$ to be $2^k$ if $\varphi\_{a\_k}(a\_k)$ halts strictly before $\varphi\_{b\_k}(b\_k)$ does, and we let $\psi(k)$ be undefined otherwise.
* Suppose $k$ is odd. Let $a\_k, b\_k$ be the unique natural numbers such that $k=2\langle a\_k,b\_k\rangle$+1. We define $\psi(k)$ to be $2^{k-1}$ if $\varphi\_{b\_k}(b\_k)$ halts strictly before $\varphi\_{a\_k}(a\_k)$ does, and we let $\psi(k)$ be undefined otherwise.

$\psi$ is clearly 1-1, p.c., of co-infinite range *(indeed, the range is "computably coinfinite" in the sense that the complement of the range contains an infinite computable set; in jargon, the range of $\psi$ is **non-simple**)*, and extendible: it is extended by the function $x\mapsto 2^{2floor({x\over 2})}$. However, it's easy to show that it's not extendible to a 1-1 total computable function, essentially since such an extension would have to always guess correctly whether one program halts before another does.
> 3 votes

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


title: Time Complexity of the code

text:
# Question
Title: Time Complexity of the code
I am having trouble finding the time complexity of the below code.

```
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """

        if root is None:
            return True

        def height(root):
            if root is None:
                return 0
            left = height(root.left)
            right = height(root.right)

            return 1 + max(left, right)

        def check(root):
            if root is None:
                return True

            if abs(height(root.left) - height(root.right)) < 2:
                return(check(root.left) and check(root.right))
            else:
                return False

        return check(root)

```

Is it `O(n^2)` or `O(n)` because first we are checking for the root, and that takes `O(n)` time and then we check for the left subtree and the right subtree, where the elements searched are halved each time?

Thanks!

# Answer
Your code has worst-case complexity $\Omega(n^{1.5})$. Consider a tree of height $h$ which is composed of a "backbone" of $h$ nodes, out of the $i$th of which (counting from the root) there is a path to the right ending at depth $h$. As an example, here is the case $h=4$:

The height is computed along the entire backbone. The subtree rooted at the backbone node of depth $h-\ell+1$ has $\binom{\ell+1}{2}$ nodes (where $\ell=1$ corresponds to the backbone's leaf), and so computing the height of all subtrees along the backbone takes time proportional to $$ \sum\_{\ell=1}^h \binom{\ell+1}{2} = \binom{h+2}{3} = \Theta(h^3). $$ In contrast, the tree contains $\binom{h+1}{2} = \Theta(h^2)$ nodes, so the running time in this case is $\Omega(n^{1.5})$ (in fact, it is $\Theta(n^{1.5})$ in this particular case).
> 2 votes

# Answer
Imagine you have left and right graph each with n nodes. Define complexity of check as $C(n)$ and complexity of height as $H(n)$. Complexity of height calculation $H(2n) = 2H(n)$ is linear or $H(n)\approx O(n)$.

Now complexity of check

$C(2n)=2C(n)+2H(n)=2\big(2C(n/2)+2H(n/2)\big)+2H(n)=$

$=4C(n/2)+4H(n/2)+4H(n/2)=4C(n/2)+8H(n/2)=$

$=...=2nC(1)+(2n\log\_2 2n)H(1)$

So overall complexity is $O(n\log n)$.

It is unexpectedly good. At first I thought it will be worse than $O(n^2)$.

The algorithm can be improved to $O(n)$ if you combine height and check functions and return height and check together:

```
def height_and_check(root):
# returns height and check pair
    if root is None:
        return 0, True

    left_height, left_check = height_and_check(root.left)
    right_height, right_check = height_and_check(root.right)

    height = 1 + max(left_height, right_height)

    check = abs(left_height - right_height) < 2 \
            and left_check \
            and right_check

    return height, check

```
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, binary-trees, recursion
---


# Question
Title: Subsampling of Frequent Words in Word2Vec
I am reading through the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf

Under section 2.3 on page 4 the authors discuss subsampling of frequent words.

Now based on my understanding of subsampling of frequent words, the goal is to reduce the number of times we sample frequent words. But here is what the paper states:

"To counter the imbalance between the rare and frequent words, we use a simple subsampling approach: each word $w\_i$ in the training set is discarded with probability computed by the formula

$$P(w\_i) = 1 - \sqrt{\frac{t}{f(w\_i)}}$$

where $f(w\_i)$ is the frequency of word $w\_i$ and $t$ is a chosen threshold typically around $10^{-5}$."

Now, I am interpreting $f(w\_i)$ as an integer value that essentially counts the number of times $w\_i$ occurs in the corpus. But this seems to not make any sense because all words then discarded with probability $.99$ or greater. Should I instead be interpreting $f(w\_i)$ as $\text{count}(w\_i)/\text{total\_count}$ where $\text{total\_count}$ is the number of words in the corpus?

# Answer
> 3 votes
My guess is that we should regard $f(w\_i)$ as a number between 0 and 1, i.e., the number of times word $w\_i$ appears divided by the number of words. This makes it an estimate of the probability of occurrence of word $w\_i$.

Then the formula seems to lead to reasonable results. If you have a very frequent word (appears as a $10^{-3}$ fraction of the words), we have $P(w\_i) = 1 - \sqrt{10^{-2}} = 0.9$, so it's very likely to be discarded. If you have a moderately infrequent word (probability of occurrence $10^{-5}$), then we have $P(w\_i) = 1 - \sqrt{1} = 0$, so it won't be discarded. If you have a word that is even rare than that, it won't be discarded either. So this discards very frequent words with high probability and keeps almost all words that are rare or moderately rare.

---
Tags: machine-learning, natural-language-processing
---


# Question
Title: What is the benefit of using one to one thread mapping model instead of Many to Many or two level?
So in the silberschatz O.S book it says Windows uses one to one model (mapping user level threads to kernel level threads)

but why? i thought many to many and two level models are much better, specially two level model, so why not use the two level mode or many to many? whats the benefit compared to other models and isn't there some overhead and limitation(like number of threads) because of using one to one?

overall, if someone wants to create a new O.S, how should he know which model to choose?

# Answer
I am gonna be very careful here and say it is due to complexity of managing threads at two different levels did not produce the expected results, the lack of a direct mapping caused issues meeting POSIX threads requirements. Notice that in the book it says that Solaris 8 and before have implemented many to many model. Here you can see the document they "explain" the retirement of this model.

> The Solaris 9 Operating Environment does not include an alternate threads implementation. The old MxN implementation has been gracefully retired and replaced with an enhanced version of the 1:1 implementation. The /usr/lib/lwp directories which held the alternate library in Solaris 8 software have been preserved, but these now simply link back to /usr/lib. Extensive testing indicates that this decision should cause no issues for existing applications. Most applications are expected to benefit from this move and binary compatibility is preserved.

Again, sadly, there was nothing concrete stated as reason, but my guess will be complexity.
> 1 votes

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


title: C++ Strings vs. Character Arrays

text:
# Question
Title: C++ Strings vs. Character Arrays
Why do you think it is that most C++ instructors teaching college level computer sciences discourage or even forbid using strings for text, instead requiring students to use character arrays?

I am assuming this methodology is somehow intended to teach good programming habits, but in my experience I don't see anything wrong with just using strings, and they are significantly easier to use and learn.

# Answer
> 7 votes
Koenig and Moe's *Accelerated C++* and Stroustrup's *Programming: Principles and Practice Using C++* are using std::string and other components from the standard library from the start. If I remember correctly, they don't even present C arrays for Koenig and Moe and Stroustrup does it quite late in the book (perhaps even just in an annex).

That approach, qualified as *modern*, is the preferred one in my circles. The other approach, often qualified as *historic*, follows more closely how C++ evolved, but doesn't take advantage of "newer" (relatively, they are 15 years old now) development and doesn't teach what is practised now (at least on projects not encumbered with too much legacy) but 10 years ago (there is always a lag before being mainstream).

# Answer
> 7 votes
For a CS student, the professor may discourage std::string and ask for char array, so as to teach basics of array. In my school, the teacher asked us to write C routines like `strlen`, `strcmp` etc. on our own. It can't get any low level then this (leaving assembly!).

By using array, instead of string, you can learn memory-management, string operations, notably parsing string. By iterating over array, you are basically parsing string, looking for white-space, special chars, tokens etc.

But I am not recommending array over string, at all. I am just giving a reason to cope with arrays, in university.

# Answer
> 4 votes
I can't say anything about "most" versus "some" programming instructors, but I can say that in a CS curriculum, the early programming courses have two goals:

* Prepare students for software engineering-type topics
* Get students used to what the basic operations a computer does are and how different implementations of higher-level concepts like strings behave

These are somewhat at odds sometimes, and different teachers will make different tradeoffs.

# Answer
> 4 votes
I guess it depends on what you're trying to teach in that course... "Computer Science" is a somewhat vague definition.

If the course is on Algorithms and Data Structures, then teaching students about `std::string` has absolutely no didactic value. Using `char` arrays as an introduction to arrays and operations thereon, however, is quite legitimate.

If the course is on object design, then I guess `std::string` has some value as an example of an abstract data type.

If the course is just on best practices in C++, then I'd worry about the kind of college your at and how they design their Computer Science curriculum.

# Answer
> 2 votes
I guess you misunderstood the actual goal of your course, as good C++ (basically) uses the abstractions provided by the standard library (why would you want to reinvent the wheel?).

There is even a quote by Stroustrup saying "keep arrays out of interfaces" in his FAQ where he gives some hints how to write safe code. Therefore I doubt that you are actually told to not use them, because they are bad, but to learn some fundamentals of how things work, so you can later use that understanding if you actually need to get into optimization or other work, for which you need the real basics.

# Answer
> 0 votes
In some case string are good in other they arent same for char

/\**Exemple 1 string use in this case string is cut by Spaces at the output if we wrote del test.txt the the output will be Line 1 del Line 2 test.txt wich is not good \**/

```
#include <iostream>
#include <stdlib.h>
using namespace std ;

string get_input ;

int main()
{
main:
    cin >> get_input ;
    system(get_input.c_str()) ;
    goto main ;
}

```

/\** Exemple 2 same program but we pass the input in a char with a field of 80 the output for the same cmd as first exemple will be del test.txt on the same line wich good\**/

```
#include <iostream>
#include <stdlib.h>
using namespace std ;

char input[80] ;
string get_input ;

int main()
{
main:
    cin.getline(input ,80) ;
    get_input = input ;
    system(get_input.c_str()) ;
    goto main ;
}

```

Strings are objects that represent sequences of characters.

The standard string class provides support for such objects with an interface similar to that of a standard container of bytes, but adding features specifically designed to operate with strings of single-byte characters.

The string class is an instantiation of the basic\_string class template that uses char (i.e., bytes) as its character type, with its default char\_traits and allocator types (see basic\_string for more info on the template).

Note that this class handles bytes independently of the encoding used: If used to handle sequences of multi-byte or variable-length characters (such as UTF-8), all members of this class (such as length or size), as well as its iterators, will still operate in terms of bytes (not actual encoded characters). -C++ Reference http://www.cplusplus.com/reference/string/string/ \[1\]:

i suggest to look at:

---
Tags: education, arrays, strings
---


# Question
Title: Calculating the set field of associative cache
In this example:

> Assume a system’s memory has 128M words. Blocks are 64 words in length and the cache consists of 32K blocks. Show the format for a main memory address assuming a 2-way set associative cache mapping scheme. Be sure to include the fields as well as their sizes.

The following is supposed to be the solution:

> Each address has 27 bits, and there are 7 in the tag field, 14 in the set field and 6 in the word field.

I understand how the word field was calculated (2^6 = 64), but I don't understand how is the set field 14?.

Shouldn't the answer be 8?

Block size is 64 words, to find the number of sets we divide total number of blocks **32K** by set size which is **64\*2=128B** (multiply by 2 since it's 2-way), my calculation should be correct, am I missing something?

> 32KB/(64\*2)B = 32KB/128B = 256 = 2^8
>
> (Which implies that we need 8 bits for the **set** field)

# Answer
> 3 votes
The memory has $128$M words = $2^{7+20}$ = $2^{27}$ words. Hence it needs needs $27$ bits for address space.

Each block has $64$ words, so the block offset = $2^6$ words. So Block offset field can be represented by $6$ bits.

Number of lines in the cache = $\frac{Cache Size}{Block Size}$ =Number of blocks = $32$K blocks = $2^{5+10}$ = $2^{15}$ blocks.

Number of sets in the cache = $\frac{Number of Lines}{Set Associativity}$ = $2^{15}$ blocks / $2$ blocks per set = $2^{14}$ sets. Hence number of bits to represent set field = $14$ bits.

Number of tag bits = $27 - (14+6) = 7$ bits.

# Answer
> 0 votes
To calculate the size of set we know that main memory address is a 2-way set associative cache mapping scheme,hence each set contains 2 blocks.

```
Hence Total no. of sets = Size of cache / Size of set
                        = (2^15/2^1)
                        = 2^14

```

(Which implies that we need 14 bits for the set field)

---
Tags: cpu-cache
---


# Question
Title: What is the use case for multi-type-parameter generics?
In C#, one can define a class/method/function with multiple type parameters. For example,

```
// function
void foo<T1, T2>(T1 x, T2 y) { /*body*/}

// class
class Bar<T1, T2> { /*body*/ }

```

I understand **how** to use it, but I don't understand **why** I need it. So I'm hoping someone can answer the following questions:

1) What is the use case for multiple type parameters?

2) Based on the use case given in Question 1, what are the alternative solutions for that use case if multiple type parameters is not a feature of the language in use?

# Answer
Some use cases for multiple type arguments include

* maps/dictionaries `Map<K,V>`, where you have one key parameter and one value parameter
* product types `Pair<A,B>`
* sum types, AKA variants `Variant<A,B>`, which represent a value which might be either of type `A` or of type `B`
* Function-like types `Func<A,B>` representing a function from `A` to `B`
* "Visitor" objects for parametric types. I.e. a visitor for `List<A>` is `ListVisitor<A,R>` where `R` is the return type of the visitor.

If we did not have multiple type arguments, or any other way to emulate multiple argument types (e.g. nested parametric classes `class T<A> { class U<B> { ...` which are a sort-of curried version of the two-arguments class), we could not express the examples above in a generic way.

Of course, a programming language could disallow generic classes and still have a specific primitive type for some of the examples above. For instance, `Func<A,B>` could be a primitive type, instead of a user/library-defined class type.
> 17 votes

---
Tags: type-theory, abstract-data-types
---


# Question
Title: Fantasy premier league dream team algorithm?
For those of you who are not familiar with FPL, here's a short version. You have players playing as either Goalkeeper, Defender, Midfielder or Forward. Each player has some price (either rounded to .5 or .0), and based on their real life performance you earn points. You have a budget of 100£ and you need to build a team, keeping in mind you have a limit for players on each position.

**Now, the problem is: If you have all players prices, their positions and total number of points they scored in a season, how do you find the highest scoring team (team score is equal to sum of all players' individual points) with, for example, 4-4-2 formation? (1GK, 4DEF, 4MID, 2FWD)**

I guess this is a variation of knapsack problem, where you have limitations to have exactly 11 players, and exactly 4-4-2 formation. So is that the best way to solve this problem and how would you solve it with these modifications/limitations, or is there a better solution?

# Answer
You can formulate an integer program for this problem. For each player $i$ let $a\_i$ be the number of points the player scored, $p\_i$ is his price. Moreover, let $G, B, M, F$ be the set of goal keepers, backs, midfielders and forwards, respectively, $P := G \cup B \cup M \cup F$ the set of all players, and $C$ is the salary cap. We use binary variables $x\_i \in \\{0, 1\\}$ for each player $i$, were $x\_i = 1$ iff player $i$ is in the optimal roster, $0$ otherwise. The optimal roster is then induced by the solution of the following program: $$\begin{aligned} \text{maximize } & \sum\_{i \in P} a\_i x\_i\\ \text{subject to } & \sum\_{i \in P} p\_i x\_i \leq C\\ & \sum\_{i \in G} x\_i = 1\\ & \sum\_{i \in B} x\_i = 4\\ & \sum\_{i \in M} x\_i = 4\\ & \sum\_{i \in F} x\_i = 2\\ & x\_i \in \\{0, 1\\} & i \in P \end{aligned} $$ Now you may have noticed that the objective function + capacity constraint is indeed a knapsack problem but you have additional constraints on the formation.

Although you can use a MIP solver of your choice, you might even exploit this knapsack structure as a subproblem by using a knapsack solver (I think there is some very popular dynamic programming approach).
> 3 votes

---
Tags: optimization, knapsack-problems
---


# Question
Title: How is deciding a problem not equivalent to finding a valid certificate for verification?
Take a decision problem $Q$, which maps encoded instances of a problem, i.e., $\lbrace 0, 1 \rbrace \ast$ to the solution set $\lbrace 0, 1 \rbrace$.
Since $Q$ is in $NP$, there exists a verification algorithm $A$, which takes an input and a certificate, in that order, as arguments and maps those to $\lbrace 0, 1 \rbrace$, depending on whether there exists a certificate proving that the solution to the input is $1$.

If this presentation of what a verification algorithm does is correct, then it is unclear to me if, for a binary-encoded problem instance $x$,

$$Q(x) = 1 \iff \exists y (A(x, y) = 1).$$

It seems to me that *if* there is a certificate, this means that the decision for that input is affirmative, so that in theory, you could attach sufficient information to a certificate such that it characterizes a solution to the decision problem, iterate through the entire set of certificates and, once you have found one that satisfies $A(x, y) = 1$, you have also found a solution to the problem for the respective input.

Maybe someone could explain to me if that equivalency above is wrong and if so, why. I know the difference between a problem and the verification part, but then again, on some level I do not.
Neither am I sure about anything else, so feel free to point out mistakes.

# Answer
> 8 votes
The problem is in the following excerpt:

> iterate through the entire set of certificates

There might be many possible certificates. For example, a SAT instance on $n$ variables has $2^n$ certificates. Iterating through all of them would take exponential time. Although processing each takes only polynomial time, processing all would take exponential time. This is the difference between verification and decision.

Your argument does show that if a problem is in nondeterministic time $T(n)$, then it is in deterministic time $\exp T(n)$. For example, $\mathsf{NP} \subseteq \mathsf{EXP}$.

---
Tags: complexity-theory, computability
---


# Question
Title: The task of recognizing game units in the screenshot
I'm new to computer vision and I want to solve the task of recognizing the game units of the game Clash Royale in the screenshot. Briefly, there are about 70 different types of gaming units belonging to two teams (they differ a little in colors and some are visible in front, others with backs). I want to find game units on the screenshot and classify their type of unit (then health and the team).

What are the best tools for task like this? What libraries will I use to simply teach the model? How many teaching examples do I need to learn the model? It seems that the quality of the screenshots is quite good and the images are clear. To what size should I reduce the screenshoot to get a good model and its speed? Maybe someone had a similar experience?

I think about CNN or a lot of HAAR cascades for each of the types of units, but I would like to receive advice.

# Answer
> 1 votes
Machine learning doesn't seem needed, since the image of each unit is always identical. One approach is to obtain a clean image of each unit, and then use template matching to find all locations where the template occurs in the screenshot. You might be able to check all locations in the screenshot whether they exactly match the template image (you will probably want to mask out the part where the health appears, as that will obscure the image). This can be done very efficiently.

To recover the health, you might also be able to do template matching on the numbers 0-10.

The way to tell what resolution you can downsize to is empirically: you experiment with different resolutions and measure the accuracy for each. There's probably no way to predict without trying it.

If you want to try machine learning, you could try a CNN, or better yet, you could try retraining the YOLOv3 object detector for your particular images (see, e.g., the YOLO project page or here). You will probably need a larger training set this way, and you'll have to do a bunch of manual annotation of sample screenshots.

Tool and library recommendations are off-topic here.

---
Tags: machine-learning, artificial-intelligence, computer-vision, image-processing, computer-games
---


# Question
Title: Choosing a random edge with restrictions
Given a bipartite graph $G = (V, U, E)$ such that $|V| = |U| =2^n$, one wants to sample an edge from $G$, uniformly at random, with the following operations:
1. One can sample $u \in U$ w.p $\frac{1}{|U|}$ ,or $v \in V$ w.p $\frac{1}{|V|}$.
2. There exists a polynomial time oracle, which can, given $u \in U$ (or $v \in V$), returns the degree of $u$ (the degree may be exponential in $n$).
3. The size of $E$ is unknown.
4. One can not test, given $u$ and $v$, if there is an edge between $u$ and $v$.
5. There is an oracle which can, given $u$, return $v$ such that $v$ uniformly chosen from the set of all neighbors of $u$.

If one has only polynomial time (in $n$) - is it possible to choose an edge uniformly at random? Is it possible to choose from a distribution close to uniform?

Without these restrictions, it would have been possible to choose $u$ w.p $\frac{deg(u)}{\sum deg(u)}$, and then choose $v$ u.a.r from the neighbors of $u$.

# Answer
> 1 votes
You can't. Consider the bipartite graph with a single edge $(u\_0,v\_0)$, with $u\_0,v\_0$ randomly chosen at time of creation of the graph. Then sampling from $U$ has only a $1/2^n$ chance to hit $u\_0$ each time, and sampling from $V$ has only a $1/2^n$ chance to hit $v\_0$ each time, so you need exponentially many samples before you can find that edge.

In particular, after making $q$ samples, there is at most a $q/2^n$ chance that you receive either $u\_0$ or $v\_0$. Without sampling either $u\_0$ or $v\_0$ you have no hope of outputting the edge $(u\_0,v\_0)$. So after polynomially many samples, there's only an exponentially small chance of outputting that edge. Yet a correct algorithm must always output that edge every time. So in general, there's no way to solve your problem, or even to output from a distribution close to the desired one.

---
Tags: algorithms, complexity-theory, graphs, probabilistic-algorithms
---


# Question
Title: Find an edge that is completely visible from point outside a polygon (Convex Hull)
I want to implement algorithms from this paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5609&rep=rep1&type=pdf

In particular, I am currently dealing with the one in section 2.2.1. In page 4 (first paragraph), one algorithm step is as follows:

Find an edge $(v\_k, v\_{k+1})$ of $P\_i$ ($P\_i$ is a convex hull) that is completely visible from $s\_i$ ($s\_i$ is a point outside the convex hull).

My question is, how can I find a completely visible edge of a convex hull, that is completely visible from a point outside the convex hull?

# Answer
> 1 votes
It is not too hard. connect the point to the end-point of an edge. If none of these two segments has an intersection with convex-hull, it means you can see that edge completely (as you consider a convex polygon).

To find the intersection, you can use a binary search and find that is there any intersection or not.

---
Tags: algorithms, computational-geometry, search-algorithms, polygons
---


# Question
Title: Concatenation of language to itself zero times
I was solving this question:

> Which of the following statement(s) is/are false?
>
> 1. $L^0=\\{\epsilon\\}$
> 2. $|L^0|=0$

The answer given was None. That is, none of these statements are false and both are true. However, I feel both are wrong. I feel

$L^1=L$ and
$L^0=\phi$

Also

$|L^0|=|\phi|=0$

Am I wrong with this?

# Answer
> 4 votes
$L^0$ is defined to be $\\{\varepsilon\\}$. (Since a string formed by concatenating zero strings together is the empty string).

This gives the answer to the first question - which is correct.

Now, $\\{\varepsilon\\}$ contains exactly one string - which is the empty string. Therefore: $|\\{\varepsilon\\}|=1$. (The given answer is wrong).

Note that $|\\{\varepsilon\\}|=1\ne0=|\varepsilon|$. Also, note that $\\{\varepsilon\\} \ne \emptyset$.

# Answer
> 4 votes
Mickey's answer is completely correct. But I'd like to explain a bit more thoroughly why that's the correct answer.

At first glance, it would make sense to have $A^0 = \varnothing$: that is, the empty set. But in practice, the special cases of this operation are defined in a way that lets useful theorems hold, and letting $A^0 = \varnothing$ doesn't prove as useful as letting $A^0 = \\{\varepsilon\\}$.

In particular, consider the concatenation operation on languages. If we have languages $A$ and $B$, then $AB$ is the language "any string from $A$ followed by any string from $B$". It follows that you can't concatenate *anything* with the truly empty language $\varnothing$: $A \varnothing = \varnothing$, and $\varnothing A = \varnothing$.

In the general case, we know that $A^x A^y = A^{x+y}$. For example, $A^2 A^3 = A^5$. And this is a useful rule for various proofs. But if we say that $A^0 = \varnothing$, then this breaks down: $A^2 A^0 = A^2 \varnothing = \varnothing$ rather than $A^2$.

If instead we define $A^0 = \\{ \varepsilon \\}$, then the rule still holds: $A^2 A^0 = A^{2+0} = A^2$. So we choose to use this definition, because it makes our system of rules more useful in general.

There are other mathematical reasons why this is more elegant. For example, $|A^n|$ can be thought of as "the number of ways to choose $n$ elements from $A$, with replacement", and there's exactly one way to choose zero elements from any set: choosing none of them at all.

But all of these different ways boil down to: we choose to use this definition, because it makes things work out nicely. Like with anything else in mathematics, it's a conscious choice to do it this way, rather than any universal law of nature; it's just a conscious choice that leads to interesting results, and thus a choice we consider useful.

# Answer
> 1 votes
Here is yet another answer complementing to already completely correct answers. As chi and Draconis state, the key property is $L^{m+n}=L^m L^n$. As Mickey states but does not explain why, this leads to $L^0=\\{\epsilon\\}$. Draconis' answer apparently makes it too easy to read as an "arbitrary" choice, or even that it is an artificial choice replacing some other, "more natural" choice.1

Here's a somewhat more general perspective. Virtually always when we use the notation $x^n$ where $n$ is a natural number, we intend $x^{(-)}$ to be a *monoid homomorphism* from the natural numbers equipped with the additive structure. This means $x$ itself must be an element of some *specified* monoid. Usually, this is implicitly specified by being the one we multiplicative notation for for elements of the relevant set. The unit and operation of the additive monoid on natural numbers are $0$ and $+$. For $x^{(-)}$ to be a monoid homomorphism means $x^0=u$ and $x^{m+n} = x^m \star x^n$ where $u$ and $\star$ are the unit and operation of the specified monoid on the set containing $x$.

Now the set of finite sequences(or lists) on an alphabet $\Sigma$, often written $\Sigma^\*$, is actually the *free monoid*2 on $\Sigma$. The unit is the empty sequence $\epsilon$ and the operation is concatenation which I'll write as $\frown$ to have it be explicit. This leads to exactly the behavior you describe on the comment to the question. That is, for words $a$, $a^{m+n}=a^m\frown a^n$ and $a^0=\epsilon$. Next, given *any* monoid on a set $X$, we can define a new monoid on the powerset of $X$ (those *elements* are subsets of $X$). If $u$ and $\star$ are the unit and operation of a given monoid on $X$, then $\\{u\\}$ is the unit for the operation (which I'll call $\dot\star$), $S\ \dot\star\ T =\\{s\star t\mid s\in S \land t \in T\\}$. (Prove this.) This is, of course, exactly the monoid structure we're using when we talk about concatenating *languages* (i.e. subsets of $\Sigma^\*$). This immediately leads to $L^0=\\{\epsilon\\}$ and $L^{m+n}=L^m\ \dot\frown\ L^n$.

There are many other monoid structures we can place on the power set of $X$. For example, for *any* set $X$ which need *not* be a monoid. We have the following two monoids on the power set of $X$: 1) unit $X$ and operation $\cap$, 2) unit $\varnothing$ and operation $\cup$. (Prove that these are monoids.) If you wanted $L\_1 L\_2$ to mean $L\_1\cup L\_2$, *then* we'd have $L^0 = \varnothing$ and $L^{m+n}=L^m\cup L^n$, but $L\_1 L\_2$ usually means $L\_1\ \dot\frown\ L\_2$ as above for which the unit, and thus $L^0$, is $\\{\epsilon\\}$. Choosing $L^0$ to be $\varnothing$ while still keeping $L\_1 L\_2$ as $L\_1\ \dot\frown\ L\_2$ means $L^{(-)}$ is no longer a monoid homomorphism. This will lead to all kinds of unexpected behavior, clumsy special-cases, and missed connections.

1 Draconis' point is more that definitions can't be wrong. One is free to define things however they like no matter how clumsy, awkward, and confusing the result may be. However, some definitions are better than others.

2 Formal language theory is very much a study of various monoids and operations upon monoids. It's pretty close to just being "Monoid Theory".

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


# Question
Title: Finding Degree of match with Soundex or Metaphone
I am working on a search where user would search names. Spelling mistakes are bound to happen. I have used edit distance, soundex and metaphone implementations in java so far. Each one separately and then different combinations too. Finally, a combination of soundex and metaphone seemed to work. There are more than 30 thousand names that would be searched for the match when ever a user enters a name. The search is sequential and would stop when ever a match is found. Now the problem is. Lets say in fol figure:-

```
   User Input Name = "Peeter"

----------------------------------------------------
 Serial       Name
----------------------------------------------------
   1           Tom
   2           Petay (Near match say 70%)
   3           Jack
   4           Peteh (Near Match say 75%)
   5           Peter (The closest Match say 100%)
----------------------------------------------------

```

The closest match for "Peeter" is "Peter" and near match is "Petay", "Peteh" etc. The search would stop at "Petay", returning "Petay" as the name which would be least expected by the user. So for me, 2 solutions comes to mind.

1. Search all 30 thousand names every time, get a list of all matches and ask user to choose the best match
2. Secondly, present 3 or say 5 top matching (by top matching i mean the closest match, let say more than 90% similar sounding) names to user.

I already have implemented option 1 but it returns some times more than 100 matches! it would not be possible for the user to go through all of them. So is there any way to implement option 2 mentioned above? i.e to find out to what degree soundex or metaphone match is made to a name.

Thanks in advance.

# Answer
> -1 votes
You can use K-nearest with the data points you have like % ,freq, or score of the edit and soundex algo.

---
Tags: search-algorithms
---


# Question
Title: Decidability of a set containing first symbols of elements of a decidable set
Let's say we have an alphabet $\Sigma = \\{a,b, \dots , z\\}$

Set $A$ consists of words $x\_i$ containing symbols from $\Sigma$ alphabet, which have this structure

$x\_i := \alpha\_i \beta\_i$, where $\alpha\_i$ is just 1 symbol from $\Sigma$ and $\beta\_i \in \Sigma^{\*}$ (can also be empty)

So the set A should look like this $A = \\{ \alpha\_1 \beta\_1, \alpha\_2 \beta\_2, \dots , \alpha\_n \beta\_n, \dots\\}$

The question is:

If the set $A$ is decidable, then **should also the set $B = \\{ \alpha\_1, \alpha\_2, \dots , \alpha\_n, \dots\\}$ be decidable**?

My thoughts..

For the set $A$, we have a total computable function $f(x\_i)$ which gives an answer, whether a given input element contains in $A$ or not. Now, when we shrink $x\_i$-s and only leave $\alpha\_i$ parts, we cannot use $f$ anymore. The only idea which came to my mind, is using this naive algorithm.

get input $\alpha\_j$
for each $x\_i \in A$
if $\alpha\_j$ is prefix of $x\_i$
return YES
return NO

And here, I guess, the problem is in `for each` statement. Here we enumerate all elements of the set $A$. For being able to do this, I guess we need to use some kind of mapping $\phi : \mathbb{N} \to \Sigma^{\*}$ and then apply $f$ on the output to get all possible $x\_i$-s. This algorithm may give a correct answer, but it also may give no answer (we will never reach to `return NO`). So my conclusion was B is not decidable (B is semi-decidable). But there might also be a 'better' algorithm?

..end of my thoughts.

I apologize if my thoughts are 100% wrong. That's how far I could reach.

Any help is much appreciated.

# Answer
You probably have to twist your head a couple of times but $B$ is decidable and it does not depend on the decidability of $A$. Note that $B \subseteq \Sigma$, i.e. a subset of your finite alphabet. Thus, $B$ is finite and hence, it is decidable.

However, this reasoning is not constructive: It is just enumerating all functions $\Sigma \to \\{0, 1\\}$ (that are $2^{|\Sigma|}$, i.e. finitely many), which are all computable, and one of them is the correct function although you do not know which one.
> 3 votes

---
Tags: computability
---


# Question
Title: Reference/book recommendations for search data structure
I am interested in data structures that support efficient searching of various kinds.

When I read the Wikipedia page of "search data structure", it says "Useful search data structures allow faster retrieval; however, they are limited to queries of some specific kind". So, obviously, there exists a correlation of one specific data structure and the searching operations it supports. For example, k-d tree supports efficient query of multiple-dimensional data.

Of course, the data structures I am thinking about are not limited to arrays or trees. They can also be graphs or more advanced structures.

I am new to this field. So I am wondering if anyone can recommend some books or review papers that summarize different search/query data structures.

Thanks in advance.

# Answer
I highly recommend MIT course on Advanced Data Structures, I was watching Eric Demaines lectures, he shows multiple examples, here are some of them:

Here some suggested reading from their website:

MIT course

YouTube lectures
> 3 votes

---
Tags: data-structures, reference-request, searching
---


title: Linux OS/HW VM cooperation

text:
# Question
Title: Linux OS/HW VM cooperation
From what i've learned, the HW is responsible for setting the accessed and dirty bits in the PTE of a process, and the OS is responsible for turning them off. My question is why?
The first part, i think is because only the HW is preforming the page table walk and it's a good opportunity for it to set them (because by doing the page walk or checking the tlb, it implies that a process wanted to access/write to a page).
Does the second part have something to do with the fact that the OS manages the page cache and all the paging to the disk go through it?

# Answer
Why? Because this design works pretty well and meets the requirements, and most alternative don't or would be more expensive or slower. In particular, this division of responsibilities lets the system implement a suitable page replacement policy for virtual pages in a way that is relatively efficient.

When asking a "why is it done this way?", it's often helpful to try to imagine some concrete alternative way of doing it, and then analyze the advantages and disadvantages of the current method compared to that alternative. You haven't listed a specific alternative, so it's hard to be a lot more specific. But for instance if you tried to do it all in software (so the OS has all responsibility), without the hardware managing the accessed or dirty bits, that would be very difficult: the only methods I can think of for doing that are clunky and will cause many context switches and thus will slow down the system a lot.
> 1 votes

---
Tags: operating-systems, virtual-memory, paging
---


title: Algorithm for a 2D path-finding puzzle

text:
# Question
Title: Algorithm for a 2D path-finding puzzle
I am trying to find an algorithm for finding an optimal solution to a puzzle of a given format. The 7 by 6 puzzle board is made out of the following pieces:

The tears are as follows:

Tears and grommets can be rotated and moved around the board, but spools, tie-offs and blockers cannot.

A simple example of the puzzle in it's starting state is:

While a more complicated version and a possible solution is:

The puzzle is scored by how many pieces are used in the solution (more is better) and how quickly the puzzle is solved.

I have so far written functions to detect and read in the board, as well as a function to check that the board is valid.

In order to solve the board, I have so far tried a brute force method, which randomly shuffled and rotated the movable pieces in the puzzle and then checked if the result was a valid solution, but this was fairly slow even for the simple boards, and extremely slow for more complex boards, and of course, did not come up with an optimal solution.

I then refined it a bit by excluding obvious wrong piece placements, but this was still over a second for small boards, and anywhere from 5 to 30 seconds for larger boards, and was also not an optimal solution.

I have heard about possibly using various path finding algorithms such as Djikstra's or A\* but I'm struggling to see how these algorithms can be used to find the longest valid path, especially when branching pieces such as the 'T' and '+' pieces come into play.

Any help would be much appreciated!

# Answer
One approach would be to bring out the big hammer and try using a SAT solver. You introduce boolean variables $x\_{\ell,p,o}$, which is true if piece $p$ is placed in orientation $o$ in location $\ell$ on the grid. Then, you write down boolean clauses to encode the conditions for a grid to be valid. Finally, you do binary search: given $k$, you try to find a placement that has score at least $k$ (by writing boolean clauses to force the score to be at least $k$ and then using a SAT solver to test whether there exists an assignment to the variables that satisfies all of the clauses), and then do binary search on $k$. This might be effective, or it might be slow; it's hard to predict, so the only way to find out is to try it.

The trickiest part of encoding into SAT will probably be calculating the score. I suspect it will be useful to introduce extra boolean variables $y\_{\ell}$, which is true if the piece at location $\ell$ is connected to the spool. Then, write constraints that capture the relationship between the $x$'s and $y$'s.
> 1 votes

---
Tags: algorithms, board-games
---


title: What is time complexity in this case?

text:
# Question
Title: What is time complexity in this case?
I have the recurrence of the form

> T(n) = T(n/2) + O(n)

This can be solved using master's theorem and if i use the results of the theorem, the recurrence evaluates to a time complexity of O(n). But if i think of it in terms of its tree, the input is reducing by half each time so we have a tree of `logn` height. Cost of each level is O(n). So we might have a complexity of O(nlogn). Now i am confused that is it O(nlogn) or O(n). Please help me.

# Answer
> 2 votes
In this problem, the input size at each level of recursion is reduced by a factor of 2. At our topmost level, we have $cn$ for some constant $c$, but in the second level? In picturing a tree, our top most level (our leaf node) has one child, $cn/2$. This child has a single child of its own: $cn/4$, and so on.

To get the time complexity for our recurrence relation, we have to sum up the work done in each layer of the tree. You state that each layer does $O(n)$ work, but this is where your mistake is. Each layer does half the work of the previous layer. Therefore we end up with the summation $\sum\_{i=0}^{n}\frac{n}{2^i}$. This sum is asymptotically equivalent to $O(n)$. Therefore, the result you reached using the Master Theorem is correct.

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Improving heading measurements from low cost compass module
I have heading measurements of two Sensors (BNO055 and HMC6343) and also accurate measurements from better sensors for comparison from a rotating platform. Most of the measurements are with some kind of potentional error source like passing train, large ferromagnetic materials.

The measurements of the BNO055 can't be used at all since he mostly doesn't even react to changes in angle. The measurements of the HMC have some other problems.

* Large Offset at the Start that only converges towards the true value after some movement of the sensor (elevation change) i guess sensors needs to calibrate at the start every time
* Sometimes small global offsets towards the true value
* Larger periodic deviations and noise (esp. near rails)

If you don't want to read the paragrpahs of my endeavors below. My question is basically is it possible to get major improvements with only positional data from one sensor and the reference data and nothing else?

I'm kind of at a loss how i could improve the measurements. I started to learn about Kalman filter and tried a simple kalman filter with a linear model: x+vt+at^2/2 (x being angle etc.). But neither sensors fusion is an option because of useless BNO measurements and also a filter with just HMC measurements with state vectors (x,v) and (x,v,a) don't really improve my measurements. (x,v,a) vector is actually even worse.

I'm kind of at a loss here. I'm trying to understand unscented/extended kalman filter but atm i don't really see the point since its for nonlienar models and i don't know how i could't describe the angular movement differently than with the simple movement equation above.

I also read something about calibrating with neural networks but are not quite sure if it's worth to invest more time into it since my time is limited.

Edit: I added some pictures of the measurements so people who might want to chip in have a better idea. The blue and red lines are not interesting. Green are the accurate measurements. Orange are the measurements of my sensor. A big problem is also that the sensor doesn't measure the right heading at the start if the antenna hasn't changed elevation yet. He seems to need to calibrate for a bit to reach his estimated value.

# Answer
While 'major' improvements is subjective, you can certainly improve your system more than it is (at least as you have described). Based on your problem description, it sounds as if your measurements may be non linear (you will have to confirm this). If this is the case, then a linear filter, such as the Kalman Filter, won't work well at all.

From here, you need to determine if these 'large periodic deviations and noise' are normally distributed or not. If they are, then you can try a non-linear filter such as the Unscented Kalman Filter (If the deviations are truly 'large', the unscented filter is preferable to the extended as it is more robust to higher levels of non-linearity). If your noise and 'periodic deviations' are not normally distributed, then you will have to consider non-parametric approaches such as the Particle Filter.

As far as sensor calibration, you could try more advanced techniques, but typically the sensor manufacturer will supply some form of calibration procedure. This procedure is typically recommended unless you are absolutely sure about a different strategy.
> 2 votes

---
Tags: algorithms, error-correcting-codes
---


# Question
Title: Easiest way to find y in $x \text{ xor } y = z$ with given $x \text{ and } z$
Let's say we have given two numbers $x, z$, and we need to find another number $y$ such that $x \text{ xor } y = z$. The xor ( exclusive or ) is bitwise operation: xor table .

I know that this can be solved if we analyze both $x \text{ and } y$ bit by bit, starting from the first, but I was wondering if it can be solved by some easier way with bitwise operations.

# Answer
> 3 votes
One can observe that, for any boolean values $a,b,c$, we have $a=b$ if and only if $a \text{ xor } c = b \text{ xor } c$.

(To prove that we note that $\Rightarrow$ is trivial, and $\Leftarrow$ follows by xor-ing with $c$ once more and applying the cancellation law.)

Hence, the equation $x \text{ xor } y = z$ is equivalent to $(x \text{ xor } y) \text{ xor } x = z \text{ xor } x$ which in turn (by the cancellation law), simplifies to $y = z \text{ xor } x$.

If we wanted to be more pedantic we could explicitly point out those steps where we also implicitly used associativity, commutativity, and the identity law.

# Answer
> 2 votes
Xoring is "reversible": $y$ xored by $x$ flips the bits of $y$ where $x$ has ones. Xoring one more time restores the initial value.

$$(y\oplus x)\oplus x=y=z\oplus x.$$

---
Tags: logic, bit-manipulation
---


# Question
Title: Alternative algorithm for minimum spanning tree construction
> Let $\textit{G(V,E)}$ be an undirected connected graph with distinct costs on its edges. Initialize $\textit{T}$ to be any spanning tree of $\textit{G}$. Consider an algorithm which replaces an edge $\textit{e}$ in $\textit{T}$ by an edge $\textit{e'}$ not in $\textit{T}$, if $\textit{e' \< e}$ and replacing it still maintains $\textit{T}$ to be a spanning tree.

I want to prove that this algorithm results in a minimum cost spanning tree of $\textit{G}$.

I am trying to prove this by contradiction - consider that $ \textit{T}$ is the tree which we obtain when the algorithm ends. We assume that there exists $\textit{T'}$ such that $\textit{W(T') \< W(T)}$.

Attempt: I tried considering an edge $\textit{e}$ to be the lowest cost edge which is in $\textit{T'}$ but not in $\textit{T}$ (there is at least one since both are different spanning trees). We add $\textit{e}$ to $\textit{T}$ - thus, creating a cycle (since $\textit{T}$ was a spanning tree). There are two possible cases:

1. $\textit{e}$ is smaller than all the edges of the cycle it induced. But, in this case, the algorithm would not have stopped at $\textit{T}$, it would have replaced one of the edges of the cycle by $\textit{e}$.
2. $\textit{e}$ is larger than all the edges of the cycle it induced. I suppose this should contradict the minimality of $\textit{T'}$.

Am I anywhere on the right track? I don't know if considering the cycle is the way to do this.

# Answer
It is not immediate to see whether OP’s approach can be adapted easily to a full proof.

Here is an answer to the same question but phrased differently, a local minimum in the graph of spanning trees is a (global) minimum spanning tree.

I will present another proof, which is more flexible and probably easier to understand.

Let $G$ be an undirected connected (finite) graph with distinct costs on its edges, as in the original question. **Consider the delete-heaviest-edge algorithm on $G$, which removes the heaviest edge in a cycle until no cycle remains.** Just to be clearer, let me call the remaining edges at the end of the algorithm $H$. Let us show that $H$ is the minimum cost spanning tree (MST) of $G$.

$H$ is a spanning tree of $G$ because of the following.

* $H$ is connected, since $G$ is connected and all we have done is breaking cycles.
* $H$ is has no cycle since the algorithm ends only if there is no cycle.
* $H$ has all vertices of $G$ since no vertex of $G$ has ever been deleted.

Because of the the cycle property, any edge in any minimal cost spanning tree (MST) of $G$ is never deleted. So all edges of any MST of $G$ remain in $H$. However, any spanning tree of $G$ has the same number of edges, so $H$ must be the unique MST of $G$. (Yes, we have also proved that there is only one MST of $G$, thanks to the distinctness of the costs).

So we have proved that **the delete-heaviest-edge algorithm finds the MST**. The flexibility of that algorithm is that in each step we can choose any particular cycle.

Following the OP, let $T$ be the spanning tree which we obtain at the end of OP's algorithm. Initialize $G'$ to be a copy of $G$ and $T'$ is the spanning tree of $G'$ that corresponds to $T$. Let $e'$ be an edge in $G'$ but not in $T'$. If we add $e'$ to $T'$, we will create a cycle since $T'$ is spanning. Note that $e'$ must be the unique heaviest edge in that cycle; otherwise, we can substitute $e'$ for that unique heaviest edge, which is in $T'$, to get a lighter spanning tree, which means the OP's algorithm must not end with $T$, a contradiction. Let us run the delete-heaviest-edge algorithm on $G'$ in the following way. We choose that cycle and delete $e'$ from $G'$. Repeat until all edges in $G'$ but not in $T'$ are deleted. What remains is exactly $T'$. Since $T'$ has no cycle, we have actually run the delete-heaviest-edge algorithm to the end. As we have proved, $T'$ is the MST of $G'$. That is, $T$ is the MST of $G$.
> 1 votes

---
Tags: algorithms, graphs, correctness-proof, minimum-spanning-tree
---


# Question
Title: Is it 100% OK to say "All software doesn't need to know the system lower than the architecture level"?
Most of you know this diagram. If this diagram is true, all software is free to not know the levels lower than ISA. But it's not true. Softwares like performance-critical programs or system softwares like OS and compilers, are often forced to understand not only ISA but also microarchitecture.

If so, what about the levels lower than microarchitecture? Is it 100% sure to say the levels lower than uArch aren't require to be understand by softwares or programmers?

# Answer
Nothing is 100% sure in life.

Abstractions are rarely perfect; they can be leaky. Nonetheless, just because developers at higher levels *sometimes* need to know about lower layers doesn't mean they always do, or usually do; and it doesn't mean the abstraction is useless.

Yes, there are cases where it is helpful to know about even lower levels of the architecture. For instance, cold boot attacks and the row hammer attack are made possible by a property of the physics of DRAM cells, so if you want to analyze the security of a system against that specific threat model, you might need to know about things at the level of devices and physics. These cases are the exception rather than the norm, but they do exist and are occasionally relevant.
> 4 votes

# Answer
I had the pleasure once to debug a problem that happened if the user put their computer to sleep and switched it on again after 40 to 50 seconds. Less than 40 or more than 50 seconds, and the problem wouldn't happen. (The 40 or 50 seconds were on the hardware that I used, the times might have been different on other hardware).

This was caused by memory cells keeping their data for a while while the computer was put to sleep, and eventually losing it. After 50 seconds, everything was gone and the software handled that fine. After 40 seconds, only *some* cells lost their data. Enough cells had the old data to convince the software to continue assuming it had valid data, but enough cells had lost their data to make things crash.

So yes, sometimes you need to go below the microarchiteture level. And as D.W. said, attackers may go below that level, and then a defense must go below that level as well. (I heard of attacks against Java Virtual Machines that basically consisted of flipping a small number of random bits using radiation. Plus a lot of complicated details, but the main attack was using radiation).
> 1 votes

# Answer
I develop high-optimized (mostly compression) algorithms and use micro-architecture knowledge every day. It allows to make algorithms 10-100x faster compared to naive variants. Here is how you can learn to this level of knowledge:

What are the best resources (book, thesis, and academia papers) for one to become better at low-level computing using the C++ language?
> -1 votes

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


# Question
Title: Shifting positive values in an array to offset the negative ones, in less than O(n^3)
I have an array 'a' which is 1xn, and has positive and negative values. In a rolling window of size m smaller than n. I want to move backwards (to the left) the positive values of the array in order to offset the negative ones. The positive values moved, need to adopt the inverse of the shape of the negative values. Highest values must be moved first to the positions where the minimum values are located. I attach some images:

# Answer
> 0 votes
If i understand the question correctly, then for the first lower part you want to get rid of all the negative values:

```
g(x) = f(x)/2 + abs(f(x))/2

```

and from the second part you want to compensate the values that you added to the first part:

```
g(x + m) = f(x + m) - abs(f(x))/2 + f(x)/2

```

I denoted the new graph as g(x) and old graph as f(x).

For the place where the first part is positive, there will be no change, but for the parts where it is negative, the value is taken from the second part.

You would have to know how much to shift. And a possible problem is that compensating is still done even if the second part doesn't have a high enough value. Since you didn't give an example of that case, i cannot guess what would be the desired outcome.

---
Tags: computational-geometry
---


# Question
Title: Find longest path in graph with N nodes and N edges
We have given weighted undirected connected graph with $n$ nodes and $n$ edges, we want to find the longest path in it. Note that the path should be in each node at most once. Since the graph has $n$ edges clearly it has exactly 1 cycle, and removing 1 edge from this cycle will lead us to a tree.

Clearly we can iterate over all edges of the cycle and run dijkstra to find this path in tree. But this has complexity of $O(N^2)$ in worse case if the whole graph is cycle. I was thinking that greedy solution that we should remove always the edge with lowest weight that lies on the cycle. How to prove this greedy solution, is it correct at all?

# Answer
> 2 votes
I know this is not what you are asking, but in fact there is an efficient algorithm.

This kind of graph problem can be solved in linear time on classes of bounded tree-width. The graphs you describe are a special case of tree-width $2$. Instead of going into the details of tree-width, I will describe the algorithm for the present problem.

We are working with segments of the cycle. Say, such a segment starts at vertex $s$ and ends in vertex $e$. The *avenue* $A$ of that segment is the segment together with all trees rooted at it. Unless the segment is the full cycle, $A$ is the respective connected component of (the graph minus (the cycle minus the segment)).

For each segment, we define $5$-tuple of numbers, called the *type* of the segment. It contains

* the length of the path from $s$ to $e$,
* the length of the longest path fully contained in $A$ that starts at $s$,
* the length of the longest path in $A$ that ends in $e$,
* the longest combined length of a *disjoint* pair of paths such as in the previous two lines, and
* the length of the longest path in $A$.

The key observation is that the type of the concatenation of two segments only depends on the types of the individual segments. Algorithmically, the respective operation on types can be done in $O(1)$. Thus, the overall algorithm works as follows:

1. Compute the type of each singleton segment.
2. Choose some point $s$ on the cycle.
3. Iteratively compute the types of all segments starting at $s$ by concatenating singletons.
4. The last such segment spans the whole cycle and the answer can be derived from its type.

Depending on the way your graph is represented as a data structure, the algorithm can be as fast as $O(n)$.

# Answer
> 3 votes
The greedy solution is not correct.

Let me construct a graph with $5$ vertices, $A$, $B$, $C$, $D$, $E$.

$AB$ is an edge with weight $1$.

$BC$ is an edge with weight $2$.

$AC$ is an edge with weight $2$.

$AD$ is an edge with weight $100$.

$CE$ is an edge with weight $100$.

The longest (heaviest) path is $DABCE$ with weight $203$. After removing $AB$, which is the lightest edge of the cycle $ABC$, the longest path is $DACE$ with weight $202$.

# Answer
> 0 votes
This can be solves in O(N) using sliding window maximum. First, locate the cycle in the graph and for each node on the cycle, use DP on tree to find the diameter of the tree and longest distance to it's leaf.

Now there are 2 cases for the longest simple path

1) The longest simple path is the longest diameter of each trees on the cycle.

2) The longest simple path is sum of the longest distance to the leaf of 2 nodes and the length between them on the cycle. Use sliding window maximum with the size equal to the number of nodes in the cycle to find the answer to this case.

The answer to this problem is the maximum value between these 2 cases.

---
Tags: graphs, weighted-graphs
---


title: Drawing a NFA for a string

text:
# Question
Title: Drawing a NFA for a string
I have these grammar rules defined as follows,

```
FDL -> FDEF FDL | ε
FDEF -> #feature #: FEXP
FEXP -> #op #( FLIST #)
FLIST -> FEXP #, FEXP | #feature

```

I know how to derive the derivative tree for a given string from this, but how do I draw a NFA for this string `{#feature #: #op #( #feature #)}*`. I have seen many examples which they draw the NFA from a regular expression, if so can I consider this string as a regular expression? If not how can I draw it?

# Answer
> 1 votes
I will leave the actual drawing up to you, but I will describe it here. You can draw a directed graph, with a start state that follows the input `#feature` to another node which follows an edge to `#:` to `#op` to `#(` to `#feature` to `#)`. The node that we land on after `#)` is the accept state. If it any point, we read some input that does not allow us to follow that path, we immediately travel to another state (in this case, a designated reject state) with no output paths.

Our accept state will only have one out edge, which we follow on the input `#feature`. This takes us back to where we traveled after our start state. If we read any other input from our accept state, we move to the designated reject state.

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


# Question
Title: Solve longest common subsequence in a non dynamic programming way?
I am working on the longest common subsequence (LCS) problem while learning dynamic programming. Below is the Java code I created to solve the problem, which is not dynamic programming as far as I understand.

```
public class LCS
{
    public static String lcs(String a, String b )
    {
    String lcs = lcs(a, b, "", 0, 0);
    return lcs;
    }
    private static String lcs(String a, String b, String lcs, int i , int j)
    {
    int length_a = a.length();
    int length_b = b.length();
    if (i == length_a || j == length_b) return lcs;
    if (a.charAt(i) == b.charAt(j))
        {
        lcs += a.charAt(i);
        i++;
        j++;
        }
    else
        {
        String lcs_i_plus = lcs(a, b, lcs ,i+1, j);
        String lcs_j_plus = lcs(a, b , lcs ,i, j+1);
        if  ( lcs_i_plus.length() > lcs_j_plus.length())
            i++;
        else
            j++;
        }
    return lcs(a, b, lcs , i, j) ;
    }
    public static void main(String[] args)
    {
    //client
    String a = "GGCACCACG";
    String b = "ACGGCGGATACG";
    String lcs = lcs(a, b);
    StdOut.println(lcs);
    }
}

```

In contrast, the book I studied offered another solution which was claimed to solve the LCS problem via dynamic programming. The code looks as follows.

```
 public class LongestCommonSubsequence
 {
    public static String lcs(String s, String t)
    {  // Compute length of LCS for all subproblems.
    int m = s.length(), n = t.length();
    int[][] opt = new int[m+1][n+1];
    for (int i = m-1; i >= 0; i--)
       for (int j = n-1; j >= 0; j--)
       if (s.charAt(i) == t.charAt(j))
          opt[i][j] = opt[i+1][j+1] + 1;
       else
          opt[i][j] = Math.max(opt[i+1][j], opt[i][j+1]);
    // Recover LCS itself.
    String lcs = "";
    int i = 0, j = 0;
    while(i < m && j < n)
    {
       if (s.charAt(i) == t.charAt(j))
       {
          lcs += s.charAt(i);
          i++;
          j++;
       }
       else if (opt[i+1][j] >= opt[i][j+1]) i++;
       else                                 j++;
    }
       return lcs;
    }
    public static void main(String[] args)
    {  StdOut.println(lcs(args[0], args[1]));  }
}

```

I have tested both implementations and they produced the same results. My questions are:

1.Is my approach correct?

2.If my approach is correct, what are the time complexity of these two approaches?

# Answer
1. Your approach is correct in the sense that you produce the correct results.
2. The book's approach has a time complexity of $O(mn)$. Since your solution doesn't use memoization and recomputes the same results repeatedly, the time complexity is much worse. In fact, your approach is functionally equivalent to the brute force method, which has a time complexity of $O(2^n)$.

Note that with

> `String lcs_i_plus = lcs(a, b, lcs ,i+1, j);`
>
> `String lcs_j_plus = lcs(a, b , lcs ,i, j+1);`

You recompute a subset of the problem on every single iteration without saving any of the results. The purpose of memoization is to save the results of the sub problems (so you don't have to recompute them) and then use those results to construct a solution to your original problem.
> 1 votes

---
Tags: dynamic-programming, memoization
---


# Question
Title: Number of strings accepted by this regular expression
This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices.

If a regular expression is of the form `(x+y)*y(a+ab)*` , then what is the maximum number of strings with length 4 will bee accepted by its language?

I've tried simplifying the expression, or drawing FSM diagrams but can't figure it out. A little help would be appreciated.

Thank you!

# Answer
*NOTE: I'm assuming `+` is the union operation, as used here, rather than the Kleene plus or a terminal symbol.*

The first step is breaking this RE into three parts: `(x+y)*`, `y`, and `(a+ab)*`. Now consider, how many ways can we make something with less than four characters from each of these?

* `(x+y)*`: one of length 0, two of length 1, four of length 2, eight of length 3
* `y`: one of length 1
* `(a+ab)*`: one of length 0, one of length 1, two of length 2 (aa, ab), three of length 3 (aaa, aab, aba)

Now, how could you combine these to get length 4?

* 0 from the first (1), 1 from the second (1), 3 from the third (3)
* 1 from the first (2), 1 from the second (1), 2 from the third (2)
* 2 from the first (4), 1 from the second (1), 1 from the third (1)
* 3 from the first (8), 1 from the second (1), 0 from the third (1)

For each of those, multiply the number of possibilities. Taking 1 from the first, 1 from the second, and 2 from the third, for instance, gives 2×1×2=4 possibilities.

The sum of these is the total number of length-4 strings matched by this RE: (1)(1)(3)+(2)(1)(2)+(4)(1)(1)+(8)(1)(1) = 3+4+4+8 = 19.
> 1 votes

---
Tags: automata, regular-languages, regular-expressions
---


# Question
Title: A problem about slicing and indexing in numpy in Python
I learned that in numpy, given a vector, slicing and indexing could give different results. I ran the following codes:

```
a = np.array([1, 2])
b = np.array([3, 4, 5])
print(b[a])
c = b[1:]
print(b)
c[0] = 1
print(b)
print(c)
print(b[1:] is c)

```

and get the result:

```
[4 5]
[3 4 5]
[3 1 5]
[1 5]
False

```

Since when I modify c, b is also changed, that means I should have a True in the last line right? Why it is not the case?

Thank you for any help!

# Answer
> 1 votes
When you slice a Numpy array, you get a special "slice" object, which holds pointers back into the array it was taken from. So if you do the same slicing operation twice, you'll get two different slice objects, which contain pointers to the same array in memory. (If you compare them using `==` instead of `is`, you'll see they compare equal, even though they're different objects.)

You can get the same effect with `memoryview`s, which are in the standard library. Each memoryview is its own object with its own address, but many memoryviews can point into the same data structure.

---
Tags: python
---


# Question
Title: Algorithm to determine which neighborhoods of a graph contain a given set of vertices S
This question concerns determine which sets in a collection of sets contain a given subset S:

An undirected graph (V,G) is given with V= {1,..,m}, and given via its neighborhood sets, N(v\_1),.., N(v\_m). A subset S of V is given {v\_{i\_1}, .., v\_{i\_k}}. The output will be the vertices whose neighborhoods contain S. The size of the instance is m + |N(v\_1)| +…+ |N(v\_m)} =n.

Does there exist a linear time algorithm, or an n log n algorithm, or even a sub-quadratic algorithm for this problem?

My naive approach would be remove from set neighborhood set N(v\_i) all vertices not in S and count remaining vertices—if |S|, put vertex i in the output, and if not, do not put vertex i in S.

I don’t have experience with hash sets (learning on my own) and don’t really understand why they are so efficient (self-studying that) but any idea on a quick algorithm would be appreciated.

-Steve

# Answer
In fact, the set of the vertices whose neighborhoods contain S is exactly

$$\bigcap\_{j=1}^mN(v\_{i\_j})$$

Proof:

since it's an undirected graph, $v\in N(u) \Leftrightarrow u\in N(v)$. A vertices $v$ whose neighborhoods contain S means that $\forall u\in S, u\in N(v) $, which is equivalent to $\forall u\in S,v\in N(u)$, thus $\bigcap\_{j=1}^mN(v\_{i\_j})$ is the desire set.

So the problem is equivalent to that:

> Given m (unordered?) lists, get the intersection of them

One can solve it in $O(n\log n)$ easily by maintain a balanced BST like a `std::set`.

Or just solve it in $O(n)$ by hashing.
> 2 votes

---
Tags: graphs, time-complexity
---


title: Right definition of linear grammar

text:
# Question
Title: Right definition of linear grammar
I was referring book by Peter Linz, which defines linear grammar as follows:

> A linear grammar is a grammar in which at most one variable can occur on the right side of any production, without restriction on the position of this variable.

The wikipedia page also defines it similar way at the top of Linear grammar page

> a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.

By these definition, it seems that the production of the following form is allowed:

> $S\rightarrow aSb$

But next on the same page, wikipedia defines it as follows:

> linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

By this definition, it seems that the productions of the above form are not allowed.

Then what is correct definition?

# Answer
They second quote from Wikipedia has lost its context. Here it is complete, with emphasis added:

> Another ***special type*** of linear grammar is the following:
>
> * linear grammars in which all nonterminals in right hand sides are at the left or right ends, but not necessarily all at the same end.

A linear grammar has at most one non-terminal on the right-hand side of any rule, as per Linz' definition.

But any linear grammar can be transformed into an equivalent linear grammar of that special type, simply by adding a new non-terminal. Wikipedia goes on to show an example of this transformation. So it is possible to assume wolog that a linear grammar is in that form, if it turns out to be helpful.
> 3 votes

---
Tags: formal-grammars
---


# Question
Title: Prove grammars with long derivations generate infinite languages
> Suppose $G$ is a CNF (Chomsky normal form ) grammar which has $v$ variables. ($|V| = v$) If there is a string that $G$ derivatives in more than $2^v$ steps, prove that $L(G)$ is infinite.

Any ideas how can i prove this?

I know derivation tree in a CNF grammar is binary. So my idea is to calculate maximum number of leaves in the tree and prove that if $L(G)$ is finite this can't be reached in more than $2^v$ steps. Can anyone help me how to prove this part?

# Answer
> 1 votes
G is in CNF. We can ignore the derivation S-\>eps since it is the only derivation of an empty string so it is only part of a derivation of length 1. I assume that the start symbol S counts as one of the "variables" or non-terminals, so there are (v-1) other non-terminals. S can only appear at level zero of the derivation.

In a derivation, every step replaces a non-terminal with a terminal, or increases the number of non-terminals by 1. Therefore, if N generates a string x of terminals and non-terminals, x is either a single terminal with a one-step derivation, or x consists of at least two symbols.

If G generates a string s, and in the derivation a symbol N derives itself (N -\> x N y, where x, y are strings of terminal and non-terminal symbols), then we found that either x or y are non-empty, and derive non-empty strings of terminals (since they were part of a derivation). And since we derived N -\> x N y, we can derive N -\> $x^k N y^k$ for any k \> 0, so the language is infinite.

So we have seen that if a non-terminal N occurs twice in any derivation, the language is infinite. Now look at the derivation of a tree. Level k of the tree has at most $2^k$ nodes. If the tree has a height h, then the nodes at levels $k = 0$ to $k = h-1$ may have contributed a derivation step, for a total of $2^h-1$ derivation steps. If a string s is derived in more than $2^v$ steps (actually, in $2^v$ or more steps), then it has a height v+1 or greater. If you look at a node at level v+1, then there are v non-terminals at levels 1 to v, and since there are only v-1 non-terminals after than S, one non-terminal must occur twice. Which makes the language infinite.

We can make any grammar epsilon-free quite easily: Introduce a new symbol $S\_0$ and a rule $S\_0-\>S$, so that $S\_0$ will not occur on any right hand side of a rule. Then as long as there is a derivation N-\>eps with N ≠ $S\_0$, remove that derivation, and for every rule with N on the right hand side, add rules with any possible subset of these N's removed. Remove all duplicate rules, and the only rule containing eps that is possibly left is $S\_0 -\> eps$. In an epsilon-free grammar we have the same fact that if the grammar contains a string s where the derivation contains a derivation N -\> x N y where x or y are non-empty, then the language is infinite.

# Answer
> 0 votes
Here is the proof of the analogous result for regular languages. Hopefully you can generalize it to your case.

**Theorem.** Suppose that $A$ is a DFA on $n$ states such that $L(A)$ contains a word of length at least $n$. Then $L(A)$ is infinite.

**Proof.** Let $w = w\_1 \ldots w\_N \in L(A)$ be a word of length $N \geq n$, and let $q\_i = \delta(q\_0,w\_1\ldots w\_i)$ for $0 \leq i \leq N$. Since $N \geq n$, the sequence $q\_0,\ldots,q\_N$ contains $N+1 \> n$ elements, and so $q\_i = q\_j$ for some $i \< j$. Let $x = w\_1 \ldots w\_i$, $y = w\_{i+1} \ldots w\_j$, $z = w\_{j+1} \ldots w\_N$. We have $$ q\_j = \delta(q\_0,xy) = \delta(\delta(q\_0,x),y) = \delta(q\_i,y). $$ Since $\delta(q\_i,y) = q\_i$, an easy induction shows that $\delta(q\_i,y^t) = q\_i$ for all $t \geq 0$, and so $$ \delta(q\_0,xy^tz) = \delta(\delta(\delta(q\_0,x),y^t),z) = \delta(\delta(q\_i,y^t),z) = \delta(q\_i,z) = \\ \delta(q\_j,z) = \delta(\delta(q\_0,xy),z) = \delta(q\_0,xyz) \in F, $$ where $F$ is the set of accepting states. This shows that $xy^tz \in L(A)$ for all $t \geq 0$. Since $y \neq \emptyset$, it follows that $L(A)$ is infinite. $\square$

Note the similarity to the proof of the pumping lemma. A similar idea works in your case, in which one of the nonterminals will repeat twice.

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


title: Optimization problems and quantifiers

text:
# Question
Title: Optimization problems and quantifiers
A simple optimization problem is of form $\max\_{x\in\mathcal R}f(x)$.

We can quantify as $\exists x\in\mathcal R\forall y\in\mathcal R f(y)\leq f(x)$.

The quantification here is $\exists\forall$.

1. Is there a meaning to $\forall\exists$ from optimization?
2. What is a good natural meaning to $\forall\exists$ quantification?

# Answer
The $\exists x \forall y$ form of quantification is used to indicate that there is some single object that has a particular relationship to all others, for instance an input that achieves the globally largest objective value in your example.

In $\forall y \exists x$ quantification, there can be a different $x$ for each $y$, but as pointed out in a comment, this is only interesting if the formula being quantified contains more than just a single inequality that allows setting $x=y$. The existence of locally optimal values (that fail to achieve a globally maximal objective value, but are perhaps only a short distance away and still achieve an absolute target value for the objective function) would be expressed in this way.
> 1 votes

---
Tags: optimization, logic
---


# Question
Title: What data structure would help find nearby coordinates quickly?
I need to write a program that does the following:

* Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places
* Store them in a data structure once
* Provide a "nearby" lookup function that can efficiently return the N closest objects for a given lat/long

Currently, I'm doing the following, which is suboptimal:

* Store all objects in a hash, with array keys like `[integer_latitude, integer_longitude]`
* At search time, find all objects in an arbitrary-sized circle around the target. Eg, if the search is at `[0,0]`, I can get all objects within 1 degree by pulling `[-1,0]`, then `[0,0]`, then `[1,0]`, then `[0,-1]`, etc.
* Order the found objects by actual distance to the target and take the top N

This is obviously inefficient, because often there are many more matches than N.

One improvement could be to examine locations in concentric squares outward from the center: all points 0 degrees from the center, all points 1 degree from the center, 2 degrees, etc, and stop after the first square when I have at least the number of objects needed. Then I could sort those by actual, fine-grained distance and take the top N.

Is there some well-established way of doing this search efficiently?

# Answer
> 1 votes
Yes, you could you could do better than a naive approach - you could use a **k-d tree** data structure.

Clever implementations, such as sklearn k-d tree do the nearest neighbour lookup in `O(log(n))` which, unless you have a high dimensional and sparse dataset, will work significantly faster than a naive `O(n)` approach.

# Answer
> 0 votes
As well as k-d trees, it's worth knowing about R-trees, as these are arguably the most popular data structure for indexing in the GIS world.

R-trees are to k-d trees as B-trees are to binary search trees. Like B-trees, R-trees tend to be very cache efficient, which makes them extremely useful for on-disk data structures as you tend to find in databases.

# Answer
> 0 votes
There are obviously many different data structures out there - you could also use a cover tree

---
Tags: data-structures, computational-geometry, search-algorithms, search-problem
---


# Question
Title: Valid bit incoherence between TLB and Page Table
In the fourth row of the TLB the valid bit is 0. The corresponding row in the pagle table (fifht row) has the valid bit 1. How is this possible? What events leads to this incoherence?

# Answer
> 4 votes
The typical scenario where this kind of incoherence can occur is when the page table has been changed. In this case, an invalid PTE has become valid; perhaps the area of address space has been allocated, or a page has been swapped in.

"But", I hear you say, "why wasn't the TLB entry flushed when the PTE changed?" Well, it probably was, but the change may have happened on a different core.

The way this is typically handled in a multiprocessing operating system is to perform a "TLB shootdown". The core which changed the PTE issues an inter-processor interrupt (also known as a "crosscall") to any other CPU which may have a copy in its TLB to instruct it to flush.

An inter-processor interrupt is an expensive operation. But, of course, it doesn't need to happen a lot of the time. For example, if the other CPU is not currently using an address space which uses the TLB entry, it can't possibly access the entry until it performs a context switch, so the flush can be delayed until the next time the CPU enters the kernel (say).

But even if the other CPU is using the address space right now, you still don't need to perform a shootdown in this specific case, because the stale TLB entry is invalid. Attempting to access it will cause a page fault, so any attempt to use the stale TLB entry will be resolved by the page fault handler. And if that never happens, you've saved yourself a costly inter-processor interrupt.

---
Tags: computer-architecture, cpu, virtual-memory, memory-access
---


# Question
Title: if an argument of a lambda only passes itself if it is further evaluated, is runtime always finite?
In order for a lambda expression to run forever, there must be at least one lambda in the expression in which an argument is passed to itself. For example the following runs forever.

$$ (\lambda x.xx)(\lambda x.xx) $$

However, I am curious if an expression could run forever if arguments were only passed to themselves like in $\lambda x.x(xy)$ in that each time it is passed, it becomes further evaluated. I suspect that this is true (that it can be evaluated in finite time) however am unsure how to prove this formally. Informally the idea is that each recursive call is guaranteed to leave the lambda in a further reduced state since the original cannot be preserved.

So my question is:

**What is a formal proof or counterexample to this claim?**

A few notes:

The opposite is definitely not true, expressions of the form $\lambda xy.(xy)x$ can run forever. For example, the following runs indefinitely.

$$ (\lambda xy.(xy)x)(\lambda xG.(Gx)G)(Lx.x) $$

Also, if when passed to itself both parts are passed an additional argument, such as $\lambda xy.(yx)(yx)$ it can run forever. For example

$$ (\lambda xy.(yx)(yx))(\lambda x.x)(\lambda xy.(yx)(yx)) $$

Additionally, I am assuming **all** lambdas within the expression meet the criteria, not just some subset of them. So something like the following would not be a counterexample

$$ (\lambda x.x(xy))(\lambda x.xx)(\lambda x.xx) $$

Edit:

As chi pointed out below, I had not given a very good definition of the criteria for this question, so I've added one.

A lambda is reduced in X if it can be written in the following form (as `<reduced-lambda>`)

```
<id> := [[all valid variable names except X]]
<id-list> := <id> <id-list> | <epsilon>
<filler> := <epsilon> | <nonempty-filler>
<nonempty-filler> := (lambda <id> <id-list> . <nonempty-filler>) <filler> | <id> <filler> | (<nonempty-filler>) <filler>
<reduction> := (X <filler> <reduction>) | (X <nonempty-filler>)
<base-reduction> := (lambda <id> <id-list> . <filler> <base-reduction> <filler>) | (<filler> <base-reduction> <filler>) | <reduction> | X
<reduced-lambda> := (lambda <id-list> X <id-list> . <filler> <base-reduction> <filler>)

```

An expression E is reduced if for every lambda L in E, for every argument A in L, L is reduced in A.

And the more precise question becomes: **does every reduced expression terminate?**

Edit 2:

I did change the above formulation slightly, the old version is in the edit history and is incorrect (twice)

# Answer
> 2 votes
(This is not a proper answer, but I wanted to share some thoughts)

To have a definitive answer one would need to precisely define what's allowed and what's not.

I noticed this, however, which perhaps could help. The term $M = \lambda xy. x(xy)$ is typeable in the simply-typed lambda calculus, which is strongly normalizing.

Instead, your other two examples, $\lambda xy. (xy)x$ and $\lambda xy.(yx)(yx)$ are not typeable in STLC.

Perhaps exploiting this, and formalizing everything precisely, one can indeed prove that using $M$ "alone" does not lead to non termination. It's hard to say, since the STLC constrains the calculus significantly.

---
Tags: lambda-calculus, halting-problem
---


# Question
Title: Finding duplicate in immutable array in linear time and constant space
We have a array of $N$+1 integers. The integers range from 1 to $N$. The array contains at least one duplicate. Our goal is to find one of the duplicate entries. We have the constraint that we cannot modify the input array. Is there any solution to this problem which has $O(N)$ time complexity and $O(1)$ space complexity?

# Answer
Let us denote the array by $a\_1,\ldots,a\_{n+1}$. Define a function from $\\{1,\ldots,n+1\\}$ to itself as follows: $f(i) = a\_i$. The graph of the function is a directed graph in which each node has outdegree 1. Since $n+1$ has indegree 0, the connected component of $n+1$ has a node with indegree 2, which corresponds to a duplicate entry. This node can be found using a cycle detection algorithm in linear time and constant space.
> 6 votes

---
Tags: algorithms, arrays
---


# Question
Title: Can we split a vector into positive and negative parts in LP?
Say you have a vector $v$ with $n$ length $v=\begin{bmatrix}v\_1&\dots&v\_{n}\end{bmatrix}$ can we write as $v=v\_+-v\_-$ where $v\_+$ agrees with $v$ on non-negative components and is $0$ otherwise and $v\_-$ agrees with $v$ on non-positive component and is $0$ otherwise.

Eg: $v=\[-1,-3,4,5,0,0,1,2,-3,-4\]$ then $v\_+=\[0,0,4,5,0,0,1,2,0,0\]$ and $v\_-=\[-1,-3,0,0,0,0,0,0,-3,-4\]$ holds.

I tried using $\max(0,v\_i)\leq v\_+(i)$ and $v\_-(i)\leq\min(0,v\_i)$ operations. I am unable to write this correctly without convex optimization.

$v$ is not a constant for me and is a variable. So is there a way to do this with only feasibility Linear Programming with only perhaps $O(1)$ integer variables?

# Answer
Unfortunately, in the general case, no.

Consider if we had a single variable $x$, one can then write out $x = x\_+ - x\_i$, and have that $x\_+, x\_- \geq 0$.

The problem is that one can increase both $x\_+$ and $x\_-$ by any value $\Delta$ and the value for $x$ stays the same. There isn't any convex way to enforce that one of the values is 0. $\min\\{x\_+, x\_-\\} = 0$ is non-convex. One can understand that trying to enforce this is non-convex, by considering two axes, one for $x\_+$ and the other for $x\_-$. Requiring that one of them be 0, is equivalent to enforcing that the solution must lie on an axis - any penalty incurred where they are both non-zero (e.g. $\min\\{x\_+, x\_i\\}$, or $x\_+ x\_-$), then implies non-convexity.

One may be able to deal with this in an acceptable way by applying an $\ell\_1$ penalty of $c(x\_+ + x\_-)$ for some small constant $c$ which doesn't cause too much distortion to the objective.

Of course, if the number of variables for which one wants to apply this is small enough, one can always consider solving all the different options explicitly (i.e., $x\_+ \geq 0, x\_- = 0$, $x\_- \geq 0, x\_+ = 0$), but this will only work for a very small number of variables.

Otherwise, one needs to resort to non-convex optimization techniques, which of course aren't guaranteed to find a global minimum.
> 1 votes

---
Tags: linear-programming
---


# Question
Title: How is quantum function $f(x) = a^x \mod N$ constructed in Shor's algorithm?
I can't see how I can apply quantum function $a^x\mod N$ to initial states. Explanations of Shor's algorithm often skips this part, and I do not see what unitary matrix this algorithm would correspond to.

reference: https://en.wikipedia.org/?title=Shor%27s\_algorithm

# Answer
This paper by Pavlidis and Gizopoulos walks through one possible construction of the circuit you're looking for and also provides references to other literature on the subject:

"Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm". Archimedes Pavlidis, Dimitris Gizopoulos. http://arxiv.org/abs/1207.0511
> 1 votes

# Answer
Remarks on Quantum Modular Exponentiation and Some Experimental Demonstrations of Shor’s Algorithm is a good survey on this topic.

I have found two perspective to this problem.

1. we can calculate the modular exponentiation in the classical computer, which tells us how to create the $x^{2^i} (mod\ N)$ gate. That is, we can view the modular exponentiation as oracle.
2. the modular exponentiation gate is implemented in the quantum circuit. One design is shown in Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm, where at least $1600 L^3$ gates are needed with $L = \log(N)$.

Anyway, the modular exponentiation is harder than QFT. In some design of the modular exponentiation, multiple QFT's are used.
> 1 votes

# Answer
The algorithm uses the functional superposition s of f. A state with 2q qubits (2q=Q, where Q is the same as in the Wikipedia article):

s(xy) = Q-1/2 where y = f(x), else 0

You can see xy as the concatenation of x and y in binary form. x and y run from 0 to Q-1.

Here is how it can be done with q ancillary qubits (3q qubits total):

* Start with 3q qubits in the zero state (1,0,0,...). I'll call the first q qubits x, the second q qubits y and the third q qubits z
* Apply the Hadamard transform to x
* Follow x to y with CNOT. This yields the state s(xyz) = Q-1/2 where x = y and z = 0, else 0
* Apply f'(x,y) = (x,f(x) XOR y) to y and z. f' is invertible and has a unitary matrix. This yields the state s(xyz) = Q-1/2 where x = y and z = f(x), else 0
* Apply g(x,y) = (x,x XOR y) to x and y. This yields the state s(xyz) = Q-1/2 where y = 0 and z = f(x), else 0
* Swap x and y with swap gates. This yields the state s(xyz) = Q-1/2 where x = 0 and z = f(y), else 0. x is in the zero state (1,0,0,...) and can be separated from yz - which forms the functional superposition of f
> -1 votes

---
Tags: quantum-computing
---


title: Category theory and graphs

text:
# Question
Title: Category theory and graphs
Could most categories , or a finite part of them be represented on a subset of a complete graph of N vertices (Kn) which is connected. and partly directed? Could all the axioms of category theory be written for such graphs?

# Answer
> 3 votes
A category consists of:

* Objects.
* Directed arrows between objects. There can be multiple arrows between any two given objects, or a unique arrow, or none.
* A composition map for arrows that takes an arrow $f$ from $x$ to $y$ and another arrow $g$ from $y$ to $z$ and outputs an arrow $gf$ from $x$ to $z$.
* Depending on the formulation, there might also be a distinguished arrow between every object and itself (the identity arrow).

The composition map has to satisfy the following axioms:

* Associativity: if $f\colon x \to y$, $g\colon y \to z$ and $h\colon z \to w$ then $h(gf) = (hg)f$.
* Identity: if $f\colon x \to y$ and $1\_x\colon x \to x$ and $1\_y\colon y \to y$ are the distinguished self loops then $f1\_x = 1\_yf = f$. (If the formulation does not include the distinguished self-loops: there exist arrows $1\_x\colon x\to x$ and $1\_y\colon y\to y$ such that $f1\_x = 1\_yf = f$.)

You can represent this data in many ways. A graph with multiple edges is, however, not enough, since you also need to specify the composition map.

# Answer
> 1 votes
Lambek and Scott use this even as a definition for a category:

> A **deductive system** is a graph in which to each object $A$ there is associated an arrow $1\_A: A\to A$, the **identity** arrow, and to each pair of arrows $f:A\to B$ and $g:B\to C$ there is associated an arrow $gf:A\to C$, the **composition** of $f$ and $g$.
>
> A logician may think of the objects as **formulas** and of the arrows as **deductions** or **proofs**, hence of
>
> $$\frac{f:A\to B \qquad g:B\to C}{gf:A\to C}$$
>
> as a **rule of inference**.
>
> A **category** is a deductive system in which the following equations hold for all $f:A\to B$, $g:B\to C$ and $h:C\to D$:
>
> $$f1\_A=f=1\_Bf$$ $$(hg)f=h(gf)$$

(Lambek & Scott. Introduction to higher order categorical logic, p. 5)

In summary: Lambek and Scott define a **deductive system** as a **(directed) graph** with **units** and **compositions** (alias **modus ponens**, alias **rule of inference**) and a **category** as a deductive system where the 'ususal' laws hold for units and rule of inference.

# Answer
> 0 votes
A connection between graphs and categories that most introduction book would mention is the free-forgetful adjunction $$(F\colon Graph \rightarrow Cat ) \dashv (U\colon Cat \rightarrow Graph)$$ between categories:

* $Graph$ of small directed graphs and graph homomorphisms
* $Cat$ of small categories and functors

To spell this out naively just the action on objects of $F$ and $U$:

* $F$ takes given graph $g$ and give out the **F**ree category $F(g)$ having as objects the same set of vertices in $g$ and as morphisms the directed paths in $g$. Morphism composition is the concatenation of paths and the identity morphism is the empty paths.
* $U$ takes a category $C$ and gives out the **U**nderlying category $U(C)$ having as vertices the objects in $C$ and as directed edges the morphisms in $C$. The action of $U$ is intuitively to *forget* that there was composition and identity and extra properties that $C$ used to have.

I think even beginners (who don't yet understand adjunction) could appreciate why $F$ and $U$ is useful because whenever a book describe a "tiny" category by means of drawing a diagram such as

$$\bullet \rightarrow \bullet \rightarrow \bullet$$

and say that it omits the identity anad transitive morphisms. What category it is describing is exactly the free category generated by the above directed graph.

---

I have a feeling that you are misunderstanding something as you mentioned

> ... represented on a subset of a complete graph of N vertices (Kn) which is **connected. and partly directed**? ...

I think what you mean is by representing a category $C$ with a graph is $U(C)$. And if that is the case, you would be wrong to say that $U(C)$ has to be "connected and partly directed". The underlying graph of a category doesn't have to be connected. Take for example, a category with just two objects and 2 identity morphisms.

A better description properties of $U(C)$ might be "transitive and reflective".

---
Tags: graphs, category-theory
---


# Question
Title: Does this progressive image compression exists?
I want to know if this progressive image compression that I have in mind exists and it it does I want know its name and/or get some references about it.

The algorithm consists of converting one high resolution image in multiple low resolution images (all of the same size, not like in wavelet transform) with the following properties:

* If you have one of them, any of them, you can reconstruct a low resolution approximation to the original image.
* You can compose many of those in any order to get better approximations to the original image.
* If you combine all low resolution images you get the original image or a very good approximation of it without perceptible artifacts.
* Algorithm is real-time, i.e. it can display a meaningful partial reconstruction of the original image at any time of the reconstruction process (independently of received sub-images and their order).

Does this algorithm exits? Is it possible at all?

I know about image reconstruction techniques, but those use similar but different images to reconstruct a higher resolution one and the result is always noisy and full of artifacts. This is not I am asking for.

# Answer
> 1 votes
I believe that the Stationary Wavelet Transform (SWT) meets your requirements: https://en.wikipedia.org/wiki/Stationary\_wavelet\_transform

1) Any given level of coefficients could be used to reconstruct the original image by running normal reconstruction but assuming zeros for the other levels.

2) Each level of coefficients stores data about a different range of spatial frequencies in the original image, and thus they can be recombined arbitrarily.

3) Unless you quantize when or after you perform the transform, the SWT is lossless.

4) I haven't done any processing time evaluation, but optimized libraries are available: https://www.mathworks.com/help/wavelet/ug/discrete-stationary-wavelet-transform-swt.html

In general though, unless you require translation invariance, you would benefit from the downsampling in the more common Discrete Wavelet Transform (DWT). The downsampling results in smaller images which requires less space to store and time to process. No information is lost by this downsampling as the frequency filters in the DWT filter out and then store (in the higher resolution levels) the frequencies that then get lost in the downsampling. The lower frequencies simply need fewer samples to be accurately reconstructed (https://en.wikipedia.org/wiki/Nyquist\_frequency).

# Answer
> -1 votes
> If you have one of them, any of them, you can reconstruct a low resolution approximation to the original image.

this means that they duplicate the information. imagine а 8x8 blue area. if each sample carries info that this are is blue, you carry N duplicates of the same info. So, the compression ratio will suffer

---
Tags: reference-request, data-compression
---