# Question
Title: Segmenting an English string with no spaces using dynamic programming
Suppose you have a function `quality(x)` that returns the quality of a sequence of letters `x`. Given a string such as "howareyoutoday," what is the most efficient way to determine that the segmentation is "how are you today" (i.e. quality(how)+quality(are)+quality(you)+quality(today) is the maximum quality possible)?

I was thinking that we could have something like the following:

```
A[0] = h, A[1] = o, ..., A[n] = y
Q[0] = quality(A[0]), Q[1] = quality(A[0]A[1]), ..., Q[n] = quality(A[0]...A[n])

```

Now to determine the segmentation, we find max{Q\[0\], .., Q\[n\]} which will return some Q\[i\] (the first space is after this). Then, we find max{Q\[i+1\], .. Q\[n\]} which returns another Q\[i\] (second space is after this), etc. until max returns Q\[n\].

I have some questions though: is this method even correct, and does it use dynamic programming? It seems to me that it does, since we build the initial Q with subproblems to the original problem. Also, is this an optimal solution? To my understanding, the worst case would be O(n^2), which would be when max returns Q\[0\], then Q\[1\], then Q\[2\], etc.

# Answer
I'm assuming your quality function measures something similar to the likelihood of the string being a word. The problem with your algorithm is that it makes a hard decision about where the first space should go before considering where the other spaces go. If you make a suboptimal decision for where the first space goes it will mess you up later on.

The dynamic programming algorithm for this problem is called the Viterbi algorithm. https://en.wikipedia.org/wiki/Viterbi\_algorithm You have to keep a table of the highest quality segmentations seen so far as you process the string from left to right. When the algorithm finishes you will be left with a ranked list of the highest quality segmentations.
> 2 votes

# Answer
No that doesn't work, without harsh qualifications on 'that' or 'work'. What if the presence vs. absence of space after a letter represents a binary encoding of some hard problem into the string, where quality(x) returns 1 if your segmentation is a solution to the hard problem and 0 if it is not a solution.
> 0 votes

---
Tags: algorithms, dynamic-programming, strings
---


# Question
Title: NP-hard proof with reduction from two known NP-hard problems
As I understand, to show that a certain problem P is NP-hard we can reduce a known NP-hard problem, Q, to problem in P in polynomial time. To show that the problem P is NP-hard in strong sense, we can reduce a know NP-hard problem Q to problem P in pseudo polynomial time. Is it possible to show that a certain problem P is NP-hard by reducing two known NP-hard problems Q and Q' to a problem in P?

# Answer
> 3 votes
If you can reduce one **NP**-hard problem to a problem $L$, then $L$ is **NP**-hard. If you can reduce a second **NP**-hard problem to $L$, then so what? You already know that $L$ is **NP**-hard. How could reducing *more* problems to $L$ make $L$ easier (e.g., not **NP**-hard)?

It's like saying, "If I have one million dollars, I'm rich. If I have two million dollars, am I still rich?"

# Answer
> -1 votes
A few definitions: a pseudo-polynomial problem is a problem which is polynomial on some parameter but that parameter itself makes the problem NP-complete. For example, unary subset sum is polynomial but the problem size is exponential.

If a problem that is NP-hard can be reduced to a polynomial problem in polynomial time, it would mean that the problem has polynomial complexity P.

To reduce a problem to an NP-hard problem by a polynomial time reduction means that the problem is NP hard.

The Cook-Levin theorem shows that all NP problems can be reduced in polynomial time to a problem in NP-complete.

So there is no guarantee that an NP-hard problem can be reduced to an NP-hard problem, but it may.

---
Tags: complexity-theory, reductions, np-hard
---


title: Possible valid and invalid codewords

text:
# Question
Title: Possible valid and invalid codewords
I have already read different things about hamming distance, hamming code, detection and correction of memory errors, but I am still not understanding many things.

I know that the hamming distance between 2 codewords is the number of bits to be reversed to convert one codeword into the other.

I know that the hamming code is the set of all possible codewords. The codewords are composed of data bits and control bits, hence the number of bits in a codeword is `n = m + r`, where `m` is the number of data bits and `r` is the number of check bits. And the number of possible codewords with `n` bits should be $2^n$.

One thing I am not understanding is what are these **valid** and invalid **codewords** and how to 'calculate' them? Why a codeword is valid and invalid? What is the connection with the **parity bits**? How to find an invalid codeword?

I'm sorry if I am asking many things together, but I am really not understanding exactly the concepts I cited above.

# Answer
> 1 votes
There's no such thing as a "valid" or "invalid" codeword. If a string of bits is a codeword in a particular code such as a Hamming code, it's "valid"; if it's not a codeword, it's "invalid".

---
Tags: memory-hardware
---


# Question
Title: Extracting maximum information from a set of exam answers and their scores
Imagine we have a multiple-choice exam with N questions. Suppose we have a set of K answer sheets to the exam and their total scores (1 for a correct answer on a question, 0 for incorrect).

How much information can we extract from this set about the true answers to the exam, and what is the shape of the space of possible answers after extracting this information? (e.g., is it convex in some sense? is it a linear subspace? or something like that)

E.g. if we have at least one answer sheet with a score of N, then we know all the correct answers. If we have an answer sheet with a score of 0, then we can exclude at least one answer from each question. \[If we have two different answer sheets both with a score of N-1, we know the correct answers to all questions in which they agree\] - (on further thought, this is actually incorrect..). Etc.

What's this problem called? Is it solvable in polynomial time? (looks like it's reducible to integer programming)

# Answer
> 2 votes
## Hardness

Recovering the correct answers to the exam is NP-hard. I'll show how to reduce one-in-three 3SAT to it.

Suppose we have a 3CNF formula $\varphi$ on $N$ variables $x\_1,\dots,x\_N$. The $i$th question on the exam is "Is $x\_i$ true?" There is one answer sheet per clause of $\varphi$. If $\varphi$ contains a clause mentioning variables $x\_i,x\_j,x\_k$, say $x\_i \lor \neg x\_j \lor x\_k$, then there's a corresponding answer sheet that has answered "Yes" to question $i$, "No" to question $j$, "Yes" to question $k$, and left all other questions blank, and this answer sheet received a score of exactly 1.

Now if you can extract the correct answer to all of the questions, then you can extract a satisfying assignment for the corresponding one-in-three 3-SAT problem -- a task that is NP-hard.

Therefore, you should not expect to find any efficient algorithm for your task (i.e., to extract the correct answers, given the scores on the answer sheets), at least in the worst case.

That's the bad news. Now for the good news:

## Algorithms

In practice, a good way to approach your problem might be to throw a SAT solver or ILP solver at it. This sounds like the kind of problem that they might be effective at, in practice, if $N$ is not too large. Your problem can be readily formulated as an instance of integer linear programming (ILP), or indeed as an instance of SAT.

---
Tags: complexity-theory, data-mining, constraint-programming
---


title: Computing the mode of XOR subsequences

text:
# Question
Title: Computing the mode of XOR subsequences
I was confronted with this problem in an online programming challenge and it has been bugging me since:

In the problem, you are given a list of 16-bit numbers, say $a\_0, a\_1, ..., a\_n$. An "XOR subsequence" is defined as the exclusive-or combination of every element in a consecutive subsequence of the list. The problem is that you must find the most commonly occurring XOR subsequence out of every possible consecutive subsequence in the list. In the event of a tie, the lowest numeric XOR value out of the most frequently occurring ones wins.

The first solution I came up with was an $O(n^2)$ solution where I compute the XOR for consecutive subsequences $a\_0,...,a\_i$ from $i=0$ to $i=n$, which can be done in $O(n)$, and doing the same thing starting at $a\_1$, etc, and incrementing a counter in a map for every result. I know this repeats a lot of work, so I tackled the problem from a different angle and tried to define it mathematically. I defined $X\_{i,j}$ to be the XOR of $a\_i,...,a\_j$ so that I could write the following:

$X\_{i,j} = \begin{cases} a\_i & \text{if } i = j \\ a\_j \oplus X\_{0, j-1} & \text{if } i = 0 \text{ and } j \> 0 \\ X\_{0,i-1} \oplus X\_{0,j} & \text{if } 0 \< i \< j \end{cases} $

I implemented that with memoization, which I believe eliminates all redundant calculations, but using memoization turns out to be slow and use $O(n^2)$ space when attempting to calculate all $X\_{i,j}$ for $0 \leq i \leq n $ and $i \leq j \leq n$, which is unacceptable.

Is there any way I can make this any faster than $O(n^2)$? Or if not, is there any efficient way to reduce the number of computations? Or am I missing some simplification to the problem that doesn't require me to compute every $X\_{i,j}$? I'm sort of new to dynamic programming, so it's been hard to wrap my brain around this problem. My original solution was too slow by a factor of about 5 seconds (vs the time limit of 4 seconds for the challenge), so I believe even a constant factor reduction in time would make the solution acceptable.

# Answer
> 4 votes
Yes, this can be solved much more efficiently. You can solve this problem in $O(b 2^b)$ time using a FFT, if each number is a $b$-bit number. In the comments, you said $b=16$, so this should be an efficient solution: something like $2^{21}$ steps of computation.

Consider the sequence $b\_{-1},b\_0,b\_1,\dots,b\_n$ defined by $b\_{-1}=0$ and $b\_i = a\_0 \oplus a\_1 \oplus \dots \oplus a\_i$. Now your problem is equivalent to asking for the value that appears most frequently, out of all of the values $b\_i \oplus b\_j$ with $i\<j$.

Let $x \in \mathbb{N}^{2^b}$ be the characteristic vector of $b\_{-1},b\_0,\dots,b\_n$. In other words, $x\_v$ is equal to the number of times that $v$ appears in the values $b\_{-1},b\_0,\dots,b\_n$; or, equivalently, $x\_v = \\#\\{i : -1 \le i \le n, b\_i = v\\}$.

Let $y \in \mathbb{N}^{2^b}$ be the characteristic vector of $\\{b\_i \oplus b\_j : i\<j\\}$. In other words, $y\_v$ is equal to the number of times that $v$ appears in the values $b\_i \oplus b\_j$; or, equivalently, $y\_v = \\#\\{(i,j) : -1 \le i \< j \le n, b\_i \oplus b\_j = v\\}$.

We see that $y = x * x$, i.e., $y$ is the convolution of $x$ with itself:

$$y\_v = \sum\_u x\_u x\_{u \oplus v}.$$

This convolution can be computed using a discrete Fourier transform on the group $(\mathbb{Z}/2\mathbb{Z})^b$. We find

$$y = \mathcal{F}^{-1}(\mathcal{F}(x)^2),$$

where here $\mathcal{F}$ is the Fourier transform and $\mathcal{F}^{-1}$ is the inverse Fourier transform.

Moreover, there is a fast Fourier transform (FFT) for this group. The FFT can be computed in $O(N \lg N)$ time, on sequences of length $N$. Here $N=2^b$, since the characteristic vector has length $2^b$, so the running time to compute $\mathcal{F}$ and $\mathcal{F}^{-1}$ is $O(b 2^b)$.

