# Question
Title: Algorithm: given very large file of strings, find lines containing substring
I'm not sure if cs.stackexchange.com is correct place to ask this question but it looks like most relevant.

On the job interview I was asked a question: lets say we have a very large file, containing a lot of lines with strings. And lets say that one line is a "document". We are building service which takes some string as input and returns numbers of documents containing this string or substring. Which approach would you use?

And I'm stuck with event trying to find a way to do it. Obviously we can just go through the file with every query and count lines containing substring and it will take O(n) time. But there should be more elegant and fast way to do it, right? I have no CS grad, so my knowledge about algorithms and data structures are not systematic.

My intuition says that it should some very basic question (like knackpack problem, for example) and I just don't know right data structure and algorithm to handle it.

It looks like suffix tree could help somehow but I can't find a way - how? Or, maybe, there is some another approach?

# Answer
You can construct a suffix tree for that very large file and once generated the same can be used for querying.
For Suffix tree generation use Suffix Array approach, there are many algorithm to generate suffix array.
This is a taxonomy of many suffix array algorithm available today
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

To starts with I would recommend prefix-doubling which required O(n log(n)) time.
You can then look at DC3 which does the job in O(n) time.
> 5 votes

# Answer
Let $\\{D\_1, D\_2, \ldots D\_m \\}$ be the set of lines (documents) in your problem. Here is a standard solution using a suffix tree.

Build the suffix tree of the string $S = D\_1 \\$ D\_2 \\$ \ldots D\_n \\$$, where $\\$$ is a separator character not found in any of your documents.

Suppose your query string is $Q$. Traverse down the suffix tree of $S$ following the characters of $Q$ to find the node (or "locus", to be precise) $v\_Q$ corresponding to string $Q$ (if no such node exists, then the string $Q$ does not exist in any of your documents). Walking down the tree takes $O(|Q|)$ time. The leaves in the subtree of $v\_Q$ correspond to all suffixes of $S$ that are prefixed by $Q$, so each leaf has the starting position of an occurrence of $Q$ in $S$.

We can add some pointers to the suffix tree so that we can find all leaves in the subtree of a node quickly. For each node, we store the pointer to the leftmost child in the subtree of that node. For each leaf, we store the pointer to the next leaf on the right. This way if node $v\_Q$ has $k$ leaves under it, we can iterate those leaves in time $O(k)$.

Now that we have the starting positions of all occurrences, we can find the documents containing the occurrences. An easy way is to precompute an array storing for each position of $S$ the id of the document containing this position. This array makes our data structure functionally similar to a *generalized suffix tree*, which is just a suffix tree for a set of strings. Your problem could also have been solved by using a generalized suffix tree as a black box.

Summing up, the total time complexity of answering the query is $O(|Q| + k)$, where $k$ is the number of occurrences of $Q$. Barring bit-parallel algoritms, this is the best you can have, because you need to at least read the query, and you need to at least list all the documents containing $Q$.

If the total size of your documents is really large, you might want to look into compressed text indices. There exist compressed representations of suffix trees that take less space, but the query time is slower as a trade-off. Burrows-Wheeler transform based indices can help if the alphabet of your documents is small or the texts are redundant. Compressed text indices that exploit redundancies in your texts are a topic of active research.
> 1 votes

---
Tags: algorithms, data-structures, strings, substrings
---


# Question
Title: Proof that if a function is computable with standard programs it is computable with Turing Machines
Where can i find a proof related to the subject mentioned?

# Answer
To write a proof, you need to define your claim precisely. "Standard programs" is not a precise term.

However, if we define "standard program" to be, for example, any valid program in the C programming language, then you can write a proof. To prove this, you describe how to simulate any valid C-program with a Turing machine, or describe a "compiler" that takes a C-program and outputs an equivalent Turing machine. Since the C-language has many features, the proof will be long and tedious, but it is doable. I don't know if anybody has gone through the trouble to write a full formal proof.
> 1 votes

---
Tags: turing-machines, proof-techniques
---


# Question
Title: Which number representation takes the largest amount of memory?
Options are:

1. Signed magnitude
2. One's complement
3. Two's complement
4. Excess notation

This is the question from an 'example of a previous exam' I've been given at university. Answers were not provided. As far as I understand only one answer must be chosen, but I'm not seeing which one.

---

### My attempt at solution

As we see from Signed number representations wikipedia article, both **1. Signed magnitude** and **2. One's complement** can be chosen as representations requiring the largest amount of memory, because they take up space for both negative and positive 0 (unlike **3. Two's complement** and **4. Excess notation**).

Is this reasonable, can we say that both 1. and 2. should be chosen as answers here despite question requiring only one answer?

# Answer
***tl;dr*-** The intended answer was probably **"*One's complement*"** since it wastes encoding on a negative zero. **"*Signed magnitude*"** has the same problem, but apparently some sources consider it more efficient because they neglect the sign-bit, presumably under type-erasure logic.

It's also possible that the answer could've been **"*Excess notation*"**, depending on how they defined it. It's possible to construct excess-notation representations that have degeneracies since multiple combinations of the value and offset could result in the same value. If such degenerate constructions are allowed, then that'd probably have been the intended answer.

---

### Logically, either one's complement or signed-magnitude

I largely agree with @gnasher729's answer in that:

1. At most, $n\_{\text{bits}}$ can encode $2^{n\_{\text{bits}}}$ values.
2. All four formats closely approximate that limit, except two would encode $1$ less value due to having degenerate representations of zero.
3. Since two formats can have degenerate representations of zero, they'd compete for being the correct answer.

So as @gnasher729 said, it seems like **"*One's complement*"** and **"*Signed magnitude*"** would be competing for being the correct answer since they both encode only $2^n-1$ distinct values (considering negative zero to be degenerate), whereas the other two encode the full possibility range of $2^n$ distinct values.

### Guess: One's compliment is the intended answer

Since two of the answers seem equally valid from a logical perspective, then it seems like it's time to start reverse-engineering what the question-writer was thinking.

Apparently some folks think that one of the two answers, **"*Signed magnitude*"**, is actually more efficient because it saves a bit:

> There were arguments for and against each of the systems. Sign & magnitude allowed for easier tracing of memory dumps (a common process 40 years ago) as small numeric values use fewer 1 bits.
>
> -"Signed number representations", Wikipedia

That seems kinda silly, but I'd speculate that that characterization was in a context in which the signed-bit acted like a sub-type qualifier that may've been removed at some point, kinda like how Java strips generic-type qualifiers.

That wouldn't seem like a fair comparison because it's apple-to-oranges; they're hiding a bit of information in the context. But, if an exam required exactly 1 answer, then it'd seem like guessing against this one may've been a slightly safer bet. Presumably, the course materials may've made the bit-erasure argument at some point.

### Possibly excess notation

If we broadly define "*excess notation*" as representing a value through a combination of two components where one's described as an "*offset*", then it's possible to construct interpretations where it's possible to represent the same number with multiple combinations of values and offsets.

If this is allowed, then **"*Excess notation*"** would've probably been the best answer.

### How to answer questions like this on an exam

If this exam were given in a class, ideally the instructor clarified what they meant by these terms and what assumptions should go into them. Then you'd know stuff like if they considered type-erasure for **"*Signed magnitude*"** and degenerate representations for **"*Excess notation*"**.

However if you know all of the logical stuff but don't know what the instructor was thinking, then this strategy might help:

1. Cross off the answers that probably aren't it, e.g. **"*Two's complement*"** is unlikely to be considered a correct answer.
2. Underline the answers that *might* be correct, under some sort of logic. For example, **"*One's compliment*"** might be correct if we assume type-erasure but don't assume overlapping representations in **"*Excess notation*"**.
3. Circle/select the answer that you figure is most likely what the instructor would consider to be correct.
4. If you have time before the exam's over, you may want to go back and write in quick notes on why each of the underlined answers might be correct.
5. If the instructor marks the question wrong when you get the exam back, you might go have a discussion with them. Instructors might opt to give students points for a question if they can show that they fully understood the material and merely were unclear about the wording of the question.
> 2 votes

# Answer
The question seems rather bizarre.

Using n bits, each representation can represent $2^n$ different values. Two of them have different representations for +0 and -0. I would assume that signed-magnitude and one's complement are used if someone values the ability to distinguish +0 and -0.

If the question was "which representation takes the largest amount of memory", then that question is already nonsense because no matter what you think about +/- 0, one's complement and signed magnitude are the same. If the question was "which representation**s** take the largest amount of memory", then I'd still say that claiming one (or two) take more than the others is very misguided.

