# Question
Title: Designing a parallel algorithm to find the second largest item in an array
Using pseudocode, I need to design a parallel algorithm that, when given k keys, a\[0\], a\[1\], a\[2\],... a\[k-1\] stored in an unsorted array a, would find the second largest key in it.

I'm new to parallel computing, so I know that in terms of sequential programming, we can use bubble sort with two passes. First pass gets your the largest element, while the second pass will get you the second largest element, the goal. Should we split the bubble sorta via parallel processing, we only need to do one pass each iterations largest element to find the second largest. My problem is I don't know how to exactly 'parallelize' the algorithm.

# Answer
I'll sketch informally one obvious variant, assuming some model with *shared* memory and *unbounded* parallelism (I'm not going to discuss the synchronization issues, though). Lets denote the size of the original array as $n$.

1. Divide your array into $k$ subarrays of approximately equal sizes $s\_i$, such that $s\_i \approx \frac{n}{k} \wedge s\_i \ge 2$, then assign each subarray to a thread or whatever you use, lets call it "process". This assignment procedure can be (should be) implemented in a way such that its time complexity is $O(1)$.
2. Then $i$-th parallel process finds the largest $M\_i$ and the second largest element $m\_i$ of $i$-th subarray *sequentially*. It's an easy linear complexity algorithm, which works in one go through all the elements of the input. So, time complexity of this step is $O\left(\frac{n}{k}\right)$. $i$-th process will store the results in the first two elements of $i$-th subarray, so you won't need to send $M\_i$ and $m\_i$ anywhere and resolve the synchronization issues connected with sending/receiving. That's why we need $s\_i \ge 2$, and if there is not enough elements then it is not worth to process it in parallel.
3. Wait until all processes finish (its called a barrier). At this point you have an array of all the results ($M\_i$ and $m\_i$) of all processes. Now, simply use the sequential algorithm again. The resulting $m$ will be the answer for the whole original array. Time complexity of this step is $O(k)$.

The overall time complexity of our algorithm is $O\left(\frac{n}{k} + k\right)$. Under this *very* simplistic model it's better to have the number of parallel processes $k \sim \sqrt{n}$ to make the overall time complexity minimal: $O \left( \sqrt{n} \right)$. This result can be easily obtained using differential calculus. Of course, this result is very far from the reality of practical parallel computing: we don't have unbounded parallelism in practice and we need to consider the parallel processing management overhead.
> 3 votes

---
Tags: algorithms, search-algorithms, parallel-computing, arrays
---


title: Z-score relations to perceptrons

text:
# Question
Title: Z-score relations to perceptrons
I am learning about preceptrons and my professor noted that z-scores are a commmon pre-processing step to normalizing input variables. Following this, I am having trouble understanding why z-scores are useful when training a preceptron?

My current understanding is that z-scores allows us to calculate the probability of a score landing inside the normal distribution and compare with scores from other normal distributions. However, how does this translate to perceptrons?

# Answer
There are two parts to your question that need to be addressed.

> 1. What transformation are you performing?
> 2. Why does that help learning?

The transformation of taking your input and turning them into "Z-scores" is *really* just centering and standardizing the variance for each variable. The reason I put "Z-score" in quotes is because there is no reason to assume that this transformed variable is distributed normally. All you have done is taken a random variable with some unknown distribution and transform it to a random variable with mean 0 and variance 1. That doesn't necessarily mean it is normally distributed. Formally, if we have $$X \sim f(\mu, \sigma^2)$$ where $X$ is a random variable $f$ is the distribution with mean $\mu$ and variance $\sigma^2$, then $$\frac{X - \mu}{\sigma} \sim f(0, 1)$$ using the basic properties of mean and variance. Nowhere does this *require* $X \sim N(\mu, \sigma^2)$, which is where Z-score comes from.

With that said, *why* does this help? By centering your data (removing the mean) from both your training data and labels, you don't need to estimate a bias term. Bias (or mean measured effect) is function of the mean of your data; therefore if your data have mean 0, you should have no measurable bias term. Setting all variables to have unit variance places them all on the same scale. Oftentimes in real data the different variables in your model may have widely different variances, which could lead to difficult to compare effect sizes. Setting everything to have similar variance simplifies interpretation.
> 3 votes

# Answer
Why does this help? Part of the reason is because of properties of the activation function.

Typically, most activation functions have their most interesting behavior around 0. For instance, the ReLu activation function switches from $f(x)=0$ to $f(x)=x$ at $x=0$. The sigmoid activation function has most of its interesting behavior at $x=0$, and plateaus at very large positive values of $x$ (and very negative values of $x$). Therefore, it's useful to have the inputs to the activation function be centered at 0. Transforming the inputs to have mean 0 ensures that most values are near the interesting part of the activation function.

Suppose you didn't transform the inputs, and inputs had values in the range \[100,101\]. Then with reasonable initial values of the weights, the input to the activation function would be some huge value (something in the vicinity of 100 times the number of inputs to that neuron). As a result, the activation function would be in a part of the input space where the activation function does nothing interesting (it's either flat or it's linear), and you're not taking advantage of the power of the neural network -- it'd be like trying to classify using a neural network where you've omitted the activation function entirely. That's not going to work well -- the activation function is an essential part of the neural network.

Now with sufficient learning, the neural network could adapt to the lack of scaling, by choosing suitable weights that basically do the rescaling for you. But initially the network is going to do very poorly, because the initial weights will be so terrible, and the optimization method (stochastic gradient descent) is going to have a hard time figuring out how to choose better weights: you're so far away from a good part of the space that any small change to the weights makes little improvement to overall performance.

So, rescaling is a heuristic that tends to make stochastic gradient descent more effective, and helps training converge more quickly and more reliably.
> 3 votes

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


# Question
Title: Prove that we can change probability in definition of PP class
According to Wikipedia, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than or equal to 1/2.

So, the problem is to prove that if in definition we change probability from 1/2 to any rational number (0,1) we obtain the same class of problems.

# Answer
> 0 votes
Lets say a separation using $p\in\mathbb{Q}$ exists for $L\subseteq\Sigma^\*$ if there exists a polynomial probabilistic Turing machine $M$ such that:

$x\in L \Rightarrow \Pr\left\[\text{M accepts x}\right\]\> p$

$x\notin L \Rightarrow \Pr\left\[\text{M accepts x}\right\]\< p$

$L\in PP$ iff there exists a separation for $L$ using $\frac{1}{2}$ (we can use a strong inequality in both cases). We proceed to show that $\forall p,q\in (0,1)\cap \mathbb{Q}$, if there exists a separation for $L$ using $p$, then there exists a separation using $q$.

We shall use the fact that a probabilistic Turing machine with access to unbiased random coins, is able to simulate an $\alpha$-biased coin for any rational (this can be strengthened) $\alpha\in \[0,1\]$, in $O(1)$ expected time. See lemma 7.14 in Arora and Barak's book for a proof.

Now, given a machine $M\_p$ with separation $p$ for $L$, lets consider a machine $M\_q$, which starts by tossing an $\alpha$-biased coin. If the outcome is $1$ then it accepts, otherwise it simulates $M\_p$ on the input and returns it's answer.

Since we want $M\_q$ to be polynomial in the worst case, we restrict the simulation of the $\alpha$-biased coin to a certain number of iterations, such that the simulation halts with probability $1-\epsilon$ (this can be done for any $\epsilon\>0$, simply use the fact that the simulation runs in expected constant time, and apply Markov's inequality). If the simulation didn't halt, $M\_q$ accepts. In this case we have:

$\Pr\left\[\text{$M\_q$ accepts x}\right\]=\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)\Pr\left\[\text{$M\_p$ accepts x}\right\]\right)$, so:

$x\in L \Rightarrow \Pr\left\[\text{$M\_q$ accepts x}\right\]\> \epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right) $

$x\notin L \Rightarrow \Pr\left\[\text{$M\_q$ accepts x}\right\]\< \epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right) $

This means it is enough to require $q=\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right)$. Equivalently,

$\alpha=\frac{q-p-\epsilon(1-p)}{1-\epsilon}$.

Since $p,q\in (0,1)\cap \mathbb{Q}$, if $q\>p$ we can find a small rational $\epsilon$ and rational $\alpha\in (0,1)$ to satisfy this. If $p\>q$ you can change $M\_q$ to reject when the outcome of the $\alpha$-biased coin is 1. When this equality holds, $M\_q$ achieves $q$ separation for $L$ and we are done.

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


# Question
Title: Sliding-window sum greater than N using as few numbers as possible
I have a problem that I'm trying to solve as part of a larger algorithm I'm implementing, and I don't know if there's a standard, well-known technique for this or not. Without going into too many details of the larger algorithm, I've managed to boil my problem down to the following mathematical summary:

I have a list of N non-negative integers, where N is a power of 2. (In the current implementation of the larger algorithm, it's 32, but it could be as low as 4). All of the integers in this list are between 0 and N-1. The total sum of the list is known to be at least 2N. I want to find a consecutive sequence of integers from the list where:

**A)** The integers in the sequence add up to at least N (higher is acceptable),

**B)** The length of the sequence is small (see below), and

**C)** I don't spend more than O(N) time finding the length of the sequence.

"Small" here does not necessarily mean "as small as possible", but it should at least be a local optimum: e.g., removing either the first or last integer from the sequence would drop the total to below N. I don't mind if I haven't found a global optimum, as long as it's a decent local optimum. Making two or three passes through the list to find a pretty good local optimum could be worth the time, but it would be better if I only had to make a single pass, or even just a partial pass (greedily find a local optimum and then stop without looking further). And making N passes through the list (for an O(N^2) solution) would be a waste of time that could more profitably be spent on other parts of my larger algorithm.

One other detail: it's highly likely that many numbers in this list will be 0. Also, due to some of the details of the larger algorithm, the numbers N/2, (N/2)-1, N/4, and (N/4)-1 are quite a bit more likely to appear in the list than other numbers. (Of course, (N/4)-1 only appears in the cases where N \> 4). It's possible that knowing this fact might help find a better solution, but I haven't yet found a good way to take advantage of this knowledge.

What I've come up with so far is a kind of sliding-window approach:

1. Starting at the left of the list, skip over any 0's or 1's since the 0's are not going to contribute anything to the solution, and the 1's won't contribute much. (The 1's are safe to skip over, because we know that the list sums to at least 2N. So even if there are N-1 1's in the list, the last item would have to be at least N+1 -- which is actually impossible given the constraints on the problem. So there could be no more than N-2 1's in the list, and the last two numbers add up to N+2 and are therefore a valid, and very short, solution).
2. Now we have the index of the first integer that's at least 2. Mark it as the leftmost point of our candidate sequence.
3. Start expanding the candidate sequence to the right, keeping a running total of the sequence length and the sum of the sequence. Once the sum is \>= N, stop. We have a candidate sequence.
4. Now start looking at the leftmost item of the candidate sequence, and consider whether dropping it out of the sequence (essentially sliding the left edge of the window to the right, reducing its length by 1) would reduce the sequence's sum to \< N or not. If the sum would still be \>= N, go ahead and drop the leftmost integer from the candidate sequence, then repeat this step.

I'm pretty sure this gives me a local optimum, but I wonder if there's a way to improve it. Is there a well-known technique for solving this problem, and I'm reinventing the wheel through ignorance?

BTW, I just saw Find the minimum count of elements summing to a pre-defined sum in the "Similar Questions" links on the right. My problem is *very* similar to that one, but with one important difference. That problem wants the smallest contiguous sub-array that sums to *exactly* N, whereas I'm quite happy to have a solution that sums to more than N. (As it happens, in my algorithm having a solution that sums to exactly N would be mildly better, but finding a local optimum *quickly* far outweighs getting a sum of exactly N). Still, if one of the solutions to that question might be adaptable to my situation, I'd like to know about it.

# Answer
> 1 votes
Yes. There is a linear-time algorithm for this problem. The algorithm finds the globally optimal solution, not just a local optimum or an approximation. I will assume the problem statement is as follows:

Input: an array $A\[1..N\]$, an integer $K$ with $1 \le K \le N$
Goal: find a (contiguous) subarray of length $\le K$ whose sum is as large as possible

This can be solved in $O(N)$ time using a divide-and-conquer algorithm. In particular, we will split the array into two equal-sized pieces, $A\[1..N/2\]$ and $A\[N/2+1..N\]$. Then there are three cases for where the maximal subarray lives:

* It is a subarray of $A\[1..N/2\]$ (wholly to the left of the split point).
* It is a subarray of $A\[N/2+1..N\]$ (wholly to the right of the split point).
* It is a subarray of the form $A\[i..j\]$ where $i \le N/2 \< j$ (it straddles the split point).

We'll check all three scenarios to find the best subarray of each form, and take the best of those three candidates. The first two cases can be checked recursively. I'll show how to check the third case in $O(K)$ time. As a result, we'll obtain a recursive algorithm whose running time is given by the recurrence relation

$$T(N) = 2 T(N/2) + O(K).$$

As long as $K = O(N / \log N)$, the solution to this recurrence relation is $T(N) = O(N)$. Since you said $K$ is small in your case, the condition will surely hold, so we obtain a linear-time algorithm for your problem.

---

So how do we check for the subarray with maximal sum that straddles the split point and has length $\le K$? First, as a preprocessing step, we compute the suffix sums $S\[i\] = A\[N/2-i\] + A\[N/2-i+1\] + \dots + A\[N/2\]$ for $i=1,\dots,K-1$. Second, as another preprocessing step, we'll compute the prefix sums $P\[j\] = A\[N/2+1\] + A\[N/2+2\] + \dots + A\[N/2+j\]$ for $j=1,\dots,K-1$. Each of those steps can be done in $O(K)$ time by a linear scan (moving leftward from the split point for $S$, and moving rightward from the split point for $P$).

Then, for each $\ell=1,2,\dots,K-1$, we compute $Q\[\ell\] = \max(P\[1\],\dots,P\[\ell\])$. This is the best sum achievable by using a subarray of length $\le \ell$ starting at $A\[N/2+1\]$. This too can be computed using a linear scan.

Finally, for each $i=1,\dots,K-1$, we compute $S\[i\] + Q\[K-i\]$; this tells us the best sum achievable by using a subarray of length $\le K$ starting at $A\[N/2-i\]$. We take the largest such value, and that is the maximum sum possible for a subarray of length $\le K$ that straddles the split point.

Each of these four steps runs in $O(K)$ time, so the total running time to compute the best subarray of the third kind is $O(K)$, as claimed above.

---
Tags: algorithms
---


# Question
Title: Testing whether a tetrahedron lies inside a Polyhedron
I have a tetrahedron $t$ and a polyhedron $p$. $t$ is constrained such that it always shares all its vertices with $p$. I want to determine whether $t$ lies *inside* $p$.

I would like to add one detail to the problem in case it may contribute to the solution: $t$ is a *Delaunay* tetrahedron and faces of $p$ are triangular and are *strongly Delaunay* both with respect to vertices of $p$. A tetrahedron is *Delaunay* if circumsphere of its vertices contains no other vertex inside it. A face is *strongly Delaunay* if there exists a circumsphere containing vertices of that face on its surface but no other vertex *on* or *inside* it.

Following figures show the same problem in $2D$ space:

**The original polygon $p$**:

**Delaunay triangulation of vertices of $p$**:

**Result of *inside/outside* test over triangles $t$**(Shaded triangles are *inside* $p$ and rest are *outside*):

**Desired result(pruning *outside* triangles)**:

---

My original problem is in 3D space so triangles $t$ in above figures translate to tetrahedrons and polygon $p$ translates to an *arbitrary* polyhedron $p$. I have figured out some formulations of this problem:

**Formulation 1**
The only parts of $t$ which can be outside $p$ are its edges and triangular faces but in general there may exist a $p$ which has edges of all *outside* $t$'s on its surface, so alternatively, this problem may also be formulated as to test whether for a tetrahedron $t$ there exists a face which lies *outside* $p$?

**Formulation 2**
I have another possible perspective towards this problem but lacking any formal idea:
Geometrically, if $t$ is outside then it will always be *sticking* on the *outer* surface of $p$. So if we can compute the *contours*(informally, the outer boundary) $C\_{V}$ and $C\_{V\_{p}}$ such that $V=V\_{t}\cup V\_{p}$ and $V\_t,V\_p$ are sets of vertices in $t,p$ respectively, then $C\_{V}=C\_{V\_p}$ *iff* $t$ lies inside $p$.

I would like to know:

* How can I solve either of **Formulation 1** or **Formulation 2**?
* Or, is there any completely different approach to solve this?

**Update:**
I now realize that this problem can be reduced to *Point in polyhedron* problem. Since an *outside* tetrahedron $t$ will have *at least* one face which lies outside $p$, so any arbitrary point on that face(except its vertices,in general) will always lie *outside* $p$. Therefore, for each face of $t$, I need to take an arbitrary point and test if that point lies *outside* $p$.

From point in polygon article I came to know about **Ray casting algorithm** and **Winding number algorithm**. Ray casting is not *numerically stable* for cases where point lies on the surface of $p$. But numerical robustness of Winding number algorithm has not been addressed there.

Based on above, my core problem now seems to be(please suggest if it should be asked as a separate question):
Is there any numerically robust algorithm for *point in polygon* problem?

# Answer
> 2 votes
I recently found one solution to this problem in a paper 'Robust inside-outside segmentation using generalized winding numbers' by Alec Jacobson et.al., here. It solves the problem of locating if a point is inside(or outside) an arbitrary(one with self-intersections, non-manifold, open-surfaces etc.) polygonal mesh using the notion of *generalized winding number*.

Problem can be solved if I compute the generalized winding number of the centroid of $t$ against the surface of $p$.

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


# Question
Title: how to use type application rule (T-TAPP)?
In the following rule,

$$\dfrac{ \Gamma \vdash t\_1 : \forall X.T\_{12} } { \Gamma \vdash t\_1 \ \[T\_2\] : \[X \mapsto T\_2\]T\_{12} } \textsf{ (T-TApp)}$$

whend doing type checking, how do know what is $X$?

Also, type checking will not give you a term which has a form $\[X \mapsto T\_2\]T\_{12}$, so how to deal with that substitution?

We will have $t\_1 \ \[T\_2\]$ during type checking and $T\_2$ could be any type such as $T, T \to T,\forall X.T$. How do we know $\[X \mapsto T\_2\]$, again?

I just could not understand how to apply this rule during type checking?

Please help!

# Answer
> 0 votes
I figured it out. there is a unification needed during type checking.

there is a condition though, $ftv(T\_2) \in \Gamma\_{tv}$, saying free type variables of $T2$ should be found in the set of type variables in type context.

Also, $X$ could be choose as any new new name which does not clash with existing names.

In type checking, you have $\Gamma \vdash M \quad t\_2 : T$, so apply that rule. we can write $\Gamma \vdash M: \forall X.T\_1$ where $unify(T , \[X \mapsto T\_2\]T\_1$), where $unify(t1,t2)$ check if these two terms are equal.

# Answer
> 5 votes
Type checking and the inference rules for type theory are *not an algorithm*. They do not tell you how to type check. They tell you what is *allowed* when you perform type checking.

The rule for application should be read as:

> If you can prove $\Gamma \vdash t\_1 : \forall T . T\_{12}$ (and we're not telling you how to do that, you'll have to figure it out) then $\Gamma \vdash t\_1\[T\_2\] : \[X \to T\_2\]T\_{12}$ for whatever $T\_2$ you choose to use (and of course we do not know what it is that you're trying to do here, the choice of $T\_2$ is entirely up to you).

So, the answer to your question is: *you* have to figure out how to find the value of $X$ and *you* have to worry about the subtitution. The rules are *not* meant to solve that problem. They are just *rules*, telling you what you *may* do.

The *correct* question that you should have asked is: *"How do I make an algorithm that will be able to perform type-checking automatically?"* This is an important question, and people put a lot of thought into it. I can give you an initial answer: try out all possibilities until you find one that works. But that's a lousy aglorithm and it's possible to do better.

---
Tags: type-theory, type-checking
---


# Question
Title: Complexity class of integer factorization
Is integer factorization confirmed to be an NP-complete problem? If not, then if one could transform IF into an equivalent problem which is already proved to be NP-complete, would it mean that IF is itself NP-complete as well? Would such a thing have any practical meaning?

# Answer
Integer factorization (or rather, an appropriate decision version) is not known to be NP-complete. In fact, it is conjectured not to be NP-complete. However, any reasonable decision version of integer factorization is in NP, and so reducible to any NP-complete problem (by definition). There are specialized algorithms for integer factorization which are better than, say, reducing integer factorization to SAT and then using a SAT solver.
> 9 votes

---
Tags: complexity-theory, integers, factoring
---


# Question
Title: Can we define an ε deterministic finite automaton?
I am studying automata and I was wandering if there is a definition of ε-DFA automaton. Is it feasible to define it?

# Answer
Expanding on adrianN's comment, sure, you can define one if you want but what would be the point?

I guess the definition you have in mind is that the transition function has the form $\delta\colon Q\times (\Sigma\cup\\{\varepsilon\\})\to Q$. That is, for each state $q$ and each symbol $a$ in the alphabet, there's exactly one state that the automaton moves to after reading that symbol. For each state, there's also a state the automaton can move to without reading a character of input (this is $\delta(q,\varepsilon)$).

Let's briefly investigate the properties of such a machine. First, note that, if you don't want a $\varepsilon$-transition from some particular state, you can set $\delta(q,\varepsilon)=q$. We can also see that this new type of automaton accepts exactly the regular languages. It's a special kind of NFA, so it can't accept any non-regular language. And any DFA is just one of these automata where $\delta(q,\varepsilon)=q$ for every state $q$, so every regular language is accepted by an automaton of this kind.

So, what have we achieved? The advantage of DFAs is that they're easy to analyze but it can be hard to construct a DFA to accept a particular language – if you don't believe me, design an algorithm that converts arbitrary regular expressions straight to DFAs, without using NFAs as an intermediate stage. Conversely, NFAs are quite easy to construct but it can be hard to analyze what they're doing – for example, compare how annoyingly difficult it is to precisely define the language accepted by an NFA, compared to a DFA.

This new type of automaton seems to combine the disadvantages of both: requiring exactly one transition per state per symbol and at most one $\varepsilon$-transition per state means that it's still going to be fiddly to design an automaton that does what you want. But the fact that the $\varepsilon$-transitions introduce nondeterminism means that it'll be harder to analyze what's going on. Meanwhile, the power of these new automata is exactly the same as the automata we already had, so we don't seem to have gained anything.
> 5 votes

# Answer
I don't think so. DFAs are, by their definition, deterministic and should have deterministic transitions for every symbol of the input string. If a transition such as $\delta(q\_0,\varepsilon)=q\_1$ exists, the automata becomes non-deterministic because the next input symbol of the string will be passed to both $q\_0$ and $q\_1$ and this is what is exhibited by $\varepsilon$-NFAs.
> 1 votes

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


# Question
Title: N songs, M instruments, how to pick K instruments to cover maximal amount of songs
I have $N$ songs, $M$ instruments.

Each song requires one or more of the $M$ instruments in order to be played.

My $K-1$ friends and I want to learn to play $K$ different instruments, and we want to pick them such that we maximize the amount of songs we will can play.

How would I efficiently solve this? I'm sure this problem maps to some well known computational problem, but nothing comes to mind at the moment.

# Answer
> 4 votes
I don't know a canonical name for this problem, but unfortunately it's NP-hard, *even when every song requires at most 2 instruments*. The upshot is that it's extremely unlikely that any polynomial-time algorithm exists that will solve every instance of your problem. I'll show this by reduction from the NP-hard problem Maximum Clique, in which we are given an undirected graph $G = (V, E)$ and a positive integer $k$, and asked whether there exists a clique of size $k$ in the graph.

To construct an instance of your problem from the Maximum Clique Instance: Create a song $s\_{uv}$ for every edge $(u, v)$ in $E$, and an instrument $t\_v$ for every vertex $v$ in $V$, and make song $s\_{uv}$ require the two instruments $t\_u$ and $t\_v$. Set $K$ (part of the input to your problem) equal to $k$ (part of the input to the Maximum Clique problem). Now run any algorithm that solves your problem on the just-created instance: if the answer is $\ge k(k-1)/2$ then return YES, otherwise return NO. (Clearly this procedure could work just as easily with an algorithm that solves the "pure decision" form of your problem, i.e., when a number $r$ is also given as part of the input, and the task is to determine whether it is possible to choose at most $K$ instruments such that at least $r$ songs can be played.)

It is easy to see that, if $G$ contains a clique of size at least $k$, then we must correctly get a YES answer: by assumption, there is a $k$-vertex clique, which comprises $k(k-1)/2$ vertex pairs, each of which are connected by an edge, so choosing the corresponding $k$ instruments satisfies the $k(k-1)/2$ corresponding songs.

In the other direction, suppose that the algorithm for your problem reports that at least $k(k-1)/2$ songs can be played; we need to show that this implies that there is a $k$-clique in $G$. Given that we permitted at most $k$ instruments to be chosen, there certainly cannot be *more* than $k(k-1)/2$ songs that we can play, since every song requires a distinct pair of instruments: so we can infer that exactly $k(k-1)/2$ songs can be played. But every choice of at most $k$ instruments that does not correspond to a $k$-clique in $G$ omits at least one of these $k(k-1)/2$ edges, and thus allows strictly fewer than this maximum possible number of songs to be played; thus the only subgraphs on at most $k$ vertices that can result in at least $k(k-1)/2$ edges are subgraphs that are $k$-cliques.

---
Tags: algorithms, sets
---


# Question
Title: Nonuniform input distributions in average case analysis
When we perform average case analysis of algorithms, we assume that the inputs to the algorithm are sampled uniformly from some underlying space. For example, the average case analysis of quicksort assumes that the unsorted array is uniformly sampled from the $n!$ permutations of $\\{1,\ldots,n\\}$.

Suppose instead that the inputs to an algorithm are chosen  *non-uniformly* over the input space.

Is the resulting analysis still "average case" analysis?

If the distribution causes the algorithm to perform at its worst (resp. best), is there a standard name for it? E.g. "adversarial (resp. favourable) distribution of inputs".

# Answer
Yes, the expected running time under some other distribution would still count as an example of average-case analysis. However, when you describe it to someone, make sure you explain what distribution you're using. I wouldn't recommend that you just call it "average-case analysis" without also explaining that you're using a non-standard probability distribution.

The worst-case distribution is always a point distribution that assigns all its probability to a single input. In other words, the worst-case probability distribution that makes the expected running time as large as possible is in fact just a single input: the input that makes the algorithm run as long as possible. Consequently, this kind of worst-case analysis coincides with the "standard" notion of worst-case running time. For this reason, there is no need for a special "name" for this; worst-case running time already covers it.

The same is true for best-case running time and the probability distribution that makes the expected running time as small as possible.
> 2 votes

---
Tags: time-complexity, average-case
---


# Question
Title: How can I find spans where the distance between two poly-lines is more or less than some threshold?
I have two poly-lines. I would like to find segments of these lines where the minimum distance between them is higher (or lower) than some threshold.

I.e. I want to find the parts of the lines highlighted in squiggly pink here:

My best attempt is to split each line into some equally sized segments, and then use dynamic programming to find the closest corresponding points on each line. This is efficient, and works, but will of course be off by some amount from the real points where the minimum distance is reached. Making the segments smaller will make the solution better (but slower), but I have a feeling a continuous and exact solution is possible?

# Answer
> 1 votes
Given a point $P$ and a polyline $L$, you can compute the distance from $P$ to $L$ (i.e., the distance from $P$ to the nearest point on $L$).

Now take the union of all of the following points:

* The endpoints of the line segments in the blue polyline
* For each endpoint of each line segment in the red polyline, the closest point on the blue polyline
* All intersection points where the blue polyline intersects the red polyline

This set can be computed efficiently, and its size is linear in the size of the input. Let $P\_1,P\_2,\dots,P\_n$ denote these points, in the order they appear on the blue polyline. Let $Q\_i$ be the point on the red polyline that is closest to $P\_i$.

Now consider any pair of consecutive points $P\_i,P\_{i+1}$. As we move along the blue polyline from $P\_i$ to $P\_{i+1}$, the distance to the red polyline will either increase monotonically or decrease monotonically. Thus, if it crosses the threshold (e.g., starts below the threshold and increases to something larger than the threshold), you can use binary search to find the point where it crosses the threshold.

In fact, we can say more. Consider a point $P = \alpha P\_1 + (1-\alpha) P\_{i+1}$, as $\alpha$ increases from $0$ to $1$, and let $Q$ be the nearest point on the red polyline to $P$. As $\alpha$ increases from $0$ to $1$, $P$ be moving along a straight-line path, i.e., along a single line segment of the blue polyline. Similarly, $Q$ will also e moving along a straight-line path, i.e., along a single line segment of the red polyline. Consequently, there's a simple formula for the distance between the two as a function of $\alpha$, and we can solve for the $\alpha$ that makes this distance equal to the threshold. Thus, this will let us precisely identify the point where the minimum distance between the two polylines is exactly equal to the threshold.

Now doing a linear scan over all consecutive pairs $P\_i,P\_{i+1}$ will enable you to find all places where the minimum distance is higher than some threshold, exactly.

---
Tags: computational-geometry, dynamic-programming
---


# Question
Title: Why a program written in the Intel assembly language cannot be executed on the PowerPC processor?
Why are these two architectures incompatible?

# Answer
> 3 votes
The PowerPC and Intel architectures vary individually in their various iterations, and are in many ways incompatible. This means the instruction sets for each will not be compatible, as well.

There are a lot of reasons why any two given architectures will not be compatible (register number/size, memory allocation schemes, processing unit differences, bus width, etc.), but at a basic level the instruction sets for the two architectures are different. You can look at the differences between them; using an iteration of each at random, the PowerPC instruction set and the Intel instruction set have different opcodes. So, even within different generations of an individual architecture family there is likely to be some incompatibility between any given assembly program, as the underlying opcodes can be different.

So, this question is a bit like asking why isn't someone who knows a human language x able to understand an animal call y? The underlying languages and structures of both systems are essentially different, while sharing some functionality at a high level. There are examples where the two share functionality and can overlap or communicate (honey birds in Africa and people who are able to call to them, people who can practice calls for various species, human use of artificial calls, etc.), but generally they are only vaguely similar in that they are both "languages," and one would not expect them to be 100% compatible.

---
Tags: computer-architecture
---


# Question
Title: How to find the symmetry group of a polynomial
Say I have a polynomial in $n$ variables of maximum degree $m$. I define its symmetry group to be the subgroup of the permutation group which fixes the polynomial when it acts on the variables. Example: $x^2+y^2+z$ has the subgroup $\langle(x,y)\rangle$. Given such a polynomial, what is the best way to find such a polynomial.

Usage Note: I need this algorithm to terminate in "a short amount of time" for $n$ about 15, $m$ about 10. Short being, I guess, less than 1 minute.

Partial progress: If all I do is test particular elements of $S\_n$, this problem is basically intractable as I need roughly $(n-2)!$ tests. Current implementation does basic checks such as the following. In my example $x$ cannot map to $z$ because $z^2$ terms do not exist. In this way we can eliminate much larger fractions of permutations. However, since $S\_n$ is so large, this approach is still too slow.

# Answer
There is a reduction from your problem to graph isomorphism, as explained in this question on Math Overflow. In particular, that answer shows how to obtain a random automorphism of the polynomial, i.e., a random permutation in the symmetric group. For example, you can start by randomly picking a pair of variables $x\_i,x\_j$ and testing whether there exists an automorphism that sends $x\_i \mapsto x\_j$; if so, you can search to find another variable $x\_k$ such that there exists an automorphism that sends $x\_i \mapsto x\_j$ and $x\_j \mapsto x\_k$; and so on until you obtain a complete permutation.

To obtain a set of generators for the symmetry group, you can repeat this search many times to obtain multiple random permutations known to be in the symmetry group; if you repeat enough times, with high probability, the resulting set will generate the entire symmetry group. Or, you can systematically enumerate the space of all permutations that are in the symmetry group; if the symmetry group is small enough, this will be efficient.

This requires us to have an oracle for solving graph isomorphism. Fortunately, there are existing graph isomorphism solvers that can solve typical instances of graph isomorphism very rapidly. For instance, you can take a look at nauty, a graph isomorphism solver that typically finishes within seconds on graphs with at most 100 vertices or so. The question on Math Overflow describes how to reduce the problem to isomorphism of colored hypergraphs; the nauty manual describes how you can convert this to an ordinary graph isomorphism problem, at the cost of some small increase in the size of the graph.

If you put all of this together, I expect it will be possible to construct an algorithm for your problem that is pretty efficient in practice, for polynomials of the size you describe.
> 3 votes

---
Tags: algorithms, polynomials, group-theory
---


title: When would one use equational dynamics?

text:
# Question
Title: When would one use equational dynamics?
I'm trying to sort out in my mind the different ways of assigning semantics to a programming language. There are two main methodologies: operational semantics and denotational semantics (I asked a previous question on the relationship between the two).

It seems to me that an operational semantics is the same as defining a dynamics for the language - that is, defining how programs are evaluated. I know two different ways of doing this: equational and structural.

A structural dynamics defines evaluation via a system of transition rules (I believe beta reductions are the canonical example). An equational dynamics only specifies reductions indirectly, by defining when one expression is equal to another. (I'm going through the trouble of defining these terms because I am uncertain how standard the terminology is).

But I can't figure out why both systems are needed. I personally prefer structural dynamics, but it feels very subjective. What are the advantages and disadvantages between the two systems?

# Answer
> 8 votes
What you call "equational dynamics" is not actually an operational semantics, it's an *equational theory*. As you note, equations by themselves do not tell us how to run programs. However, they are needed because we want to express the idea of *program equivalence*. For instance, an optimizer replaces a piece of code with an equivalent piece of code (which is hopefully more efficient). But what does "equivalent" mean here?

We can use *observational equivalence*: two programs are equivalent if we can make exactly the same observations about them. In other words, they behave the same way. This kind of equivalence is defined using operational semantics.

An alternative is to start by *prescribing* equivalences. We *want* certain programs to be equivalent, usually because we have some mathematical understanding of how things are supposed to work. For instance $\beta$-reduction $(\lambda x . e\_1) e\_2 = e\_1\[e\_2/x\]$ is an equation which expresses the mathematical meaning of $\lambda$-abstraction. In practice is is often easier to come up with equations than with an operational semantics. (For instance, when Matija Pretnar and I worked on Eff, we knew exactly what the equations were because we were actullay trying to turn equational theories into a programming language. Also, when Alonzo Church came up with the $\lambda$-calculus he wrote down equations that expressed the mathematical properties of functions and function application.) The problem then is to find an operational semantics which respects the equations, but at the same time does not introduce (too many) observational equivalences that are not implied by the equations.

---
Tags: programming-languages, semantics, operational-semantics
---


# Question
Title: Heap-like notation of a BST (BFT bit-vectors) for succinct representation
I'm researching the topic of succinct tree representations right now and came across this presentation. On slide 17 there is an example of heap-like notation of a BST (using BFT bit-vectors) and the author claims that the amount of bits needed to represent a tree of $n$ elements (without their values) is exactly $2n+1$.

According to my calculations, it's $2n-1$. Here they are:

1. As in this representation every BST is represented as a complete tree, for the complete tree of height $k$ it has $2^{k+1}-1$ nodes.
2. On average for $n$ nodes tree has a height of $log\_2n$.
3. Replacing the $k$ from the first list item with the average BST height from the second list item I received:

$$2^{log\_2n+1}-1=2n-1$$

What am I missing in my calculations? Where do these 2 extra bits come from?

Thanks in advance for your answer!

# Answer
You can count it like this:

Let $n$ be the original number of nodes

Each original node has 2 children after adding the external nodes.

So 1 bit for the original node and 2 for its children. Total $3n$ bits.

But we are over counting here because original node is child of one other original node. So we subtract $n$ and get $2n$.

But we over corrected the count because root node has no parent so we add back 1 bit.

$2n + 1$.
> 0 votes

---
Tags: binary-trees, search-trees, succinct-data-structures
---


# Question
Title: Recurrence for quaternary search algorithm
I have to come up with the recurrence for the quaternary search algorithm.

My initial thought is $T(n)=4T(\frac{n}{4})+c$ because the algorithm examines all four subproblems, and each is one quarter the size of the entire array. But this can't be right because that yields a complexity of $O(n)$. I looked on Google and the complexity of quaternary searches are supposed to be $\log\_4n$, but I don't know what the recurrence would be to get me that complexity.

Any help would be greatly appreciated. Thanks!

# Answer
The correct recursion formula is $T(n) = T(\frac{n}{4}) + c$, which yields $O(lgn)$. Because the base is 4 here, for quaternary searches it becomes $O(log\_4n)$.
> 0 votes

# Answer
Your recurrence is wrong, which is why you get the wrong answer. I suspect that the reason your recurrence is wrong is that you don't quite understand the algorithm. Try mimicking your reasoning on binary search until you successfully get the correct running time in that case.

Moreover, as mentioned in the comments, the running time (assuming constant-time comparisons and the RAM machine model) is $\Theta(\log n)$, but cannot get more accurate than that. To get $\log\_4 n$ you need to count something more specific, such as the number of comparisons performed by the algorithm.
> 2 votes

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Inputting a superposition into a cNOT gate
I am unsure how to calculate what happens when you put a superposition as the control qubit into a cNOT gate or what happens when you put a superposition as the target qubit into a cNOT gate. I know what matrix represents the cNOT and I know that each superposition would be represented by $\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle$, but would you take these two four dimensional vectors and multiply them both by the cNOT matrix? If so, in what order? I just don't quite understand.

Any help would be appreciated. Thanks!

# Answer
> 4 votes
This is more of a question on linear algebra rather than a question about quantum computation. You should probably have a firm grip on basic linear algebra (vector spaces, linear operators, inner product, etc) before delving into quantum computation (there's no way around it).

CNOT is a linear operator in our vector space, $\mathbb{C}^4$ (were only dealing with linear transformations, specifically unitary). In order to specify how a linear transformation operates on an arbitrary vector, it is enough to specify how it operates on each member of a basis for our vector space. Suppose we apply some linear operator $T$ on an arbitrary superposition, then by linearity:

$T\left(\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle\right)= \alpha T|00\rangle+\beta T|01\rangle + \gamma T|10\rangle + \delta T|11\rangle$

$T|ij\rangle$ is the application of the operator $T$ on the vector $|ij\rangle$. The application of a linear operator in a finite dimensional vector space can be described by matrix multiplication, so this means multiplying the matrix representing $T$ by the vector $|ij\rangle$. The "order" you refer to does not matter, because addition in a vector space is commutative.

Since you know how to apply CNOT to the four basic states, the above equality shows you how to apply it on an arbitrary superposition.

When talking about matrix representation, the vector $\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle$ is represented by $ \begin{pmatrix} \alpha\\ \beta\\ \gamma\\ \delta \end{pmatrix} \in\mathbb{C}^4$, so applying CNOT to this state means multiplying it's matrix by this vector, i.e.

$CNOT\left(\alpha |00\rangle + \beta|01\rangle+\gamma|10\rangle+\delta|11\rangle\right)= \begin{pmatrix} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{pmatrix} \begin{pmatrix} \alpha\\ \beta\\ \gamma\\ \delta \end{pmatrix}= \begin{pmatrix} \alpha\\ \beta\\ \delta\\ \gamma \end{pmatrix} $.

This is obviously equivalent to applying CNOT to each of the four vectors in $\mathbb{C}^4$ and adding up the results.

---
Tags: logic, quantum-computing, linear-algebra
---


# Question
Title: How to find whether a grammar is ambiguous?
$$S\rightarrow aAB$$ $$A\rightarrow bBb$$ $$B\rightarrow A|\epsilon$$

I'm choosing the string abbbb.

First left most derivation is the following:

$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abebB\Rightarrow abebA\Rightarrow abebbBb\Rightarrow abebbeb = abbbb$$

Second left most derivation is the following:

$$S\Rightarrow aAB\Rightarrow abBbB\Rightarrow abAbB\Rightarrow abbBbbB\Rightarrow abbebbB\Rightarrow abbebbe = abbbb$$

Can someone tell me whether I'm correct in saying that the grammar is ambiguous?

This question has been taken from chapter 5 of "An Introduction to Formal Languages and Automata" by Peter Linz 5th Edition. The question states to prove that the grammar is **unambiguous** (however it is not). Hence, the aim of posting this question is to make sure that I've understood ambiguity and distinction between parse trees properly. I'm studying formal languages on my own and do not have the luxury of an instructor.

# Answer
> 4 votes
Since you are trying to prove that the *grammar* is ambiguous, you must simply provide an example of a string where that grammar results in more than one parse tree or derivation. (Note that this is an entirely different ordeal than trying to prove that a grammar is unambiguous.) Since the string abbbb indeed has two distinct leftmost derivations, you have shown that the grammar is ambiguous. This proves that the grammar is *not* *un*ambiguous since it is not the case that each string has at most one parse tree or derivation.

---
Tags: formal-languages, automata, formal-grammars, ambiguity
---


title: Expected versus Randomized

text:
# Question
Title: Expected versus Randomized
Is there any difference between expected polynomial time and randomized polynomial time algorithm?

# Answer
*RP* (randomized polynomial time) is a complexity class for algorithms that *always* run in polynomial time, while possibly make truly random choices, and always rejecting correctly while usually accepting correctly (i.e., with probability greater than $\frac{1}{2}$).

Expected polynomial time usually means that the complexity is polynomial time only in expectation, and the answer is always correct.

Suppose you have the following (silly) algorithm to check if the first element, in an array with length *n*, is the maximum:

1. Scan the array, check if the first element is maximum.
2. With probability $\left(\frac{1}{2}\right)^n$, uselessly scan the array an additional $\frac{2^n}{n}$ times, and recheck the result of step 1.
3. Return the answer from 1 in any case.

This algorithm has expected polynomial time. The cost of the first step is $\Theta(n)$. The expected cost of the second step is $\Theta\left( \left(\frac{1}{2}\right)^n n \frac{2^n}{n}\right) = O(1)$. The cost of the third step is constant. Conversely, it is not in *RP* because the second step can run in time $\Theta\left( 2^n \right)$ for an unfortunate randomized outcome.
> 3 votes

---
Tags: algorithms, randomized-algorithms
---


# Question
Title: Can Breadth-First Search be Implemented Recursively without Data Structures?
I'm in a data structures course, but our current unit discusses recursion and not data structures, and I need to implement breadth-first recursion for the purpose of finding the shortest path through a maze. Is there a way to do this just using the basic structure of recursive calls and base cases? Or will I need data structures such as queues or stacks to implement breadth-first recursion?

# Answer
> 9 votes
You basically have two choices: "cheating" by embedding a queue in the nodes, and simulating BFS with higher complexity.

---

**Embedded-Queue Cheating**

If you look at virtually any description of BFS, e.g., this one on Wikipedia, then you can see that the algorithm adds attributes to nodes. E.g., the Wikipedia version adds to each node the attributes `distance` and `parent`.

So, even if you aren't allowed to use some clearly-cut external queue data structure, you can easily embed one using node attributes:

```
def BFS(G, root):
    for each node in G:
        n.distance = inf
        n.parent = None
        n.next = None

    root.distance = 0
    head = tail = root

    while head is not None:
         current = tail
         tail = tail.next

         for each node adjacent to current:
             if n.distance == inf:
                  n.distance = current.distance + 1
                  n.parent = parent
                  head.next = n
                  head = head.next
                  if tail is None:
                       tail = head

```

Note that the above code is iterative, but it's trivial to make it recursive.

---

**Higher-Complexity Simulation**

It's possible to run BFS recursively without any data structures, but with higher complexity. DFS, as opposed to BFS, uses a stack instead of a queue, and so it can be implemented recursively.

Suppose we modify DFS so that it takes a `max_depth` parameter:

```
 MaxDepthDFS(G, s, max_depth)

```

It should perform DFS until it reaches the first unvisited node at `max_depth` level, and returns whether it indeed found such a node. Then we could write the following variation of BFS:

```
 def BFS(G, s):

     depth = 0
     for i = 0, ..., |V|:
         if not DFS(G, s, depth)
             depth += 1

```

Again, note that the above code is iterative, but it's trivial to make it recursive.

---

Besides such (cheap) tricks, you cannot run BFS, as it uses a queue, and not a stack. Say, to the contrary, you have a recursive function

```
BFSVisit(G, s, current, more)

```

and consider the case where $s$ has $m$ neighbors. Then at the $m$th invocation, `more` needs to carry $\omega(1)$ information, and thus is already a data structure.

---
Tags: algorithms, data-structures, recursion, graph-traversal
---


# Question
Title: Complexity of parity game solving compared to PLS, PPA, and PPAD
Since parity game solving is in TFNP ("Total Function Nondeterministic Polynomial") (and the decision version is is NP ∩ coNP), I wonder whether it is contained in PLS ("Polynomial Local Search") or PPA ("Polynomial Parity Argument")? Add PPP ("Polynomial Pigeonhole Principle") if you want, even so this would probably mean that it is already contained in PPAD ("Polynomial Parity Arguments on Directed graphs"), and hence in PPA.

Or is it rather the other way round and parity game solving can be shown to be hard for PLS or PPAD? But that would be surprising, since a recursive algorithm that solves parity games is known (even if it is not efficient in the worst case).

---

**Edit 12 March 2017:** I recently learned that parity game solving has been shown to be possible in quasipolynomial time. Here are the quoted references:

> Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan.
>
> A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus Ibsen-Jensen.
>
> Succinct progress measures for solving parity games, by Marcin Jurdziński and Ranko Lazić.

An implementation and comparison with previous approaches is available (classic strategy improvement "wins" on random instances, but gets "slow" on Friedmann’s trap examples):

An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space, by John Fearnley, Sanjay Jain, Sven Schewe, Frank Stephan, Dominik Wojtczak

# Answer
> 2 votes
Yes, solving parity games is known to be in PPAD (and thus PPA and PPP too) and PLS, and is thus unlikely to be hard for either (since this would imply containment of one of these classes in the other).

See, e.g.,

Daskalakis, Constantinos, and Christos Papadimitriou. "Continuous local search." Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 2011.

and combine the membership of Simple Stochastic Games (SSGs) in CLS (which is in PPAD and PLS) with the well-known observation that solving parity games can be reduced to solving SSGs in polynomial time.

The reason that these problems are in PPAD is that they admit "optimality equations", rather like Bellman equations, that characterize solutions as fixed points. The reason these problems are in PLS is that they can be solved with local improvement algorithms like strategy improvement (a two-player generalization of policy iteration for MDPs).

---
Tags: complexity-theory, game-theory, game-semantics
---


# Question
Title: Do finite state machines need transitions for all symbols?
I want to know if I want to draw up a finite state machine, say for example binary strings and I want a finite state machine that accepts only one kind of binary string e.g: 0110. Do I, for each state have to account for another symbol of the binary language being read during transition. Like for the first transition, this will be caused by 0 being read, but what if a 1 is read...do I have to implement a trap state or do I just not account for the fact that a 1 could be entered 1st?

# Answer
Your question isn't entirely clear but it's easy enough to just list all the possible answers that could arise, depending on exactly what you mean.

If you're asking about nondeterministic finite automata (NFAs) then you don't need to account for every symbol. The rule is that, if you're in a state and you encounter a symbol that has no transition, then that branch of the computation rejects immediately.

If you're asking about deterministic finite automata (DFAs), then it depends on exactly what definition you're using. The classical definition (e.g., in Sipser) is that every state must have *exactly one* transition for each possible symbol. In that interpretation, you need a trap state, since you must specify what happens for every possible symbol you could read. Other authors, though, say that each state of a DFA has *at most one* transition for each symbol. In that case, you don't need a trap state: as with an NFA, if you read a symbol that has no transition, you reject.
> 5 votes

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


title: Horspool's String Search on 0s and 1s

text:
# Question
Title: Horspool's String Search on 0s and 1s
I'm confused in trying to solve the following problem:
Find the number of comparisons made by Horspool's string search algorithm in the following case:

String: `001001001001`
Pattern: `111`

**Attempt 1**
The shift table value for `0` as per the algorithm should be 3 i.e. length of the pattern, because `0` is not part of the pattern.

`001001001001`
`111`

`001001001001`
`---111`

... and so on. This leads to 2 comparisons in each of the 4 shifts i.e. *8 comparisons*.

**Attempt 2**
Instead, the answer, and also my intuition, suggests *5 comparisons*:

`001001001001`
`111`

`001001001001`
`--111`

`001001001001`
`-----111`

... and so on. 2 comparisons needed in the first run and only 1 in each of the following 3 shifts i.e. total of 5.

Intuitively, it makes sense NOT to slide along the pattern 3 spaces \[attempt 1\] in the first run of the algorithm because we are not taking into account that the first character of the pattern - `1`\- is the same as the last character of our previous string match block - `001`.

I would like help in correcting my understanding of the algorithm.

# Answer
> 3 votes
Both - attempt 1 and 2 - are incorrect executions of the Horspool's algorithm. After the first round of trying to match the pattern in the text:

`001001001001`
`111`

There are *two comparisons* made of which the second one `0 == 1` fails. Now, the shift is determined **by the last character in the section of the text being matched** i.e. shift value of `1` which is 1. The next search round looks like:

`001001001001`
`-111`

This has only *one comparison* `0 == 1` which fails. The shift is now decided by the value of shift value of `0` which is 3, thus making the next round as follows:

`001001001001`
`----111`

This also has only *one comparison*, just like the previous one resulting in another shift of 3. The next round is also the same, with *one comparison*.

The total now, correctly, stands at 5.

---
Tags: algorithms, strings, exact-string-matching
---


title: What problems are solvable in Datalog?

text:
# Question
Title: What problems are solvable in Datalog?
Datalog is not Turing complete. It does however have the wonderful property of not being order sensitive. What problems can be solved in Datalog? Where does it fit in the Chomsky hierarchy, i.e. what abstract machine does it model?

# Answer
According to these slides, deciding whether a single atom is generated by a Datalog program is EXPTIME-complete. There are several corresponding machine models, for example an EXPTIME Turing machine or an EXPTIME RAM machine.
> 5 votes

---
Tags: computation-models, chomsky-hierarchy
---


# Question
Title: How does the CPU form the binary representation for a number?
More generally, how those translating softwares, for example, an assembler, like *nasm*, know how to transform in machine code the number "10", from this command: `add marks, 10`.

I know there is other things that needs to be comprehended about compilers, but I can't find some intuitive explications, like the addition of two numbers, where there were implemented logical gates which deal with those operations.

Specifically, which hardware resources are involved in creating the binary form of a number?

# Answer
Numbers are translated according to the encoding supported by the architecture, usually 2's complement for signed integers, and regular unsigned binary encoding for unsigned integers in modern computers. There exist deterministic algorithms for translating a decimal number into binary form and back.

The compiler will perform these algorithms on the character constants it reads from the source code (most likely in a text encoding), and then use some sort of procedure or function to translate them into binary form. Compilers will also usually reduce expressions to constants if possible as a part of their optimizations (e.g. 10 \>\> 2 becomes 2).

One possible function for, say, compilers written in C might be the `atoi()` function from the C Standard Library, which translates a string of ASCII characters into an `int`. This `int` will have an implementation-specific encoding, but is usually 2's complement these days.

Since the translation of text to binary encoding is implementation-specific, the terms of how it actually does it (whether in software or hardware) is not guaranteed. However, usually the translation will just take place as a procedure written in software to run on top of the more basic hardware instructions (e.g. a direct ASCII --\> binary integer representation may not exist on something as simple as 32-bit MIPS, but there will be an `atoi()` function for a C Standard Library on MIPS).
> 1 votes

# Answer
The translation of constants in their decimal form is done during the *parsing* stage of the compilation process.

In the parsing stage, the compiler executes code that transforms the text file into a compiler-internal representation of the program. The parser has a set of rules that tell it when to expect a number. Numbers are translated into binary form by a compiler functions that a programmer once wrote.

An assembler has internally a list of opcodes and the parameter types of the architecture. It will try to match the line with one of the type classes. So it will, for example, accept the line "add eax, 3" if and only if there is an opcode for adding a constant (of some length) to a register. The string "3" can only be a number, so it will be parsed as such.

About the additions: There are two cases to be considered. Modern compilers can often perform arithmetic operations between constants at compile time. So if a C program contains the phrase "10+20", then the machine code will contain a "30" instead. In all other cases, the generated program will contain an addition operation in the binary opcode format of the processor that the program is supposed to run on. So the addition is just forwarded to the processors built-in addition command.

How an addition is implemented in a process is a classical topic in computer architecture. The respective Wikipedia page contains an overview.
> 1 votes

---
Tags: computer-architecture, arithmetic, number-formats
---


# Question
Title: Using existential quantifier within implication
I had used an existential quantifier within an implication, as below:

$$\exists ~ \sigma\_{opt}~~~ \wedge~~~ n \in R^{+}~ ,~0\<n\<1 \rightarrow ~~ \sigma\_{opt} = n$$

I've, recently, found that it is illegal to do that and just universal quantifier could be used in this situation. Could anybody explain the reason?

# Answer
> 5 votes
Your statement attempts to be express in formal logic the following sentence:

> There exist $\sigma\_{opt}$ and $n$ in $R^+$ such that if $0 \< n \< 1$ then $\sigma\_{opt} = n$.

The attempt at translation goes about by replacing English words by mathematical symbols, while keeping English syntax. Unfortunately, that is not how this sort of translation works. Just as when translating between human languages the syntax needs to be changed, here as well you have to conform to the syntax of statements in predicate logic. Your statement is, unfortunately, ungrammatical (more formally, it is not *well-formed*, that is, it is not a *wff*).

The syntax of sentences in predicate logic is described in many sources, so let me just mention that the following sentence is valid: $$ \exists \sigma\_{opt} \in R^+ \exists n \in R^+ \\; (0 \< n \land n \< 1) \to \sigma\_{opt} = n. $$ We often allow shortcuts to be used, and so consider the following statement to be valid as well (standing for the former statement): $$ \exists \sigma\_{opt},n \in R^+ \\; 0 \< n \< 1 \to \sigma\_{opt} = n. $$ You are using a different shortcut for folding the two existential quantifiers, but your convention is not standard; it's better to use standard conventions, unless there's a good reason to deviate from standard practice.

Finally, I'm not sure what your statement is supposed to express, but it probably doesn't express what you were hoping for: it doesn't depend on any parameter (this is why it's a statement rather than just a formula), which was probably not your original intention.

---
Tags: logic, first-order-logic
---


# Question
Title: Showing that u#v with u a substring of v is not context-free
I need to find whether this language is context-free or not:

```
{u#v | u,v belong to {a,b,c}* and u is a substring of v}, over alphabet {a,b,c,#}

```

I suspect that it's not, and am trying to approach it via Pumping Lemma, but then I noticed that: any examples like a^n#a^n will not work, cos we can always make vwx in the second a^n such that after pumping, u is still a substring of v; then I tried playing around with # like a#ab^(n-3), but get lost with the choice of v and x since it's possible for one of them to be empty string.

This is homework so just a hint will be okay for me.

# Answer
> 1 votes
Okay I got confused when developing my ideas, and a simple example using Pumping Lemma would be: $a^nb^n\\#a^nb^n$. Consider this: clearly $v$ and $x$ cannot contain $\\#$, otherwise when pumping more or less $\\#$ appear and the new string is not in the language. Now suppose $vwx$ are in the left $a^nb^n$, then $v^2$ and $x^2$ will make it longer than the R.H.S.; then if $vwx$ are in the right $a^nb^n$, then $v^0x^0$ will make the R.H.S. shorter than the left. This gives us the only possibility that $v$ in the first $b^n$ and $x$ in the second $a^n$, and clearly no matter how you pump it the new string cannot be in the same language, and this solves the problem.

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


# Question
Title: Which of the choices displayed is not a possible order in which Depth-First search could mark the vertices of the graph displayed as visited?
Which of the choices displayed is not a possible order in which Depth-First search could mark the vertices of the graph displayed as visited ?

# Answer
This looks like a homework problem to me. Anyways, the answer would be (D), as vertex 'c' has to be visited before vertex 'b' This is because while recursing, when the root is set to be vertex 'd' all of its children ('c') have to be visited before we can visit the next child ('b') of the parent node ('a').
> 2 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: A dynamic programming problema on containers and product
We have two production lines - product and container (two integer arrays product\_list\[N\] and container\_list\[M\]). If the volume of a container is equal or larger than that of a product, then we could put the product into that container.

We want to put as many products into containers as possible.

We can pick any initial position of products (any i in product\_list array), and match each container one by one. We can't skip product but we can skip containers. No recurring of arrays i.e. product line won't go back if reach the end.

My solution is that, start from first product until last product (for i = 0; i \< N), then match the container list from 1st to the last (for j = 0; j \< M). For each starting point i, count the number of matched products (count\_array\[i\]+1 if container\_list\[j\] \>= product\_list\[i\]). Finally output the maximum of the count array.

I believe my algorithm isn't optimal, but I can't come up with a better way to do this problem in dynamic programming.

Any help will be appreciated! Thanks for everyone reading this problem!

# Answer
> 2 votes
Here is one approach, I could think of.

$T(x, y) = $ The maximum number of products which could be put into containers if we start at position $x$ in **container** line, whereas position $y$ in the **product** line.

If $size(C\_x) \>= size(P\_y)$ we can either choose or skip the container. Else if the size of container is smaller, since we cannot skip the product, we would have to skip the container.

Hence, the recursion would be: \begin{equation} T\[x, y\]=\begin{cases} max(1 + T\[x+1,\hspace{1mm} y+1\], \hspace{2mm} T\[x+1,\hspace{1mm} y\]), & \text{if $size(C\_x) \>= size(P\_y)$}.\\ T\[x+1,\hspace{1mm}y\], & \text{otherwise}. \end{cases} \end{equation}

Starting from the end of both the arrays, $$max(T\[1,i\]) \hspace{2mm}: \hspace{2mm} 1\<=i\<=n$$ should have the required result.

http://ideone.com/3dsrZu

---
Tags: algorithms, dynamic-programming, linear-programming
---


# Question
Title: What crossover operator should I use for arranging students in classrooms?
I am building a genetic algorithm to solve a "classroom map" problem. The goal is to place correctly students depending on several factors (shortsighted students, turbulent students...).
Here, the genomes is the classroom layout, each classroom has a fixed blackboard and tables positions, what varies is the position of the students.
Now, if I want to cross two classrooms genomes, I can't simply mix both together, otherwise, say that on genome A student "Bob" is on table #3, and that on genome B the same student "Bob" is on table #15, and that the "child genome" gets table #3 from genome A and table #15 from genome B, then, "Bob" would be on two tables at the same time... no really great.

How can I solve this issue ?

Thank you.

# Answer
> 5 votes
What you're (probably) doing:

```
0 = Bob
1 = Mary
2 = John
3 = Susan

parents
[2 | 1 | 0 | 3] => John takes first seat, ..., Susan takes fourth seat.
[3 | 2 | 1 | 0] => Susan takes first seat, ..., Bob takes fourth seat.
       ^
one point crossover
[3 | 2 | 0 | 3]   Where is Susan? (and Mary?)
[2 | 1 | 1 | 0]

```

What you can do:

* allow the generation of an invalid chromosome / individual assigning a **very low fitness value**. Such individual will be penalized (ignored) during evolution.

This is very time consuming and not effective
* **repair** an invalid chromosome. It's time consuming but it could work
* use ***ad-hoc* operators**.

E.g. with **Partially Matched Crossover**:

<sup>(from Genetic Algorithm)</sup>

PMX builds an offspring by choosing a subsequence from one parent preserving as many positions as possible from the other parent.

> 1. A subsequence is delimited by two cut points. After this, the segments between the cut points are swapped (the positions in yellow). We have the map: 1↔8, 9↔5, 8↔7 and 6↔3.
>     2. Fill the positions for which there is no conflict. In the example shown, the positions `4` and `2` in both chromosomes (the positions in blue).
>     3. Use the map to fill the remaining positions (the positions in green). Note that using the mapping 1↔8 in the `o1` vector a conflict occurs again so one must apply the mapping 8↔7 to obtain a number not repeated.

Other operators are listed in Crossover for ordered chromosomes but pay attention to the fact that some operators tend to preserve the relative positions more than the absolute positions.
* **change point of view / representation**.

E.g. `[2 | 1 | 0 | 3]` or `[3 | 2 | 1 | 0]` are permutations. Standard GA crossover operators produce offspring which aren't permutations. A clever representation of permutations could avoid the problem.

You can represent a permutation as its inversion sequence: for each element `i`, store in `a[i]` how many elements larger than `i` are to the left of `i` in the permutation.

The only constraint on `a[i]` is that it cannot be larger than `N - i` (`N` is the number of genes).

Now standard crossover of two valid inversion sequences always produces two valid inversion sequences: no need for special handling of repeating elements.

This idea is described in Genetic Algorithm Solution of the TSP Avoiding Special Crossover and Mutation (Göktürk Üçoluk).

# Answer
> 0 votes
Simple. Don't do the Crossover;it's not necessary. Just use mutation.

---
Tags: algorithms, optimization, genetic-algorithms
---


# Question
Title: The extension of a code is itself a code
I'm reading Cover's "Elements of Information Theory" and I have a problem with the definition of uniquely decodable code.

> A code is said to be singular if there exist two elements that map to the same string. In other case it is said to be non singular.
>
> Let $C$ be a code. The extension of $C$ is the homomorphism $C^{\*}$ between $\chi$ and $D$ with respect to concatenation that is, $C(x\_1 \> \cdots x\_n) = C(x\_1) \cdots C(x\_n)$.
>
> Let $C$ be a code. $C$ is uniquely decodable if its extension $C^{\*}$ is non-singular.

According to the last definition the extension of a code is itself a code but as it has domain $\chi^{\*}$ where $\chi \subseteq \mathbb{R}$ (that last statement is mine).

How can I view the extension as a code?

# Answer
> 1 votes
Cover and Thomas are using here the following definition of a code: given a domain $D$ and an alphabet $A$, a code is a mapping from $D$ to $A^\*$. That is, a code assigns every element of $D$ a word over $A$. The extension of the code is a code from $D^\*$ to $A^\*$ defined by concatenation.

For example, let $D = \\{a,b\\}$ and $A = \\{0,1\\}$, and consider the code $C$ given by $C(a) = 0$, $C(b) = 00$. Its extension $C^\*$ is a function from $\\{a,b\\}^\*$ to $\\{0,1\\}^\*$ obtained by replacing each $a$ by $0$ and each $b$ by $00$. For example, $C^\*(ab) = C(a)C(b) = 000$. Since $C^\*(ba) = C(b)C(a) = 000$ as well, the code $C^\*$ is singular.

A code $C$ is *uniquely decodable* if there do not exist two sets of words $x\_1\ldots x\_n$ and $y\_1\ldots y\_m$ such that $C(x\_1)\ldots C(x\_n) = C(y\_1)\ldots C(y\_m)$. This is exactly the same as saying that $C^\*$ is non-singular, since the condition is completely equivalent to $C^\*(x\_1\ldots x\_n) = C^\*(y\_1\ldots y\_n)$.

---
Tags: information-theory, coding-theory
---


# Question
Title: (Possibly Easy) Formal Language Question
I am looking at a "practice test" for a Theory of Computation class. It was a test in a previous year.

I am asked to prove that, given L1 and L2 are regular, the union and difference are both regular.

It seems to me that for the union, since all the members of each separate set are regular, and the union consists exactly of all those members, therefore the union is regular.

And since the difference (L1-L2) is just a subset of L1, it is also regular.

This seems awfully straightforward and skips a lot of process.

Is it correct or am I missing something?

# Answer
The reasoning you give is not formal enough. For the union case, you're just restating the theorem "the union of regular sets is regular since the union of regular sets is regular"; for the difference case, your assertion "a subset of a regular language is regular" is false ($\Sigma^\*$ is regular and every language is a subset of $\Sigma^\*$).

Regular languages are defined in terms of finite automata. The general approach to a proof is that you look at the definitions of what is given (L1 and L2 are regular, so there are automata...) and show a logical reasoning from that to the definition of what you want to prove (there is an automaton ... therefore L3 is regular).
> 9 votes

# Answer
Your question is based on a category error. You say "all the members of each separate set are regular" but that statement doesn't make sense. The members of the sets L1 and L2 are *strings* but regularity is a property of *languages*.
> 5 votes

---
Tags: formal-languages
---


# Question
Title: Why is the running time for BFS $O(b^{d+1})$?
In my Artificial Intelligence class, in a section on Uninformed Search Algorithms, the textbook for the class (and as was discussed in lecture) the running time for Breadth First Search is listed as being: $O(b^{d+1})$ with the following explanation:

Normally (or at least in my experience thus far in Algorithms) I've seen the running time of BFS to be $O(V+E)$ so why is it different here. Is this a special case?

# Answer
> 9 votes
This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to solve.

The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits everything in the graph. We measure the number of vertices ($V$) and the number of edges ($E)$, and the running time is measured in terms of these two parameters. Also, the algorithms community usually analyzes the case where we *run BFS until every vertex in the graph has been visited*. If this is the goal, and those are the parameters we care about, the running time to visit every vertex is indeed $O(V+E)$.

The artificial community typically considers a different scenario: we have an infinite or very large graph, and we're not going to visit all of it; we're going to visit only a tiny fraction of the graph, only as much as necessary until we can find one node with a particular property (a target node / goal node). Think of the state space of a game like chess, or the 15-puzzle, or something like that. In addition, in the cases that typically arise in artificial intelligence, usually the portion of the graph that we're going to visit looks sorta like a tree: each vertex has on average about $b$ edges leading out of it. So in this situation, a bound like $O(V+E)$ is not helpful: it is a valid *upper bound*, but it is extremely loose -- the number of states (vertices) you actually need to visit might be much smaller than the total number of states (vertices) that exist. So, in AI applications, we usually want a better estimate of the number of states visited. That's what leads to the $O(b^d)$ estimate.

Both upper bounds are valid, in the situation where they apply. But the two situations they're focused on are very different. It's the same algorithm (BFS), applied in two different contexts... and because of some differences in the characteristics, it makes sense to measure its running time differently in the two settings.

# Answer
> 8 votes
The bounds $O(|V|+|E|)$ and $O(b^d)$ are talking about different things. The former is appropriate when you know what $V$ and $E$ are in advance, and they're both finite. The latter is appropriate when the graph is only defined implicitly and may be infinite, or where you've decided in advance that you're only going to search to a fixed depth.

An example of the case where the $O(b^d)$ bound is appropriate is chess.1 Here, you're not given the state graph: rather, you're given the initial position and the rules to generate new positions from wherever you are at the moment. The number of reachable positions is so large that a bound of $O(|V|+\cdots)$ is meaningless. For the same reason, we're not going to search the whole graph for checkmate. Instead, we'll fix some depth $d$ and say, "OK, looking $d$ moves ahead, what's the best position I can reach?"

---

1 The adversarial nature of chess means you have to use minimax rather than BFS, but the principles are the same, as they apply to this question. Using BFS would assume that your opponent is co-operating to help you win as quickly as possible.

# Answer
> 3 votes
$O(b^d)$ is a correct if crappy (read: rough) bound: it bounds the number of nodes from above with the complete tree with height $d$.

Since $\log n \leq d \leq n$ (with $n$ the number of nodes), you can see that the bound is tight for $d \in \Theta(\log n)$ but is not for $d \in \omega(\log n)$.

Don't let this source confuse you: BFS, if implemented in a reasonable way, has running time in $\Theta(n)$ (on trees) and space usage in $O(n)$ (proportional to the maximum level width, in fact).

# Answer
> 2 votes
It seems that the author later addresses what D.W. and David said, at section **3.3.2**, Artificial Intelligence: A modern approach, 3rd Edition.

> Time and space complexity are always considered with respect to some measure of the problem difficulty. In theoretical computer science, the typical measure is the size of the state space graph, $|V | + |E|$, where **V** is the set of vertices (nodes) of the graph and **E** is the set of edges (links). This is appropriate when the graph is an explicit data structure that is input to the search program. (The map of Romania is an example of this.) In AI, the graph is often represented implicitly by the initial state, actions, and transition model and is frequently infinite. For these reasons, complexity is expressed in terms of three quantities: **b**, the branching BRANCHING FACTOR factor or maximum number of successors of any node; **d**, the depth of the shallowest goal DEPTH node (i.e., the number of steps along the path from the root); and **m**, the maximum length of any path in the state space. Time is often measured in terms of the number of nodes generated during the search, and space in terms of the maximum number of nodes stored in memory. For the most part, we describe time and space complexity for search on a tree; for a graph, the answer depends on how “redundant” the paths in the state space are.

---
Tags: algorithm-analysis, runtime-analysis, search-algorithms, trees, graph-traversal
---


title: Equivalent definitions for subgraph

text:
# Question
Title: Equivalent definitions for subgraph
I know that a graph G' is a subgraph for G if V(G')⊆V(G) and E(G')⊆E(G).

Today my professor wrote that G' is a subgraph for G if G' is a graph and V(G')⊆V(G), and then he told us that this definition is equivalent to the one we've seen before (= the first line in this post).

However, I don't think that these definitions are equivalent. In fact, if this is G:

```
       2
     /   \
    1     3

```

and this is G':

```
    1 - 3

```

we have that G' is a subgraph for G according to the second definition (wrong), while it is not according to the first one (right).

Am I missing something or was the professor wrong?

# Answer
The alternative definition that you attribute to your professor is wrong, as your counterexample clearly shows.

I hope your professor actually said something else and you misunderstood him/her!
> 2 votes

---
Tags: graphs
---


# Question
Title: Solution to the recurrence T(n) = 2T(n − 3)
We were asked the following question in our exam:

Solve or bound the recurrence `T(n) = 2T(n − 3)` for `n>3` provided `T(1) = T(2) = T(3) = 1`.

How do I go about solving this type of recurrence? For a normal recurrence of the form `T(n) = 2T(n - 3) + cn`, I would have considered `cn` to be the root and then solved the remainder of the tree. However, since the constant term is missing here, it means that the work done in each recursive call is 0. So, what would be the time complexity? Is my understanding incorrect?

Thanks for you help!

P.S.: This is not this, because this one has the constant term missing.

# Answer
It is easy to see the first nine terms of $\small T(n)$ is:

$$ \small \begin{array}{|c|c|c|c|c|c|c|c|c|} \hline \color{red}{T(1)} & \color{blue}{T(2)} & \color{olive}{T(3)} & \color{red}{T(4)} & \color{blue}{T(5)} & \color{olive}{T(6)} & \color{red}{T(7)} & \color{blue}{T(8)} & \color{olive}{T(9)} \\ \hline 1 & 1 & 1 & 2 & 2 & 2 & 4 & 4 & 4 \\ \hline \end{array} $$

> **Observation**: For integer $\small k \geq 0$, $\small T(3k+1) = T(3k+2) = T(3k+3)$. You can prove it by induction, where the base case is $\small T(1) = T(2) = T(3)= 1$.

Given $\small n$, let $\small k$ be the smallest integer with $\small 3k \geq n$. In other words, $\small k = \lceil n / 3\rceil$. By the observation above, $\small T(n) = T(3k)$. Therefore, we have $$ \small T(n) = T(3k) = 2\cdot T(3(k-1)) = 2^2\cdot T(3(k-2)) = \cdots = 2^{k-1}T(3) = 2^{k-1} = 2^{\lceil n / 3\rceil - 1} $$
> 3 votes

---
Tags: recurrence-relation, recursion
---


# Question
Title: Can A still be a key if two tuples are the same
I am studying database functional dependency. It says if A can functionally determine all other attributes, it is considered to be a key.

What if 2 tuples are exactly the same, can we still say A is a key? To me A cannot determine an unique tuple.

# Answer
> 3 votes
Pragmatically, You are correct that when you declare something as a primary key, that it must correspond to one tuple. Databases will not allow you to store a tuple in a table if the primary key already exists for a tuple in the table.

Theoretically, If $R$ is a relation with the following set A of attributes $\\{a\_1, a\_2,..., a\_n\\}$, then a primary key on the relation $R$ would be a subset $P \subset A$ such that for $F:P \rightarrow A$, we have $\forall x,y \in P $ $F(x)=F(y) \rightarrow x=y$. This basically just means that the primary key forms a one-to-one mapping from the domain of keys to the range of corresponding tuples.

If you have that two tuples are the same $A$ and $B$, then this implies that $A = B$,and we still have that $F(A)=F(B)$ so that there is no violation, in that sense.

# Answer
> 1 votes
"What if 2 tuples are exactly the same ?"

If you are using relational database model, all tuples (rows) are unique. No two tuples(rows) can be same in a relation (table).

---
Tags: terminology, database-theory
---


# Question
Title: Finding the Candidate Keys of a Relation Using the FD's
I have definitely checked out many different related posts. I have also done different sample problems from online sources as well from a similar problem. However, I am stuck on the problem below specifically.

> Given the following relation $R$ and the set of functional dependencies $S$ that hold on $R$, find all candidate keys for $R$. Show your work.
>
> $R(A, B, C, D, E, F)$
>
> $S:$
>
> $AB \rightarrow C$
>
> $AC \rightarrow B$
>
> $AD \rightarrow E$
>
> $BC \rightarrow A$
>
> $E \rightarrow F$

Initially, I broke the attributes into groups: attributes found only on the left, only on the right, and on both sides (they are $D$, $ABCE$, and $F$ respectively). I also know that I should try to compute the closure of $D$. This is where I get stuck. At first glance, this seems like I am unable to solve this problem, which isn't true. I also tried computing the closures of $(AD)$, $(BD)$, $(CD)$, and $(ED)$ because I thought that the closure of $D = D$. Any thoughts?

# Answer
> 3 votes
You are right to start with the closures of the attributes. Finding the closures will help with finding the candidate keys.

There might be more efficient ways to go about this. What works for me at least is to look at the given functional dependencies. If none of them have single attributes on the left-hand side, then don't bother with finding the closures of the individual attributes-- they will just be themselves. I.e. given R(A,B,C) and FDs A,B-\>C and B,C-\>A, the closures of each individual attribute {A}+, {B}+, and {C}+, will be, respectively, {A}, {B}, {C}.

Here, though, you have one FD that has a single-attribute on its left-hand side: E-\>F. The closure of {E}+ is E itself plus whatever E can determine, which is F, thus {E}+ = {E,F}.

Now, you have figured out the closures of the individual attributes. But that doesn't go far since the rest of the FDs have two attributes on their left-hand sides. You can then calculate the closure of, say, {A,B}+. Automatically you can add A and B into that closure since each attribute determines itself. Now look to the set of given FDs and you see that there is one that goes A,B-\>C. Since you already have A and B inside the closure (you have all of the attributes on the FD's left-hand side in your closure) then you can add whatever attributes are on the right-hand side into your closure. So now the closure of {A,B}+ = {A,B,C}.

Essentially you keep building larger closures with the ultimate goal of finding closures that encompass the entire set of attributes.

In this case, the candidate keys (there are three) all have three-attributes each. Try calculating the closure of {A,B,D}+. You know automatically that A,B,D should go inside it. You can also add whatever attributes are in closures that are subsets of {A,B,D}+, such as {A,B}+ from before. Thus, you can add C to the closure which now looks like {A,B,C,D}. Now check the list of given FDs again and you will see that A,D-\>E can now be added, since A and D are inside the closure. Thus, the closure is now {A,B,C,D,E}. Finally, you can add in the FD of E-\>F. And that completes the set of attributes of the relation.

Here is a useful tool for checking your work: http://raymondcho.net/RelationalDatabaseTools/RelationalDatabaseTools.html

You can use it to check your work on calculating closures and candidate keys.

# Answer
> 2 votes
Follow the following steps :

1\> Check which attributes are not present in RHS of the Functional Dependencies (FDs).These attributes cannot be derived and have to present in all the candidate keys. {D in this case}

2\> Check closure of D. D- {D} D cannot derive all other attributes =\> not candidate key

3\> Start checking closure of pairs of 2 attributes that include D. (AD,BD,CD) Closure(AD)-{A,D,E,F} cannot derive all other attributes=\> not candidate key Closure(BD)-{B,D} not candidate key Closure(CD)-{C,D} not candidate key

4\> Start checking closure of chunk of 3 attributes that include D. (ABD,BCD,ACD) Closure(ABD)-{A,B,D,C,E,F} all attributes covered =\> Candidate key Closure (BCD)-{B,C,D,A,E,F} all attributes covered =\> Candidate key Closure(ACD)- {A,C,D,E,F,B} all attributes covered =\> Candidate Key

5\> Start checking closure of chunk of 4 attributes that include D. (ABCD) But ABCD is a super key of ABD (OR BCD OR ACD) and cannot be a candidate key.

Thus the candidate keys here are ABD,BCD and ACD.

---
Tags: database-theory, relational-algebra
---


# Question
Title: Effiecient Repeat Evaluation of Large Multivariable Expressions
I am working with a professor to implement an optimization algorithm for determining the maximum and minimum of large (100+ variable) multi-variable expressions (not restricted to polynomials). Part of this process involves picking random values for all variables and then evaluating the expression for near "neighbors" (slight variations in all sub-sets of the variables).

Simplified Example:

f(x,y,z) = x^2 + sin(y/x)/log2(3z)

1. Start at random point (1,1,1)
2. Test all neighbors by altering each variable by +/- 0.1:

{1,1,1.1}, {1,1.1,1}, {1, 1.1, 1.1}, {1.1,1,1}, {1.1,1,1.1}, {1.1,1.1,1\], ...

Over the course of the optimization the same expression will be evaluated many millions of times. It seems like there must be an efficient way to prevent reevaluating portions of the expression that have already be evaluated, or at least recently evaluated. I am struggling to come up with an efficient way of doing this. I understand that computers are smoking fast at math calculations so maybe attempting this optimization is unwarranted even with large expression size, however expression evaluation is the bottleneck in the process at the moment. Thanks for you time and thoughts on this!

# Answer
> 2 votes
In symbolic computation, hash consing is a technique that consists of systematically remembering the result of function calls in a cache. The cache is indexed by functions and their parameters. Before performing an operation, you look up the call in the cache, and if you find it, you don't perform the function call. Function calls include data constructors, so there is only a single copy of any data structure in memory, and data structures can be compared by physical address. If the computation is highly repetitive, involving many identical parts, this can be a huge performance and memory benefit as it removes any redundancy in computation and memory. If the computation involves little repetition then it's just wasted time doing failed cache lookups and wasted memory for a cache that isn't used.

The same technique can be applied to numerical computations: store all intermediate results in a cache indexed by function calls. I don't know how effective it could be in practice.

As floating point is involved, you need to decide what it means for values to be equal. The most straightforward approach is to use floating point equality; assuming consistent compilation, the same mathematical operation on the same parameters always yields the same result, but you will miss equalities resulting from obtaining the same result in two different ways that are mathematically equivalent (e.g. you may not get the same result for `f(x,y)` and `f(y,x)` even if `f` is mathematically symmetric).

# Answer
> 1 votes
This is known as continuous optimization or mathematical optimization. There's an enormous literature on this; I suggest you spend some time reading about it.

If you can compute gradients (partial derivatives), you can use "first-order methods", such as gradient descent. If you can't, you can use "gradient-free methods", such as hillclimbing. There are many others -- the best method will depend on the specific nature of your particular instance.

Depending on the structure of the specific objective function you want to minimize, there may be ways to avoid re-computing intermediate values. For instance, stochastic gradient descent is a version of gradient descent that does exactly this, when the objective function can be written as the sum of lots of terms, where each term can be computed efficiently. For instance, TensorFlow is a library that has nice support for this kind of optimization.

Without more detail about your specific problem, it's probably not possible to give a more specific recommendation about which method to use.

---
Tags: optimization
---


# Question
Title: Find and prove asymptotic upperbound for T(n)
How would I go about solving this?

# Answer
> 1 votes
Can you show that $T(\\,)$ is increasing? That is, can you show that $T(n)\< T(m)$ for $n\<m$? If you can, then $T(n/5) \le T((7n)/10)$ so $$ T(n) \le 2T(\frac{7}{10}n) + 3n $$ and the upper bound of this is easy to compute by, say, the Master Theorem.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: More details on a language decided in $\Theta(\log \log n)$ space
In Language with $\log \log n$ space complexity?, the following non-regular language is described:

$$L = \\{b(0) \\# b(1) \\# \dots \\# b(2^k-1) \mid k\in \mathbb{N}\\}$$

where $b(i)$ is the $k$-bit binary representation of $i$. This can evidently be computed in $\log \log n$ space, where $n$ is the length of the string, using the typical TM with input-output tapes.

This is apparently a common example used in complexity theory, however I would like some clarification on the method of calculation -- the answer given is very unclear and differs from the method defined in the reported source.

1. In the answer given, it says we do the check only when $m$ is smaller than the width of the first block. Am I misunderstanding this? If we do this, we never check the MSB of each representation, so for example the string $10\\# 11 \\# 10 \\# 11$ would be accepted since it never checks $m=2$.
2. Do we check if the $m$ least significant bits form a counter modulo $m$, or modulo $2^m$? The lecture cited checks the ending modulo $2^m$, but the answer says modulo $m$. Wouldn't having a counter that goes up to $2^m$ take $m$ space which is already too much space ($m = O(\log n)$)? If we're supposed to make the counter modulo $m$, how do we take binary numbers modulo $m$ while still satisfying the space requirement? If $m$ is a power of two we can just do addition with overflow, but what about when it's not?I don't see an obvious, space-efficient algorithm for doing this in general.
3. Furthermore, even if we can do this in the given space, I don't see why the method taking modulo $m$ decides the language. For example, I can give you $00 \\# 11 \\# 10 \\# 11$ and the LSBs form a counter "modulo $1$" and the two LSBs form a counter modulo $2$.

If anyone can clear up my questions that would be greatly appreciated. I think it's likely that there's just one thing I'm fundamentally misunderstanding about the presentation here which is causing everything else to not make any sense.

# Answer
> 3 votes
The trick here is to forget about the details as stated in the answer, and think about what would make the claim correct.

If $k$ were known, you could verify that the input is indeed $b(0)\\#\cdots\\#b(2^k-1)$ as follows: (below, a *word* is stuff between adjacent sharp signs)

1. The first word is $0^k$.
2. For any two contiguous words $x,y$, it holds that $y=x+1$.
3. The last word is $1^k$.

This can be accomplished in space $O(k)$.

Unfortunately, we don't know $k$ in advance, and even if we did, it's not necessarily the case that $k = O(\log \log n)$ – there could be much less than $2^k-1$ words. Therefore we use a slightly different approach. Let $K$ be the length of the first word. For each $t \leq K$, we verify the following:

1. The first word ends with $0^t$.
2. For any two contiguous words $x,y$, the $t$-bit suffixes $x',y'$ satisfy $y'=x'+1$ modulo $2^t$.
3. The last word ends with $1^t$.

If these tests pass for all $t \leq K$, then we accept the word. The $t$th test can only pass if the input is at least $(t+1)2^t-1$ symbols long and uses only $O(\log t)$ space, and this implies that the algorithm uses $O(\log\log n)$ space.

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