Once you have the characteristic vector $y$, you just look for the index $i$ such that $y\_i$ is maximized. This is the desired output value.

All in all, this gives an algorithm with $O(b 2^b)$ running time. This is probably much better than your $O(n^2)$ algorithm, for your particular parameters, but implementing it takes considerably more sophistication (you have to know how to implement a non-standard FFT, for a particular finite group).

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


# Question
Title: Stable marriage problem with only one side having preferences
I was wondering about a variation on the Stable Marriage Problem. Initially, we have two sets of entities, usually males and females, and they have preference lists ranking the other group, and through a series of proposals, we end up with a stable matching.

Thinking of it like medical schools and applicants, each medical school has a different number of slots available, so is there an intuitive or simple augmentation to the basic algorithm that solves this case?

The second question is, what if only one side has a preference ranking? For example, say medical students have preferences, but the schools do not, and simply have some number of spaces available (different between each school). All (or many of) the students (say 50 students) prefer school A, but it only has 5 slots or so. Is it possible to determine if there is a "matching" that allows everyone to get a choice in their top 3 or top 5 or something along those lines?

Clearly, if schools A, B, C have only 5 slots each, and 10 students rank the schools 1. A, 2. B, 3. C it is not possible for everyone to have their top 3. There are 30 "wants" and only 15 available slots. What I am interested in is determining if it possible and if possible, finding one of those matchings.

If this question makes no sense I can try to elaborate the specific use case it came up in.

# Answer
The answer to your first question is: yes, there is a simple augmentation. It is described in the standard literature on the stable marriage problem. See the Wikipedia article for references in the literature where this is described. It is also described here: The stable marriage algorithm with asymmetric arrays. See also https://cs.stackexchange.com/a/28528/755.

Your second question is an instance of the assignment problem. We form a bipartite graph, with an edge between a doctor $d$ and a school $s$ if the school $s$ is among $d$'s top 3 choices. Then we want to know whether there is a perfect matching in this graph. (If a school has multiple slots, then make multiple copies, one copy per slot.) There are polynomial-time algorithms to determine whether a bipartite graph has a perfect matching. See also Existence of bipartite perfect matching.

So, the answer to your second question is: yes, it is possible.
> 5 votes

---
Tags: algorithms, bipartite-matching, matching, assignment-problem
---


title: Proving that $2^n$ does not divide $n!$

text:
# Question
Title: Proving that $2^n$ does not divide $n!$
How can prove that $2^n \nmid n!$ using binary representation for $n!$ and $2^n$.

# Answer
> 0 votes
I was working in counting *how many trailing zeros has $n!$ in base-2*, it'll be $d$. Because, trailing zeros means that you can divide $n!$ by 2, $d$ times.

$$ n! = \underbrace{\****1\overbrace{0000\cdots 000}^{d\text{ zeros}}}\_{\lfloor \log n!\rfloor + 1 \ \text{ digits}}\ \ \Rightarrow \\, 2^{d}\\, \vert\\, n!\ \ \ \ \text{ with \*}\in \\{0,1\\}$$

So, If $T(n)$ counts trailing zeros for $n!$.

$$ T(0) = 1\ \ \ T(1) = 0 \ \ \ T(n) = \lfloor n/2 \rfloor + T(\lfloor n/2 \rfloor)$$

Or it could be $$ T(n) = \sum \_{i=1}^{\log n} \left \lfloor \frac{n }{2^i} \right \rfloor$$

So, there is a counterexample, consider it, $n=2^k$

$$ \begin{align} T(n) &= \sum \_{i=1}^{\log n} \left \lfloor \frac{2^k}{2^i} \right \rfloor =\sum \_{i=1}^{k} 2^{k-i} = \sum \_{i=1}^{k} 2^{k-i} = 2^k \left ( \sum \_{i=1}^{k} 2^{-i} \right )\\ & = 2^k \left( \frac{(1/2)-(1/2)^{k+1}}{1 - (1/2)} \right) = \frac{2^{k-1} - 1/2}{1/2} = 2^k -1 \end{align} $$

then $2^{k} - 1\ \vert\ n!$, and for that $2^{n} \not\vert\ n!$.

# Answer
> 5 votes
Idea: Count explicitly how many factors $2$ the numbers in $\[1..n\]$ contribute to $n!$.

Observe that every other number adds one (the even numbers), every fourth adds another (those divisible by four), every eighth another, and so on. Hence, the number $\\#\_2(n!)$ of factors $2$ in $n!$ fulfills

$\qquad\displaystyle\begin{align\*} \\#\_2(n!) &\leq \sum\_{i=1}^{\log\_2(n)} \frac{n}{2^i} \\ &= n \cdot \sum\_{i=1}^{\log\_2(n)} \frac{1}{2^i} \\ &= n \cdot \frac{n-1}{n} \\ &= n-1 \\;. \end{align\*}$

Therefore, $2^n$ can not be a divisor of $n!$.

---
Tags: discrete-mathematics, number-theory
---


# Question
Title: Is there a way to predict rendering times?
In purpose of load balancing I need to approximatively predict rendering time my graphics software (in the specific case it's Autodesk Maya) needs to render a task given an input file (*.ma/*.mb) and rendering parameters.

1. An intuitive way to do it is to render several frames from different parts of a scene and to extrapolate the results. Is there a better way to do it?
2. If no, is it enough to render several separated frames or I should take short series of frames in different moments of the scene?

# Answer
> 0 votes
You can predict it using Machine Larning / Data Mining algorithms, provided you have prior knowledge of the data. In your case,you should know the rendering time from previous experiments.

You can use any predition models. Some of them like bayesian models gives high accuracy prediction,but are computationally complex. Statistical models are very fast,but the provide less accurate results. You can use decision tree based models for a balanced performance. CART algorithms is a good one. Use any datamining tools like weka,Rstudio or rapidminer to make the job easy.

---
Tags: heuristics, graphics
---


title: Longest "bounded" subsequence

text:
# Question
Title: Longest "bounded" subsequence
Given a sequence of comparable objects $a\_1, a\_2, \ldots a\_n,$ how quickly can we find the longest subsequence $s$ such that $s\_i \> s\_1$ for $i \> 1$? Or equivalently, how quickly can we find

$$ \underset{i}{\arg\max} \\; \\# \\{j \mid a\_j \> a\_i, i \< j \le n \\} $$

Can it be done in less than $\Omega(n\\,\lg n)$ comparisons in the worst case?

A $\Theta(n\\,\lg n)$ algorithm is to scan from right to left, inserting each element into a balanced tree, keeping track of how many elements in the tree are larger.

This was inspired by this thread on reddit.

# Answer
No, $\Omega(n\log n)$ comparisons are required. Let $k = \Theta(n)$ be an integer parameter and consider the following family of inputs.

$$k+1,\\:k+2,\\:k,\\:k+2,\\:k-1,\\:k+2,\\:\ldots,\\:2,\\:k+2,\\:1,\\:k+2,\\:x\_1,\\:x\_2,\\:\ldots,\\:x\_k$$

Note that, for $a\in\\{1,\\:2,\\:\ldots,\\:k+1\\}$, the maximum bounded subsequence beginning with $a$ consists of $a$, then $a$ copies of $k+2$, then a subsequence of $x\_1,x\_2,\ldots,x\_k$. It is not profitable to begin anywhere else, since the maximum bounded subsequence beginning with $k+1$ has length at least $k+2$.

Let the adversary in this lower bound choose a random permutation $\pi$ on $\\{1,2,\ldots,k\\}$ and answer as though $x\_j=\pi(j)+1/2$. This setting ensures that every maximum bounded subsequence beginning with $a\in\\{1,\\:2,\\:\ldots,\\:k-1\\}$ has length exactly $k+2$. By the following argument, however, the algorithm cannot be sure of this fact unless it sorts $x\_1,x\_2,\ldots,x\_k$.

Suppose that the algorithm cannot infer the order of $x\_i$ and $x\_j$. Without loss of generality, assume that $i=\pi^{-1}(\pi(j)-1)$, so that $x\_i$ immediately precedes $x\_j$ in the imagined sorted order of $x\_1,x\_2,\ldots,x\_k$. It is consistent with the algorithm's observations that

$$x\_\ell=\begin{cases}\pi(j)+1/2&\text{if }\ell=i\\\pi(\ell)+1/2&\text{if }\ell\ne i,\end{cases}$$

which would give rise to a bounded subsequence of length $k+3\>k+2$.
> 2 votes

---
Tags: algorithms, subsequences
---


# Question
Title: Decidability of a language of Turing Machine descriptions
Given the language

> $\\{ \<M\> \mid\\:$ M is a Turing machine and there is some w ∈ Σ\* for which the computation M(w) takes more than 10 transitions$\\}$

How can one prove that this language is decidable?

# Answer
Given a Turing Machine M (with its finite number of tape symbols, finite number of states, etc...), how hard is it to prove that there is an input on which it will run for more than 10 steps? How much of the input will be read in 10 steps at most? How many different computations have to be checked to see whether one takes more than 10 steps?

**added later**: I was editing this when the reference to question Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable? was given as comment.
> 1 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: Algorithm to determine whether a given graph is a caterpillar tree
I am looking for an algorithm with time complexity in $\mathcal O(|V|)$ that determines whether a given graph $G=(V,E)$ is a caterpillar tree.

A caterpillar tree is a tree that has a path to which all nodes are connected by a maximum of one edge. So for every vertex v there is a vertex u on the path so that the disctance between v und u is at most 1. In other words, removing all the leaves results in a simple path.

The only progress I've made so far is that I could use breadth-first search or depth-first search to traverse the graph. They have a complexity of $\mathcal O(|V|+|E|)$, but in a caterpillar tree, $|E|=|V|-1$, so I end up in $\mathcal O(2|V|)$ = $\mathcal O(|V|)$.

Is that idea correct? If so, then how can I modify BFS/DFS to do what I want? I am thinking of adding a branch depth counter of some sort and allowing only one branch with length \>1 (the central path of the caterpillar), but I have no idea how to implement that without changing the original algorithm too much.

# Answer
> 5 votes
When considering such recognition algorithms, it is sometimes helpful to consider equivalent characterizations of the graph in question. Your observations and ideas are valid.

In other words, we can first prove that caterpillars are such trees that when you delete all the leaves and incident edges, you are left with a path graph. This immediately suggest a simple linear time algorithm: check that your input graph is a tree, remove all the leaves, and check that you have a path.

In fact, I suggest you divide your problem into 3 subtasks you can work on independently:

1. Implement a function that outputs YES/NO based on whether the input graph is a tree.
2. Implement a function that removes all the leaves and the edges incident to them from the input graph.
3. Implement a function that outputs YES/NO based on whether the input graph is a path.

---
Tags: algorithms, trees, graph-traversal
---


# Question
Title: Do data structures help to reduce complexity of operations, at the cost of something else?
I often heard that using data structures help to reduce (time or space) complexity of some operations.

1. I wonder if that is achieved at the cost of something else?
2. When solving a problem, is something still conserved, over all choices of data structures and algorithms, just like the conservation of energy? Such as some kind of overall (time or space) complexity of an algorithms and a data structure being used?

# Answer
> 4 votes
To represent a collection of integers, you can use an array with one word of memory per element. For instance, say $A = \[0,1,7,10\]$. Alternatively, you could use an array $B$ to represent the same collection in the obvious way: $B = \[1,1,0,0,0,0,0,1,0,0,1\]$. Searching for element $x$ in $A$ takes $\Theta(n)$ time (or perhaps just logarithmic time if $A$ is indeed sorted), but you can do the same in $B$ in $O(1)$ time by just looking at $B\[x\]$, i.e. just indexing $B$ at position $x$. This is a tradeoff: by using more memory for $B$, you get faster lookups. Time-memory tradeoffs like this are often encountered.

Sometimes, one can show that to solve a problem, you *must always no matter what* spend some time, memory, or other resource to solve it. In such results, one must *always* specify the model of computation used. For instance, there is a well-known decision tree lower bound of $\Omega(n \log n)$ for sorting. So in this model, you absolutely can't beat this bound no matter what you do.

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


# Question
Title: Prerequisites of computational complexity theory
what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical background and good book suggestions for each topic ... thanks

# Answer
> 6 votes
Here are some prerequisites:

1. Mathematical maturity. You get this by taking math courses.
2. Mathematical induction. Important.
3. Rudimentary calculus. That also includes all you need to know about big O notation, which you can learn as part of your study of algorithms and complexity. Calculus is mainly used for estimating sums and in general asymptotic analysis.
4. Rudimentary linear algebra. Not relevant for everything, but common enough.
5. Basic discrete probability theory (linearity of expectation, Markov's and Chebyshev's inequalities, Bernoulli random variable, binomial distribution, indicator variables). Very helpful. Part of it (Chernoff's bound) you will learn as part of your study.
6. Basic graph theory. Most people probably don't actually have any background in graph theory to begin with, and learn whatever they need as part of their algorithms course.

Since calculus and linear algebra are common enough, what is probably most challenging is discrete probability theory. There are many textbooks covering this, and probably all of them are fine. Whatever you don't learn ahead of time you will pick up in your algorithms and complexity classes.

On the other hand, it is important to be proficient in induction and arithmetic manipulations, and to have some basic level of mathematical maturity. The only way to achieve this is to gather experience in doing basic proof-based math.

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


# Question
Title: How much money do you need to pay for pilots and their assistants?
I am new in writing recursive algorithm so I tried this problem from SPOJ but I could not formulate the recursive relation from where I can find the optimal solution. Can anyone help me to see the optimal solution of the problem below please.

> There are N pilots working for his company (N is even) and N/2 plane crews needs to be made. A plane crew consists of two pilots - a captain and his assistant. A captain must be older than his assistant. Each pilot has a contract granting him two possible salaries - one as a captain and the other as an assistant. A captain's salary is larger than assistant's for the same pilot. However, it is possible that an assistant has larger salary than his captain. Write a program that will compute the minimal amount of money Charlie needs to give for the pilots' salaries if he decides to spend some time to make the optimal (i.e. the cheapest) arrangement of pilots in crews.
>
> **Input**
>
> The first line of input contains integer N, 2 ≤ N ≤ 10,000, N is even, the number of pilots working for the Charlie's company. The next N lines of input contain pilots' salaries. The lines are sorted by pilot's age, the salaries of the youngest pilot are given the first. Each of those N lines contains two integers separated by a space character, X i Y, 1 ≤ Y \< X ≤ 100,000, a salary as a captain (X) and a salary as an assistant (Y).
>
> **Output**
>
> The first and only line of output should contain the minimal amount of money Charlie needs to give for the pilots' salaries.

Like

4

Person:1 Captain Salary =5 Assistant Salary=3

Person:2 Captain Salary =6 Assistant Salary=2

Person:3 Captain Salary =8 Assistant Salary=1

Person:4 Captain Salary =9 Assistant Salary=6

Here Ans would be 19.

we have to say Min how much money we have to pay to select 2 crews where all the N pilots are part of as Pilot or Assistant.

Can someone help me to solve in Polynomial Time please

# Answer
This is an instance of the assignment problem. There are polynomial-time algorithms for the assignment problem, as described on Wikipedia. Put another way, your job is to find a minimum weight perfect matching in a bipartite graph. There are polynomial-time algorithms for that.
> 5 votes

---
Tags: algorithms, recursion
---


title: Confusion in "mask bits"

text:
# Question
Title: Confusion in "mask bits"
This is the question:

> By definition of the IEEE754 standard, 32-bit floating point numbers are represented as follows:
>
> S (1 bit) E (8 bits) M (23 bits) S: Sign bit E: Exponent M: Mantissa
>
> Which of the following is the correct “mask bits” in hexadecimal to be used for extracting only the exponent part of the above format?
> Here, “mask bits” means a bit pattern which is logically ANDed withthe 32-bit floating point value.
>
> a) 107FFFFF b) 7F800000 c) FF100000 d) FF800000