(And the number $-2^{n-1}$ that can be represented with n bits two's complement or signed magnitude has its own problems where both negation and division can lead to overflow).
> 3 votes

---
Tags: arithmetic, numeral-representations
---


# Question
Title: The recursive solution to the all-pairs shortest-paths of Floyd-Warshall algorithm
In the Floyd-Warshall algorithm we have:

Let $d\_{ij}^{(k)}$ be the weight of a shortest path from vertex $i$ to $j$ for which all intermediate vertices are in the set $\\{1, 2, \cdots, k\\}$ then

\begin{align\*} &d\_{ij}^{(k)}= \begin{cases} w\_{ij} & \text{ if } k = 0 \\ \min\\{d\_{ij}^{(k-1)}, d\_{ik}^{(k-1)} + d\_{kj}^{(k-1)}\\} & \text{ if } k \> 0 \end{cases}\\ \end{align\*}

In fact it considers whether $k$ is an intermediate vertex in the shortest path from $i$ to $j$ or not. If $k$ is an intermediate it selects $d\_{ik}^{(k-1)} + d\_{kj}^{(k-1)}$ becuase it decomposes the shortest path to $i \stackrel{p\_1}{\leadsto} k \stackrel{p\_2}{\leadsto} j$ otherwise $d\_{ij}^{(k-1)}$ since $k$ is not an intermediate vertex so it has no effect on the shortest path.

**My problem is**, For a given shortest path between $i$ and $j$, $k$ is an intermediate vertex or not and its existence is deduced from the structure of the graph not our decision. so we have no freedom to select or not to select the $k$, because if $k$ is an intermediate vertex so we must choose $d\_{ik}^{(k-1)} + d\_{kj}^{(k-1)}$ and if not we must choose $d\_{ij}^{(k-1)}$. But when in formula it takes $\min$ between two numbers, it sounds like that it has option to select any of them while based on the structure of the graph there is no option for us. I believe the formula must be

\begin{align\*} &d\_{ij}^{(k)}= \begin{cases} w\_{ij} & \text{ if } k = 0 \\ d\_{ij}^{(k-1)} & \text{ if } k \> 0 \text{ and } k \notin \text{ intermediate}(p)\\ d\_{ik}^{(k-1)} + d\_{kj}^{(k-1)} & \text{ if } k \> 0 \text{ and } k \in \text{ intermediate}(p) \end{cases}\\ \end{align\*}

# Answer
> 4 votes
In fact the algorithm *determines* whether the vertex $k$ is "intermediate" on the path from $i$ to $j$. If indeed $d\_{ik}^{(k-1)} + d\_{kj}^{(k-1)} \< d\_{ij}^{(k-1)} $ during the computation we know that (up to the first $k$ vertices) the vertex $k$ is needed to obtain a shorter path between $i$ and $j$.

So, in my opinion, the algorithm takes into account the structure of the graph!

# Answer
> 3 votes
The Floyd–Warshall algorithm computes the weight of the shortest *walk* between any two vertices (a walk is defined like a path, but with repeated vertices allowed). Assuming all weights are positive, the shortest walk is always a path, since if a walk hits the same vertex twice, then we can remove the cycle to obtain a shorter walk.

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


# Question
Title: Is there any difference between these two languages?
If I have the following two languages:

$L\_1= \\{ w \in \\{a,b\\} |$ $w$ has neither $ab$ nor $ba$ as a subword$\\}$

$L\_2= \\{ w \in \\{a,b\\}^\* |$ $w$ has neither $ab$ nor $ba$ as a subword$\\}$.

Is there any difference between $L\_1$ and $L\_2$? I understand the impact of the Kleene star, but I don't see what difference it makes here.

# Answer
> 2 votes
Yes there is. $w \in \\{ a, b\\}$ means that $w$ may be either $a$ or $b$, while $w \in \\{ a, b\\}^\*$ means that $w$ may be a string over $a$ and $b$ including the empty string $\epsilon$. In particular $L\_1$ is a language having only $a$ and $b$, i.e, $L\_1 = \\{a, b\\}$.

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


# Question
Title: how to bound the probability that quicksort takes greater than n lg n time?
I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed)

