# Question
Title: Turing machine that decides $A=\{0^{2^n} | n \ge 0 \}$ with an alphabet of two symbols
I need to build a turing machine that decides $A=\\{0^{2^n} | n \ge 0 \\}$ with an alphabet of two symbols - $\\{0, \\\_ \\}$.

I'm aware of the known TM that decides this language with three symbols $\\{0, x, \\\_\\}$ but I am not able to come up with one that does it with just two.

Any advice would be highly appreciated

# Answer
> 2 votes
I'm assuming that $\\\_$ denotes the blank character. A strategy for the TM you are looking for is the following:

1. Check if the input is a single $0$, if so accept.
2. Replace every other $0$ with $\\\_$. If, during this process, the number of encountered $0$s is odd, reject.
3. Pack all the $0$s together. This can be done as follows:
    1. Reset the head to the beginning of the tape (search for a $0$ preceded by two $\\\_$).
    2. Locate the last $0$ (i.e., the only one followed by two $\\\_$) and, in the process, remember if a $\\\_$ is encountered before it.
    3. If no $\\\_$ is encountered you are done. Otherwise continue.
    4. Replace the last $0$ with $\\\_$.
    5. Locate the first $0$ and write write $0$ before it.
    6. Repeat from step 3.2.
4. Repeat from step 1.

---
Tags: turing-machines
---


title: Computability of function composition

text:
# Question
Title: Computability of function composition
I have some problems to understand computability and hope you can help me. In the lecture we had following problem:

Consider the three partial functions $f,g,h\colon N \to N$, where $f$ is computable and $g$ is not computable. The following two statements are correct:

1. If $h(x) = g(f(x))$, then $h$ could be computable.
2. If $g(x) = h(f(x))$, then $h$ is not computable.

Well, 2 is clear I think, because we know that $g$ is not computable and $f$ is computable, so $h$ has to be not computable, otherwise $g$ would be computable.

But 1 is a big problem for me. If $f$ is computable and $g$ is not computable, how can $h$ be computable?

# Answer
> 0 votes
Suppose that $f(x) = 0$. Then $g(f(x))$ is computable for any function $g$, computable or not. This explains 1.

As for 2, the composition of two computable functions is computable, so if both $f$ and $h$ are computable, so is $g$. Since $f$ is computable and $g$ isn't, the only conclusion is that $h$ is not computable.

---
Tags: computability, church-turing-thesis
---


# Question
Title: Is any of the assumptions hold true for the mentioned?
Suppose the use of linear regression. The result of the MSE is 120.5(mean squared error) for the train-set. Wev'e reached the minimum of training the data.

Is it possible that by applying Lasso(L1 form) we would get a lower MSE for the train? and for the test? is the same also holds for Ridge(L2 form)?

* Lasso Train
* Lasso Test
* Ridge Train
* Ridge Test

# Answer
Regularization will always increase the MSE loss on the training set (training loss). Intuitively, it constraints/limits the set of regression lines you can use.

However, the MSE loss on the test set can be either increase (for the same reason) or decrease (if it has helped combat overfitting and helped bias the classifier towards a simpler hypothesis, and if simpler hypotheses are more likely to be correct).
> 1 votes

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Finding a $g(n)$ so that $f(n) = O(g(n))$
I am having trouble on the following algorithms question:

Given $f(n) = \sum^n\_{y{=}1} (n^5\cdot y^{22})$, I am trying to find a $g(n)$ such that $f(n) = O(g(n))$. I know that this means I need to find constants $c,n\_{0}$ so that $f(n) \leq g(n)$ for all $n \> n\_{0}$.

I began by considering the expansion of $f(n) = n^{5}\cdot1^{22} + n^{5}\cdot2^{22} + ... + n^{5}\cdot(n-1)^{22} + n^{5}\cdot n^{22}$.

This gave me two ideas for a solution:

First, I thought to set $g(n) = c \cdot n^{27}$ (given that this is the largest exponential term of $f(n)$), but where I am stuck is picking the right $c$. I had the idea of picking $(n-1)n^{5}$ (there are $n-1$ other terms and the largest exponential of each term is $n^{5}$), but I'm stuck for two reasons:

1. Can $c$ be dependent on $n$? By definition it seems like the answer is no since $c$ is a constant.
2. The choice of $c = (n-1)n^{5}$ is dubious. Consider the term $(n-1)^{22}n^{5}$, the largest portion is $(n-1)^{23}$, not $n^{5}$.

My second idea is to let $g(n) = c \cdot n^{5} + n^{27}$, and let $c = \sum^{n-1}\_{y{=}1} (y^{22})$, but again this seems incorrect because $c$ depends on $n$.

I would love some feedback on these attempts, thanks!

# Answer
Suppose that you don't really know Faulhaber's formula.

Let's prove by induction that $$S\_k(n)=\sum\_{t=1}^n t^k\in O(n^{k+1})$$

For $k=0$ we have that $S\_0(n)=n\in O(n)$.

Assume that for all $s\<k$ we have that $S\_s(n)\in O(n^{s+1})$.

In order to bound $S\_k(n)$, lets start with computing the difference $S\_{k+1}(n+1)-S\_{k+1}(n)$ in two ways. Yes, the subscript is overshooting. It is $k+1$ rather than $k$.

$$ \begin{align} (n+1)^{k+1}&=S\_{k+1}(n+1)-S\_{k+1}(n)\\ &=\sum\_{t=1}^{n+1}t^{k+1}-\sum\_{t=1}^{n}t^{k+1}\\ &=1+\sum\_{t=1}^{n}(t+1)^{k+1}-\sum\_{t=1}^{n}t^{k+1}\\ &=1+\sum\_{t=1}^{n}\left\[(t+1)^{k+1}-t^{k+1}\right\]\\ &=1+\sum\_{t=1}^{n}\sum\_{s=0}^{\color{red}{k}}\binom{k+1}{s}t^s\\ &=1+(k+1)\color{red}{\sum\_{t=1}^{n}t^k}+\sum\_{s=0}^{k-1}\binom{k+1}{s}\sum\_{t=1}^{n}t^s\\ &=1+(k+1)\color{red}{S\_k(n)}++\sum\_{s=0}^{k-1}\binom{k+1}{s}S\_s(n) \end{align} $$

Solving in the equation above for the term in red, $\color{red}{S\_k(n)}$, we get that it is equal to $\frac{1}{k+1}(n+1)^{k+1}$ plus a linear combination of $S\_s(n)$ for $s\<k$. Since these are in $O(n^k)$, it follows that $S\_k(n)\in O(n^{k+1})$.

---

In your case $f(n)=n^5S\_{22}(n)\in n^5O(n^{23})=O(n^{28})$
> 2 votes

# Answer
For any $f$ we have $f \in O(f)$ i.e. trivial answer to your question is $g=f$. Presumably you need to clarify more exactly conditions on $g$. On other hand if we change all members of sum with maximum one, then we have $f \in O(n^{28})$.

Now about questions:

1. $c$ is independent from $n$ by definition
2. outgoing from 1. you cannot consider $c = (n-1)n^{5}$
> 2 votes

# Answer
A simple way to estimate/bound $\sum\_{0 \le k \le n} k^m$ is to approximate by an integral (do a sketch of the curve and the staircase representing the sum), so you see:

$\begin{align\*} \sum\_{0 \le k \le n} k^m \le \int\_0^n x^m \\, \mathrm{d} x \\ = \frac{n^{m + 1}}{m + 1} \end{align\*}$

By sandwiching the staircase between curves (start/end of each staircase step), you get lower and upper bounds.
> 1 votes

---
Tags: algorithms, big-o-notation
---


# Question
Title: Relation between mathematical functions and trees?
I try to express datastructures in a form of mathematical functions. For example an array or a dictionary is just a function to me.

Is there a good way to model a tree in terms of functions?

# Answer
A tree structure can be completely described by three functions:

* a function that given a node $x$ returns the number of children of that node,
* a function that given a node $x$ and index $i$ returns the $i$th child of that node, and
* a function that given a node $x$ returns an associated value $v$ stored at that node.
> 2 votes

---
Tags: data-structures, trees
---


# Question
Title: What is the difference between the fundamental matrix and the essential matrix?
Could someone, in plain english, explain the distinction between the fundamental matrix and the essential matrix in multi-view computer vision?

How are they different, and how can each be used in computing the 3D position of a point imaged from multiple views?

# Answer
Both matrices relate corresponding points in two images. The difference is that in the case of the Fundamental matrix, the points are in pixel coordinates, while in the case of the Essential matrix, the points are in "normalized image coordinates". Normalized image coordinates have the origin at the optical center of the image, and the $x$ and $y$ coordinates are normalized by the focal length in pixels: $f\_x$ and $f\_y$ respectively, so that they are dimensionless.

The two matrices are related as follows: $E = K^TFK$, where $K$ is the intrinsic matrix of the camera.

Note that this is a special case, where both images have been taken with the same camera. If the images were taken with different cameras, then you would have two different sets of intrinsics: $K$ and $K'$. Then $E = (K')^TFK$.

$F$ has 7 degrees of freedom, while $E$ has 5 degrees of freedom, because it takes the camera parameters into account. That's why there is an 8-point algorithm for computing the fundamental matrix and a 5-point algorithm for computing the essential matrix.

One way to get 3D camera motion from matching points from a pair of images images is to estimate the fundamental matrix, compute the essential matrix, and then to get the rotation and translation between the cameras from the essential matrix. This, of course, assumes that you know the intrinsics of your camera. Also, this would give you up-to-scale motion, with the translation being a unit vector.
> 19 votes

# Answer
I want to add one thing to @Dima's answer, just so things are absolutely clear:

$E = (K')^TFK$ (note the transpose)

You can see how this also captures that the fundamental matrix takes image coordinates as inputs and not normalized 3D points. Let $x$, $x'$ be 2 normalized 3D points:

$(x')^T\*E\*x = (x')^T(K')^TFKx = (K'x')^TF(Kx)$

I can't comment yet because I don't have 50 reputation ...
> 7 votes

# Answer
The other answer does not emphasize some important points.

1. the fundamental matrix $F$ is a generalization of the essential matrix $E$
2. the fundamental matrix does not assume the cameras to be calibrated (i.e. you don't know $M$ and $M'$, which are the homographies needed to project a 3d point onto the image plane of camera $C$ and $C'$, respectively)
3. the essential matrix was discovered before the fundamental matrix
4. in principle, to estimate the fundamental matrix you need more point-to-point correspondences than to estimate the essential matrix (because the fundamental matrix has more degrees of freedom, i.e. more parameters you need to find)
> 4 votes

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


# Question
Title: How does reduction of a decision problem work?
I am given the following problem description:

> Given $l$ lists, $L\_1$, $L\_2$, . . .$L\_l$ each containing $N$ bit vectors of $n$ bits each, we want to find tuples $(x\_1,···,x\_l)$ with $x\_i$ in the corresponding $L\_i$, such that:$$⊕\_{i=1}^l x\_i = S $$ for some target n-bit vector $S$. In other words, we want to find one element from list such that the XOR of the chosen elements is the target $S$

Now I am required to show that if we can solve the equation in the case where $S=0$, we can for the same cost solve it for an arbitrary value (with exact same parameters, $N$, $n$, and $l$). I am given a hint to proceed by **reducing** an instance with $S \neq 0$ to an instance with $S=0$.

What am I missing that I am not able to reduce it?

# Answer
> 3 votes
Let $I$ be your instance and consider the instance $I'$ obtained by replacing each bit vector $y$ in $L\_1$ with $y' = y \oplus S$ (where $\oplus$ denotes bitwise xor). Call $L'\_1$ the list containing all vectors $y'$.

Consider the tuples $(x\_1, x\_2, \dots, x\_l)$ and $(x'\_1, x\_2, \dots, x\_l)$ where $x\_i \in L\_i$ and $x'\_1 \in L'\_1$. We have: $$ x\_1 \oplus ( \oplus\_{i=2}^l x\_i ) = \oplus\_{i=1}^l x\_i = S \iff (x\_1 \oplus S) \oplus ( \oplus\_{i=2}^l x\_i ) = x'\_1\oplus ( \oplus\_{i=2}^l x\_i ) = S \oplus S = 0, $$ showing that there is a solution to $I$ iff there is a solution to $I'$ (and you can convert one solution into the other in linear time).

---
Tags: algorithms, algorithm-analysis, decision-problem
---


# Question
Title: Algorithm to sample high-dimensional parameter space of expensive cost function
I am looking for recommendations for algorithms (apparently this is the right SO site for that) that efficiently scan the high-dimensional parameter space of a cost function that is very expensive to evaluate.

* By expensive to evaluate I mean that one can only do O(1) evaluations per second on a modern computer.
* By efficiently I mean that the algorithm should learn to avoid regions where there are no solutions: the evaluation of the cost function may fail for certain sets of parameters.
* Still under the aspect of efficiency, the algorithm should yield a set of samples that represent a (ideally unbiased) coverage of all solutions in the whole parameter space within a reasonable number of samples.
* The parameters are continuous numbers within predefined bounds.
* The cost function is "mostly well-behaved".

I am not so much after importance sampling, so I guess I am looking for an improved random sampling that is adaptive in the sense that it learns which parts of parameter space to avoid.

*Background information:*

I am looking into a specific physics model where from ~20 input parameters a set of outputs (masses and decay probabilities) are computed. This is the bottleneck CPU-wise. My goal is to identify allowed ranges for the input parameters for which the outputs fulfil certain constraints that are implemented in terms of a cost function. Not all possible combinations of input parameters give meaningful physics, therefore a large (but acceptably so) fraction of calculations will fail.

At the moment I am successfully using parallel simulated annealing to find solutions (input parameters) that come very close to the known minimum of the cost function. So finding a (nearly) optimal solution is "easy".

What I would now like to improve is the coverage: sampling from the whole input parameter space (e.g. below some threshold of the cost function). This would allow projections onto 1-D or 2-D subspaces of the input-parameter space to be done to see where valid models lie.

In this example

the yellow bin holds most of the samples because the cost function depends on this particular output such that it ought to be close to 125. The interesting part though is the dependence of the output on the input. One can guess from the plot that lower values of the input would also give the desired output, and below ~ 1000 we see some structure, where the input apparently is too low to achieve the desired output. However, the statistics is very low. Therefore, I am looking for another algorithm which yields a sampling that covers input-parameter space more evenly (subject to the constraint that invalid input parameter sets should be avoided).

# Answer
> 0 votes
I don't know how to sample from the space of nearly-optimal solutions, but I'll share one approach you could consider.

It appears that you want to estimate the density of good solutions, at different points in the input space. It appears you are gridding up the parameter space and estimating the density in each cell of the grid. Here is a possible alternate method to do that.

Suppose we have a cell $C \subseteq \mathbb{R}^{20}$ in the parameter space, which might take the form $C = \[\ell\_1,u\_1\] \times \cdots \times \[\ell\_{20},u\_{20}\]$, i.e., $\ell\_i$ is the lower bound on the $i$th coordinate and $u\_i$ the upper bound. Let $V(C)$ be the volume of cell $C$. We'll estimate the density of good solutions in $C$. Pick a volume $v$ that is a fraction of $V(C)$, let $\alpha=v^{1/20}$, and then repeat the following 100 times:

* Pick a random point $w \in C$. Form the smaller cell $C\_x = \[w\_1-\alpha/2,w\_1+\alpha/2\] \times \cdots \times \[w\_{20}-\alpha/2,w\_{20}+\alpha/2\]$. Use your optimization method to search whether there is a good solution in the cell $C\_x$. (For many optimization methods, it is easy to enforce constraints that set an upper and lower bound on each coordinate in the parameter space.)

Now based on the number of times that you were able to find a good solution, you can form an estimate of the density of good solutions in $C$. If this count is close to zero, double $v$ and repeat. If this count is close to 100, halve $v$ and repeat. Repeat until you get a count that is not too close to 0 or 100, and the result should give you a pretty good estimate of the density in $C$.

You can now iterate this, once per cell $C$, and use that to produce the kind of plot you are hoping for.

Here I've adopted standard methods for #SAT, i.e., for estimating the number of solutions to a SAT instance, to your specific problem.

---
Tags: algorithms, sampling, monte-carlo
---


# Question
Title: How balanced is a binary tree in the average case?
For algorithms involving binary trees, time or space complexity is often O(logn) in the best case of a completely balanced tree, and O(n) in the worst case of a completely unbalanced tree. Sure, it's a generalization, but it's also a reasonable one.

But in real algorithms, we're typically not interested in the rare worst case performance, much less the best case performance. Rather, we're interested in how the algorithm performs in typical use. This begs an interesting (and useful) question: How balanced is a binary tree on average? Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"?

# Answer
> Is there a reasonable way to approach that problem, or is it so dependent on use case that there's no better answer than "take a look at the binary trees you're using in your algorithm"?

To be a bit stereotypical: yes. There are reasonable ways to approach the problem, but it's so dependent on use case that you will need to take a look at how your *particular* algorithm builds binary trees to get information about your algorithm.

More specifically: you ask about the 'average' balance of a binary tree, but you can't have an average without a *probability distribution* on the set of binary trees. There are (infinitely) many different probability distributions, and different algorithms for generating trees will lead to different distributions on the set of trees generated.

For example, since the number of binary trees on $n$ nodes is finite, we can talk about the *uniform* distribution where we consider every binary tree equally probable, and ask what the average balance is there. For concreteness, I'm going to use height as a measure of the balance of a tree, because it's easy and well-studied, but note that there are plenty of other metrics you could measure by: maximal ratio between subtree sizes, for instance, would be another reasonable one. Looked at over the uniform distribution of $n$-node binary trees, the average height is proportional to $\sqrt{n}$, (almost) 'right between' the two extremes.

But very few algorithms would lead to a uniform distribution on binary trees. As an example of a more reasonable distribution, we could choose a permutation uniformly at random from the $n!$ permutations on $\\{1\ldots n\\}$ and then build a binary tree by inserting nodes labeled $1$ through $n$ into a tree in the given order. It can be shown that this process yields a tree with average height proportional to $\log n$, so trees generated in natural fashion from random data are generally 'pretty good'.
> 4 votes

# Answer
Most of the time when binary trees are used, we first create in a way we define; heap, B+ tree, 2-3 tree and etc. So, the probability of being a balanced tree also depends on the tree building algorithm. for example, a list of length 2^n -1 convert into heap definitely give a balanced tree.
Just a thought.
> 1 votes

# Answer
You can't really talk about "average", only about "average for my use case". For example, assume I have a sorted array, and I turn it into a tree by starting with an empty tree, and adding the items in the order they are in the array.

In that case, a trivial algorithm doing no re-balancing ends up with a tree of height n. Or my data might come from some external source which might be sorted, or mostly sorted. I would say that a case where you insert items in random order is actually quite unusual.
> 0 votes

---
Tags: complexity-theory, binary-trees
---


# Question
Title: Find the maximum number of contiguous occurrences of smaller string s in a larger string l
Say we have two strings s and l, and they only have characters 'a' through 'z' (lowercase English alphabet characters). The task is to find the maximum number of consecutive occurrences of s in l.

Ex.

s = "ab"

l = "defgababajklabe"

The answer here would be 2, because there is "abab" which would be 2 consecutive occurrences of string s in l.

My initial thought was to go through each character in l, and try to match the substring starting at that position with s, if it matched we would increment our count and keep track of some global maximum. We would also set the value of our next starting point to one position after the end of this matched portion.

If at any point there is a mismatch, then we wouldn't have to re-check all the previous characters, we would just go to one position after the start point, that would be our new start point.

For example, when processing the given example, we would eventually set start to index 4 (0 based index), and match ab, then set it to index 6 and match ab again, then set index to 8. At that point there would be a mismatch, and we would just start matching again at index 9. There is no need to start over from index 5.

This is my guess, and it appears to work, but I can't seem to prove why this works. Can someone help me understand why this works? Or doesn't work?

# Answer
> 1 votes
You algorithm as described doesn't work. Consider $s=baab$ and $I=\textrm{baabaabbaab}$. Your algorithm would match $s$ with the first $4$ characters of $I$, and since the next $4$ characters don't match $s$, it would then continue with searching $s$ in $I' = aabbaab$.

There is only one occurrence of $s$ in $I'$ causing your algorithm to return $1$ (while the correct answer is $2$).

Here is a solution for your problem that runs in $O(|I|)$ **worst-case** time. We can safely assume $|s| \le |I|$, as otherwise the answer is trivially $0$.

**Step 1**. Construct a DFA $D$ for the language of all words that end with $s$. This DFA is essentially a path labelled with the characters in $s$ where the last state is a final state. Additionally, each state has "back-edges" that handle characters different from the (at most one) "forward" edge in the path. These "back-edges" point to the state representing the larger prefix of $s$ that is also a suffix of the string read so far. This sounds more complicated than it really is, and can be computed in linear time (for any constant-size alphabet). Here is an example for $s=\textrm{abba}$ on the alphabet $\\{a,b\\}$.

**Step 2**. Now now create an array $A\[1, \dots, |I|\]$, and feed each character of $I$ to $D$. Whenever $D$ is in the final state after reading the $i$-th character of $I$ set $A\[i\]$ to $1$, otherwise set $A\[i\]$ to $0$.

**Step 3**. Compute the maximum number of consecutive occurrences of $s$ in $I$ using dynamic programming and the array $A$. Define $B\[i\]$ as the maximum number of contiguous occurrences of $s$ in the prefix $I\_i$ consisting of the first $i$ character of $I$, with the additional constraint that the last occurrence in the contiguous sequence must end with the last character of $I\_i$. For $i = 0, 1, \dots, |s|-1$ we have $B\[i\]=0$, while for $i = |s|, \dots, |I|$ we can write: $$ B\[i\] = \begin{cases} 0 & \mbox{if $A\[i\]=0$} \\ 1 + B\[i-|s|\] & \mbox{if $A\[i\]=1$} \end{cases} = A\[i\](1+B\[i-|s|\]). $$

Then the solution to your problem is then $\ell = \max\_{i=0, \dots, |I|} B\[i\]$ and the $\ell$ consecutive occurrences of $s$ start at character number $\arg \max\_{i=0, \dots, |I|} B\[i\] - \ell |s|$ in $I$.

A naive implementation of the dynamic programming algorithm requires time $O(|I|)$ and space $O(|I|)$. However, one can observe that the value stored in $B\[i\]$ is useless after $B\[i+|s|\]$ has been computed (except for finding $\ell$). Then, we can replace $B$ with a circular array of length $|s|$ (so that each access to $B\[i\]$ becomes an access to $B\[i \bmod |s|\]$) and compute $\ell$ by keeping track of the maximum values of $B\[i\]$ encountered so far.

Moreover, the array $A$ is not needed as we can run Step 2 and Step 3 in parallel: we feed the $i$-th character of $I$ to $D$ and immediately compute $B\[i \bmod |s|\]$ depending on whether $D$ is in the final state or not.

With these modifications the algorithm requires $O(|I|)$ time and $O(|s|)$ space.

Finally, notice that we don't really need to explicitly represent $D$: knowing, for each prefix $s'$ of $s$ and each character $c$ of the alphabet, the length of the longest prefix of $s$ that is a suffix of $s \circ c$ is enough (where $\circ$ denotes concatenation). See this chapter from Jeff Erickson's book Algorithms for a way to efficiently compute these quantities.

# Answer
> 1 votes
The string that you are looking for ("maximum number of repetitions of baab") starts with a b obviously. So you can look for a "b" at position x and check if it is followed by "aab". After you found k repeats of the string at positions x to x + 4k-1, you think you could restart the search at position x + 4k. However, there is another b in the search string.

In your particular case, if you found *one* baab, a longer sequence could start at position x+3. If you found k repeats of baab, since any b at the end of a baab except the last was followed by a b, the string you look for could start at x + 4k - 1.

If the string you search for contains multiple b's, like baabaaab, you would check carefully that the search string can't start at the second b.

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


title: What is the average turnaround time?

text:
# Question
Title: What is the average turnaround time?
For the following jobs:

The **average wait time** would be using a FCFS algorithm:

(6-6)+(7-2)+(11-5)+(17-5)+(14-1) -\> 0+5+6+10+13 -\> 34/5 = 7 (6.8)

What would the **average turnaround time** be?

# Answer
> 10 votes
You need to determine at what time each job is completed. With a first-come-first-served scheduler, this is simple to calculate: each job starts as soon as the processor becomes free, and takes exactly its burst time to complete. You've already calculated the start and end times to calculate the wait times, so use that to obtain the turnaround time.

For example, A arrives at time 0. The processor is free, so it starts at time 0 and ends at time 6. Then the processor runs B, which had to wait for 5 units, and finishes at time 8, for a turnaround time of 7.

The answer from the book seems to be totaling the completion times, without regard for the arrival time. This is not something I recognize as “turnaround time”.

# Answer
> 2 votes
In textbooks, the solution given is 6+8+13+20+21= 68/5 = 13.6 This is because the textbooks (including Operating System Concepts 8e by Silberschatz,Gagne,Gelvin) define turnaround time as the time that elapses between the submission and the termination of the process, which is the sum of arrival time, waiting time, execution time and time spent in device queues. Since in this problem we are considering FCFS scheduling, the termination instant for processes are 6,8,13,20,21 starting from the time of submission . Taking their average gives the answer at the back of the textbook. I think that this terminology goes back to the batch systems where all the "jobs" were submitted at the same time as a batch. The arrival time refers to the time it takes for a process to be created and brought into the Main Memory from the job pool after submission. Drawing a Gantt Chart would make it easier to calculate the various times according to various definitions.

# Answer
> 1 votes
the turnaround time is TAT= Completion time-arrival time for A=6-0 B=8-1 C=13-2 D=20-3 E=21-7 that gives 6+7+11+17+14/5=11

so average TAT=11

# Answer
> 1 votes
As already said the Tournaround time (TAT) is the time between submission and completion. If we look at the tasks:

A arrives at time 0 (submission time) and takes 6 timeunits to finish. that means the TAT of A is 6.

lets look at task B it arrives at time 1. but it has to wait for A to finish. A finishes at 6 and then B starts working and finishes at 8. Now we subtract the arrival time minus finishing time 8-1=7 which is the TAT.

Now C--\> arrival time 2; working time (burst) 5 ;finishing time:13 --\> Tat 13-2=11

Now D--\> arrival time 3; working time (burst) 7 ;finishing time:20 --\> Tat 20-3=17

Now E--\> arrival time 7; working time (burst) 1 ;finishing time:21 --\> Tat 21-7=14

now the result--\>(6+7+11+17+14)/5=11

!tada!

# Answer
> 0 votes
EXECUTION TIME-ARRIVAL TIME=TURN AROUND TIME AND THEN THE EXECUTION ADDS TO THE NEXT EXECUTION TO THE ALREADY EXISTING TIME TO SUBTRACT THE ARRIVAL TIME . THEN ADD ALL THE TURNAROUND TIME AND THE DIVIDE THERE SUM TOTAL BY THERE TOTAL NUMBER

# Answer
> 0 votes
## TAT is Brust time + Waiting time

Process A finished with turnaround time of 6. Process B finished with turnaround time of 8. Process C finished with turnaround time of 13. Process D finished with turnaround time of 20. Process E finished with turnaround time of 21. The average turnaround time is 13.6

---

---
Tags: algorithms, operating-systems, process-scheduling, scheduling
---


# Question
Title: How do two H gates act on two entangled qubits?
In this circuit, if the two qubits are initialized at state 0, then after the oracle they are entangled and in the state:

$$\frac{1}{2} (|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$

My question is, how do the two $H$ gates act on them? Do they act like:

$$\frac{1}{4} \[(|0\rangle+|1\rangle)\otimes(|0\rangle+|1\rangle) + (|0\rangle+|1\rangle)\otimes(|0\rangle-|1\rangle) + (|0\rangle-|1\rangle)\otimes(|0\rangle+|1\rangle) - (|0\rangle-|1\rangle)\otimes(|0\rangle-|1\rangle)\]$$

which in the end nothing has changed. My intuition tells me that it's wrong.

Update: The figure above is from a circuit to implement Grover's algorithm. The whole figure is given below:

The state is indeed not changed after the two $H$ gates, so why do they add them here?

# Answer
The Hadamard gate performs the following operation on a single qubit: \begin{align} |0\rangle &\to \frac{|0\rangle + |1\rangle}{\sqrt{2}} \\ |1\rangle &\to \frac{|0\rangle - |1\rangle}{\sqrt{2}} \end{align} This gives the action on pure states. The action extends linearly to mixed states: $$ \alpha|0\rangle + \beta|1\rangle \to \alpha\frac{|0\rangle + |1\rangle}{\sqrt{2}} + \beta\frac{|0\rangle - |1\rangle}{\sqrt{2}} $$

What happens when there are seveal qubits around? In this case, it is common to denote $|a\rangle \otimes |b\rangle$ by $|ab\rangle$, for brevity. If we apply a Hadamard gate on the first qubit, then it only affects the first qubit: \begin{align} |0b\rangle &\to \frac{|0b\rangle + |1b\rangle}{\sqrt{2}} \\ |1b\rangle &\to \frac{|0b\rangle - |1b\rangle}{\sqrt{2}} \end{align} Similarly, if we apply a Hadamard gate on the second qubit, then it only affects the second qubit: \begin{align} |a0\rangle &\to \frac{|a0\rangle + |a1\rangle}{\sqrt{2}} \\ |a1\rangle &\to \frac{|a0\rangle - |a1\rangle}{\sqrt{2}} \end{align} The two operations commute.

What happens to a general mixed state? Denoting by $\stackrel{(i)}\to$ the application of $H$ on the $i$'th bit, we get \begin{align} &\alpha|00\rangle + \beta|01\rangle + \gamma|10\rangle + \delta|11\rangle \\ \stackrel{(1)}\to &\alpha\frac{|00\rangle + |10\rangle}{\sqrt{2}} + \gamma\frac{|00\rangle - |10\rangle}{\sqrt{2}} + \beta\frac{|01\rangle + |11\rangle}{\sqrt{2}} + \delta\frac{|01\rangle - |11\rangle}{\sqrt{2}} \\ = &\frac{\alpha+\gamma}{\sqrt{2}} |00\rangle + \frac{\beta+\delta}{\sqrt{2}} |01\rangle + \frac{\alpha-\gamma}{\sqrt{2}} |10\rangle + \frac{\beta-\delta}{\sqrt{2}} |11\rangle \\ \stackrel{(2)} \to &\frac{\alpha+\gamma}{\sqrt{2}} \frac{|00\rangle + |01\rangle}{\sqrt{2}} + \frac{\beta+\delta}{\sqrt{2}} \frac{|00\rangle - |01\rangle}{\sqrt{2}} + \frac{\alpha-\gamma}{\sqrt{2}} \frac{|10\rangle + |11\rangle}{\sqrt{2}} + \frac{\beta-\delta}{\sqrt{2}} \frac{|10\rangle - |11\rangle}{\sqrt{2}} \\ = &\frac{\alpha+\beta+\gamma+\delta}{2} |00\rangle + \frac{\alpha-\beta+\gamma-\delta}{2} |01\rangle + \frac{\alpha+\beta-\gamma-\delta}{2} |10\rangle + \frac{\alpha-\beta-\gamma+\delta}{2} |11\rangle \end{align}

The Hadamard gate is Hermitian, and so applying it twice in a row results in the starting point: $HH = I$. Therefore if the oracle does nothing, you do get what you started from. But usually the oracle does change the qubits somehow.
> 2 votes

---
Tags: quantum-computing
---


# Question
Title: Working of PDA for $\{a^m b^n c^k \mid m=n \text{ or } n=k\}$
I understand that the language $L = \\{ a^mb^nc^k \mid m=n \text{ or } n=k \\}$ is context-free because it can be represented as the union of $L\_1 = \\{a^mb^mc^k\\}$ and $L\_2 = \\{a^mb^kc^k\\}$, which are both context-free. But I can't figure out the working of the PDA accepting $L$.

To check whether $m=n$, first of all $m$ many $a$'s will be pushed, then on every occurrence of $b$, one $a$ will be popped out, or if stack becomes empty, then remaining $b$'s will be pushed. After this, either stack will be empty, meaning $m=n$, or $m-n$ many $a$'s or $n-m$ many $b$'s will remain in the stack, meaning $m \neq n$. How can we check whether $n=k$ now?

# Answer
> 3 votes
The PDA first guesses whether $m=n$ or $n=k$. According to the guess, it either just checks that $m=n$, or just checks that $n=k$.

What your heuristic argument suggests is that this language cannot be accepted by a *deterministic* PDA. You can likely show this by adapting the proof here.

---
Tags: context-free, pushdown-automata
---


# Question
Title: What is an intuitive way to explain and understand De Morgan's Law?
De Morgan's Law is often introduced in an introductory mathematics for computer science course, and I often see it as a way to turn statements from AND to OR by negating terms.

Is there a more intuitive explanation for why this works rather than just remembering truth tables? To me this is like using black magic, what's a better way to explain this so that it makes sense to a less mathematically inclined individual?

# Answer
If you like to visualize it, use the venn diagrams. See this, for instance.

I find it more simple just to memorize the basic 2 laws: everytime you "break" a negation line, you replace the AND to OR (or vice versa). Adding two negation lines changes nothing (but gives you more "lines" to break). It just works.
> 12 votes

# Answer
Insert real-world predicates and read aloud, for instance:

> It can not be both winter *and* summer (at any point in time).

and

> (At any point in time) It is *not* winter *or* it is *not* summer.

Clearly, the two statements are equivalent.
> 14 votes

# Answer
The statement $\left(\bigcup\_i A\_i\right)^c \subseteq \bigcap\_i A\_i^c$ is equivalent to $$x \in \left(\bigcup\_i A\_i\right)^c \Longrightarrow x \in \bigcap\_i A\_i^c$$ and can be read as follows:

> If $x$ is not in some $A\_i$, then $x$ is not in any $A\_i$.

I think this latter statement is obvious. You can similarily read the converse inclusion.
> 2 votes

# Answer
$\mathbf{(A \cdot B)'} = A' + B'$

**They can't make you pizza and chips:**

*They're either missing the pizza, missing the chips or missing both*

$\mathbf{(A+B)'} = A'\cdot B'$

**He doesn't have an Xbox or a Playstation**

*He doesn't have an Xbox and he doesn't have a Playstation*
> 0 votes

---
Tags: logic, discrete-mathematics, didactics
---


# Question
Title: Removing left recursion with terminals only
I have a grammar:

$G → id \> id$
$| id \< id$
$| G and id$

Does anybody know how I can do left recursive elimination on this one, when it doesn't have any extra non terminals?

# Answer
You'll need to introduce a new non-terminal to factor this, like:

$\begin{align\*} G &\to id A \\ A &\to \< id \mid \> id \end{align\*}$

Then you'll need to get rid of the left recursion.
> 0 votes

---
Tags: formal-grammars, compilers, left-recursion
---


# Question
Title: Queue FIFO search speed up through the change of visited array?
As I was preparing for the CCC this year, I am quite confused as to why a certain code modification was able to speed up my code for CCC Seniors Problem 2.

Here was the C++ source code for my first attempt, which scored **13/15** in the cccgrader website as well as the DMOJ online judging website.

```
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;
vector<pii> vpairs[1000001];
vector<vector<bool>> vis;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int A,B;
    cin>>A>>B;
    for(int i=0;i<A;i++)
    {
        vector<bool> newvecbool;
        for(int j=0;j<B;j++)
        {
            newvecbool.push_back(false);
            int k;
            cin>>k;
            vpairs[k].push_back(pii(i,j));
        }
        vis.push_back(newvecbool);
    }
    queue<pii> queue;
    queue.push(pii(A,B));
    while(!queue.empty())
    {
        pii curpair = queue.front();
        queue.pop();
        if(curpair.first==1 && curpair.second==1){
            cout<<"yes";
            return 0;
        }
        vis[curpair.first-1][curpair.second-1] = true;
        int value = curpair.first*curpair.second;
       // cout<<curpair.first<<' '<<curpair.second<<endl;
        for(int i=0; i<vpairs[value].size();i++)
        {
            pii pair = vpairs[value][i];
            if(!vis[pair.first][pair.second]){
                //vis[pair.first][pair.second] = true;
                queue.push(pii(pair.first+1,pair.second+1));
            }
        }
    }
    cout<<"no";
}

```

Here, on the other hand, was my second attempt, being much faster in time and scoring **15/15** on both the cccgrader and the DMOJ judging website.

```
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vint;
typedef pair<int,int> pii;
vector<pii> vpairs[1000001];
vector<vector<bool>> vis;
int main(void){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int A,B;
    cin>>A>>B;
    for(int i=0;i<A;i++)
    {
        vector<bool> newvecbool;
        for(int j=0;j<B;j++)
        {
            newvecbool.push_back(false);
            int k;
            cin>>k;
            vpairs[k].push_back(pii(i,j));
        }
        vis.push_back(newvecbool);
    }
    queue<pii> queue;
    queue.push(pii(A,B));
    while(!queue.empty())
    {
        pii curpair = queue.front();
        queue.pop();
        if(curpair.first==1 && curpair.second==1){
            cout<<"yes";
            return 0;
        }
        //vis[curpair.first-1][curpair.second-1] = true;
        int value = curpair.first*curpair.second;
       // cout<<curpair.first<<' '<<curpair.second<<endl;
        for(int i=0; i<vpairs[value].size();i++)
        {
            pii pair = vpairs[value][i];
            if(!vis[pair.first][pair.second]){
                vis[pair.first][pair.second] = true;
                queue.push(pii(pair.first+1,pair.second+1));
            }
        }
    }
    cout<<"no";
}

```

As you may have noticed, the only difference between the two source codes is the position in which the **vis** vector, a vector used to store the pairs of integers of visited coordinates, is set to **true**. after visit of a coordinate point. One is right after the if statement, whilst one is in the while loop. I'm not quite sure what led to the speed increase.

Any help will be greatly appreciated.

# Answer
Suppose 3 rooms each of which contains number 6 have been visited before any room the product of whose coordinates is 6 has been visited.

In the first version of your code, every room of the second kind will be put into the queue 3 times.

In the second version of your code, every room of the second kind will be put into the queue only 1 time (except possibly the room at (A,B), which will be put into the queue 2 times).

The difference between 3 times and 1 time is what slows down the first version. In general, there might be $m$ rooms of the first kind for the corresponding second kind. The appropriate average of $m$ in the test cases is substantially greater than 1. Hence you see the significant speedup from the first version to second version.

---

A good rule of thumb across all these kinds of searching problems is to try setting `visited` as soon as possible to avoid unnecessary and sometimes even incorrect computations.
> 1 votes

---
Tags: complexity-theory, time-complexity, queues
---


# Question
Title: would complexity of constraint satisfaction problem bound the constrained optimization problem?
If a constraint satisfaction problem $x \in Y$ is NP-Complete. Can I conclude that the optimization problem $^\* =\text{argmax}\_x (x)$ s.t. $x \in Y$ is also NP-Complete?

# Answer
> 1 votes
No, no optimization problem can be $\mathsf{NP}$-complete since all $\mathsf{NP}$-complete problems are in $\mathsf{NP}$ and $\mathsf{NP}$ only contains **decision** problems.

---
Tags: complexity-theory, constraint-satisfaction
---


# Question
Title: How does Instruction Set Architecture (ISA) affect performance?
If 2 CPUs have the same Instruction Set Architecture, which of the following properties will be the same?

1. Clock Rate
2. CPI
3. Execution time
4. No. of instructions
5. MIPS

# Answer
> 1 votes
Same ISA means they understand the same instructions in binary. They can certainly be very different in speed. Look at e.g. the x86 family (disregard the instructions added over time). The very latest Pentium is certainly much faster than the first 386, and even within each "number" there are variations.

Even crasser, remember ye goode olden days of i486 and overclocking? Even *the same chip* can (sometimes) run at different clock rates. BTW, that is something current laptops do: To conserve battery power, the CPU runs at a lower clock rate when possible.

# Answer
> 1 votes
Only the number of instructions would be the same. Clock Rate, CPI, Execution time and MIPS depend on the micro-architecture (also known as hardware architecture).

---
Tags: computer-architecture
---


title: Converting into CNF

text:
# Question
Title: Converting into CNF
I am still a bit confused by how to convert into CNF even though I have the rules written down.

How do I convert the following sentence into CNF?

$(I \lor M) \Rightarrow H$

I know I need to get rid of the implication symbol and when its in the form $(I \Rightarrow H)$ or $(M \Rightarrow H)$ then I can see how to do it, but when its one sentence like this how do I factor out the implication?

The reason I am stuck is because I do not know how to get rid of the resulting or:

$(\neg I \lor H) \lor (\neg M \lor H) \Rightarrow I$ think the OR here needs to be an AND to be CNF

Thanks

# Answer
> 1 votes
We have that $A \Rightarrow B$ is same with $\neg A \lor B$. This gives, that $(I \lor M)\Rightarrow H$ is same with $\neg(I \lor M)\lor H$.

And we have that $\neg(I \lor M)$ is same with $\neg I \land \neg M$

Putting together we have that $(I \lor M)\Rightarrow H $ is same with $\neg I \land \neg M \lor H = (\neg I \land \neg M) \lor H = (\neg I \lor H) \land (\neg M \lor H )$.

---
Tags: logic, artificial-intelligence
---


# Question
Title: Creation of skip list: Las Vegas or Monte Carlo?
I have come across this video on skip lists:

https://www.youtube.com/watch?v=UGaOXaXAM5M

Clearly, the creation of skip-list from a sorted singly linked list is a randomized algorithm. But I am confused: is it a Las Vegas algorithm or a Monte Carlo algorithm?

I feel it is a Monte Carlo algorithm since there is a possiblity of an incorrect output(degenerate case where every node is in every level), and if we don't maintain a checking condition, we won't know where the algo went wrong.

Am I correct?

P.S. My first question here.

# Answer
The difference between a Las Vegas algorithm and a Monte Carlo algorithm is that a Las Vegas algorithm is always correct but its running time may be large with small probability, whereas a Monte Carlo algorithm always has the same time complexity but may give wrong results with small probability.

These definitions are more appropriate for decision problems and optimization problems, and less for data structures. That said, they still make sense for data structures. Here are two examples:

* Skip-lists correctly implement the list abstract data type. They are efficient with high probability. This is like a Las Vegas algorithm.
* Bloom filters are always efficient (in this case we care about space complexity), but may give wrong results to queries. This is like a Monte Carlo algorithm.

Most data structures are designed with the Las Vegas objective in mind.
> 1 votes

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


title: Running time question

text:
# Question
Title: Running time question
If I have two kinds of LinkedList $A$ and $B$.

> $A$ is a move to front one which means:
> \>\>\> lst1 = 1, 2, 3, 4, 5, 6, 7, 8, 9
> \>\>\> lst1.**contain**(7)
> True
> \>\>\> lst1.to\_list
> 7, 1, 2, 3, 4, 5, 6, 8, 9
> $B$ is a swap list, which means:
> \>\>\> lst2 = 1, 2, 3, 4, 5, 6, 7, 8, 9
> \>\>\> lst2.**contain**(7)
> True
> \>\>\> lst2.to\_list
> 1, 2, 3, 4, 5, 7, 6, 8, 9

I want to find a searching sequence such that the running time of $B$ is faster than $A$. I mean the Theta of them would be different. The length of lst1 and lst2 are both $n$. We search $m$ times and can search different elements for different times.

# Answer
> 1 votes
The move-to-front heuristic is 4-competitive in the model where swapping adjacent elements costs one unit. This means that if the optimal strategy has cost $N$, then move-to-front has cost at most $4N$. In particular, if a swap list has cost $N$ on some searching sequence, then move-to-front will have cost at most $4N$.

See for example MIT OpenCourseWare or Princeton Slides.

# Answer
> 0 votes
The sequence `7, 1` will be ever so slightly faster for $B$ than for $A$, however, both structures have running time $O(n)$ for checking membership and are therefore not particularly suited if this is the main point of the data structure.

The former list is reminiscent of a Least Recently Used (LRU) cache.

---
Tags: runtime-analysis
---


# Question
Title: Is it possible to compute the minimum vertex covering set in quasi-polynomial time, by knowing the vertex cover number?
If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$ in quasi-polynomial time? As I found, we cannot find any quasi-polynomial time solution for NP-hard problems (or at least it is a strong conjecture) such as finding the minimum vertex covering set.

# Answer
Suppose there is an algorithm $A(G,c)$ which runs in time $T(n)$, where $n$ is the number of vertices in $G$, as long as $c$ is the vertex cover number.

Given a graph $G$, run $A(G,0),\ldots,A(G,n)$ in parallel, for $T(n)$ time each. Some of the copies will terminate within $T(n)$, outputting a set. Out of all such outputs which are vertex covers, choose the one of minimal size. This gives an algorithm for minimum vertex cover running in time $O(nT(n))$.
> 1 votes

---
Tags: complexity-theory, graphs, complexity-classes, vertex-cover
---


# Question
Title: Metrics on which Clock Cycles Per Instruction(CPI) depends
In the book - *Computer Organization and Design: The Hardware/Software Interface \[RISC-V Edition\] by Patterson and Hennessy*, CPI is defined like this:

> The term **clock cycles per instruction**, which is the average number of clock cycles each instruction takes to execute, is often abbreviated as CPI. Since different instructions may take different amounts of time depending on what they do, CPI is an average of all the instructions executed in the program. CPI provides one way of comparing two different implementations of the identical instruction set architecture, since the number of instructions executed for a program will, of course, be the same.

---

I am solving *question 1.7* from the Exercises section of *chapter 1*:

> **1.7** Compilers can have a profound impact on the performance of an application. Assume that for a program, compiler A results in a dynamic instruction count of 1.0E9($I\_A)$ and has an execution time of 1.1 s($T\_A$), while compiler B results in a dynamic instruction count of 1.2E9($I\_B)$ and an execution time of 1.5 s($T\_B$).
>
> a. Find the average CPI(both $CPI\_A$ and $CPI\_B$) for each program given that the processor has a clock cycle time of 1 ns.
>
> b. Assume the compiled programs run on **two different processors**. If the execution times on the two processors are the same, how much faster is the clock of the processor($P\_A$) running compiler A’s code versus the clock of the processor($P\_B$) running compiler B’s code?
>
> c. A new compiler C is developed that uses only 6.0E8 instructions($I\_C$) and has an average CPI($CPI\_C$) of 1.1. What is the speedup of using this new compiler versus using compiler A or B on the original processor?

Attempted Solution:

> a.
>
> > Using the formula $T = I * CPI * CC$
> >
> > where $CC = $ clock cycle time, I calculated *part a* of the question
> >
> > $CPI\_A = \frac{T\_A}{I\_A * CC\_A} = 1.1$
> >
> > Similarly, $CPI\_B = 1.25$
>
> b.
>
> > Given, execution times on two different processors are same
> >
> > Again using the formula, I calculated
> >
> > $\frac{T\_A}{T\_B} = \frac{I\_A * CPI\_A * CC\_A}{I\_B * CPI\_B * CC\_B}$
> >
> > My task is to find $\frac{CC\_A}{CC\_B}$, which I am unable to, since I don't know the value of $CPI\_A$ and $CPI\_B$.
>
> c.
>
> > Again, using the formula, I calculated
> >
> > $\frac{T\_A}{T\_C} = \frac{I\_A * CPI\_A * CC\_A}{I\_C * CPI\_C * CC\_C}$
> >
> > My task is to find $\frac{T\_A}{T\_C}$, which I am unable to, since I don't know the value of $CPI\_A$. Here I know that, $CC\_A = CC\_C$, since the processor remains same.

**In *part b* and *part c* of the solution, will the value of $CPI$ be same as that calculated in *part a*. If so, please explain why? What are the metrics on which $CPI$ depends. Does it not change with processor, or execution time, or any other metric?**

# Answer
> 1 votes
In part `a` same processor is assumed, and 2 compilers are used. In part `b`, 2 processors with different clock frequency is used, since the execution times for both processors are equal but the CPIs and dynamic instruction counts are unequal. The CPI for both processors is the same as the CPI from part `a` because the same compilers were used and the same compiled program is run. So the dynamic instruction count and CPI is the same from part `a`.

$\frac{f\_A}{f\_B}=\frac{CC\_B}{CC\_A}=\frac{T\_B}{CPI\_B\*I\_B}\*\frac{CPI\_A\*I\_A}{T\_A}$.

Since $T\_A=T\_B$, we get

$\frac{f\_A}{f\_B}=\frac{CPI\_A\*I\_A}{CPI\_B\*I\_B} = \frac{1.1\*1\*10^9}{1.25\*1.2\*10^9} =0.7333 $

or $\frac{f\_B}{f\_A} = 1.37$

For part `c`, use CPIs obtained in part `a`.

Speedup

$\frac{T\_A}{T\_C}=1.67$

$\frac{T\_B}{T\_C}=2.27$

CPI depends on the processor's hardware architecture, processor clock frequency, compiler and the number of instructions.

---
Tags: computer-architecture, cpu, performance, clocks
---


# Question
Title: What is the complexity class of finding vertex cover number of a simple graph?
Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the vertex cover number denoted by $\tau(G)$. Is there any previous result about this research question?

# Answer
It is actually finding the number that is NP-complete. The (decision) problem is formally stated as follows:

**Vertex cover**. Given a graph $G = (V, E)$ and an integer $k$, does there exist a set of at most $k$ vertices $C \subseteq V$ such that every edge has at least one endpoint in $C$?

As you can see, this is precisely your $\tau(G)$.

The other problem is often called the *optimization* problem, and is defined as following:

**Vertex cover optimization**. Given a graph $G = (V, E)$, find a set $C \subseteq V$ of minimum size such that every edge has at least one endpoint in $C$.

---

The two problems are quite easy to jump between, at least if you are given polynomial time. If you have an algorithm for the optimization problem, I'm sure you have already found out how to answer the decision version.

But given an algorithm for the decision version it is quite easy to create an optimization algorithm. You can try to work it out yourself, but a hint is to see what happens with $\tau(G)$ if you remove a vertex from the graph.
> 1 votes

---
Tags: complexity-theory, graphs, complexity-classes, vertex-cover
---


# Question
Title: Which data structure can be used to determine most experienced person in a shift?
**Problem Statement:** There are $n$ hours in a day and you have $w$ workers. For each worker $i$ you will be given $x\_i$ (work experience), $s\_i$ (shift start time) and $e\_i$ (shift end time) on a separate line. Here $s\_i$ and $e\_i$ are both inclusive. At any given hour $t$ in a day, you have to determine who is the most experienced worker available.

I thought of two approaches:

1. Keep an interval array of size $n$. For each worker $i$, from index $s\_i$ to $e\_i$ of the array, fill it with $x\_i$ if current value in the array is lesser. This is memory intensive.
2. Store $\left( x\_i, s\_i, e\_i \right)$ for each worker $i$ in a list. Loop through the list for every $t$ provided to find the most experienced person. This is CPU intensive.

I want to know which data structure can be used to solve this problem optimally.

# Answer
Let $s\_i$, $e\_i$, $x\_i$, be the shift start time, shift end time, and experience of the $i$-th worker. For each worker define the following two *events*:

* A shift-start event is a triple $(s\_i, 0, i)$.
* A shift-end event is a triple $(e\_i, 1, i)$.

Collect all events in an array $E$ and sort it in increasing order (lexicographically). This requires $O(w \log w)$ time.

We will process these events in order. Maintain a pointer $p$ to the next event in $E$ to process. Also maintain a priority queue $Q$ that supports deletions (an implementation using a binary heap suffices). Initially $Q$ is empty.

For each hour $t$ of the day, in increasing order, do the following:

* Scan $E$ by advancing $p$ to find all (shift-start) events of the form $(t, 0, i)$. For each such event, add key $i$ with priority $x\_i$ to $Q$.
* Look at the key $j$ at top of $Q$ (in constant time). Report $j$ as the most experienced worker at time $t$.
* Scan $E$ by advancing $p$ to find all (shift-end) events of the form $(t, 1, i)$. For each such event, delete key $i$ from $Q$.

This requires $O(w)$ space to store $E$ and $Q$, and at most $O(n + w \log w)$ time since there are $2w$ insertions/deletions into/from $Q$, each of which requires $O(\log w)$ time.
> 3 votes

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


title: Sum of products over k-permutations

text:
# Question
Title: Sum of products over k-permutations
Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n\_1...n\_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to most efficiently calculate the sum, over all $K$-permutations, of products $A\[1,n\_1\] * A\[2,n\_2\] * ... * A\[k,n\_K\]$?

For example, let $K=3$ and $N=5$. One possible K-permutation is (5, 1, 3), and the corresponding product is $A\[1,5\] * A\[2,1\] * A\[3,3\]$. But what must be calculated is the sum of such products over all K-permutations, e.g.:

$$ A\[1,1\] * A\[2,2\] * A\[3,3\] + \\ A\[1,1\] * A\[2,2\] * A\[3,4\] + \\ A\[1,1\] * A\[2,2\] * A\[3,5\] + \\ A\[1,1\] * A\[2,3\] * A\[3,4\] + \\ A\[1,1\] * A\[2,3\] * A\[3,5\] + \\ A\[1,1\] * A\[2,4\] * A\[3,5\] + \\ ... $$

I am not even sure there is an efficient (polynomial time) solution, the most I have been able to come up with has about $2^M$ complexity which is unacceptable.

# Answer
> 2 votes
When $K = N$, the polynomial you are trying to compute is known as the permanent. The best algorithms for computing the permanent use $\tilde{O}(2^N)$ arithmetic operations, see Wikipedia. The VP≠VNP conjecture implies that the permanent cannot be computed using a polynomial number of operations.

For general $K$, your function is a known extension of the permanent. Ryser's algorithm, one of the $\tilde{O}(2^N)$ algorithms for the square case, extends to the rectangular case as well.

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


# Question
Title: Why is SAT so important in theoretical computer science?
In my *Computability and Complexity* class, we are focusing on P, NP, NP-complete, and NP-hard problems and the one thing that keeps coming up is the SAT problem, in the context of reduction from one complexity to another or to explain certain concepts.

Why is SAT so ubiquitous in theoretical computer science?

# Answer
SAT was the first problem shown to be NP-complete, in Stephen Cook's seminal paper. Even nowadays, when introducing the theory of NP-completeness, the starting point is usually the NP-completeness of SAT.

SAT is also amenable to surprisingly successful heuristic algorithms, implemented by software known as *SAT solvers*. As a result, there is a lot of practical interest into formulating problems efficiently as instances of SAT.

SAT also shows up in fine-grained complexity, one of whose main assumptions is the strong exponential time hypothesis, which is a conjecture on the computational complexity of SAT.
> 47 votes

# Answer
It is worth mentioning that mathematicians cared about SAT \[1\] even before it was shown to be NP-complete. See for example Godel's 1956 letter to Von Neumann, where it is known that SAT is $\Omega(n)$ (which I believe is still the best lower bound known, although we know explicit constant factors for some lower bound at least), and discussed that if SAT is $O(n^2)$ it would have vast consequences for mathematics.

I have quoted the relevant passage below for completeness:

> One can obviously easily construct a Turing machine, which for every formula $F$ in first order predicate logic and every natural number $n$, allows one to decide if there is a proof of $F$ of length $n$ (length = number of symbols). Let $\Psi(F, n)$ be the number of steps the machine requires for this and let $\phi(n) = \max\_F\Psi(F, n)$. The question is how fast $\psi(n)$ grows for an optimal machine. One can show that $\psi(n)≥kn$. If there really were a machine with $\phi(n)\sim kn$ (or even $\sim kn^2$), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungsproblem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine.
>
> ...
>
> after all $\phi(n)\sim kn$ (or $\sim kn^2$) only means that the number of steps as opposed to trial and error can be reduced from $N$ to $\log N$ (or $(\log N)^2$). However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.

---

\[1\] The problem discussed there is perhaps closer to something like TQBF than SAT, but Arora and Barak describe it as SAT in passing, and I am no logician.
> 15 votes

# Answer
I'll add another perspective, based loosely on Andreas Blass's comment on the accepted answer: SAT is in some sense 'conceptually universal' for a broad class of NP-complete problems. To be more specific, I'd argue that SAT captures the essence of *Constraint Satisfaction Problems*: find a configuration that satisfies a given set of conditions. Sudoku is a canonical example: we want to place a multiset of objects (usually given as numbers) in a grid such that each row has exactly one of each object *and* each column has exactly one of each object *and* each specific subgrid has exactly one of each object.

SAT acts as a sort of assembly language for CSPs; we can 'compile down' a constraint problem into a set of specifically boolean constraints and then transform them into normal form. For instance, for a 4x4 sudoku we could use $4\times4\times4=64$ variables $v\_{i,j,n}$ for $1\leq i,j,n\leq 4$ where $v\_{i,j,n}$ is true iff the $(i,j)$'th cell of the grid contains the object labeled $\bar{n}$. The constraint that the first row has at least one instance of object $\bar{1}$, for instance, is the clause $v\_{1,1,1}|v\_{2,1,1}|v\_{3,1,1}|v\_{4,1,1}$. The constraint that it has no more than one is a little more complicated, but still 'just' polynomially so; it can be expressed as $\neg(v\_{1,1,1}\wedge v\_{2,1,1})$ $\wedge\neg(v\_{1,1,1}\wedge v\_{3,1,1})$ $\wedge\neg(v\_{1,1,1}\wedge v\_{4,1,1})$ $\wedge\neg(v\_{2,1,1}\wedge v\_{3,1,1})$ $\wedge\neg(v\_{2,1,1}\wedge v\_{4,1,1})$ $\wedge\neg(v\_{3,1,1}\wedge v\_{4,1,1})$. In other words, make sure that no two cells in the row both have an instance of object $\bar{1}$. Similar constraints will make sure that every cell has an object and no single cell has two objects in it, etc.

This process is obviously clunky, but hopefully you can see how it's also *mechanical*, in much the same way as translating a higher-level programming language into assembly code is; we simply need to find some set of booleans that describes the possible state of the thing we're looking for and then write out the set of constraints that those booleans must satisfy both in order to be a valid configuration and in order to be a solution to the problem. Indeed, my understanding is that actual CSP solvers work a lot like this: there's a 'higher level language' for expressing constraints in, and those constraints are then translated down to either SAT or something much like it, to which various solving algorithms can be applied.
> 12 votes

# Answer
You've gotten a number of good answers already so I hesitate to try to contribute more, but I see two more factors that I think make SAT particularly interesting to a lot of people.

### "Nearly" Polynomial

The first factor is the "proximity" between 2SAT and 3SAT. We know how to solve 2SAT problems in polynomial time, and have proven that 3SAT is NP complete. It's easy to compare the two, see how they differ, come up with ideas for how it might be possible to transform a 3SAT problem into some equivalent 2SAT problem, etc.

### Easy Verification

The other factor is that with SAT problems, the goal is clear and it's usually pretty obvious whether we've actually solved the problem or not.

Many of the better known NP-complete problems deal with optimization (e.g., knapsack, traveling salesman). Consider, for the moment, if I have an algorithm that claims to produce the optimal result for traveling salesman in polynomial time.

Especially if you try to examine this on a black-box basis, it may be difficult to be sure whether this actually produces the right result or not. In most cases, about all you could do would be to use some well-known algorithm, and try to find a set of inputs for which you could get a better result than I did. But it's basically a completely open-ended search, and your results could never be "yes it works"--only "it doesn't work" or "it might work".
> 5 votes

---
Tags: complexity-theory, np-complete, satisfiability
---


# Question
Title: Why does the Pumping Lemma Constraint |xy| ≤ p mean that y can't be 1 in the string 0p1p
I am trying to get my head around the Pumping Lemma to prove a language is non-regular.

I am reading the Sipser text book and he gives the following example.

Let B be the language $\\{0^n 1^n | n \ge 0\\}$

Let $s = 0^p 1^p$

I understand that the idea is you can split this string into xyz such that y can be pumped. It is the constraint of $|xy| \le p$ that is confusing me.

Sipser notes that due to this constraint y could not equal 01 nor could it equal 1. Why would y equaling either of those values violate the given constraint.

I am generally quite confused by the Pumping Lemma so any general advice or good resources you can recommend, I would appreciate.

Thanks!

# Answer
Let $p$ be the pumping length of your language. As you say, the string $s$ can be written as $s = xyz$ where $|xy| \le p$. By the choice of $s=0^p 1^p$, you know that the first $p$ characters of $s$ are all $0$, therefore $xy$ (which contains at most $p$ character) must be a string containing only $0$s. Since $y$ is a suffix of $xy$, $y$ must also contain only $0$s.
> 2 votes

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


title: Correctness of Dijkstra's algorithm

text:
# Question
Title: Correctness of Dijkstra's algorithm
This question is about the correctness proof of Dijkstra's algorithm in the third edition of *Introduction to Algorithms* by Cormen et al. (pages 660–661).

The proof makes a case that considering path $p$ is the shortest path that connects a vertex in set $S$ (set of vertices where the distance of nodes to node $s$, the starting node, is minimal) to a vertex in set $u$ in $V-S$. It then considers the first vertex as $y$ in set $V-S$ along the path $p$. It argues that $y.d \leq u.d$ which is intuitive as $y$ precedes $u$ in set $V-S$. The second argument that since both $u$ and $y$ were in $V-S$ when $u$ was chosen thus $u.d \leq y.d$. I have following two doubts about the second argument:

1. Why were $y$ and $u$ both in $V-S$ when $u$ was chosen? We know by our construction that when both $u$ and $y$ are in $V-S$, then $y$ will be chosen before $u$.
2. The node $u$ is chosen such that when it's added to set $S$ it is not at the minimum distance from node $s$. How is this used in this proof?

# Answer
In answer to both of your questions:

Firstly, note that during the maintenance phase of the loop invariant proof, we are in the process of inserting *u* into *S*, and the way that *y* is defined is that it is a node in *V\S* while this is happening, therefore *u* and *y* exist in *V\S* at the same time when *u* is inserted. This answers your first question.

Secondly, note that in the proof, we assume that *u.d**δ(s,u)*. It therefore follows that there would be a pair of nodes *x* and *y* (such that *π(y)=x* such that *x ∈ S* and *y ∈ V\S*) such that *y ≠ u* and therefore *y* must come **before** *u*, because otherwise from the Convergence Property it would automatically follow that *u.d = δ(s,u)* which would be a contradiction to our assumption. Therefore from here it must follow that *y* comes before *u*. But note that from the first point I made above, *y* must come **after** *u*. And this is exactly the whole point of the proof, both of these things cannot happen simultaneously unless *y.d = δ(s,y) = δ(s,u) = u.d*.

Note that we used the assumption that *u* is not the minimal distance from *s* when added to *S* by showing that we reach a contradiction if we assume this.
> 1 votes

---
Tags: algorithms, algorithm-analysis, shortest-path, correctness-proof, loop-invariants
---


# Question
Title: How is a program stored before compiling?
When we write code, after compilation the code will be converted to machine language and then stored in the hard disk. But before compiling the code, it is still in the high-level language. How and where is the memory allocated for the source code before compilation?

I assume that before compiling the code is stored in RAM. How is the code stored in RAM? Because I think we can store only machine language in RAM.

# Answer
> 4 votes
Here is a **brief overview** of a typical compilation and execution flow on a computer:

1. Type in the source code in a plain text editor.
2. This source code consists of characters. Characters are encoded as bits. An example of encoding is ASCII. These bits are stored on the disk, when you save the source code.
3. Invoke the compiler to compile the source code. The compiler parses the source code file(s), produces object code and links the object files to produce a machine language file called executable. The executable is stored on the disk.
4. Run the executable. This is called execution.

* At all steps in the process, the operating system controls and co-ordinates processes and does the memory management.
* Data is stored in the RAM temporarily when the process running on the machine requires it.
* Data is stored on the disk when it needs to be stored permanently.
* There is also a process called swapping which is done by the OS when there is no RAM memory left. A section of the disk memory is used for swapping.
* There can be multiple processes running on the machine. These processes can run parallely or concurrently. The operating system allocates resources for processes and schedules the processes to run using scheduling algorithms.

This was just a brief overview. To learn more, I highly recommend the free online course on MIT's OCW called Computational Structures.

# Answer
> 2 votes
Typically source code is stored in a file on your hard drive or SSD drive. Usually you have backup copies in all kinds of places, and you use source code control to store more copies in more places, together with the ability to get older versions or newer versions to your files at any time.

When compiling, the source code files are read like any other files. Maybe they are read completely, or only in parts. Whatever the author of the compiler thinks is most efficient. The source code will be moved to the address space of the compiler, and then to RAM. Depending on your operating system, if you compile the same program multiple times, file contents may be automatically cached in RAM.

# Answer
> 0 votes
This reply was stored in RAM on your computer as part of the mechanisms involved in you reading it.

It is very definitely not written in machine code. I don't even know what the machine code of your computer is.

Fundamentally, RAM stores bits. The *meaning* of the bits is not inherent in the bits. These particular bits are used as data to some software that turns them into dots on a screen.

More fundamentally: if RAM only stored "machine code", there would be no data for the machine code to compute with.

---
Tags: computer-architecture, operating-systems, compilers, memory-management
---


# Question
Title: Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $
Is there any difference between saying $ L\_1 = \\{(a^n b^n)^m \mid n, m \ge 1\\} $ with $ L\_2 = \\{a^n b^n \mid n \ge 1\\}^+ $?

I know that for $v = abab$ we have $v \in L\_1$ and $v \in L\_2$

my understanding is that there is no difference between them and for $w = abaaabbb$ we have $ w \in L\_1$ and $w \in L\_2$ . but I have a feeling that maybe $w \notin L\_1$, because it doesn't have the same $n$ for different $a^n b^n$.

Also, does the same apply for Kleene star $\*$ too? for example if we have $ L\_3 = \\{(a^n b^n)^m \mid n \ge 1, m \ge 0\\} $ and $ L\_4 = \\{a^n b^n \mid n \ge 1\\}^\* $, Are $L\_3$ and $L\_4$ equal?

# Answer
Indeed, $abaaabbb \notin L\_1$ because the string is not of the form $(a^nb^n)^m$ which is the repetition of a fixed string with the same number of $a$ and $b$.

The language $L\_2$ is the Kleene closure of $\\{a^nb^n \mid n\ge1\\}$, consisting of all arbitrary concatenations of strings of the form $a^nb^n$. We can choose different strings of this form, and do not have to stick with the same one each time, like in $L\_1$. Hence $L\_2$ contains $abaaabbb$.

As for your original version of the question (now edited) it contained the notation $\\{(a^nb^n)^+ \mid n\ge1\\}$. I would not denote a language that way. The Kleene plus is a language operator, which takes a language (set of strings), and turns it into a language. By writing $\\{(a^nb^n)^+ \mid n\ge1\\}$ you get the set $(a^nb^n)^+$ within the set brackets, which can be called a "type error".
> 2 votes

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


# Question
Title: Finding shortest path for DAG using dynamic programming vs topological sort?
Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the minimum of all vertices that have a path to it?

# Answer
> 0 votes
To use dynamic programming, you need to choose the order in which you fill in values for the vertices. The correct order is a topologically sorted order (any other order won't work). So, the two solutions are in some sense equivalent. Any solution is likely to use both components: topological sorting to determine the order to enumerate the vertices, and something like dynamic programming to fill in the value at each vertex.

---
Tags: graphs, dynamic-programming, shortest-path, directed-graphs
---


# Question
Title: Is machine epsilon the largest relative error in representing a number as a floating point number?
Is machine epsilon the largest relative error in representing a number as a floating point number?

There are so many definitions of machine epsilon. I'm starting to get confused. Isn't the machine epsilon the smallest?

# Answer
> 1 votes
In the *most common* usage, and in particular in IEEE-754, machine epsilon is the smallest number $\epsilon$ such that $1 + \epsilon \ne 1$.

It does have an interpretation in terms of relative distance between numbers: It is the largest relative separation of two consecutive normal numbers.

There are a couple of important points to understand here:

* This is only about *normal* numbers, as opposed to *subnormal* numbers (i.e. what older standards called "denormal numbers").
* It is about *consecutive* numbers, namely, some floating point number and its closest neighbour.
* Machine epsilon measures *separation*, not *error*. It is the relative distance between those floating-point numbers, not the relative error between a floating point number and anything.

So if $x\_1$ and $x\_2$ are consecutive normal numbers, then:

$$0.5\epsilon \le \frac{|x\_2 - x\_1|}{\max(|x\_1|,|x\_2|)} \le \epsilon$$

So if you have a candidate real number, and you want to represent it as a floating-point number, how bad can the relative error be?

As gnasher729 rightly pointed out, it can be as large as you want if the real number would overflow, underflow, or be subnormal. But assuming that it's in a reasonable range, meaning that it is between two consecutive normal numbers, then one of those normal numbers is within $0.5\epsilon$ of it in a relative sense.

Because this is a fraught definition, the term that we usually use is "units of last place", or "ulp" for short. If a real number is within the normal number range, there is a floating point number whose error is at most 0.5ulp.

# Answer
> 0 votes
If you read "machine epsilon" you really need to look up the definition that your book uses for it. It is all over the place. I’d define it as “difference between 1 and the next larger floating point number”, alternatively “the value of the least significant bit of a floating point number between 1 and 2”. Let’s call this number u for short.

"The largest relative error" is very unlikely to be the "machine epsilon": All computers including tablets and phones in my possession have floating point arithmetic following the IEEE 754 Standard, and there the largest possible relative error is -1 or +1: Let d be the value of the least significant bit of a denormalised numbers, then a result of d/2 would be rounded to 0 for a relative error of -1; a result just a tiny bit larger than d/2 would be rounded to d, for a relative error close to 1.

For normalised results, rounding to nearest, if 2^k \<= x \<= 2 * 2^k then numbers are 2^k * u apart. The absolute rounding error is up to 1/2 2^k * u. If x = m * 2^k with 1 \<= m \<= 2, then the relative error is at most (1 / 2m) * u. This means results slightly less than a power of two have lower bounds for the relative error. This can be used if you calculate something like a * b * c: Sometimes you can rearrange the order of operations to reduce the bounds for the rounding error.

There are implementations like IBM’s “long double” on POWER where machine epsilon makes little sense.

---
Tags: computer-architecture
---


# Question
Title: How do i make sure i get the correct Bellman Ford path?
I was studying shortest path algorithms and was met with an issue regarding Bellman Ford for the image below.

Following the graph, i see that node 3 has a length of 1 while node 2 has a length of 2. When computing the path from 1 to 8 which is the correct path between 1-\>2-\>6-\>4-\>7-\>8 and 1-\>3-\>2-\>6-\>4-\>7-\>8 ?

I can see that 1-\>2-\>6-\>4-\>7-\>8 has the smallest path length but i'm confused because node 2 has length 2 while node 3 has length 1.

Will Bellman always give the shortest possible path or might it output a longer path because one of the nodes had shorter length but led to a longer path?

# Answer
From Wikipedia:

> The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

What is a shortest path? According to Wikipedia:

> In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

Wikipedia isn't always a reliable source, but in this case the definitions are spot on. Suppose that $G=(V,E,w)$ is a weighted undirected graph. A *path* between two vertices $x,y \in V$ is a list $$ v\_0 = x, v\_1, \ldots, v\_\ell = y $$ such that $(v\_i,v\_{i+1}) \in E$ for all $i \< \ell$ (possibly $\ell = 0$). The *weight* of the path is $$ \sum\_{i=0}^{\ell-1} w(v\_i,v\_{i+1}). $$ A *shortest path* between $x$ and $y$ is a path with minimum weight.

The Bellman–Ford algorithm finds the lengths of all shortest paths from a given vertex $x$ to all other vertices. It also generates auxiliary information which makes it possible to find the corresponding shortest paths.
> 0 votes

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


# Question
Title: DFA for $\{0^m1^n \mid m+n \text{ is even}\}$
How do I construct a DFA for the language $\\{0^m1^n \mid m+n \text{ is even}\\}$? The corresponding regular expression is $(00)^\*(11)^\* + (00)^\*0(11)^\*1$.

# Answer
This language can be described as 'zero or more zeroes followed by zero ore more ones, where if the number of zeroes is even, so are the number of ones, and vice versa'.

So you just need to keep track of the parity of both the zeroes and ones, and if they match, accept.
> 1 votes

# Answer
The easiest way to construct a DFA for your language is your product construction.

The starting point is a DFA for $0^\*1^\*$ (above) and one for all strings of even length (below):

$0^\*1^\*$" /\>

Applying the product construction, we get a DFA for the intersection:

We can improve on this DFA slightly by merging the two states on the right:

This is the minimal DFA for the language. To show this, it is enough to show that two different accepting states are needed, and that three different non-accepting states are needed.

We need two different accepting states due to the words $\epsilon$ and $01$: while $00$ is in the language, $0100$ isn't.

We need three different rejecting states due to the words $0,1,10$: while $00$ is in the language, $10$ and $100$ aren't; and while $11$ is in the language, $101$ isn't.
> 0 votes

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


# Question
Title: Selecting connected subgraph that exceeds value c, with least possible weight
Given a graph $G$ where each node has a value $c$ and weight $w$, I want to select a connected subgraph $V^\*$, such that,

1. Sum of all values in $V^\*$ crosses threshold $t$.
2. Sum of all weights(say $w^\*$) in $V^\*$ is as low as possible.

A practical example is finding smallest continuous area of a country that hosts at least $x\\%$ of the population. In this case, value would be population, and weight would be area.

I found a related question, but it only asks about the complexity, not the algorithm.

I thought of 0 - 1 knapsack, such that values and weights swap role. So,

1. Size of knapsack is $t$, however we are allowed to cross it once.
2. minimize $w^\*$.

However, I think this won't work, mainly because we can't order the nodes by $value/weights$, and secondly because of ability to exceed knapsack size.

# Answer
> 3 votes
This problem is NP-hard. Let $S = \\{x\_1, \dots, x\_n\\}$ be an instance of partition. Create a clique $G$ on $n$ nodes $v\_1, \dots, v\_n$. Set both the cost and the weight of $v\_i$ to $x\_i$. Set $t = \frac{1}{2}\sum\_{x\_i \in S} x\_i$.

If there is a subset $C$ of $S$ such that $2 \sum\_{x\_i \in C} x\_i = \sum\_{x\_i \in S} x\_i$, then the set of vertices $\\{v\_i \mid x\_i \in C\\}$ is connected, has total value $t$ and total weight $t$.

If there is no subset $C$ of $S$ such that $2 \sum\_{x\_i \in C} x\_i = \sum\_{x\_i \in S} x\_i$ then every subset of vertices of $G$ either has total value smaller than $t$ (and hence is not a feasible solution), or has a total value larger than $t$, and hence also weight larger than $t$.

Then you have that the answer to the instance of partition is yes if and only if the optimal solution to your problem has measure (total weight) $t$.

# Answer
> 1 votes
Here is another reduction from minimum Steiner tree that also shows that your problem is *strongly* NP-hard.

Let $\langle G, T \rangle$ be an instance of minimum Steiner tree, where $G=(V,E)$ is a graph and $T$ is a set of terminals. Let $w\_e$ be the weight of edge $e$ in $G$ and assume that all $w\_e$ are positive.

Construct a new graph $G'$ by starting from $G$ and splitting each edge $e$ by adding vertex $v\_e$, i.e., replace $e=(u,v)$ with the two edges $(u, v\_e)$ and $(v\_e, v)$. Assign weight $w\_e$ to each $v\_e$. Assign value $1$ to all vertices in $T$. All unspecified weights/values are $0$.

An instance of your problem consists of the graph $G'$ and the threshold $t=|T|$.

A Steiner tree $S=(V',E')$ of $G$ having weight at most $W$ can be converted into a subgraph $H$ of $G'$ with weight $W$ and value $t$. Simply chose $H$ as the subgraph of $G'$ induced by the vertices in $V' \cup \\{v\_e \mid e \in E'\\}$.

Similarly, a solution $H=(V',E')$ of weight $W$ to your problem must contain all terminals and can be converted into a Steiner tree $S$ with weight at most $W$ by taking any spanning tree of the subgraph $G\_H$ of $G$ induced by the edges in $\\{ e \in E \mid v\_e \in V'\\}$. Notice that if $H$ is an *optimal* solution to your problem then $G\_H$ is already tree (this is ensured by the condition $w\_e \> 0$).

---
Tags: algorithms, graphs
---


# Question
Title: How do I compute the address of the next element?
I have to work on something , but I am making an error that I can not identify. Propably, it is going to sound simple to you but it's my first course on computer architecture and there is nothing in my slides or book. "We are given a memory, where the smallest chuck of information that can be adressed is 1 byte, and we use 32 - bit memory adresses. Arrays , contain doubles, and each elememnt is an 8 - byte one." &x\[0\]=0x0000A100 ."

I want to compute the adresses of &x\[i\] , i=1,2.. What I did thought was the right approach is: Since, we have a memory that is byte - adressable then we can do it as such : &x\[i\] and &x\[i+1\] have a dc offset which is 8 -byte and since it is byte adressable then :
&x\[i+1\] = &x\[i\] + 8
And I used an online calculator to get these results :

But they are wrong...

# Answer
The offset should be 4 bytes, since 1 byte is 8 bits and 32 bits contain 4 bytes.
> 0 votes

---
Tags: computer-architecture, memory-hardware, cache
---


# Question
Title: $L_{\Sigma^*}=\{\langle M\rangle|L(M)=\Sigma^*\}\notin coRE$
I'm trying to understand why: $$L\_{\Sigma^\*}=\\{\langle M\rangle|L(M)=\Sigma^\*\\}\notin coRE$$ As I see it TM, $\langle M\rangle$, should accept all the inputs, and if one of the inputs rejected it's not $L(M)=\Sigma^\*$ any more, so why it's not? $$L\_{\Sigma^\*}\in coRE$$

$\*$ I familiar with the reductions $HP\le L\_{\Sigma^\*}$ and $HP\le \overline{L\_{\Sigma^\*}}$ to proof $L\_{\Sigma^\*}, \overline{L\_{\Sigma^\*}}\notin RE$

# Answer
> 1 votes
You say

> $\langle M \rangle$ should accept all the inputs, and if one of the inputs rejected it's not $L(M)=\Sigma^∗$.

The above two statements are true, but you are not handling all behaviors of $M$. In particular you are not considering that $M$ could never halt on some input $x$. In that case $L(M) \neq \Sigma^\*$.

In short, your observation do not imply the existence of a Turing machine that accepts on input $M$ whenever $L(M) \neq \Sigma^\*$, which would show $\overline{L\_{\Sigma^\*}} \in \mathsf{RE}$.

In fact, you can formally prove that $\overline{L\_{\Sigma^\*}} \not\in \mathsf{RE}$ by reducing from the halting problem: for any Turing machine $T$ you can construct another machine $M\_T$ that simulates $T$ and then accepts. If $\overline{L\_{\Sigma^\*}}$ were in RE, then there would be a Turing machine $T^\*$ that accepts iff $M\_T \in \overline{L\_{\Sigma^\*}}$, i.e., iff $T$ does not halt. Interleaving the execution of $T^\*$ with that of $T$ itself allows you to solve the halting problem.

---
Tags: formal-languages, computability
---


# Question
Title: Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL
I want to prove that $L = \\{a, b\\}^\* - \\{(a^n b^n)^m \mid n, m \ge 1\\}$ is a Context Free Language.

so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free Languages but have not been successful yet.

Any guidance and explanation would be greatly appreciated.

# Answer
> 3 votes
Suppose that $w$ is in the language. We can write $w$ as a concatenation of *runs*: $$ w = a^{i\_1} b^{j\_1} a^{i\_2} b^{j\_2} \dots a^{i\_m} b^{j\_m}, $$ where all indices other than possibly $i\_1,j\_m$ are strictly positive.

A word of this form belongs to $(a^nb^n)^m$ if all indices are equal. Since $w$ is in the language, there must exist two indices which are different. There are several cases to consider:

1. $w = \epsilon$.
2. $i\_1 = 0$ and $w \neq \epsilon$. In other words, $w$ starts with $b$.
3. $j\_m = 0$ and $w \neq \epsilon$. In other words, $w$ ends with $a$.
4. $i\_s \neq i\_t$ for some $s \< t$. The word is thus of the general form $$ (a+b)^\*ba^xb^+(a^+b^+)^\*a^yb(a+b)^\*, $$ where $x \neq y$.
5. $j\_s \neq j\_t$ for some $s \< t$. This is similar to the preceding case.
6. $i\_s \neq j\_t$ for some $s \leq t$. The word is thus of the general form $$ (a+b)^\*ba^x(b^+a^+)^\*b^ya(a+b)^\*, $$ where $x \neq y$.
7. $j\_s \neq i\_t$ for some $s \< t$. This is similar to the preceding case.

Starting with a context-free grammar for $\\{a^xb^y : x \neq y \\}$ (a standard exercise – separate into cases $x\<y$ and $x\>y$), you can create a grammar covering all the cases above.

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