The given answer is b : 7F800000, but i have no idea why, can anyone give me an explanation, i'm greatly appreciated!

Is that because :

7F800000 = 0**111 1111 1**000 (8)

While others answer contain more `"1"` in binary format?

# Answer
> 2 votes
When you bitwise `AND` a number in this format with `7F800000` you get:

```
    SEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM
AND 01111111100000000000000000000000

  = 0EEEEEEEE00000000000000000000000

```

Everything gets set to `0` except the exponent. Yes, it is necessary for the correct answer to have 8 ones, but it is also necessary that they are in the correct positions. `00007F80` would not be correct because it would result in:

```
    SEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM
AND 00000000000000000111111110000000

  = 00000000000000000MMMMMMMM0000000

```

---
Tags: encoding-scheme, number-formats
---


# Question
Title: Why does this pumping lemma application "prove" that 0*1* is not regular?
Here is a proof that $0^\*1^\*$ is not regular, even though it is regular. I'm having a hard time figuring out what is wrong with the proof.

Assume $0^\*1^\*$ is regular. Let $p$ be the pumping length as defined by the pumping lemma. Let $s = 0^{p-1}11$, then $|s| \ge p$ and $s \in 0^\*1^\*$. According to the pumping lemma, we can split $s$ into three parts $s = xyz$ such that $|y|\>0$, $|xy| \le p$, and $xy^iz \in 0^\*1^\*$ for $i \ge 0$. Let $x = \varepsilon$, $y = 0^{p-1}1$, and $z = 1$. Clearly, $|xy| \le p$ and $|y|\>0$. However, $xy^2z = 0^{p-1}10^{p-1}11$ is not a member of $0^\*1^\*$. This is a contradiction to the pumping lemma, therefore $0^\*1^\*$ is not regular.

We know $0^\*1^\*$ is regular, building a NFA for it is easy. What is wrong with this proof?

# Answer
> 6 votes
The idea is that there is some partition that fulfills the condition of the pumping lemma - you do not have the choice of the x, y, and z - you have to show that there exists no x, y, and z that satisfies the conditions.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Identity in the category of types and functions
In the model of (functional) programming languages as a category where the objects are types and the arrows are functions, I'm trying to really understand what's really the identity arrow.

Barr-Wells "Category Theory for CS" says you need the id function, but I wonder: it really has to be the "do nothing" function? For any type A, doesn't any function f:A-\>A work? If looking at type level, I can't distinguish the functions, shouldn't be ok?

I'm trying to find a counter-example but couldn't.

EDIT: I was thinking on the Hask category but I guess my question in Category Theory terms is: Does every endomorphism in an object A is isomorphic to the identity arrow in A?

# Answer
> 1 votes
It has to satisfy the properties of the identity arrow - i.e. its left and right composition with any other arrow is that arrow.

Of course, you can have multiple different categories where the objects are types (for some definition of "types" - it's actually really complicated, if not impossible, once you start looking at polymorphic or dependent types) and arrows are something somehow related to functions between them. What exactly you choose to call "arrow" is up to you, as long as it satisfies the required properties (composition and identity).

A trivial example, you can say that "let us define that the (sole) arrow between type $A$ and type $B$ represents the family of all functions between $A$ and $B$" - in this category the sole arrow $A \to A$ will happen to also be the identity arrow. I suppose this is what you mean under "looking at type level".

Or you can say: For a given family of equivalence relations $Eq\_T$ on every type $T$, let us define that there is one arrow between type $A$ and type $B$ for every function $A \to B$, modulo the function equivalence relation "maps $Eq\_A$ to $Eq\_B$". Then if you take the usual equality relation on integers and consider the arrows $int \to int$, in this category you'll only have one identity arrow - the function that maps a number to itself. The function $x \to x+1$ will not work.

---
Tags: category-theory
---


# Question
Title: Which addresses belong to which network, given a fixed subnet mask?
> The subnet mask for a particular network is 255.255.31.0.
> Which of the following IP address belongs to this network?
>
> 1. 172.57.88,62 & 172.56.87.233
> 2. 10.35.28.2 & 10.35.29.4
> 3. 191.203.31.87 & 191.234.31.88
> 4. 128.8.129.43 & 128.8.161.55

Little bit confuse about 3rd octet of SM ( i.e **.31** ) But got the point that 5 bit was hired from 3rd octet for subnetting.

**The principle** : convert the dotted-quad IP addresses and mask to 32-bit unsigned integers and AND each address with the mask. If the results are the same, they're in the same subnet.

By using above principle Ans is D.
***But Can I do it directly ?***
Means

1. By looking at SM it is clear that , it belongs to class B.
2. Option A and C are 2 different networks.( there 2nd octet is different i.e. **172.57** and **172.56** and **191.203** and **191.234** )
3. Option B is Class A network.( so cant be the answer)
4. Option D is class B network , and its 1st two octet are also same i.e. **128.8** and **128.8** so now no problem to apply above principle to final check.

Can I think like this before applying principle ? ( just to save time )

# Answer
> 0 votes
No. You can't use your shortcut method.

Your rules #2 and #4 are fine, but rules #1 and #3 are not valid. For example, it's possible (and common) to have a local network 10.0.0.x where the subnet mask is 255.255.255.0. Suppose the IP address of a local host is 10.0.0.7. Your rule #3 would suggest that it can't be a match, because 10.x.y.z belongs to a class A network, whereas the subnet mask looks like the mask for a class C. However, that rule leads you to the wrong conclusion. In fact, you can have a network 10.0.0.x with subnet mask 255.255.255.0. It's possible to take a large network (a class A network) and divide it into multiple smaller local area networks, each with a separate subset of the address space of the large network.

---
Tags: computer-networks
---


# Question
Title: Satisfiability of first-order logic is undecidable?
I struggle with understanding why the satisfiability in the first-order logic is undecidable. Could you explain it with some examples? I've also seen that satisfiability in some first-order formulas are decidable.

Please explain it with as much as many examples.

# Answer
The fact that first-order logic (with some non-triviality constraints) is undecidable means that no algorithm can decide correctly whether a given first-order formula is true or not. However, for any single statement $\varphi$ it is easy to come up with an algorithm that decides $\varphi$ correctly (just hard-code the answer). So it is impossible to give examples of "undecidable statements", since there is no such thing.

What is possible is to give a restricted set of sentences whose truth value is already undecidable. In effect, this is what the proof of undecidability does. The proof shows that you can encode the statement "the Turing machine $T$ halts on empty input" in first-order logic (again, given some mild non-triviality constraints), so this infinite sequence of statement is already undecidable, that is, no algorithm can correctly decide whether such a formula is true or not.
> 7 votes

---
Tags: computability, undecidability, satisfiability, first-order-logic
---


# Question
Title: What do f(x) and g(x) represent in Big O notation?
I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) \in O(g(x))$. Obviously $f(x)$ is the running time of the given algorithm we are comparing against infinity, but what does $g(x)$ represent?