> Consider RANDOMIZED-QUICKSORT operating on a sequence of *n* distinct input numbers. Prove that for any constant *k* \> 0, all but *O*(1/*nᵏ*) of the *n*! input permutations yield an *O*(*n* lg *n*) running time.

By RANDOMIZED-QUICKSORT, they simply mean quicksort with the pivot randomly selected from interval being partitioned, as opposed to always being chosen as, say the last element or something.

A previous thread on this same question had a single answer, which consisted entirely of a dead link plus a working link that leads to a set of (in my opinion) poorly-written notes for an undergraduate class, that does not answer the question, only having a very brief discussion of a particular case of quicksort with *n* ≈ 20.

I'm not even sure how to rigorously pose the question; my best shot is this:

> Prove that for any *k* \> 0, there exists positive constants *a*, *b*, and *n*₀ such that for all *n* \> *n*₀, the probability that RANDOMIZED-QUICKSORT makes more than *a n* lg *n* comparisons is less than *b* /*nᵏ*:

A similar problem appears in Knuth's *The Art of Computer Programming vol 3, Sorting and Searching*, as problem 42 on page 137 (with some minor notational edits for clarity):

> For any real number *c* \> 0, prove that the probability is less than exp(-*c*) that quicksort will make more than (*c* \+ 1)(*n* \+ 1)*H* comparisons when sorting random data, where *H* = 1 + 1/2 + 1/3 ... 1/n. (This upper bound is especially interesting when *c* is, say, , where *h* is small and positive).

The solution to this problem is given at the end of the book, and consists only of the following:

> This is a special case of a general theorem due to R. M. Karp, see *JACM* **41** (1994), 1136-1150, section 2.8. Significantly sharper asymptotic bounds for tails of the quicksort distributions have been obtained by McDiarmid and Hayward, *J. Algorithms* **21** (1996), 476-507.

I hunted down the Karp paper, and it indeed proves the result from the Knuth problem.

While CLRS seemingly refers to Knuth for a great deal of the former's material, it seems to be that the result that CLRS is asking us to prove is actually stronger than the result in the Knuth problem. In particular if we take the parameter *c* in Knuth's result to be any *c*(*n*) = ω(1), e.g. even something extremely slowly growing like *c*(*n*) = ln ln ln *n*, then the Karp result says that the probability is less than exp\[-*c*(*n*)\] that quicksort will make more than \[*c*(*n*) + 1\](n + 1)H comparisons. Since H = Θ(lg n), this number is Θ\[*c*(*n*) n lg n\], and since we have defined *c*(*n*) = ω(1), this number is ω\[ n lg n \], with maximum generality. However, with the choice *c*(*n*) = ln ln ln n, the upper bound of the probability is exp\[-*c*(*n*)\] = 1 / ln ln n, which is a much weaker upper bound than what CLRS is asking for: less than *O*(1/*nᵏ*) for any constant *k* \> 0.

My questions are the following: is my interpretation of the CLRS question (the quoted block above, immediately after I say "my best shot is this") correct? If not, what, specifically, is CLRS actually asking us to prove? Also, what is the relationship between the CLRS question and the Knuth question? Is the Knuth result weaker than the CLRS result? If so, does the CLRS result draw on more recent published research than the 1994 Karp paper cited in Knuth's "answer"?

Also, some further relevant reading: the McDiarmid paper that Knuth's answer points to cites a 1991 paper by Rosler, who showed that

$$ \Pr\left\[\left|\frac{Q\_{n}}{E\[Q\_{n}\]}-1\right|\>\varepsilon\right\]=O\left(\frac{1}{n^{k}}\right) $$

where $Q\_n$ is a random variable indicating the number of comparisons made by quicksort on an input of size $n$, $\varepsilon$ is a fixed constant, and $k$ is any positive real number. It seems likely that this is the source of the result asked for in the original CLRS problem, although the formulation of the probability in the above equation does not seem extremely obviously equivalent to the CLRS phrasing.

# Answer
> 3 votes
The exercise is extremely poorly worded. The problem is that Randomized-Quicksort is a randomized algorithm, and so it doesn't have a "running time", or rather, its running time is a random variable. I suspect that this is a typo, and that the intension was to analyze the *deterministic* Quicksort algorithm. Assuming this correction, here is a more formal version of the exercise:

> Show that for all $k \> 0$ there exist constants $a\_k,b\_k$ such that for all $n$, there exists a subset $S \subseteq S\_n$ (where $S\_n$ is the set of all permutations of $1,\ldots,n$) of size at most $(a\_k/n^k) n!$ such that for all $\pi \in S\_n \setminus S$, the running time of Quicksort on $\pi$ is at most $b\_k n \log n$.

In order to prove the exercise, presumably you need to use material from Theorem 12.4, which states that the expected height of a randomly built binary search tree of size $n$ (formed by choosing a random permutation in $S\_n$ and adding the elements to a binary search tree in that order) is $O(\log n)$. You then argue roughly as follows:

1. When running Quicksort on a permutation in $S\_n$, the running time is $O(nh)$, where $h$ is the height of the binary search tree formed from the permutation.
2. The argument of Theorem 12.4 can be strengthened to show that for each $k\>0$ there exist $a\_k,b\_k$ such that when constructing a random binary search tree, the probability that the height exceeds $b\_k \log n$ is at most $a\_k/n^k$.
3. Putting the two ingredients together yields the problem.

# Answer
> 3 votes
Here's a possible answer to the original CLRS question itself, based on the outline provided in the accepted answer above.

Let $X\_n$ be the random variable indicating the height of a randomly-built binary search tree on $n$ distinct keys. Page 302 of CLRS showed that

$$ \mathrm{E}\left\[2^{X\_n}\right\]\leq \frac{1}{4} \left(\begin{array}{c} n+3\\ 3 \end{array}\right) = O(n^3) $$

By Markov's inequality (proven in exercise C.3-6 of CLRS), we have for any $t \> 0$:

$$ \Pr\left\\{ X\_{n}\geq \lg t\right\\} = \Pr\left\\{ 2^{X\_{n}}\geq t \right\\} \leq\frac{\mathrm{E}\[2^{X\_{n}}\]}{t}=O\left( n^3t^{-1} \right) $$

Hence, choosing $t = n^{3+k}$ for any $k\>0$, we have

$$ \Pr\left\\{ X\_{n}\geq (k+3)\lg n\right\\} = O\left( n^{-k} \right) $$

Mapping this back to the quicksort problem, as discussed in the accepted answer above, we obtain that the probability of quicksort taking time larger than $(k+3) n \lg n$ is $O\left( n^{-k} \right)$, which completes the proof.

Note that this result is useful because the set of sequences that take time larger than $(k+3) n \lg n$ includes, as a subset, all the sequences that take worse-than-average behavior, such as for example already-sorted sequences, which elicit $\Theta(n^2)$ runtime, as well as everything in between the average and worst, e.g. $\omega(n \lg n)$ and $o(n^2)$. Hence, bounding the probability of this set also bounds the probability of the subset.

---
Tags: algorithms, sorting, probability-theory, randomized-algorithms, quicksort
---


title: What does 'buffering' mean?

text:
# Question
Title: What does 'buffering' mean?
I read the lecture 4 of CS162 (UC Berkeley: https://inst.eecs.berkeley.edu/~cs162/sp17/static/lectures/4.pdf), but I got little bit confused about the meaning of the keyword "buffered" they used when mentioning the following informations:

> Kernel buffered reads
>
> Kernel buffered writes
>
> Data buffered automatically by C-library functions

What does each of 'buffering' and 'buffered' mean?

# Answer
> 4 votes
When reading from a source, often a program wants to read data a few bytes at a time. For instance, the program can ask the OS for the next 4 bytes from a file, so to read the next 32-bit integer. Then, it can repeat the operation again and again, until all the integers have been read.

However, that is rather inefficient. First, disk (or even SSD) reads are done in hardware using large chunks, only, like 512 or more bytes. Reading that much only for 4 bytes is a waste of band. Second, switching between user mode and kernel mode has its cost, and it would be better if any such switch would transfer a non-trivial amount of data.

For that reason, reading is usually done in large chunks, using a "buffer". Basically, the OS reads a large-ish portion of the file (say, a few KBs), and keeps this in a kernel-space array (the "buffer"). This is done in one large chunk so to optimize disk/SSD access. After this, when the program asks for the next bytes, the OS does not need to involve the hardware, and can return data from the buffer.

Context switches are similarly optimized. The C library also commonly reads a large chunk form the OS, using a user-space buffer, using only one system call (= one switch). In this way, when the application program asks for the next (say) 4 bytes, the C library can copy from the buffer without making system calls.

When the buffer becomes empty, the C library starts asking again to the OS, and the OS starts asking again to the hardware.

Buffered writing is similar, but in the other direction, converting many small writes to fewer big ones, so to improve performance. This is done by the C library and the OS/kernel.

---
Tags: operating-systems, streaming-algorithm
---


# Question
Title: return a key of a node with maximum value within a range of keys in B+ tree
I've been asked a question about B+ Tree.

**The question is:** Suppose we have object of the following type:

`class Obj {
private:
 int value;
 int key;
public:
 Obj(int uniq_key , int value)
}`

and I am creating a Generic B+ tree which will sort objects in it leafs nodes by keys and not by values. (The keys are unique values aren't) Now I want to return the key of a node containes **Maximum value** within a range of keys. For Example:

If I have the following objects inserted in my B+ tree:

`Obj a(1,10) , Obj(2,5) , Obj(3,0)`

Then by calling this method I will get a return value : **1**

I thought of having an extra rank tree with the same data stored in it and a pointer from a leaf node in the B+ tree to it's equivalent node in the rank tree but I think that there is a solution involves adding extra data in the nodes in the B+ tree which can solve this issue.

**p.s.** I don't know if this post is duplicated - I couldn't find anything else answering this kind of question.

Thank you, Michael

# Answer
Augment each node to contain the key of the node with maximum value, among all nodes that are underneath it (among all of its descendants). You can easily maintain/update this augmented information each time you modify the tree, by using the fact that the maximum for any node can be recomputed using just the information in its direct children (you don't need to look at its grandchildren etc.).

Now any range can be expressed as the union of $O(\log n)$ subtrees. In other words, you can find $O(\log n)$ nodes such that their descendants cover the range exactly. So, the max value of any node within that range can be obtained by looking at the values in those nodes, and taking the max of them. In this way each query can be answered in $O(\log n)$ time.
> 1 votes

---
Tags: data-structures, search-trees, balanced-search-trees, searching, b-tree
---


title: Count numbers less than $K$ in array

text:
# Question
Title: Count numbers less than $K$ in array
Let's say we have given array $A$ consisting of $n$ integers, and integer $K$. Now we want to count number of indexes $i$ such that $A\_i\<K$. What is the easiest way to pre-process the array and answer queries for different $K$ fast. Note that the elements of the array will be small up to $10^5$, so it will be possible to count how many times each elements appears.

For example, let $A = \\{1, 2, 3,0,0,2\\}, K =3$ the answer is $5$, because all $\\{1,2,0,0,2\\}$ are less than $3$.

I know that we can implement this with segment tree and than answer queries in $O(\log N)$, but I was thinking that we can implement easier solution that is easier to code.

# Answer
> 4 votes
Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case $10^5$) in pseudocode

```
count = new int[C] (array of integers)
for every a[i] in a
   count[a[i]]++
for i = 1, i < C, i++
   count[i] += count[i-1]

```

To Answer a query for a given k you just return `count[k - 1]`

# Answer
> 3 votes
As mentioned in comments, you can sort the array as a pre-process. Then answer to the query in $O(\log(n))$ using binary search. The implementation is common and easier.

---
Tags: data-structures, counting
---


# Question
Title: non-binary locality-sensitive hashing with random projections
I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to which side of the hyperplane a data point lies. I want to use locality sensitive hashing with a random projection, but I need to be able to produce more than just two possible indexes.

I'm wondering if I could make an LSH by binning data according to this strategy:

1. Initialize a d x k matrix, where d is the input data dimensionality and k is the number of hash indexes we want.
2. Project incoming data into k-dimensional space using this matrix.
3. Take the argmax of the new k-dimensional vector. In other words, output the dimension that has the largest value.

If not, does anyone know of another technique? Thanks!

# Answer
> 1 votes
Let $h\_r(x)$ be a hash function that hashes a point $x$ to a one-bit hash output. Then you can construct a hash function that gives you a $b$-bit hash output, by concatenating $b$ independent one-bit hashes:

$$h\_{r\_1,\dots,r\_b}(x) = (h\_{r\_1}(x), \dots, h\_{r\_b}(x)).$$

For example, you can pick $b$ random hyperplanes; then the $i$th bit of the hash will indicate where the point falls relative to the $i$th hyperplane.

This avoids the need to invent new LSH functions.

---
Tags: algorithms, approximation, randomized-algorithms, hashing
---


# Question
Title: If all edges are unweighted AND DIRECTED, can one use BFS to obtain a MST?
I've looked through CS SE and I've found a page that said you could find use BFS to find a MST if the edges are unweighted, but what if the edges are directed?

Given a directed graph between V vertices, I'm trying to find the minimum directed edges I need to add in order for every vertex to be connected to every other vertex.

Is MST the way to go? Or, is there another way I'm not thinking of.

I apologize if this question is too easy, as I am very new to programming. I appreciate any help. Thanks!

# Answer
This is known as an arborescence. There are algorithms for this problem, such as the Chu-Liu/Edmonds algorithm, but they are more complex than just doing a BFS. See also https://stackoverflow.com/q/21991823/781723.
> 2 votes

---
Tags: algorithms, graphs, recursion, minimum-spanning-tree
---


# Question
Title: Is there an analog of "regular" for infinite strings?
Consider the sequence $s\_1 = (1, 0, 1, 0,\dots)$. It seems "regular" in a way that, e.g. $s\_2 = (1, 2, 3, 4,\dots)$ is not.

I'm not sure how to formalize this intuition though. One thing which jumps out at me is that $L =\\{(0 1)^n\\}$ is a regular language, and $s\_1$ is in some sense the limit of the strings in this language.

Is there a terminology for considering these infinite strings? Do we have something analogous to the pumping lemma, whereby we can state that any such "infinite regular" string is of the form $x y^ {\infty}z$ with $x$, $y$, $z$ finite?

# Answer
> 15 votes
Probably the most specific term to describe your first string, $010101\dots$ is *periodic*. A string $x\_1x\_2\dots$ (finite or infinite) is periodic if there is some $t$ such that, for all $i$, $x\_i=x\_{i+t}$. In the case of this example, we can take $t=2$. A slightly weaker notion is that a string is *eventually periodic* if there are $n$ and $t$ such that $x\_i=x\_{i+t}$ for all $i\geq n$.

More generally, though, there is a direct analogue of the regular languages, which is the $\omega$-regular languages. These are recognized by natural generalizations of finite automata. The state set is still finite but the acceptance criterion must be modified to deal with infinite words – in particular, we can't just say "Accept if the automaton finishes in an accepting state" because the automaton never finishes processing its infinite input.

The simplest class of automata for infinite words are Büchi automata. They are defined exactly like the finite automata you're used to, and they accept their input if at least one accepting state is visited infinitely often during the automaton's run. One difference from ordinary finite automata is that it turns out that nondeterministic Büchi automata are more powerful than deterministic ones, and the $\omega$-regular languages are the ones accepted by nondeterministic Büchi automata. Other sensible acceptance criteria lead to other automaton models which accept the same class of langauges.

Note that it doesn't quite make sense to write $xy^\omega z$, since you can't have anything *after* an infinite sequence of $y$s. At least, you can't if the positions in your string are indexed by the natural numbers. If they're indexed by larger ordinals this can make sense.

I can't actually remember if there's an analogue of the pumping lemma for $\omega$-regular languages. This is slightly embarrassing, though it is most of a decade since I taught a graduate class on this stuff.

# Answer
> 3 votes
This is a basic result in Type Two Effectivity, which I think answers your question from a computable point of view. In the following, our languages consist only of infinite strings. We denote the set of infinite strings $\Sigma^\omega$.

> Theorem: If a realizable automaton terminates on every infinite string, then the language of the automaton is equal to $S\Sigma^\omega$ where $S$ is a finite set of finite strings.

The proof is by Konig's lemma.

The conclusion is that a language over infinite strings is either "simple" in some sense (which is an interesting fact) or undecidable. Any non-trivial notion of language over infinite strings is undecidable.

---

You can presumably study less simple languages if you allow membership to be *semidecidable* rather than decidable. This can still be considered "computer science" and not just infinitary mathematics (it's to do with search problems instead of decision problems; semidecidability is in a sense sufficient for doing a search).

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


# Question
Title: What algorithm could I use to find the largest set of disjoint members from a set of subsets of a set?
I've written a political quiz based on data from the public whip. They group politicians' votes by policy; each vote can belong to many policies. There are too many policies for me to ask a question for each one, and anyway some are duplicates and some policies' votes are subsets of other policies. In the past, I've manually chosen a subset of policies to use in my quiz try to maximise the number of votes included without double-counting any, but I'm worried that that may introduce my biases into what is supposed to be as neutral as possible a quiz. So I'd like to find the set of policies which maximises the number of votes included without counting any of them twice.

Is there a known algorithm I could use to do this? I've seen similar questions elsewhere on this site but they generally seem to involve sets of intervals or geometric shapes.

# Answer
> 3 votes
The problem you describe is known as set packing, and it has a natural ILP formulation. You can start with some ILP solver you have access to, and it should be a highly competitive solution. There are many heuristics to choose from as well if you don't require optimal solutions.

---
Tags: algorithms, sets
---


title: Integer log2 as a catamorphism?

text:
# Question
Title: Integer log2 as a catamorphism?
Recursion schemes are structured methods for expressing recursive functions, of increasing interest due to their ubiquity in functional programming. For example, catamorphisms (familiar in the guise of 'fold' on lists) can be defined for all inductively-defined (i.e. algebraic) data types and in the particular case below, for natural numbers ("A natural number is either zero, or the successor of a natural number).

Q. Can (floor) log2 on the natural numbers (setting log2(0) to be 0) be readily expressed as a single recursion scheme (e.g. a catamorphism), as opposed to via a hylomorphism (which is an anamorphism followed by catamorphism)?

A formulation of log2 via metamorphisms is given in Martin Erwig's Metamorphic Programming. Can it instead be expressed simply as a catamorphism?

# Answer
> 3 votes
```
recNat :: (Integer -> a -> a) -> a -> Integer -> a
recNat s z n | n <= 0    = z
             | otherwise = s (n-1) (recNat s z (n-1))
-- Exercise: Express this in terms of foldNat.

log2 :: Integer -> Integer
log2 = fst . recNat (\n (c, p) -> if 2*p > n+1 then (c, p) else (c+1, 2*p)) (0, 1)

```

---
Tags: recursion
---


title: Buying as many items for as much money

text:
# Question
Title: Buying as many items for as much money
I cant find a way to implement a certain solution. Let me flesh out the problem.

Somebody gives you X amount of money and sends you to the shop to buy Y amount of items. You must spend as much money as you can and buy as many items as you can. You cant have more money they X. You cant buy more than Y amount of items. Some money can left afterwards, but as little as it can. You can buy less than Y items, but only if there is no other option. You cant buy same item more than once - items are unique.

Examples:

You have 15£, and need to buy 2 items. There are 4 items for 10£, 5£, 4£ and 3£. You buy 10£ and 5£ items. Perfect scenario - 15£ spend, 2 items aquired.

You have 15£ and have to buy 3 items. There are 4 items for 4£, 3£, 2£, 1£. You buy 4£, 3£ and 2£ items. 9£ and 3 items aquired.

You have 15£ and have to buy 2 items. There are 4 items for 20£, 19£ and 14£. You buy only 14£ item.

I think you understand by now how it works.

Implementation(Javascript):

```
var arrayOfItems = [];
arrayOfItems[0] = {"name":"Sandwich","price":15};
arrayOfItems[1] = {"name":"Water","price":10};
arrayOfItems[2] = {"name":"Cookie","price":5};

function getItems(moneyAmount,itemsAmount){
    //your code here....
}

var items1 = getItems(21,2); //returns [0,2]
var items2 = getItems(25,2); //returns [0,1]
var items3 = getItems(14,2); //returns [1]

```

I need to invent the inside of getItems() function. Can you lead me how to do this?

Thank you for help.

# Answer
> -1 votes
This is a classic Knapsack problem some examples: Knapsack.java, JS example

Here is a pseudo code from Introduction to Algorithms, MIT:

---
Tags: optimization
---


# Question
Title: Paint the balls: what patterns can be painted?
You are given a number $k$ which specifies the number of consecutive balls you can paint in a go. You are given a string $S$ of length $l$. $l$ is the number of balls and each character in the string specifies the color of the $i^{th}$ ball. I want to know whether it is possible to color all the balls in the given pattern.

e.g.,
$S=rrggg$,
$l=5$,
$k=3$

We can color this pattern in two operations. As a first step we paint first three balls in red color and in the second step last three balls in green. Hence the answer should be $2$.

I conjecture that we can always generate a pattern provided that there's at least one consecutive sequence that has same color and $l \ge k$. I've formed this conjecture using various sample tests but there's no concrete proof that I could produce. Is the conjecture true? Can you prove it?

If this can be proved logically, it's easier to code the solution of the above problem. I'd like to see the proof of the conjecture that it's always possible to produce the pattern if there's at least one consecutive sequence that has same color and $l \ge k$.

# Answer
Every pattern with a run of length $\ell$ is feasible. Indeed, consider first that the last run has length at least $\ell$. We go over the string from left to right, and for each $i$, we paint balls $i,i+1,\ldots,i+\ell-1$ with the required color for position $i$. After going over all possible indices (i.e., all but the last $\ell-1$), we have painted the pattern.

Now suppose that there is such a run in the middle, say $r,\ldots,s$. We run the algorithm above up to position $r-1$, and the we run a similar algorithm going from left to right, until ball $r$ is painted. We have painted the pattern.

As for the optimal number of moves, one natural algorithm to consider is the algorithm described above, with a simple optimization: when attempting to paint the $i$th ball, if it is already of the correct color, then don't bother. I conjecture that this algorithm, or some simple variant of it, is indeed optimal.
> 1 votes

---
Tags: algorithms, strings
---


# Question
Title: An algorithm to detect if the conversion rate growth acceleration rate is still rising or stopped
An example.

I have bought a currency while the rate was 1.0. As soon as the conversion rate has increased to 2.0 I would like to sell the currency. Now, that would be an easy task to do. But we are not searching for "easy" tasks, are we?

What if there was a way to determine, whether the rate is still growing or not? For example, what if the conversion rate was still growing at +0.5 per minute, in that case - I would be able to sell the currency at rate 3.0 if only I have waited for 2 more minutes. Alternatively, I would be able to sell the currency at an even higher rate, if it was determined that the acceleration rate either stopped, or became negative.

Here is a visual representation of what I want to accomplish:

* black line - good, but too early to sell
* green line - sell now
* red line - better sell it now, before rate decreased

Is there an algorithm to accomplish this task?

At this point - it is not clear to me:

1. What would be the best time range to take into acceleration rate calculations. Should I consider the rate change during the last 10 minutes, 5 minutes or 20 seconds?
2. How do I determine that the "growth" (acceleration rate) has stopped or is close to being stopped?
3. Do I only need to know only the conversion rate, or also number of trades (buys/sells) at a given time frame?

Any advices are appreciated.

# Answer
> 1 votes
You are seeking to predict future values of the time series based on past values. There's *lots* in the area of time series analysis and prediction; I suggest reading about those topics. The right approach will depend on domain knowledge and how currency rates tend to change and what statistical model is appropriate in your setting.

---
Tags: algorithms
---


title: Difference between NFA and NBA

text:
# Question
Title: Difference between NFA and NBA
NFA (nondeterministic finite automata) accepts only finite words while a NBA (nondeterministic Büchi automata) accepts infinite words (and hence $\omega-$regular languages).

I think the example automata accepts finite word like $A,B,A,B$. But it also accepts infinite words like $A,B,A,B,...$.

How can i know if the example-automata accepts the finite language $(AB)^\*$ or the infinite language $(AB)^{\omega}$(is the automata an NFA or NBA)?

Can it be differed and if yes how?

# Answer
It's impossible to tell if all you have is the pictorial representation, since these look the same for both types of automata. Even if you're given a formal specification you won't necessarily be able to tell the difference (it depends on how these automata are encoded).

This kind of ambiguity is similar to linguistic ambiguity that can occur in real life. For example, suppose you see the word "impossible" written on the wall. Can you tell whether it's English or French?

Sometimes this kind of ambiguity is purposeful. For example, the pictorial representation of a DFA doubles as the pictorial representation of an equivalent NFA. The only difference in your case is that the two interpretations are inequivalent.
> 1 votes

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


title: Proof Carrying LLVM?

text:
# Question
Title: Proof Carrying LLVM?
I am intrigued by and understand the very basics of Proof Carrying Code (PCC) and I recognize that LLVM is a machine-independent intermediate language. LLVM is the intermediate form of many languages, including the new Rust language. Typed Assembly is another style of intermediate form which can be used to generate PCC proofs but it has not gained the same popularity/utility. I've heard of Singularity, Verve and JX.

As I understand it, generating PCC proofs are within practicality even for large programs, but that their resulting size and verification burden (necessary only once per "installation") are non-negligible. I don't care about 10x (discardable) proofs nor several hours of verification - I'm very interested in a provably-safe operating environment.

Is there anything missing from the LLVM language or type system that would prevent us from emitting such proofs? Or can you tell that am I missing something about the bigger picture?

# More

> PCC for what properties? Memory safety?

Yes, memory safety which I *believe* is a minimum policy required to ensure that a process cannot take over the kernel or another application. Seems to me that (popularly) a message passing interprocess-communication scheme restores some of the functionality taken away by direct memory access (Erlang, Singularity OS).

> Do you have a citation/reference for your statement about practicality?

Here's something that suggests its practicality to me: "It has been shown that proofs for Java type safety can be compressed to 12%–20% of the size of x86 machine code ... but unfortunately this increases the proof checking time by a factor of 3". -- Interpretation of Necula, Oracle-Based Checking of Untrusted Software by Franz

> What research have you done?

I've been following this topic (including the names I mentioned previously) over the years reading and absorbing what I can comprehend.

> I think it helps to separate "is it possible to do PCC for LLVM bitcode?" from "why doesn't the Clang compiler currently implement PCC?"

Yes, I'm mostly interested in "is it possible to do PCC for LLVM bitcode?" - but I'm not being too specific because I'm not confident that I understand how all the pieces fit together which is why I'm here trying to get an answer from a human who already gets it and can contribute to the understanding of people who are merely at my stage of understanding.

But see, related to your "why doesn't the Clang compiler currently implement PCC?", I would have assumed that the LLVM compiler (the one that goes from LLVM to assembly) would be the one capable of emitting the proof, since it still has higher level concepts of the code before it gets erased in the final binary (as does, I believe, TAL) and of interest because type-safe languages like C# and Rust compile to LLVM, possibly with enough type information to unify the approach among all LLVM languages. So had I been more specific, I'd be getting shat on for that.

> I think it would help to clarify exactly what you're asking about

That's pretty much what *I'm* looking for!

# Answer
> 3 votes
This is a project I've been thinking of venturing into for a few years now, and I was fortunate to have a very useful discussion about it at the time I started planning it with Chris Lattner (at the time, one of the main architects of LLVM, although better known these days perhaps for his work on Swift).

It does seem that there is a possibility of producing correctness proofs for a subset of C (or potentially C++) using LLVM. There has already been some work done which would be useful:

* As discussed in comments, memory safety is critical. Without memory safety, type safety is essentially irrelevant. A number of memory-safety related analyses and transformations have already been implemented for LLVM that could help. These include:
* "fat pointers", i.e. transformation of C style pointers into pointers into areas of defined size, in order to catch bound errors
* a transformation applied to dynamic memory allocation that enables detection of use of pointers after they have been freed. These two features are described in this paper.

For the subset of C programs that perform no type casts, applying these transformations may be adequate. Of course, real C and/or C++ code often uses typecasts, and adding this facility is more challenging. For performance sake, as many of these cases as possible must be caught at verification time rather than runtime, although in the end of the day the use of runtime type information and a dynamic casting implementation would be enough to allow for entirely safe C code.

---
Tags: compilers, correctness-proof, software-verification, automated-theorem-proving
---


# Question
Title: On clarification of intersection of classes definition
How do you define $\oplus P\cap PP$?

1. $L\in\oplus P$ iff $\exists\mbox{ NTM }M:\forall x,\\#acc\_M(x)\mod2\equiv0$.
2. $L\in PP$ iff $\exists\mbox{ NTM }M:\forall x,\\#acc\_M(x)\>\\#rej\_M(x)$.

Consider the classes $C\_1,C\_2,C\_3$.

$L\in C\_1$ iff $\exists\mbox{ NTM }M:\forall x\\#acc\_M(x)\>\\#rej\_M(x)\mbox{ and }\\#acc\_M(x)\mod2\equiv0$?

$L\in C\_2$ if $\exists\mbox{ NTM }M\_1:\forall x\\#acc\_{M\_1}(x)\>\\#rej\_{M\_1}(x)\mbox{ and }\\#acc\_{M\_1}(x)\mod2\equiv0$ and $L\not\in C\_2$ if $\exists\mbox{ NTM }{M\_2}:\forall x\\#acc\_{M\_2}(x)\leq \\#rej\_{M\_2}(x)\mbox{ and }\\#acc\_{M\_2}(x)\mod2\equiv1$.

$\exists\mbox{ NTM }M'$ such that $L\in C\_3$ if $\forall x\\#acc\_{M\_1}(x)\>\\#rej\_{M'}(x)\mbox{ and }\\#acc\_{M'}(x)\mod2\equiv0$ and $L\not\in C\_3$ if $\forall x\\#acc\_{M'}(x)\leq \\#rej\_{M'}(x)\mbox{ and }\\#acc\_{M'}(x)\mod2\equiv1$.

Which of $C\_1,C\_2,C\_3$ defines $\oplus P\cap PP$ and which one $\oplus P\wedge PP$? What about last one?

# Answer
> 2 votes
Complexity classes are sets of languages. Intersection of sets is intersection of sets.

---
Tags: complexity-theory, proof-techniques, complexity-classes, closure-properties
---


# Question
Title: Doubt with the halting problem undecidable proof
The Halting problem proof can be seen as the following programs:

1. Ends(P, I) is a program that detects (returns true or false) if the program P will halt or not with the input I
2. Diag( P ): is a program that

2.1 Halts if P( P ) doesn't halt

2.2 Doesn't halt if P (P) halts

If we use (2) with input Diag it state:

1. Diag(Diag) halts if Diag(Diag) doesn't halt
2. Diag(Diag) doesn't halt if Diag(Diag) doesn't halt

Which by contradiction is proven that the program Ends can't exist.

Until here everything is fine. But What if instead of thinking on halt or never halt, we think in steps.

What if I do the following analogy:

1. Ends( P, I, S ) is a program that detects (returns true or false) if the program P with the input I, it will halt in less or equal S steps.
2. Diag( P, S) = Diag( P ): is a program that:

2.1 That halts in less or equal than S steps if Ends( P, P, S ) doesn't halts in less or equal than S steps.

2.2 That doesn't halts in less or equals than S steps if Ends( P, P, S ) halts in less or equal than S steps.

if we use (2):

1. Diag( Diag) halts in less or equal than S steps if Ends( Diag, Diag, S ) doesn't halt in less or equal than S steps.
2. Diag ( Diag ) doesn't halt in less or equals than S steps if Ends( Diag, Diag, S ) halt in less or equal than S steps.

Which is the almost the same contradiction, and in this case Ends is possible to build.

What I'm doing wrong?

# Answer
The main problem with your analogy is the construction of Diag. The usual proof goes as follow:

1. **Assume** Ends exists.
2. Then we **can construct** Diag with a Turing machine calling Ends. As follows:

`Diag(P) = If Ends(P,P) then Loop indefinitely Else Terminates.`

3. This leads to a contradiction thus Ends does not exist.

What you are doing is the following:

1'. **Construct** Ends(P,I,S).

2'. **Construct** Diag(P,S).

3'. This leads to a contradiction.

The main problem is that you do not provide the actual construction of Diag in step 2' as we did it in step 2. How can you implement Diag with a TM machine calling Ends? I do not think so as you need more than S steps to run the program Ends.
> 1 votes

---
Tags: undecidability, correctness-proof, halting-problem
---


# Question
Title: How to calculate the complexity of a TM?
I have the language

$\\{ w \mid w \text{ contains an equal amount of symbols } a \text{ and } b\\}$.

I want to show that the language is in the class $\textsf{P}$. To do this, I must give an implementation level description of the relevant Turing machine. I'm not very knowledgeable on Turing machines, but I think I would be able to write down a possible transition function, but from this how do I compute the complexity, in order to show it is in the class $\textsf{P}$?

# Answer
> 1 votes
You only have to show that there exists a Turing machine that decides the language, and such that the number of steps taken by it is a polynomial in the size of the input, in this case a polynomial in $|w|$.

An example of such a machine is the following. Scan the tape left to right until you find both an $a$ and a $b$, and replace both of them with a new symbol, let's say $x$. If you fail to find both an $a$ and a $b$, there are two cases: if every nonblank symbol on the tape is $x$, answer $\textsf{YES}$, otherwise answer $\textsf{NO}$.

It should be easy to see that the number of steps is $O(|w|^2)$, and therefore the language is in $\textsf{P}$.

Just a pedantic note: we usually talk about the complexity of languages or problems, not machines. It would be more appropriate to say "number of steps taken" or "amount of space used" rather than "time complexity" or "space complexity" when talking about a specific Turing machine.

---
Tags: complexity-theory, turing-machines
---


# Question
Title: Finding shortest path involving additional restrictions
Question: If you were on an island(Vertex) which are connected to multiple other islands, and to get from island A to B it takes time T and does damage D to your boat. What is the fastest route from A to B such that the total damage is strictly less than a given value H.

I tried using Dijkstra's algorithm to build a sub-tree however the shortest route may not be acceptable since the total damage could be greater than H. Any suggestions? Please keep the answer simple since I am a high school student.

# Answer
We can create a new graph consisting of $N\cdot (H + 1)$ nodes and apply the Dijkstra algorithm on that graph. We will denote the new nodes as $(u, h):$ which means that the boat is at island $u$ and has been damaged by $h$ units, where $h$ is between $0$ and $H$. For each edge $(u, v, d, t)$ that goes from island $u$ to island $v$ while taking $d$ damage and $t$ time, we will create multiple edges in the new graph $((u, h), (v, h+d), t)$ (for $0 \leq h \leq H-d$). Your starting node will be $(A, 0)$ and to find the shortest path to $B$ you need to apply the Dijkstra algorithm and take the minimum time to $(B, h)$ for some $h$ between $0$ and $H$.
> 2 votes

---
Tags: algorithms, graphs
---


# Question
Title: Iterative DFS space complexity O(|E|)? Same vertex appears multiple times in stack?
I'm referring to a question already asked on stackoverflow: https://stackoverflow.com/questions/25988965/does-depth-first-search-create-redundancy

However I'm not quite convinced by the answers provided there.

Some iterative DFS implementations that I have seen (such as the one provided by Wikipedia) allow vertices to be pushed onto the stack more than once.

The space complexity would thus be $Θ(|E|)$ in the worst case. (While a recursive implementation of DFS would only require at most $Θ(|V|)$ space.)

Certain implementations check if a vertex has already been discovered before pushing it onto the stack, but this does not affect the space complexity of $Θ(|E|)$ since a vertex is only marked as discovered when it is popped off the stack and not when it is pushed (Thus we are not keeping track of vertices currently in the stack). This only makes sure that vertices which enter and leave the stack are never pushed onto the stack again.

Instead, one would have to mark a vertex before pushing it onto the stack and then check each time before pushing a vertex if it has already been marked (is currently in the stack) in order to avoid multiple occurrences of a same vertex in the stack (As you would do in BFS, where a queue is used instead).

My question is, why would one want to allow multiple occurrences of a same vertex in the stack and why one cannot simply apply the method mentioned above (which is used in BFS) in order to achieve space complexity of $Θ(|V|)$ ?

To illustrate the issue consider this example from the link that I provided:

> For example, consider the graph where node 1 points to node 2, which points to node 3, which points to node 4, and so on, up to node 100. Each of these nodes points to node 0. Consider applying the Wikipedia DFS algorithm to this graph, with node 1 as the start state. First, node 0 will be pushed onto the stack. Then node 2 will be pushed. Next, node 2 will be popped off the stack, and since it has not been explored, its children will be pushed onto the stack, (without checking whether they have already been added to the stack!). Node 2's children are node 0 and node 3. Next, node 3 will be expanded, pushing node 0 and node 4 onto the stack. This will continue until the stack is filled with 100 occurrences of node 0.

# Answer
> why would one want to allow multiple occurrences of a same vertex in the stack

For general remarks, I can only guess here since I can't read the minds of others.

A recursive method incurs quite some cost for managing registers and the (call) stack; an explicit stack may be so much faster that, usually, the iterative method is faster even though it's worse on memory.

Saying "usually", keep in mind that your arguments are *worst*-case considerations. Depending on the graphs you're looking at, the actual behaviour may be very different. When you ask on Stack Overflow, you'll usually get practice-driven trade-offs: use what's faster *in your setting*.

> why one cannot simply apply the method mentioned above (which is used in BFS) in order to achieve space complexity of O(|V|)

Because then you don't have DFS any more! We always want to follow the edge to a node that we discovered *last*. We have to keep track of the "older" edges with the explicit stack; the call stack remembers them for us by reference, thus saving the memory.

---

If you are very concerned about memory consumption -- which, depending on your inputs, you may have to be! -- there are ways around keeping duplicates in the stack. Here is one idea.

For each node, store in an array not only whether it was already visited/handled, but also its position in the stack (either by pointer or index). If you add a node to the stack and that position is set *remove the old stack entry*, then push the new one.

Clearly, this keeps the stack at $\leq |V|$ entries. Also, if removing items from the middle of the stack is fast, it does not make the algorithm (much) slower -- the node *will* have to be removed either way. If not, then a new trade-off appears.
> 0 votes

---
Tags: algorithms, graphs, algorithm-analysis, graph-traversal, space-analysis
---


# Question
Title: Can a 3 Color DFS be used to identify cycles (not just detect them)?
Can a 3 color DFS be used to identify all cycles in a directed graph not just detect them?

In other words if I have a directed graph with multiple cycles, can I run a function on them such that the function returns the list of nodes that compose each simple directed cycle in the graph and not just a boolean true or false? Most answers online show pseudocode for detection and not identification (ie functions which return boolean values instead of node lists). You can assume that the graphs I'm referring to are mostly tree like in structure and aren't deeper than 5 nodes or so.

So for example, for this graph:

The list would be \[\[a,b,e\], \[f,g\], \[c,d\], \[d,h\]\]

With white, grey, black DFS a cycle is found when a node already colored grey is visited a second time through a different edge. What I'm struggling to wrap my head around is when this happens, how do we back track to identify all of the nodes involved in this detected cycle without increasing complexity or running DFS a second time. In the example below, if we do a DFS (exploring right edges first) starting at A, the stack will look like this \[A,B,C,E,D,B\] and the cycle will be detected when B is visited a second time. Given this stack how do we deduce that C D and B only are part of the cycle and not E or A?

I am aware that there are plenty of algorithms other than DFS that can do this (such as Johnson's algorithm or Tarjan's with a twist) I just want something simple to implement.

# Answer
The moment you find a grey node, you have the edge that closes the cycle in hand. All other edges are part of the DFS tree. That is, store the "cycle-closing" edge and obtain the rest afterwards.

That is, assuming that those are the cycles you are interested in. Other cycles (such that contain more than one non-DFS-tree edge) are more complicated, but I don't think those are easy to cover. A directed graph may have super-exponentially many cycles, so you can't expect to list them all with a simple, linear-time traversal.
> 1 votes

# Answer
The answer to this question is YES. A three color DFS algorithm can be used to both detect *and identify* the nodes associated with all simple cycles in a directed graph with more or less the same time complexity.

The key is to keep a stack of parent and child pairs as you recursively explore the graph using white, grey, black (3 color) depth first search. You must also remember to pop pairs off the stack after you are done exploring a child (ie when the child's color is set to black). This will give you an easy way to trace what nodes are traversed going to and from a "starting node" in a cycle.

I will add more detail and an example implementation later!
> 0 votes

# Answer
Here is an algorithm which takes your stack content $S$ when loop was detected & return array of the nodes which are forming cycle. From your example it is $ \[A,B,C,E,D,B\]$

```
 Algorithm_Get_Loop_Nodes(S):
     cycle_nodes = []
     repeated_node = S[top]
     while S[top] != repeated_node:
         prev_node = S.pop()
         curr_node = S[top]
         if curr_node is parent of prev_node:
            cycle_nodes.add(curr_node)
     return cycle_nodes

```
> 0 votes

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Algorithm to calculate numbers of 10^x smaller than given one
I am struggling to create a smart algorithm. Currently I have produced one which is super-ugly and not efficient because I am casting `numerics` to `strings` back and forth, not really useful to share it here.

The point of algorithm is to get a number `10^x` which is smaller than a given one.

Examples:

* 600 =\> 100
* 34.54 =\> 10
* 7.2 =\> 1
* 0.123 =\> 0.1

I am sure I am missing something. Is there any smart way of doing that?

# Answer
> 1 votes
$Num \geq 10^{x} $

$\implies x \leq log\_{10}(Num)$

Then $x = \lfloor log\_{10}(Num) \rfloor $.

$10^{x}$ would be your number.

---
Tags: algorithms
---


# Question
Title: How would I go about determining popularity and relevance among articles and use it to improve my search algorithm
**Disclaimer:** First of all I've had a lot of trouble finding the right stack exchange site for this question and I don't know if it's correct here either.

**The Problem:** I'm working on a search algorithm for a django powered website which allows people to write articles on various subjects and search for articles on the webpage.

I've got a database in which I store articles for people to read on a website. I'm storing each article with a bit of information like:

**Articles:**

* A title.
* A predetermined category where the writer can choose from when adding an article (sports, economy, politics).
* Tags which the writer of the article can input themselves.
* Length of the article in characters
* A short description
* Dated added
* Date updated

I've a few easy ways a user can search an article based on the title ( for example shortest first or newest first)

I'm now working on adding a way to search based on popularity but I have a hard time to determine what I define as popular.

I'm saving article views in a different database table which contains:

**Views:**

* User ID
* article ID
* Timestamp

Each row inside this table is considered 1 view so I can see exactly when certain articles are doing well in terms of amount of views it gets. If I would search for an article with the most views in the database it would look something like this in django:

```
Article.objects.order_by('-views')[:30]

```

In this case views is stored in the table, However I store it in a different table so I can have the functionality described above.

The problem however is that if I have 1 article which is a few years old with a high number of views, for example lets say there has been a sports event (like the Olympic games of 2014) and a lot of people have read the article but the article is no longer very relevant as this same event has been done again (that would be the Olympic games of 2018 happening this year).

Now lets say someone searches for popular articles about the Olympic games. Even though the articles about the Olympic games of 2014 have gathered more views than those of 2018 (as they have been written roughly 4 years ago and therefor have had more time to gather views)

In this case the more relevant articles should be presented to the user before the more popular articles.

**My Potential Solution:**

I'm thinking of adding a column to the article table for memorizing the 'importance' of each article, then I can have Importance be determined by other factors

for example if I want to have the amount of views be a factor for each view importance gets a bit higher, but if the view has been within the last week it might count as 2 views. therefor favoring more actual articles slightly more over articles with more views but written a few years ago. this also allows me to for example measure the time each reader spends on an article and have that influence importance as well.

However I'm not sure if this would be the best way of doing things as there are a few problems like:

1. If importance is stored in the database it has to be updated regularly and periodically which may cause performance problems whenever the user accesses an article while the database is updating it's articles importance.
2. Calculating the importance in real time every time a user doe a search will also take a huge amount of processing power if the amount of users is very high, it will also probably cause a lot of redundancy whenever 2 users search for the same articles and the exact same importance factor is calculated twice.

How would I go about implementing this way of sorting the search results without needing lots of processing power? Is this the best way to do it? How do other search engines handle this problem?

# Answer
> 1 votes
It seems to me like 'relevance' is a qualitative abstraction. Thus you need to define your own heuristic for your service which defines what relevance is.

I think it would be best to look for solutions in third party applications such as elasticsearch instead of implementing your own.

# Answer
> 0 votes
One option would be to add a metric which weights the views by age. The older the view the less weight it has. `weight = 1 - constant * ((date(today) - date(posted)) / date(today))`

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


# Question
Title: Are all turing complete languages interchangeable
Note, while I know how to program, I'm quite a beginner at CS theory.

According to this answer

> Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do.

And any program written in any Turing complete language can be rewritten in another.

Ok. This makes sense. I can translate (compile) C into Assembly (and I do it everyday!), and can translate Assembly into C (You can write a virtual machine in C). And the same applies to any other language - you can compile any language into Assembly, and then run it in a VM written in another other language.

But can *any* program written in a Turing complete language be re-written in another?

What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

Ok. So you'll say that since we're dealing with computer *theory*, we're not discussing physical device limitations.

But what about a device that doesn't have multiplication? division? To the best of my knowledge (though this is more of a question for math.SE), one can't emulate multiplication (and definitely not division) with addition and subtraction \[1\].

So how would a "turing complete language" (which can add, subtract, and jump) emulate another language which can add, subtract, multiply and jump?

**EDIT**

\[1\]. On arbitrary real numbers.

# Answer
> 54 votes
Turing-completeness says one thing and one thing only: a model of computation is Turing-complete, if any computation that can be modeled by a Turing Machine can also be modeled by that model.

So, what are the computations a Turing Machine can model? Well, first and foremost, Alan Turing and all of his colleagues were only ever interested in functions on natural numbers. So, the Turing Machine (and the λ-calculus, the SK combinator calculus, μ-recursive functions, …) only talk about the computability of functions on natural numbers. If you are not talking about a function on natural numbers, then the concept of Turing-completeness doesn't even make sense, it is simply not applicable.

Note, however, that we can encode lots of interesting things as natural numbers. We can encode strings as natural numbers, we can encode graphs as natural numbers, we can encode booleans as natural numbers. We can encode *Turing Machines* as natural numbers, which allows us to create Turing Machines that talk about Turing Machines!

And, of course, not all functions on natural numbers are computable. A Turing Machine can only compute *some* functions on natural numbers, the λ-calculus can only compute *some* functions on natural numbers, the SK combinator calculus can only compute *some* functions on natural numbers, …. Surprisingly (or not), it turns out that *every* model of computation (that is actually realizable in our physical universe) can compute the *same* functions on natural numbers (at least for all the models we have found up till now). \[Note: obviously, there are *weaker* models of computation, but we have not yet found one that is *stronger*, except some that are obviously incompatible with our physical universe, such as models using real numbers or time travel.\]

This fact, that after a long time of searching for lots of different models, we find, every single time, that they can compute *exactly* the same functions, is the basis for the Church-Turing-Thesis, which says (roughly) that all models of computation are equally powerful, and that all of them capture the "ideal" notion of what it means to be "computable". (There is also a second, more philosophical aspect of the CTT, namely that a *human* following an algorithm can also compute exactly the same functions a TM can compute and no more.)

**However**, none of this says anything about

* how efficient the various models are
* how *convenient* they are to use
* what *else* they can do *besides* compute functions on the natural numbers

And *that* is precisely where the differences between different models of computation (and programming languages) come into play.

As an example of different performance, both a Random Access Machine and a Turing Machine can copy an array. But, a RAM needs $O(size\_{array})$ operations to do that, while a TM needs $O(size\_{array}^2)$ operations, since it needs to skip across $size\_{array}$ elements of the array for copying each element, and there are $size\_{array}$ elements to copy.

As an example for different convenience, you can just compare code written in a very high-level language, code written in assembly, and the description of a TM for solving the same problem.

And your light switch is an example of the third kind of difference, things that some models can do that are not functions on natural numbers and thus have nothing to do with Turing-completeness.

To answer your specific questions:

> But can *any* program written in a Turing complete language be re-written in another?

No. Only if the program computes a Turing-computable function on natural numbers. And even then, it might need a complex encoding. For example, λ-calculus doesn't even have natural numbers, they need to be encoded using functions (because functions is the only thing λ-calculus has).

This encoding of the input and output can be very complex, as can expressing the algorithm. So, while it is true that any program *can* be rewritten, the rewritten program may be much more complex, much larger, use much more memory, and be much slower.

> What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

A lightbulb is not a Turing-computable function on natural numbers. Really, a lightbulb is neither a function nor a computation. Switching a lightbulb on and off is an I/O side-effect. Turing Machines don't model I/O side-effects, and Turing-completess is not relevant to them.

> On arbitrary real numbers.

Turing-completeness only deals with computable functions on natural numbers, it doesn't concern itself with real numbers.

Turing-completeness is simply not very interesting when it comes to questions like yours for two reasons:

1. It is not a very high hurdle. All you need is `IF`, `GOTO`, `WHILE`, and a single integer variable (assuming the variable can hold arbitrarily large integers). Or, recursion. Lots and lots and lots of stuff is Turing-complete. The card game *Magic: The Gathering* is Turing-complete. CSS3 is Turing-complete. The `sendmail` configuration file is Turing-complete. The Intel x86 MMU is Turing-complete. The Intel x86 `MOV` instruction is Turing-complete. PowerPoint animations are Turing-complete. Excel (without scripting, only using formulas) is Turing-complete. The BGP routing protocol is Turing-complete. `sed` is Turing-complete. Apache `mod_rewrite` rules are Turing-complete. Google for "(accidentally OR surprisingly) turing complete" to find some other interesting examples. If almost everything is Turing-complete, being Turing-complete stops being an interesting property.
2. It is not actually necessary to be useful. Lots of useful stuff *isn't* Turing-complete. CSS before version 3 isn't Turing-complete (and the fact that CSS3 *is* isn't actually used by anyone). SQL before 1999 was not Turing-complete, yet, it was tremendously useful even then. The C programming language without additional libraries doesn't seem to be Turing-complete. Dependently-typed languages are, more or less by definition, not Turing-complete, yet, you can write operating systems, web servers, and games in them.

Edwin Brady, the author of Idris, uses the term "Tetris-complete" to talk about some of these aspects. Being Tetris-complete isn't rigorously defined (other than the obvious "can be used to implement Tetris"), but it encompasses stuff like being high-level enough and expressive enough that you can write a game without going insane, being able to interact with the outside world (input and output), being able to express side-effects, being able to write an event loop, being able to express reactive, asynchronous, and concurrent programming, being able to interact with the operating system, being able to interact with foreign libraries (in other words: being able to call and be called by C code) and so on. Those are much more interesting features of a general purpose programming language than Turing-completeness is.

---

You may find my answer to the question you linked interesting, which touches on some of the same points even though it answers a different question.

# Answer
> 9 votes
Of course you can implement multiplication with addition and subtraction:

```
/* Assume b is positive for simplicity */
int multiply(int a, int b) {
  int res = 0;
  while (b > 0) { res += a; b -= 1; }
  return res;
}

```

The fact that you likely wouldn't do that does not make it less possible.

Division is hardly more difficult:

```
/* Assume a and b are positive for simplicity */
int divide(int a, int b) {
  int res = 0;
  while (a >= b) { res += 1; a -= b; }
  return res;
}

```

And how do you think the multiplication and division are actually performed by the CPU's circuitry? Hint: it is not an enormous lookup table. It is more efficient than the above, since bit shifting is also used, but it is fundamentally implemented in terms of addition and subtract.

# Answer
> 6 votes
No physical (actually existing) machine is or can ever be Turing complete, because Turing completeness requires infinite storage and the universe is not infinite.

It follows from this that the affirmative answer to whether two abstract machines are equivalent doesn't help you answer the question whether two physical approximations of those machines are equivalent.

Therefore the Turing equivalence of the abstract models of (for example) two languages doesn't mean that each can compute everything the other can compute in practice. One may run up against physical limitations before the other.

# Answer
> 3 votes
You could implement multiplication and division as repeated addition and subtraction respectively, observing that $nm = n + n(m-1)$ and $m/n = 1 + (m-n)/n$.

As a matter of fact, the operations “add 1”, “subtract 1” and “conditional jump if a specified register is zero” are sufficient to make a computational model Turing-complete (see the 2-counter machine as a reference for a very minimal Turing-complete computational model).

It is also possible to implement them in a way that preserves computational complexity. First of all, observe that multiplication by $2$ is “free” ($2n = n+n$). Using multiplication by $2$, looping and subtraction we can easily implement the euclidean algorithm for the division by two. With multiplication and division by two, we can implement the russian algorithm for multiplication, observing that $m \times 2n = 2m \times n$ and $m \times (2n+1) = m + 2m \times n$. With arbitrary multiplication, we can finally implement the full euclidean algorithm for division.

# Answer
> 3 votes
***tl;dr*-** Turing machines are just a basic logical description for a general logical system's operation. They can do most of the stuff we can describe, including calling specialized opcodes and constructed mathematical operations.

---

> What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

In a Turing model, symbols like an `LIGHTBUTTON` opcode are just strings in whatever alphabet the Turing computer uses.

So, the Turing machine would be responsible for producing the string `"LIGHTBUTTON"`, or some integer value that corresponds to that opcode; whether or not an external entity acts upon it isn't the Turing computer's business.

C programs have the same limitation. This is, a C program can only call the opcode for `LIGHTBUTTON`, however whether or not the CPU actually performs an operation associated with that opcode is up to the CPU.

---

> But what about a device that doesn't have multiplication? division? To the best of my knowledge (though this is more of a question for math.SE), one can't emulate multiplication (and definitely not division) with addition and subtraction \[on arbitrary real numbers\].

Yup, a Turing machine could do those things, even on real numbers, to the extent that any human-describable logic could. The Turing machine could be as simple as a Rule 110 cellular automation.

The trick's to build up a logic system from whatever physics the machine naturally has. For example, mainstream CPU's can do multiplication and division because they have arithmetic logic unit (ALU's). But the ALU's aren't magic; they're just simple logic gates themselves. And those logic gates are made out transistors. And those transistors are made out of doped-up sand.

So, to get a Turing-complete device to do math, just gotta program it that way.

In fact, you can do real computation on Turing machines! To demonstrate this, here's WolframAlpha calculating $\pi-\pi=0$. I mean, sure, Turing machines can't infinitely expand $\pi$ in finite time, but that's okay; no one infinitely expands $\pi$, including humans. But if we credit humans with doing math with real numbers, e.g. $\pi-\pi=0$, then we have to give Turing machines credit for the same.

# Answer
> 3 votes
> But can any program written in a Turing complete language be re-written in another?

If the input to the program is an arbitrarily-long sequence of bits, and the output is also an arbitrarily-long sequence of bits, then YES. Assuming you have the time and energy to rewrite it, and that you don't care about performance, and that you have enough physical memory for both implementations.

The practical considerations that mean two Turing-complete languages are not interchangeable include:

* they support different kinds of input and output (e.g. SQL database access)
* they have different libraries of data types (e.g. support for Unicode strings)
* they provide different programming paradigms optimized for different tasks (e.g. objects, threads, coroutines, first-class functions)
* they provide different function libraries (e.g. XML parsing and serialization)

# Answer
> 1 votes
No. Turing-completeness has nothing to do with *programs*, it's about *mathematical functions* (or *algorithms*). Any algorithm - any *computation* \- you can do in C, you can do in any other Turing-complete language (this should be obvious). But Turing-completeness doesn't actually say you can do I/O - at all. It doesn't talk about the hardware at all. Just the computations.

You can extend a Turing-complete language with any hardware operation you want (technically, this is how `fputc` and `fgetc` work in C). If you take two Turing-complete languages and extend them with *identical* hardware-specific operations, then they remain interchangeable. So your assembly language with `LIGHTBULB` operation is *more powerful* than Turing-complete; you could say it's *Turing-complete over `LIGHTBULB`*. To make any other language identical to it, it also needs to be Turing-complete over `LIGHTBULB`; the easiest way to do that is to add a `LIGHTBULB` primitive / instruction / function / etc. to it.

This is why C implementations generally either support inline assembler, or document a way to call functions written in assembler, and why implementations of other languages generally provide a way to call functions written in C.

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


# Question
Title: Origins of the numerical notation for types in type theory
In several papers on type theory it's possible to see some sort of numerical notation for types based on the number of possible constructors for the type. For example, the unit type is usually written as $1$, as there's only one possible constructor for it; similarly, they use $2$ for booleans, $x + y$ for disjoint unions (sum types), $x * y$ for product types, and so on.

This kind of notation seems to be assumed familiar to the reader. Where does it come from? Are there any sources that explicitly explain this notation?

# Answer
> 5 votes
This almost certainly derives from (finite) set theory. The cardinality of a finite set $S$, written $|S|$, is the number of distinct elements it has. For finite sets, we have the following relations: $$\begin{align} |\emptyset| & = 0 \\ |1| & = 1 \\ |A\times B| & = |A||B| \\ |A\uplus B| & = |A|+|B| \\ |B^A| & = |B|^{|A|} \end{align}$$ where $A\times B$ is the Cartesian product of $A$ and $B$, $A\uplus B$ is the disjoint union of $A$ and $B$, and $B^A$ is the set of functions from $A$ to $B$. The type theoretic constructions $A\times B$ (product types), $A+B$ (sum types), and $A\to B$ (function types) correspond to these set theoretic constructs. For example, finite sets form a model of the simply typed lambda calculus with products and sums where product, sum, and function types are interpreted as exactly the constructs on finite sets above. This correspondence is not general. There are many other models of the simply typed lambda calculus that will interpret these type constructions differently. Nevertheless, this is the archetypal example.

Category theorists often use similar notation but it is motivated the same way.

Another take on this is that these type operations (ignoring function types though their existence implies distributivity) make types into a commutative semiring up to isomorphism. Equations that you can prove in the theory of commutative semirings give rise to type isomorphisms.

# Answer
> 5 votes
Although they obviously come from a much more ancient tradition (we'd need to pick apart sources from Zermelo, Russel and Wittgenstein to get to the bottom of this!), the 1972 article *An intuitionistic theory of types* by Martin-Löf already contains the notations $+$ and $\times$ for disjoint sum and Cartesian product, respectively, and have been standard ever since.

It's worth a read: https://michaelt.github.io/martin-lof/An-Intuitionisitic-Theory-of-Types-1972.pdf

I'm not sure when the notations $\mathbf{0}$, $\mathbf{1}$ and $\mathbf{2}$ became widespread. I remember seeing them in Connor McBride's articles first, but that's just anecdotal. As Derek points out, the notations are very reasonable.

---
Tags: type-theory
---


title: Perspective-Three-Point Questions

text:
# Question
Title: Perspective-Three-Point Questions
I'm following this explanation on the P3P problem and have a few questions.

1. In the heading labeled **Section 1** they project the image plane points onto a *unit sphere*. I'm not sure why they do this, is this to simulate a camera lens? I know in OpenCV, we first compute the intrinsics of the camera and factor it into `solvePnP`. Is this unit sphere serving a similar purpose?
2. Also in **Section 1**, where did $u^{'}\_x$, $u^{'}\_y$, and $u^{'}\_z$ come from, and what are they? If we are projecting onto a 2D plane then why do we need the third component? I know the standard answer is "because homogenous coordinates" but I can't seem to find an explanation as to why we use them or what they really are.
3. Also in **Section 1** what does "normalize using L2 norm" mean, and what did this step accomplish?

I'm hoping if I understand **Section 1**, I can understand the notation in the following sections.

Thanks!

# Answer
**1 & 3**. Not related to OpenCV. In this context, projecting into the unit sphere is the same as normalizing, which is making the vector's L2 norm (AKA the Euclidean norm or commonly marked as $||u||\_2$ or in short $||u||$) equal 1. This is done to simplify the term in the beginning of step two: $\cos{\alpha} = \frac{v\*u}{||u||\cdot||v||}=v\*u$

**2**. Before you divide the vector with the focal length (distance between the plane and $P$), the projected point is a point in space that is on the image plane. This point would change if the focal length changes, but what you really want here is a point that is independent of the focal point, since it shouldn't matter to the pose of the $ABC$ triangle. Dividing with the focal length here is like changing the focal length to 1.
> 2 votes

---
Tags: computer-vision
---


# Question
Title: Is "Feral Concurrency Control" a disparaging description?
The paper Feral Concurrency Control: An Empirical Investigation of Modern Application Integrity uses the term "feral" in a way I have never seen before.

> Rails has developed a range of concurrency control strategies, two of which operate external to the database, at the application level, which we term feral concurrency control mechanisms.

The paper shows that various application-level data validations are less reliable than database-level checks.

The only usage of "feral" I'd seen previously applied to untamed animals - eg, "feral cats".

Are the authors using the term disparagingly, or does "feral" mean something different in this context?

# Answer
Sorry for coming to this issue so late. For context, I am one of the coauthors of the paper. The term "feral concurrency control" in the paper was inspired by the common usage "feral database" (similarly "feral system") said by IT admin people, to refer to databases or systems that were run by staff outside the control of IT services. For example, a university department might keep a database of student information, separate from the centrally managed official student record system. See https://en.wikipedia.org/wiki/Feral\_information\_systems

The connotation is of something that has escaped from control and is acting wild (like a feral cat is a cat that is, or descends from one which, escaped from domestication and became wild)
> 8 votes

# Answer
# I think it's disparaging

Toward the end of the paper, there's a section called "Domesticating Feral Mechanisms", proposing solutions to the problems the paper describes.

So it appears that the authors do indeed picture application-level concurrency control mechanisms as animals which may be expected to poo on the carpet.
> 2 votes

---
Tags: terminology
---


# Question
Title: How to identify object(s) in image when given a list of all images?
I see a lot of articles and topics about OpenCV and machine learning in regards to identifying general things (like cats, or alphanumeric characters) but I am wondering if something more specific is easier/detailed somewhere.

Basically, if I have a folder of 20 images, how would I identify those images contained with another image? Like for a game, where you have to find all the hidden items in an image but are given a list of the items to find.

To make this even easier, let's just pick one image to find within another and also assume this image to search in won't even change the original image at all (no skewing or rotating), just put it (non-overlapping) somewhere zero or many times. If done correctly, I would imagine the results would be an array of rectangles that contain each instance of the image. Just looking for any assistance in learning how to write a program that can do this, even if its just articles/books regarding the technique. Thank you

# Answer
> 2 votes
Think of images as matrices (2D arrays) of numbers that indicate brightness. If you are looking for an exact match of an image in another, you are looking for comparing 2D integer arrays, which could be done with a double for loop that is done for each possible match location (so it is a 4 deep for loop acutaly).

A more interesting related problem is searching an image with no exact match, but with some kind of similarity instead. For that task you should read into template matching algorithms.

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


title: What does "local" mean?

text:
# Question
Title: What does "local" mean?
I study graph theory on my own using Diestel's *Graph Theory* book (with Algorithmic graph theory in mind). I don't understand what *local property*, *global property*, *locality* mean given a graph $G$.

For example, on the page 5 it says

> The average degree quantifies globally what is measured **locally** by the vertex degrees: the number of edges of $G$ per vertex. Sometimes it will be convenient to express this ratio directly, as $\varepsilon(G) := |E|/|V|$.

In particular, I found the following phrases including the word *local...*

* *local information* (pg. 46)
* *maximum local density* (pg. 61)
* *the above local structures* (pg. 101)
* *locally looks like a tree* (pg. 110)
* *there is a local reason for it* (pg. 110)
* *we are looking for local implications of global assumptions* (pg. 181).

and many more...

Could someone explain (possibly with examples) what these *local* and *global* mean in the context of the graph theory?

# Answer
**Local property** \- a property that relates to a specific vertex and its near neighbors. For example, the number of neighbors or 2nd order neighbors a vertex $v$ has. "*locally looks like a tree*" more formally could be written as the sub-graph of vertices with distance $k$ or less of the vertex $v$ is a tree.

**Global property** \- a property that relates to the graph, like its diameter, average degree, number of connected components or even its size.
> 6 votes

---
Tags: graphs, terminology
---


# Question
Title: Recursive functions from O(n) complexity to O(log n)
For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each time?

For example, take this recursive reverse\_string function ...

```
    def reverse_string1(s):
        if len(s) < 2:
             return s
        return reverse_string1(s[1:]) + s[0]

```

... compared to this function that does the same string reversal:

```
   def reverse_string2(s):
       if len(s)<2:
             return s
       mdpt = len(s)/2
       r1 = reverse_string2(s[:mdpt])
       r2 = reverse_string2(s[mdpt:])
       return r2 + r1

```

Does the latter function successfully reduce the runtime complexity from linear to logarithmic?

# Answer
> 3 votes
```
   r1 = reverse_string2(s[:mdpt])
   r2 = reverse_string2(s[mdpt:])

```

Here you go in recursion twice. In both recursions you will again recurse twice, etc, which makes $2\*2\*2... = O(2^{\log n}) = O(n)$. So the complexity is the same.

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


# Question
Title: Problem in analyzing asymptotic notation in using The Master Theorem
As we know for master theorem: T(n)=aT(n/b)+Θ(nd) this formate is required.. But for T(n)=2T(n/2)+2^n If I want to apply theorem what will be value of d here? We cant just take d=2 here..right?

# Answer
> 0 votes
The master theorem concerns recurrence relations of the form:

$T(n)=aT(n/b)+\color{red}{f(n)}$ this formate is required, where $a\geqslant 1, b\>1$

This fits for case 3 of the theorem:

$f(n)=\Theta(n^c)$ where $c\>\log \_2 2=1$ can you procced from here?

---
Tags: master-theorem
---