# Answer
***Summary**: $f$ and $g$ are typically functions, and $f$ is typically the runtime and $g$ is typically the asymptotic complexity of $f$. But if any of this is unclear from the description, I think it is best to either find another explanation, or to forget about application domains and intuitions for a second and go back to the definitions.*

---

They're both functions. The fact that they are named "f" and "g" is probably due to the usual naming convention of functions, just like "x", "y" and "z" are usual names given to variables.

In this context, $f(x)$ is often the runtime of the algorithm under question, while $g(x)$ is used to denote the asymptotic complexity of $f(x)$; so $f(x) \in O(g(n))$ (or, $f(x) = O(g(n))$). But, convention or not, what $f$ and $g$ are, and they're relation to each other (if any), should be clear and unambiguous from the explanation. Not something that the reader has to *guess* based on what it *usually* means. (And the reader should have the mathematical maturity that is necessary to understand the concept.)

Personally, when I am confused about terms and names that are being used, I like to try to forget everything that the terms and names are *ultimately* used to represent. In computer programming, big-o is often used to describe algorithms. But big-o notation itself abstracts such things away; it is only about functions and their relation to each other. Forget about "runtime", "complexity" or anything else that has to do with the intended application of the notation.

Here is an example:

> Let $f$ and $g$ be two functions defined on some subset of the real numbers. One writes
>
> $f(x) = O(g(x))$ as $x \to \infty$,
>
> if and only if there is a positive constant $M$ such that for all sufficiently large values of $x$, $f(x)$ is at most $M$ multiplied by the absolute value of $g(x)$. That is, $f(x) = O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x\_0$ such that
>
> $|f(x)| \leq M \cdot |g(x)|$ for all $x \geq x\_0$.

We see that $f$ and $g$ are functions. Together with all the variables used, and the relations between them, what $f(x) = O(g(x))$ means is as clear as you might reasonably expect from a Wikipedia article on a mathematical topic. We don't have to consider what this notation is supposed to be used for, and neither what those functions are even supposed to represent/model. Now, going back to the application domain of algorithm analysis; can we use this notation to describe algorithms? Yes, since runtimes of algorithms are just functions on real numbers. Then what does it mean when $f(x) = O(g(x))$, in the context of algorithm analysis? If $f(x)$ is the runtime of the algorithm, then this notation means that $f(x)$ (a runtime) does not grow more quickly than a multiple of $g(x)$, for sufficiently large $x$. That's all from reading from the definition, and interpreting $f(x)$ as a runtime.

## Pitfalls of *convention*

Sometimes, conventions can be misleading. In fact, we've seen a "violation" of a usual mathematical convention in this post.

$f(x) = O(g(n))$

Here, the $=$ sign is used. At least for us non-mathematicians, we are used to this sign denoting a sort of *equality* between two things. This usually means that the two things are of the same *type*, e.g. they are both real numbers, and that they are *equal* in some sense. In particular, $=$ is often an *equivalence relation*. But *this is not the case of this particular use of the $=$ sign*. First of all, $f(x) = O(g(n))$ does *not* mean that $f(x)$ and $g(x)$ are equal: the closest "normal" relation to this is "$f(x)$ is less than or equal to $g(x)$", which obviously has nothing to do with equality (except as a special case). Secondly, $f(x)$ and $O(g(x))$ are not even of the same type: $f(x)$ is a function, while $O(g(x))$ is a class of functions. (An alternative notation to $f(x) = O(g(x))$ is $f(x) \in O(g(x))$, which I used in the beginning. It is arguably more "honest".)
> 12 votes

# Answer
A statement like "$f \in O(g)$" types and binds the identifiers $f$ and $g$ *by the definition* of $O$. So you really have to look at the definition of $O$, e.g. here. You'll see that both the argument of $O$ and its elements (since $O(.)$ is a set) are *functions*.

Once you agree that this makes sense, it does no longer matter¹ whether you write $f \in O(g)$, $u \in O(a)$ or $\mathrm{Jack} \in O(\mathrm{Martha})$. Using $f$, $g$ and $h$ for "generic" functions is a convention carried over from mathematics; in CS you also find $T$ in the context of algorithm analysis (representing a runtime function).

For more reading on Landau notation, I recommend our reference questions and the many posts tagged we have around.

---

1. Granted, disregarding conventions tends to confuse people.
> 4 votes

# Answer
$f(x)$ and $g(x)$ are functions. $f$ typically models the time an algorithm takes to work on an input of size $x$. When we say $f(x) = O(g(x))$, what we mean is approximately "the time taken by the algorithm to work on an input of size $x$ grows no more quickly than a multiple of $g(x)$ for sufficiently large $x$."
> 2 votes

---
Tags: terminology, landau-notation
---


# Question
Title: Find point with smallest average distance to a set of given points
Someone recently shared with me the following problem (which I guess appeared in some kind of past coding contest):

> Given $n$ points $P\_i=(x\_i,y\_i)$ in the 2-dimensional plane, find the point $Q=(x,y)$ that minimizes the average distance from $P\_i$ to $Q$.

In other words, we want to find $Q$ that minimizes the objective function $f(Q) = \sum\_i d(P\_i,Q)$. Here $d(\cdot,\cdot)$ represents the usual Euclidean (L2) distance. I'm told that in the coding contest this was phrased in terms of finding the best location to put a washroom somewhere in an office building, so that the average distance to all employees is minimized.

Is there an elementary solution to this problem? In other words, a polynomial-time algorithm that does not require knowledge of advanced methods (say, beyond what undergraduate computer science majors could be expected to understand).

---

If we were on the 1D real line rather than the 2D plane, this problem would be easy. In one dimension, the solution is exactly the median of $x\_1,\dots,x\_n$. However, this does not seem to generalize to the 2-dimensional plane. It's tempting to take $x$ to be the median of $x\_1,\dots,x\_n$ and $y$ to be the median of $y\_1,\dots,y\_n$, but this does not provide the optimal solution: a counterexample is to look at three points at three of the corners of a square. (The component-wise median is at a corner, but the optimal location is somewhere inside the square.)

It looks like this problem is a special case of the two-dimensional Euclidean $p$-median problem, for $p=1$. Apparently the two-dimensional Euclidean $p$-median problem is NP-hard when $p$ is part of the input (Megiddo and Supowit, SIAM J Computing 13(1) Feb 1984) -- but here we have the special case where $p=1$, so the NP-hardness result doesn't apply to this special case. I haven't been able to use this search phrase to help find an algorithm.

If the distance metric was the Manhattan (L1) distance, there would be a number of clean solutions. The component-wise median would be optimal, since the Manhattan metric is linearly separable in the $x$-coordinates and $y$-coordinates. For similar reasons, we could solve it using linear programming. However, here we have the Euclidean distance, which is not linearly separable, so those methods do not seem to apply.

See also Find the point with minimum max distance to any point in a set, which looks at a related but different problem, the smallest-circle problem, where the objective function is $g(Q) = \max\_i d(P\_i,Q)$. However, the techniques used for that problem don't seem to apply here.

Right now the approach I can see is a heuristic algorithm: use standard black-box optimization methods such as hill-climbing or gradient ascent to find the point $Q$. However, there is no guarantee that this finds the exact optimum.

If there's a solution that does not require understanding advanced computational geometry algorithms (e.g., Voronoi diagrams, Delaunay triangulation, etc.), even better!

# Answer
This point is known as the geometric median, also known as the 1-median.

Apparently, there is no simple algorithm for computing the geometric median. Instead, one must use some kind of numerical approximation. Wikipedia mentions Weiszfeld's algorithm, which appears to be a kind of iterative descent algorithm, and cites other more sophisticated algorithms.

This is a special case of the Weber problem, a facility location problem. Standard solvers for facilitation location problems be able to compute the geometric median for you, by framing this as an instance of the Weber problem.
> 7 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Data structure to insert, update and sort indexes by frequency and query an index for a particular cumulative frequency
Here is the description of the data structure I am looking for:

Initial Original Data

```
Index | Frequency |
  1         3
  2         1
  3         7
  4         2
  5         6

```

Now it should be kept **Sort**-ed by their frequency inside the data structure like this,

```
Index | Frequency | Cumulative Frequency |
  2         1               1
  4         2               3
  1         3               6
  5         6               12
  3         7               19

```

Now, if I **Insert** a new entry item (index 6) with frequency of 2, the data structure should maintain it like this:

```
Index | Frequency | Cumulative Frequency |
  2         1               1
  4         2               3
->6         2               5
  1         3               8
  5         6               14
  3         7               21

```

Now, a frequency increase of 3 at Index 2 should **Update** the structure as following:

```
  Index | Frequency | Cumulative Frequency |
| ~~2           1               1~~
|   4           2               2
|   6           2               4
|   1           3               7
|-> 2        1+3 = 4            11
    5           6               17
    3           7               24

```

You can see above that the frequencies can repeat in many indices. (see index 4 and 6 above).

Now my **Query** to find the index that contains a cumulative frequency should be resulted in the following way

```
Query(cumulative frequency) | Result (Index at the data structure)
            3                       6
            1                       4
            20                      3
            7                       1

```

I have already explored Fenwick Tree (Binary Indexed Tree). It has a very efficient, O(log(n)), way to insert and update frequency at an index and to find the index for a specfic cumulative frequency. But I did not find a way to keep the Indexes sorted by their frequency.

Other structures like Treap, Red-Black tree can store the frequency in a sorted way but I could not find a way to search the index with the specific cumulative frequency using those data structures.

# Answer
> 2 votes
This can be easily handled using a standard balanced tree data structure, augmented with a Fenwick tree and a hashmap:

* Store the items in a binary tree. Each leaf stores information about a single item. The leaves should be stored in increasing frequency, i.e., sorted by frequency, from least frequent to most frequent.
* To help compute the cumulative frequency, augment the binary tree to store some additional information in each node. In each node, store the sum of the frequencies of all of the items underneath it (i.e., of all of the leaves under that node). These values can be easily updated as the tree changes. This is basically the idea behind Fenwick trees for computing prefix sums.
* Also, add a hashmap that maps from the value (what you call "index") to the associated leaf where that index is found in the binary tree.

Now you can support all of the operations you mentioned efficiently. If you use a standard balanced binary tree data structure, the running time for all operations is $O(\log n)$:

* Sort: All of the items are already stored in sorted order, sorted by increasing frequency, so this happens automatically.
* Insert: You can insert a new item into the tree in $O(\log n)$ time.
* Update: You can increase the frequency of a particular item by deleting it from the tree, increasing its frequency, and inserting it into the new location. In a balanced binary tree, this takes $O(\log n)$ time, since deletion can be done in $O(\log n)$ time, as can insertion.
* Query: You can now find the first index $i$ where the sum of the frequencies of the first $i$ leaves is at least $t$, by using binary search. Note that you can efficiently compute prefix sums of the frequencies by using the extra values stored in each node of the tree. Therefore, binary search suffices, and can be done in $O(\log n)$ time.

There are many balanced binary tree data structures, including red-black trees, AVL trees, 2-3 trees, etc. They all have the property that standard operations are guaranteed to take at most $O(\log n)$ time. You can use any of them for your purposes.

# Answer
> 0 votes
There's 3 sub-problems here:

1. Maintain a list of items sorted by frequency
2. Locate an item at a given value of cumulative frequency
3. Locate an item at a given index

Problem 3 can be solved by adding a hash table to the rest of the answer.

Problems 1 and 2 can be addressed at the same time by using a data structure like the Finger tree or rope (see my answer in another thread) - they are both basically strings with efficient concatenation and splitting, with the twist that you can split at a point where a given monotonic predicate ("measure") becomes true, rather than simply at an index. See Monoids and Finger trees, as well as the rope article, for a discussion of this process.

Then you can use a pair of measures (maximum, sum). Problem 1 is solved by locating the insertion point as the point where maximum-so-far becomes greater than the item being inserted. Problem 2 is the same but for sum-so-far.

---
Tags: data-structures, dictionaries
---


title: solving a number theoretical problem

text:
# Question
Title: solving a number theoretical problem
In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), highest common factor (hcf), or greatest common measure (gcm), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

Given an integer N. Now Find how many GCD(A,B)=B Where 1≤A≤B≤N For example,for N=3 the result will be 5.It can be found in the following way.

GCD(1,1)=1 OK

GCD(1,2)=1

GCD(1,3)=1

GCD(2,1)=1 OK

GCD(2,2)=2 OK

GCD(2,3)=2

GCD(3,1)=1 OK

GCD(3,2)=1

GCD(3,3)=3 OK

Here we get 5 combination where GCD(A,B)=B But how can I calculate it for 1≤N≤10^9 efficiently?

# Answer
Hint: $\mathrm{gcd}(a,b) = b$ iff $b|a$. Since you're only looking for pairs in which $a \leq b$, this forces $a = b$.
> 5 votes

# Answer
You could try using Stein's method, which is especially efficient on binary computers:

$$\gcd(0,v) = v$$ $$\gcd(2u,2v) = 2 \gcd(u,v)$$ $$\gcd(2u+1,2v) = \gcd(2u+1,v)$$ $$\gcd(2u,2v+1) = \gcd(u,2v+1)$$ $$\gcd(2u+1,2v+1) = \gcd(u-v,2v+1)$$

That is:

$$\hbox{gcdcheck}(0,v) = \hbox{true}$$ $$\hbox{gcdcheck}(2u,2v) = \hbox{false}$$ $$\hbox{gcdcheck}(2u+1,2v) = \hbox{false}$$ $$\hbox{gcdcheck}(2u,2v+1) = \hbox{gcdcheck}(u,2v+1)$$ $$\hbox{gcdcheck}(2u+1,2v+1) = \hbox{gcdcheck}(u-v,2v+1)$$

Now implement this using dynamic programming. Use the fact that only the (odd,odd) cases need to be stored.
> 1 votes

# Answer
Looking at your worked out example, I believe that where you said `1≤A≤B≤N` you meant `1≤B≤A≤N`. And then your gcd equation only happens if `B` divides `A`.

If that is true, then your equation is equivalent to the following. How many pairs `(B, A)` are there with both less than or equal to `N` such that `A = B * C` for some `C`?

And now we can break into three cases. The cases are:

1. `B < C`
2. `B = C`
3. `C < B`

The number in case 2 is the floor of `sqrt(N)`.

The number in cases 1 and 3 are the same.

The only hard part that is left is counting the number in case 1. And for that we can just run through the possible values of `B` up to `sqrt(N)`, for each one adding `floor(N/B) - B`.

In the case of `N = 3` the calculation then becomes `floor(sqrt(3)) + 2 * ( floor(3/1) - 1) ) = 1 + 2 * (3 - 1) = 5`.

This is not very informative, so let's do the case of `N = 10`. Then the calculation becomes

```
floor(sqrt(10)) + 2 * ((floor(10/1) - 1) + (floor(10/2) - 2) + (floor(10/3) - 3))
  = 3 + 2 * ((10 - 1) + (5 - 2) + (3 - 3))
  = 3 + 2 * (9 + 3 + 0)
  = 27

```

This equation requires `O(sqrt(N))` terms. So for `N` around a billion you'll need to do tens of thousands of operations, which is not hard on current computers.
> 1 votes

---
Tags: algorithms
---


title: Show that 6n^2 + 12n is O(n^2)

text:
# Question
Title: Show that 6n^2 + 12n is O(n^2)
I understand how I would do this if the problem were as such

$8n + 5$ is $O(n)$

$c\>0$ and an integer constant $n(not 0) \geq 1$ such that $8n + 5 \leq cn$ for every integer $n \geq n(not 0)$

we could let $c= 13$ and $n(not 0) = 1$

or we could let $c = 9$ and $n( not 0) = 5$.

I'm just not sure how to go about $6n^2 +12n$

# Answer
> 2 votes
Let $f(n)=6n^2 + 12n$

The $O$ notation for $f(n)$ can be derived from the following simplification rules:

1. If $f(n)$ is a sum of several terms, we keep only the one with largest growth rate.
2. If $f(n)$ is a product of several factors, any constant is omitted.

From rule 1, $f(n)$ is a sum of two terms, the one with largest growth rate is the one with the largest exponent as a function of $n$, that is: $6n^2$

From rule 2, $6$ is a constant in $6n^2$ because it does not depend on $n$, so it is omitted.

Then: $f(n)$ is $O(n^2)$

---
Tags: algorithms, asymptotics, landau-notation
---


# Question
Title: Finding paths of certain length in trees
In a graph tree, is there any "smart/existing/efficient" algorithm to find linear segments of defined length?

For example given a tree graph:

```
g = {1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, 6 -> 12, 1 -> 3, 2 -> 5, 3 -> 7,
   4 -> 9};
TreePlot[g, VertexLabeling -> True]

```

How can one find all linear segments of length 4. In this example this would be

```
1 2 4 8
1 2 4 9
1 3 6 12
2 1 3 7
2 1 3 6
9 4 2 5
...

```

This is probably a common problem, but I guess I have not yet found the right keywords for google. The naive implementation would be to visit every node, then recursively try to get four nodes away and delete all duplicated segments at the end...

# Answer
> 3 votes
*Idea:* Root the tree in an arbitrary node. For every node, count

* paths in its subtrees,
* paths that start in a subtree and end in the root, and
* paths that start in one subtree, traverse the root and end in another subtree.

That is, for a given node $v$ with children $u\_1, \dots, u\_m$, the number $p(v,k)$ of paths of length $k$ (counting nodes) in the subtree $T\_v$ rooted in $v$ is

$\qquad\displaystyle\begin{align\*} p(v,k) &= \sum\_{i=1}^m \biggl\[ p(u\_i,k) \biggr\] \\ &\ + \sum\_{i=1}^m \biggl\[ p\_r(u\_i,k-1) \biggr\] \\ &\ + \sum\_{i=1}^{m-1} \sum\_{j=i+1}^m \sum\_{l=1}^{k-2} \biggl\[ p(u\_i,l) \cdot p(u\_j,k-1-l) \biggr\] \end{align\*}$

for $k \geq 2$; we anchor the recurrence in $p(v,1) = 1$ for all $v$. For the paths ending in the root, we get the (simpler) recurrence

$\qquad\begin{align\*} p\_r(v,k) &= \sum\_{i=1}^m p\_r(u\_i,k-1) \end{align\*}$

which also anchors in $p\_r(v,1) = 1$.

These recurrences immediately imply a recursive algorithm (computing both simultaneously).

The runtime is in "$\Theta(m^2k)$" per node of degree $m$; hence, on trees with finitely bounded degree, the algorithm runs in time $\Theta(nk)$. Otherwise, it may take time $\Theta(n^2k)$ (e.g. on stars).

# Answer
> 2 votes
Any linear segment goes up for some length, then goes down. (Once you start going down, you can't go back up again, because you'd re-visit a vertex you'd already visited).

So, any linear segment of length four consists of an upwards-heading segment of length $\ell$ (where $0 \le \ell \le 4$), followed by a downwards-heading segment of length $4-\ell$. Therefore, the following algorithm works:

* For each vertex $v$ in the tree:

+ For each $\ell \in \\{0,1,2,3,4\\}$:

    - For each upwards-heading segment $s$ of length $\ell$ that has $v$ as its top vertex:

        * For each upwards-heading segment $t$ of length $4-\ell$ that has $v$ as its top vertex:

            + Output the concatenation of $s$ and $t$ (i.e., the reverse of $s$, followed by $t$).

To make this work, we need some way to enumerate all upwards-heading segments of length $\ell$ that end at a vertex $v$. This can be done by enumerating all children that are $\ell$ levels below $v$; for each such child $c$, we can go upwards $\ell$ times (following parent pointers), and that gives such a segment. Moreover, every such segment can be obtained in this way.

The overall running time will be $O(n^2)$, where $n$ is the number of vertices in your tree.

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


title: What does "schema" mean?

text:
# Question
Title: What does "schema" mean?
1. In a relational model,

* a schema is something which specifies the name and data type of each field.
    * The word "schema" is also used in "conceptual schema", "physical schema" and "external schema".

What do "schema" mean separately in the above two cases? Are they related?

Are they related to the "schema" in cognitive psychology?
2. Is "schema" used in other areas of computer science, such as artificial intelligence, programming languages, ...?
3. What does "schema" mean in computer science besides database?

Thanks!

# Answer
> 5 votes
**1. \**What is Schema\****\- In a relational database, the schema defines the tables, the fields in each table, and the relationships between fields and tables.

Yes, They are related to these 3 words, **"conceptual schema"**, **"physical schema"** and **"external schema"**.

* External schema for **user views**
* Conceptual schema **integrates external schemata**
* Internal schema that defines **physical storage structures**

**No, It has no relation with "schema" in cognitive psychology**

**2. Yes**, Schema used in other area also like in-

**Programming & Algorithms** -XML Schema , Schema (genetic algorithms)
**Science**\- Body Schema, Image Schema
**Mathematics**\- Axiom Schema (related to Mathematical Logic)

**3.** Refer above point 1 & 2

---
Tags: terminology
---


# Question
Title: Finding context free grammar for this language?
I needed help finding the context free grammar of this string

$$ 10^{n}10^{n}1 $$

So far an idea I have is $$ S\rightarrow 1S1S1\mid 0S \mid \varepsilon $$

Any assistance you can provide would be greatly appreciated!

# Answer
When looking for CFGs for an expression like yours, it is often handy to **work from the inside out**, especially whan you need to match symbols. Think of your expression as $1(0^n10^n)1$. The interior part, within the parentheses, consists of a $1$ surrounded by an equal number of zeros on each side. We could generate this by the production $T\rightarrow 0T0$, since repeated use of this production would result in derivations like $$ T\Rightarrow 0T0\Rightarrow 00T00\Rightarrow 000T000 $$ and so on. In other words, we could have $T\stackrel{\*}{\Rightarrow} 0^nT0^n$, where the star over the arrow means "eventually results in". Now all you have to do is get the $1$ in the middle. That's easy: just add the production $T\rightarrow 1$. In sum, you can get the part in parentheses by the productions $$ T\rightarrow 0T0\mid 1 $$ Now that you have the middle part, just add the external $1$s to a start variable production $S\rightarrow 1T1$, giving the full grammar $$\begin{align} S&\rightarrow 1T1\\ T&\rightarrow 0T0\mid 1 \end{align}$$

Your attempt was a good start, since you did generate the correct number of $1$s, but there was no guarantee that the two $S$ variables in $S\rightarrow1S1S1$ would generate the matching $0$s you need.
> 3 votes

# Answer
*This answer was inspired by Rick Decker's answer*. I thought he made an interesting remark about working inside out, and I tried to replace it in a more general understanding of context-freeness.

Context-free grammars are often (actually always) elaborate ways of writing ornate strings of well nested parentheses, possibly of different shapes (see Chomsky-Schutzenberger second theorem). One problem is usually to see the parentheses hidden behing the ornaments. In your case, it is pretty easy, because even though the opening and closing parentheses hide behind the same ornament $0$, they betray themselves because it is specified that the two sequences of zeros have the same length, like a sequence of opening parentheses followed by a sequence of closing ones.

Hence, it becomes quite natural to try to generate these as parentheses.

Now, if you are asked to generate $(^nw)^n$, where $w$ is any string, it is quite natural to write the rule $X\to (X)\mid w$. Then all you have to do is replace the parentheses by $0$, both opening and closing parentheses, an to replace $w$ by $1$ (that is called a homomorphism in the Chomsky-Schutzenberger theorem). This gives you $X\to 0X0\mid 1$.

I leave the rest to you.

On Raphael's suggestion, for **more techniques to build a CF grammar**, see this page which also describes in more detail the Chomsky-Schutzenberger theorem
> 3 votes

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


title: High Dimensional Data Structures

text:
# Question
Title: High Dimensional Data Structures
I have a 20-dimensional dataset, with a large amount of data points. I would like to have each dimension discretized into bins. Per bin, I would like to be able to access two neighbours per dimension (i.e. +1 and -1 per dimension). Basically I want to be able to easily access 2\*d (where d is the dimensionality) neighbours. For lower dimensions, this would be quite easy to do using a multidimensional array (i.e. for point `data[0][1][2]` I would access its neighbours `data[0][1][3]` and `data[0][1][1]` for the third dimension). However, when this approach is scaled up to higher dimensions, memory becomes an issue.

What kind of data structures would be suitable to use, where the most important criterium is the quick and easy access to its +1 and -1 neighbours?

# Answer
> 2 votes
I would suggest you to use a hierarchical K-means, or a hierarchical vocabulary tree approach. For example:

http://gecco.org.chemie.uni-frankfurt.de/hkmeans/H-k-means.pdf http://www.vlfeat.org/overview/hikm.html

CVPR Paper with application: http://www.vis.uky.edu/~stewe/publications/nister\_stewenius\_cvpr2006.pdf

FLANN also has some kind of hierarchical capabilities.

# Answer
> 2 votes
You can compress sparse multi-dimensional array by using a hash table. Calculate hash key for the required coordinates and use that as O(1) look-up to the cells in the array. If the cell is empty it doesn't exist in the hash table. This is trivial to implement with `std::unordered_map` if you use C++.

# Answer
> 0 votes
Use a quantization scheme, but **not** vector quantization as this will quantize a feature vector as a whole and you mention in the question, you need a quantization per vector coordinate (i.e per dimension)

The thresholds you will use for quantization will affectthe classification or clustering or whatever scope this is used for

For example you can try to cluster the data in each separate dimension coordinate and then this will provide the quantization and the neighbors (for this coordinate)

Possibly an implementation detail is that you would need to keep track of the feature vector index (or id or a unique identifier) in order to be able to mix the data back into feature vectors and still maintain the per-coordinate clustering

# Answer
> 0 votes
I would suggest you k-d Tree for High Dimensions Data, best use of this data structure in Nearest Neighbor Searching.

---
Tags: data-structures, big-data
---


title: Are DCFLs closed under reversal?

text:
# Question
Title: Are DCFLs closed under reversal?
According to this chart, DCFLs are closed under reversal.

However, I am not convinced as the intuitive proof (reversing the arrows of the controlling finite state machine and switching the pushes and pops) for this seems to depend on non-determinism in choosing the null transition to take from the initial state (since the new initial state would contain a null transition to all the old final states).

This would make the "reverse PDA" of a DPDA non-deterministic whenever there is more than a single final state in the original DPDA.

What is the fallacy in my argument? Or is there another way to go about proving this?

# Answer
I looked up Hopcroft and Ullman 1979 and it say on page 281 that it is not closed under reversal. But I found no proof in my very fast look at the relevant chapter.

Searching the web does also give a negative answer, with counter example, on stackoverflow by a member of CS (notation adapted):

> $(a+b+c)^\*WcW^R$, where $W \in (a+b)^+$; this is non-deterministic because you don't know where the $WcW$ bit starts.
>
> $W^RcW(a+b+c)^\*$, where $W \in (a+b)^+$; this is deterministic because you can write a deterministic PDA to accept simple palindromes of the form $W^RcW$ and modify the accepting state to loop to itself on any of $a$, $b$ and $c$.
>
> The trick here is that PDAs have to read input from left to right.
> 10 votes

---
Tags: formal-languages, context-free, closure-properties, pushdown-automata, nondeterminism
---


# Question
Title: Proving NP hardness of maximum sum of means of a partition into k sets
I am trying to show the following problem is NP-hard and would like some help.

> *Inputs:* Integer $k$, and unordered set of $N$ numbers, $O$
>
> *Output:* the $\max \sum\limits\_{S\_i \in S} \operatorname{mean}(S\_i)$
>
> where $S=\\{S\_1,S\_2,...,S\_k\\}$, $O=S\_1 \cup S\_2 \cup \dots \cup S\_k$ and elements of $S$ are disjoint.

In simpler terms, partition $O$ into $k$ sets to maximize the total sum of the means of the sets.

This problem is a special case of a graph partition problem I am trying to prove NP-hard. I suspect even this special case that removes the graph structure is NP-hard and might be easier to prove. I have tried to reduce from the partition problem (minimize difference of sum of 2 sets).

# Answer
Put each of the $k-1$ greatest numbers in their own set, and the remaining numbers all together in the $k$th set. This linear-time algorithm can be proved correct by using the following (non-strictly) improving moves to reach the specified optimal solution from any other.

1. Given two numbers $a\<b$ with $a\in S\_i$ and $b\in S\_j$ and $\lvert S\_i\rvert\le\lvert S\_j\rvert$, swap $a$ and $b$.
2. Given $S\_i,S\_j$ where $|S\_i|\ne 1$ and where all of the numbers in $S\_i$ are greater than or equal to all of the numbers in $S\_j$, move the smallest number in $S\_i$ to $S\_j$. (This move does not decrease the average of $S\_i$, and does not decrease the average of $S\_j$.)

An alternative correctness proof uses a linear relaxation. Let the numbers be $a\_1\ge\cdots\ge a\_n$ and consider the following linear program.

\begin{align} &\text{maximize }\sum\_{i=1}^na\_ix\_i\\ &\text{subject to}\\ &\sum\_{i=1}^nx\_i=k&(w)\\ &\forall i\in\\{1,\ldots,n\\},\quad-x\_i\le\frac{-1}{n-(k-1)}&(y\_i)\\ &\forall i\in\\{1,\ldots,n\\},\quad x\_i\le1&(z\_i) \end{align}

Given a partition, for all $i\in\\{1,\ldots,n\\}$, we can set $x\_i=1/\lvert S\_j\rvert$, where $a\_i\in S\_j$. It follows that this program is in fact a relaxation. The proposed partition sets $x\_1,\ldots,x\_{k-1}=1$ and $x\_k,\ldots,x\_n=1/(n-(k-1))$.

Here is the dual program. By weak duality, feasible solutions of this program upperbound the objective value of the primal.

\begin{align} &\text{minimize }kw+\sum\_{i=1}^n\left(\frac{-y\_i}{n-(k-1)}+z\_i\right)\\ &\text{subject to}\\ &\forall i\in\\{1,\ldots,n\\},\quad w-y\_i+z\_i=a\_i&(x\_i)\\ &\forall i\in\\{1,\ldots,n\\},\quad y\_i,z\_i\ge0\\ \end{align}

Here is a feasible solution to the dual program whose objective value is equal to the previously proposed primal solution. It follows that both solutions are optimal.

\begin{align} w&=a\_k\\ y\_i&=\begin{cases}a\_k-a\_i&\text{if }i\in\\{k,\ldots,n\\}\\0&\text{otherwise}\end{cases}\\ z\_i&=\begin{cases}a\_i-a\_k&\text{if }i\in\\{1,\\:\ldots,\\:k-1\\}\\0&\text{otherwise}\end{cases} \end{align}
> 6 votes

---
Tags: complexity-theory, np-hard, set-cover
---


# Question
Title: What algorithms solve the minimun multidimensional multidemand 0-1 knapsack problem?
I've found an heuristic algorithm\[scatter search\] that solves the common version of MDMKP(MultiDemand Multidimensional Knapsack Problem)\[the one that maximizes\] but what about the minimize version? is there any algorithm for that kind of problem? is it possible to obtain the solution to the minimum MDMKP from the maximum MDMKP? Here's the maximum MDMKP formally expressed:

# Answer
Negate the coefficients (the $c\_j$'s) and adjusting the other coefficients correspondingly.

In particular, replace $c\_j$ with $-c\_j$. Note that $\sum -c\_j x\_j$ is maximized whenever $\sum c\_j x\_j$ is minimized. Then, you can apply a change of variables to get the new linear inequalities (try $x\_j=1-y\_j$).
> 0 votes

---
Tags: optimization, combinatorics
---


# Question
Title: Is Horowitz and Sahni's data structure book outdated?
I found that Fundamentals of data structures (1982) by Ellis Horowitz and Sartaj Sahni draws my attention naturally, probably because of

* their formal treatment of data structures, and
* their choice of topics and
* their way of organizing the topics into chapters and sections.

But the book was published in early 1980's. I wonder if the topics and the treatment in the book are outdated?

It doesn't seem to have later editions, but only some derivations for specific programming languages.

p.s.: What would you recommend? Thanks.

---

A view of its table of content:

```
Preface
CONTENTS
CHAPTER 1 INTRODUCTION
1.1 Overview
1.2 SPARKS
1.3 How to Create Programs
1.4 How to Analyze Programs
References and Selected Readings
Exercises
CHAPTER 2 ARRAYS
2.1 Axiomatization
2.2 Ordered Lists
2.3 Sparse Matrices
2.4 Representation of Arrays
Exercises
CHAPTER 3 STACKS AND QUEUES
3.1 Fundamentals
3.2 A Mazing Problem
3.3 Evaluation of Expressions
3.4 Multiple Stacks and Queues
Exercises
CHAPTER 4 LINKED LISTS
4.1 Singly Linked Lists
4.2 Linked Stacks and Queues
4.3 The Storage Pool
4.4 Polynomial Addition
4.5 More on Linked Lists
4.6 Equivalence Relations
4.7 Sparse Matrices
4.8 Doubly Linked Lists and Dynamic Storage Management
4.9 Generalized Lists
4.10 Garbage Collection and Compaction
4.11 STRINGS - Case Study
4.11.1 Data Representations for STRINGS
4.11.2 Pattern Matching in STRINGS
4.12 Implementing Node Structures
References and Selected Readings
Exercises
CHAPTER 5 TREES
5.1 Basic Terminology
5.2 Binary Trees
5.3 Binary Tree Representations
5.4 Binary Tree Traversal
5.5 More on Binary Trees
5.6 Threaded Binary Trees
5.7 Binary Tree Representation of Trees
5.8 Applications of Trees
5.8.1 Set Representation
5.8.2 Decision Trees
5.8.3 Game Trees
5.9 Counting Binary Trees
References and Selected Readings
Exercises
CHAPTER 6 GRAPHS
6.1 Terminology and Representations
6.1.1 Introduction
6.1.2 Definitions and Terminology
6.1.3 Graph Representations
6.2 Traversals, Connected Components and Spanning Trees . . .
6.3 Shortest Paths and Transitive Closure
6.4 Activity Networks, Topological Sort and Critical Paths . ...
6.5 Enumerating All Paths
References and Selected Readings
Exercises
CHAPTER 7 INTERNAL SORTING
7.1 Searching
7.2 Insertion Sort
7.3 Quicksort
7.4 How Fast Can We Sort?
7.5 2-Way Merge Sort
7.6 Heap Sort
7.7 Sorting on Several Keys
7.8 Practical Considerations for Internal Sorting
References and Selected Readings
Exercises
CHAPTER 8 EXTERNAL SORTING
8.1 Storage Devices
8.1.1 Magnetic Tapes
8.1.2 Disk Storage
8.2 Sorting With Disks
8.2.1 K-Way Merging
8.2.2 Buffer Handling for Parallel Operation
8.2.3 Run Generation
8.3 Sorting with Tapes
8.3.1 Balanced Merge Sorts
8.3.2 Polyphase Merge
8.3.3 Sorting with Fewer Than 3 Tapes
References and Selected Readings
Exercises
CHAPTER 9 SYMBOL TABLES
9.1 Static Tree Tables
9.2 Dynamic Tree Tables
9.3 Hash Tables
9.3.1 Hashing Functions
9.3.2 Overflow Handling
9.3.3 Theoretical Evaluation of Overflow Techniques
References and Selected Readings
Exercises
CHAPTER 10 FILES
10.1 Files, Queries and Sequential Organizations
10.2 Index Techniques
10.2.1 Cylinder-Surface Indexing
10.2.2 Hashed Indexes
10.2.3 Tree Indexing -Trees
10.2.4 Trie Indexing
10.3 File Organizations
10.3.1 Sequential Organizations
10.3.2 Random Organizations
10.3.3 Linked Organization
10.3.4 Inverted Files
10.3.5 Cellular Partitions
10.4 Storage Management
References and Selected Readings
Exercises
APPENDIX A: SPARKS
APPENDIX B: ETHICAL CODE IN INFORMATION PROCESSING
APPENDIX C: ALGORITHM INDEX BY CHAPTER .
INDEX 562

```

# Answer
> 5 votes
## Yes.

I strongly recommend Pat Morin's more modern textbook *Open Data Structures*, available for free in several dialects at http://opendatastructures.org/.

# Answer
> 1 votes
There was a second edition of this book published in 2007 — ISBN 0929306406. So yes, the edition you have is outdated.

---
Tags: data-structures, books
---


# Question
Title: Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states
Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept.

I understand that the pumping lemma can be used to show that if a language has a length greater than the number of states, which is the pumping length, then it may not be a regular language. However, I don't understand how a language can be rejected by a DFA based on the number of accept states it has.

For example, I know that `a* \cup b*` is not a regular language because of the pumping lemma, but how do I know that it is not accepted by a DFA with only 1 accept state?

# Answer
$\\{\lambda, a, a^2, \dots, a^n\\}$. All states in which these words are accepted must be different, in order to avoid loops (and stay finite).
> 10 votes

# Answer
Yes, there is a simple generalization of the Myhill-Nerode theorem that provides the characterization you seem to be looking for.

Let $\sim$ be the equivalence relation defined by the Myhill-Nerode theorem, i.e., $x \sim y$ if there is no suffix $z$ such that exactly one of $xz,yz$ are in $L$. Let $S$ denote the set of equivalence classes of $\sim$, i.e., $S = \\{\[x\] : x \in \Sigma^\*\\}$, where $\[x\] = \\{y \in \Sigma^\* : x \sim y\\}$. The Myhill-Nerode theorem tells us that any DFA for $L$ must have at least $|S|$ states. We can think of $S$ as the statespace of the minimal DFA that accepts $L$.

Now define $A$ to be the set of equivalence classes that contain at least one element of $L$, i.e., $A= \\{\[x\] : x \in L\\}$. Note that $A \subseteq S$. Also, we can think of $A$ as the set of accepting states for the minimal DFA that accepts $L$. In particular, any DFA that accepts $L$ must have at least $|A|$ accept states: consider any DFA $M$ that accepts $L$; then there is a function mapping the statespace of $M$ to $S$, and mapping the set of accepting states to $A$. (See the proof of the Myhill-Nerode theorem for the construction of this function.)

Therefore, $|A|=|\\{\[x\] : x \in L\\}|$ provides a lower bound on the number of accepting states of any DFA that accepts $L$, in terms of a property of $L$. If you find a language $L$ where $|A|\>n$, then you know that there is no DFA that has $\le n$ accepting states and that accepts $L$.
> 5 votes

---
Tags: formal-languages, regular-languages, finite-automata, regular-expressions, pumping-lemma
---


# Question
Title: are the activations of hidden nodes in an ANN binary or real valued?
this may seem to be a pretty basic question, but it is something i have been puzzling over for some time.

when calculating the activations of nodes in a hidden layer in an ANN using sigmoid neurons for use with the backpropagation algorithm - should the output of the neuron be thresholded or not?

say the activation vector for layer $i$ is calculated by:

$\mathbf{a}\_i = \sigma(\mathbf{w}\_i\mathbf{a}\_{i-1} + \mathbf{b}\_i)$

where $\sigma$ is the sigmoid activation function

should it actually be:

$\mathbf{a}\_i = (\sigma(\mathbf{w}\_i\mathbf{a}\_{i-1} + \mathbf{b}\_i) \> 0.5$)

to ensure that $\mathbf{a}\_i$ is binary vector? or should the real value from $\sigma$ be passed on to the next layer?

my main reason for asking this is that biological neurons don't transmit real valued data, but i haven't really been able to find any definitive answer anywhere to this question or anyone who explicitly says to threshold the value; it seems like a pretty fundamental question to the functioning of ANNs, so either i am missing something in my reading, or it is considered so common-sense that it doesn't need to be mentioned much.

any help would be greatly appreciated

# Answer
> 2 votes
When you do thresholding your activation function becomes a step function. The problem with that is that step functions are not differentiable, so you would not be able to do basic gradient descent to learn the parameters. You can see the sigmoid as a continuous approximation of a step function.

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


# Question
Title: Proving that shortest path distance of adjacent nodes can't differ by more than one
Could someone explain this proof to the following question?

> Lemma 22.1 from intro to algorithms
>
> Let $G=(V,E)$ be a directed or undirected graph, and let $s\in V$ be any vertex. Then, for any edge $(u,v)\in E$,
>
> $$\mathrm{dist}(s,v)\leq \mathrm{dist}(s,u)+1\\,.$$ *Proof.* If $u$ is reachable from $s$, then so is $v$. In this case, the shortest path from $s$ to $v$ cannot be longer than the shortest path from $s$ to $u$ followed by the edge $(u,v)$ and thus the inequality holds.

I drew this to visualize the problem but I don't see how what I drew is wrong and how the proof is correct.

If going from $s$ to $u$ has less vertices along that path than going from $s$ to $v$, than the shortest distance of $s$ to $v$ should be greater than going from $s$ to $u$ and $s$ to $u$ to $v$.

# Answer
> 1 votes
I don't understand your diagram but the point is that, if there is a $x$–$y$ path of length $k$ then the distance from $x$ to $y$ cannot be bigger than $k$.

So, suppose the shortest path1 $P$ from $s$ to $v$ has length $k$. If that path includes $u$, then there is a path of length less than $k$ from $s$ to $u$. Since there is a path of length less than $k$, the distance from $u$ to $v$ is less than $k$, so it is less than or equal to $k+1$, as required. On the other hand, if $P$ does not include $u$, then $P$ followed by the edge $uv$ is a path from $s$ to $v$ of length $k+1$. Since there is a path of length $k+1$, the shortest path can't be longer than that, so the distance is at most $k+1$.

1 I should really say "a shortest path", since there can be multiple different paths, all of the same length.

# Answer
> 1 votes
Consider the shortest path between $s$ and $u$, and suppose it has $n$ edges. Then append one edge to the path, which is $(u,v)$. We get *a* path from $s$ to $v$, of length $n+1$.

By definition, the length of the *shortest* path between $s$ and $v$ is not greater than $n+1$, which is the length of some path between $s$ an $v$.

Makes sense?

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


# Question
Title: Online and parallizeable set intersection algorithm
I have problem that is reducible to the following:

From a collection of stacks, find all items whose "keys" are on all stacks.

My current solution to this problem is to just pop things off as quickly as possible store the items in the language's set type, compute the intersection every once in a while (the stacks are refilling constantly), and use that set, repeat.

The issue here is that the equivalent of the `pop` operation is expensive (I can do this at most 4k times a second), and it kills the chance of multithreading (as `pop`s are destructive).

Is there a way of doing this such that I can multithread the intersection bit? I cannot practically use shared memory or requeuing items. The threads can communicate with each other via pipes/sockets if need be, but such communication should be kept to a minimum (not really interesting in starting up some whole separate client/server thing just for this part of my application)

As an idea of what I am dealing with, there can be up to 15 million items on the queues at any one time. By the time its "over" all items will have a match.

Ideas?

**Clarification:** These are message stacks (well queues really but the same thing) over the network. A pop is a consume operation over network, and push is a publish. Thats why its so slow. Since the issues is one of latency rather than bandwidth, multithreading can potentially help. I am not CPU bound. I have ~10 stacks, and up to 10 million items at a time. I have no control over the implementation of the stacks.

# Answer
> 1 votes
Apparently this is a distributed systems problem. You have ~ 10 stacks, each with up to 10 million items at a time, and each stack living on a different machine.

Here is one simple candidate solution. Have a separate "monitor" machine, whose sole purpose is to continually compute the intersection. Any time one of the stacks is modified, the machine storing that stack should send a message to the monitor message describing the change. (These diffs can be batched, depending upon your latency requirements.)

Now you have all the data on a single machine, the monitor machine. When running on a single machine, you can completely avoid all of the concurrency issues associated with multithreading or distributed systems -- e.g., the need for synchronization, locks, etc.

Moreover, the amount of data is small enough that it could easily be stored in the available RAM on that monitor machine. (Why? If each entry is large, hash it first using a good hash function and a large enough hash output that you won't see collisions. If each hash value is 128 bits, then storing all 100 million hashed items takes 1.6GB. If you use SHA256 truncated to 128 bits as your hash function, by the birthday paradox, the chances of encountering a hash collision are incredibly small.)

Once all of the data is living in RAM on a single machine, the problem becomes much easier. For example, one approach would be to build an index data structure: a hashmap that maps each key to a 10-bit bitmap that indicates which of the stacks it is stored on. You can easily update this hashmap as the individual stacks change.

You can also easily use this hashmap to compute the intersection: just have a doubly linked list threaded through the entries of this hashmap where the bitmap is equal to 11111111111 (all 1's). Any time a bitmap changes from 11111111111 to something else, you remove it from the doubly linked list. Any time a bitmap changes from something else to 11111111111, you insert it into the doubly linked list.

The amount of data you need to transfer from other machines to the monitor machine is very small, especially since you only need to send the hashed items to the monitor, not the original items. If each of the 10 machines will do at most 4k push/pop's per second (taken from your question), then that's 64 KB of hashed data per second per machine. If we add another 32 bytes or so of overhead (packet headers), that's about 200 KB/s of data out of each machine, or about 2 MB/s of data into the monitor machine -- a very manageable amount. On a 1 Gbps Ethernet link you won't notice this, and you might not notice it even on a 100 Mbps link. You can reduce the amount of traffic by a factor of 2-5x by batching such messages and/or by using a shorter hash.

This should provide an efficient algorithm to compute the intersection, and keep it updated on the fly as each of the stacks change.

---
Tags: algorithms, sets, online-algorithms
---


# Question
Title: Calculating cache memory based on LRU algorithm
Assuming i have 4 blocks of cache memory, Using the LRU (Least Recently Used) replacement algorithm on this following sequence of access to memory blocks: 1 2 3 4 5 2 5 4 1 5 2 3 :

```
1   2   3   4   5   2   5   4   1   5   2   3

1   1   1   1   5   5   5   5   5   5   5   5
    2   2   2   2   2   2   2   2   2   2   2
        3   3   3   3   3   3   1   1   1   1
            4   4   4   4   4   4   4   4   3

```

So in the end, the cache memory will contains this memory blocks : "5 2 1 3"

But the correct answer is "1 5 2 3"

Please tell me what am I doing wrong here!

# Answer
> 3 votes
Least recently used cache do the following things: we add the numbers to the top(front) representing that it is the "most recent" and thus the end of this will be the number which is least recent.

1. If the cache is not full, **1 a)**. add to the cache if the entry is not in the cache. **1 b)**. If the entry is in cache we make that most recent and continue.
2. If the cache is full, **2 a)** If the value is already in the cache we just move it up(front) so that it represent most recent after this. **2 b)** If the value is not in the cache we remove the least recent one and add the current value to the top(front)to represent that as the most recent.

Now let me explain you the sample which you have provided.

```
**Input**                     **cache**(front represent most recent and end represent least recent

1   2   3   4   5   2   5   4   1   5   2   3  --> inputs

1   2   3   4   5   2   5   4   1   5   2   3  --->(this is our cache) **top represent most recent**
-   1   2   3   4   5   2   5   4   1   5   2
-   -   1   2   3   4   4   2   5   4   1   5
-   -   -   1   2   3   3   3   2   2   4   1  ----> **end represent the least recent**

```

So we have our answer as,(from most recent to least recent) = 3,2,5,1

hope this helps you.Sorry for my bad editing.

---
Tags: memory-management, cpu-cache, paging
---


# Question
Title: Enumerating the elements of an integer lattice $\mathbb{Z}^n$
The elements of $\mathbb{Z}$ can be enumerated as $0, 1, -1, 2, -2, 3, -3, \ldots$. Similarly, the points of the lattice $\mathbb{Z}^2$ can be enumerated

$$(0,0), (1,0), (0,1), (-1,0), (0,-1), (2,0), (1,1), (0,2), (-1,1), \ldots$$

I would like to extend this algorithm to $\mathbb{Z}^n$. Is there a simple way to do that?

Note that the ordering of the elements may vary. The only condition should be that if $B\_1$ and $B\_2$ are two closed balls in the metric $L^1$ on $\mathbb{Z}^n$, and $B\_1 \subset B\_2$, then all the elements of $B\_1$ should be enumerated before any element of $B\_2 - B\_1$.

# Answer
> 1 votes
Your additional condition requires the tuples to be listed in ascending order of the sum of the absolute value of their components. We are free to choose the order of tuples with the same sum, so I propose the following procedure:

`list(k,n)` lists the $k$-tuples, where the absolute values sum to $n$:

```
For i=n downto -n:
  Output all outputs of list(k-1,n-|i|), each prefixed by i.

```

`list(k)` lists all $k$-tuples:

```
n=0;
While true:
  Output all outputs of list(k,n).
  n++.

```

---
Tags: algorithms, enumeration
---


# Question
Title: Set containment of MinimumBadPrefix and BadPrefix of a Safety Property
This question is related to formal model checking theory, but I cannot find a tag for it.

Let $P\_{safe}$ be a safety property.

$BadPref(P\_{safe})$ is the set of bad prefixes for $P\_{safe}$

A Safety property $P\_{safe}$ over Atomic Proposition $AP$ is regular if its set of bad prefixes is a regular language over $2^{AP}$

Is the following true?

1. If $L$ is a regular language with $MinBadPref(P\_{safe}) \subset L \subset BadPref(P\_{safe})$, then $P\_{safe}$ is regular.
2. If $P\_{safe}$ is regular, then any L for which $MinBadPref(P\_{safe}) \subset L \subset BadPref(P\_{safe})$ is regular.

My attempt to 2. is that it's true

$P\_{safe}$ is regular then $MinBadPref(P\_{safe})$ is regular and so is $BadPref(P\_{safe})$. A NFA $N$ recognizing $BadPref(P\_{safe})$ can be obtained by adding self loops on the final states of the NFA $M$ recognizing $MinBadPref(P\_{safe})$. And $L$ is recognized by some NFA containing a subset of the self loops added to $M$. Therefore $L$ is regular.

And what about 1.?

# Answer
> 1 votes
For (1), I will only give a sketch at first, in case you want to work it out yourself; I can add some details later if you want. Try proving the following:

$w\in BadPref$ if and only if $w$ has a prefix $u$ which is in $L$.

(2) is already covered quite well by David's comments.

---
Tags: automata, formal-methods, model-checking
---


# Question
Title: Is there a technique for statically checking that a function is only called at a particular rate?
I was reading this article about types, and started wondering how static type checkers could enforce other properties in programs. For example, say I wanted to create a language which would allow checking at compile time that a particular function was only called at most once every 300ms. How would I go about specifying the language to allow that to be enforced? What existing languages try to enforce similar properties?

# Answer
> 4 votes
The property you mention is probably not something that sounds like an ideal fit for enforcement by type systems, so it's not the first example I would suggest looking at, if you want to learn more about how type systems can be used to enforce a variety of properties. (I'm not saying it is impossible to enforce that property using a type system, but it might not look natural or feel super-useful to an everyday programmer, and the type system might need some hand-holding or help from the programmer.)

However, there *are* other properties that are a better fit for type systems. For instance, you might look at dependent type systems, which can be used to enforce many properties.

In my experience, type systems tend to be more useful for enforcing safety properties. It tends to be harder to reason about time or liveness properties using a type system (I'm not saying it is impossible, but it might be harder or less natural).

You might also enjoy reading about the Curry-Howard correspondence, which shows a correspondence between theorems and types (and between a proof of a particular theorem vs a particular program that can be given a particular type). Proof-carrying code is one example of a system that relies heavily on this view of proofs-as-programs. The goal there is to prove non-trivial properties of a program. The theorem you want to prove gets encoded as a type, and the proof gets encoded as an expression in an abstract language; then checking the validity of the proof becomes as simple as checking that the expression has the claimed type. This essentially shows how you can reduce "showing that the program satisfies a particular safety property" to type-checking.

---

In a similar but not identical vein, you might also enjoy looking at languages like Haskell and the QuickCheck tool, which uses the rich type information available from the Haskell type system to synthesize test cases. Anecdotally, QuickCheck is effective at finding many bugs. This is not an example of using the type system to enforce absence of a particular kind of bug, so much as using the type system to make random testing more effective and thereby tend to help programmers catch many bugs earlier.

# Answer
> 4 votes
Many problems of this kind can be adressed by **abstract interpretation** of programs. It may well be that abstract interpretations can always be expressed in type systems, but I am not quite sure about it as I did not follow the field for a long time. The early work, at least, was often perceived as interpreting types differently.

A very early paper on this, very easy reading, is the following. It is mostly examples, as I recall. It was fun reading at the time.

Michel Sintzoff: Calculating properties of programs by valuations on specific models, Proceedings of ACM conference on Proving assertions about programs, 1972 doi:10.1145/800235.807086

Later work on abstract interpretation was devoted to formalization of the concept.

You will find major references on the web and in Wikipedia.

The simplest example of abstract interpretation is taught in elementary school. It is the "Casting out nines" test. It can be used to check that the value of an expression satisfies a property when the values of the unknown arguments satisfy that property. The checking is done by actually evaluating the expression in a different interpretation domain. In this case, the abstract value can also be seen as types for the variables.

# Answer
> 3 votes
I'm aware of at least one attempt to use unification to infer time-like facts about programs. The following papers are from David Gifford's research group at MIT, back in the late 1980s/early 1990s. They infer the "times" of functions as polymorphic expressions of the "times" of their inputs. Dornic's paper tries to infer time complexity of functions, while Reistad's paper tries to infer actual time estimates in terms of the measured cost of micro-operations (like dereferencing a pointer or returning a value from a function.)

Dornic, Vincent; Jouvelot, Pierre; Gifford, David K.: Polymorphic time systems for estimating program complexity. *ACM Lett. Program. Lang. Syst.* 1(1):33-45, March 1992. DOI=10.1145/130616.130620.

Reistad, Brian; Gifford, David K.: Static Dependent Costs for Estimating Program Execution Time. *ACM Conference on Lisp and Functional Programming,* 1994: 65-78.

---
Tags: algorithm-analysis, compilers, type-checking
---