# Question
Title: What algorithm should I use to find the closest solution to a given total using a list of integers?
My problem is this:

Let's say I have an arbitrary list of integers A\[2013, 54, 3, 32 1, 23...\]

What is the best strategy to find which of those numbers I should add together to have a sum equal or closest to a given number ?

Obviously there is always the brute force method but I'm interested in knowing if there is a more optimised one.

# Answer
> 2 votes
When packing luggage into a car, you put the biggest items in first and then fit the smaller items around them. By analogy, a heuristic approach to your problem is to start with the member of your set that is as large as possible while still being smaller than your target. Then repeat the process for the difference between you current total and your target, and so on. This is known as a greedy algorithm.

For example, if your set is $\\{2,3,5,8,13,21, 34\\}$ and you target is $32$, start with $21$ (the largest value less than $32$), then add $8$ (because this is the large value less than $32-21=11$), and then add $3$.

A greedy algorithm is quick and simple, but will not always give you the best solution. For example, if your set is $\\{1, 5, 23, 26\\}$ and you target is $30$ then the greedy algorithm gives $26+1=27$, whereas the best solution is $23+5+1=29$.

# Answer
> 1 votes
The problem is NP-complete, but polynomial in the value of the given number, with a quite low polynomial degree. It's only difficult if the numbers involved are large.

Sorting from smallest to largest and adding until no number fits is not very clever, because it will likely be a rather large number that doesn't fit, and you won't get close to the desired sum. Much better to sort from largest to smallest and add the largest numbers first.

Now if you have items with a sum *close* to S, you can try to improve this. For example if your sum is too small by 117, but the smallest unused item is 317, you'd try if you have an item X in your list, and an item Y not in the list, where Y is about 200 smaller than X - swap X against Y, add the item of size 317. Even a simple algorithm will likely find you good improvements.

A completely different method: Let the desired sum be S, with a very large S (like many trillions). Then you can choose an s' say around 1,000,000, multiply all numbers involved by (s' / S), find items with a sum close to 1,000,000, and then pick the original items. Try for a few sums that are close to 1,000,000.

# Answer
> 0 votes
Thanks to @Yuval 's comment I was led to the Knapsack Problem which is exactly what I was looking for.

Although I did not understand much of the solutions proposed to this NP-complete problem in Wikipedia, I thought of a fast but totally unreliable approach:

Just sort the list of available integers from smallest to largest and start adding them until the desired condition is met.

I think that if all differences between two members of the integer set do not vary much then this approach is probably going to give the best and only solution.

---
Tags: complexity-theory, search-algorithms
---


title: Functions of CPU

text:
# Question
Title: Functions of CPU
What part of the CPU communicates with all the other parts of the processor and makes the processor faster by containing frequently used data or instructions?

# Answer
Answer: The cache

From Wikipedia:

> A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, which stores copies of the data from frequently used main memory locations. Most CPUs have different independent caches, including instruction and data caches, where the data cache is usually organized as a hierarchy of more cache levels (L1, L2, L3, L4, etc.).
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: When can a Non-Deterministic Finite Automaton with Epsilon transitions considered to be in an accepted state?
A non-deterministic finite automaton is considered to be halted when either the whole input string has been consumed or when we reach a state where no available transition (if any) matches the current character being read.

If the machine halts when it's in an accepted state and at the same time the whole input has been consumed the input string is considered to be accepted.

Now, when introduce $\epsilon$ transitions the machine doesn't necessarily halt when the whole input string has been consumed, for it is possible that there are still $\epsilon$ transitions available.

Suppose we have a NFA that is in an accepted state and also that the whole input has been consumed, but there are still $\epsilon$ transitions available in this state, can we considered the input string to be accepted or do we need to "follow the trail" of $\epsilon$ transitions until we reach a state where no other transition is available?

# Answer
One issue is that the way you're using the English language is appropriate for talking about DFAs but not appropriate for NFAs.

With a DFA, we can say "the DFA is in state $q$ after reading the input". That is well-defined for a DFA.

That is not well-defined for NFAs. There may be multiple possible runs, each of which ends in a different state. So it doesn't make sense to say "the NFA is in an accepting state after reading the whole input", because there may be multiple possible runs, some of which are in an accepting state and some of which are not.

The formal definition of a NFA gives a precise definition of under what conditions a string is considered to be accepted. Please consult any good textbook. The short answer to your last question is yes, the input string is accepted in that situation, as there exists a run of the NFA that ends in an accepting state and where the whole input has been consumed. But there's little point in us repeating material that's already covered in standard textbooks, and if you work through the definitions, you should be able to figure this out for yourself.
> 0 votes

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


# Question
Title: Difficulty in understanding few steps in the proof: "The class $\mathscr{H}_{p,m}$ of hash functions is universal"
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the following excerpt regarding the said proof and the steps where I felt difficulty are marked with $\dagger$ and $\dagger\dagger$ respectively.

## Designing a universal class of hash functions

$p$ is a prime number large enough so that every possible key $k$ is in the range $0$ to $p — 1$, inclusive. Let $Z\_p$ denote the set $\\{0, 1,..., p — 1\\}$, and let $Z\_p^\*$ denote the set $\\{1, 2,..., p — 1\\}$.Because of the assumption that the size of the universe of keys is greater than the number of slots $m$ in the hash table, we have $p \> m$.

We now define the hash function $h\_{a,b}$ for any $a \in Z\_p^\*$ and any $b \in Z\_p$ :

$h\_{a,b} = ((a.k + b) \mod p) \mod m $.

The family of all such hash functions:

$$\mathscr{H}\_{p,m}=\\{h\_{a,b}: a \in Z\_p^\* , b \in Z\_p\\}$$

---

> Theorem: The class $\mathscr{H}\_{p,m}$ of hash functions is universal.

---

Proof:

Consider two distinct keys $k$ and $l$ from $Z\_p$, so that $k \neq l$. For a given hash function $h\_{a,b}$ we let

$$r = (ak + b) \mod p$$ ,

$$s = (al + b) \mod p $$.

We first note that $r\neq s$. Why? Observe that

$$r — s = a(k — l) (\mod p)$$ .

It follows that $г \neq s$ because $p$ is prime and both $a$ and $(k — l)$ are nonzero modulo $p$, and so their product must also be nonzero modulo $p$

Therefore, during the computation of any $h\_{a,b}$ in $\mathscr{H}\_{p,m}$, distinct inputs $k$ and $l$ map to distinct values $r$ and $s$ modulo $p$; there are no collisions yet at the "mod p level." ***Moreover, each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $r \neq s$, since we can solve for $a$ and $b$ given $r$ and $s$***$^\dagger$:

$$a = ((r — s)((k — l)^{-1}\mod p)) \mod p $$,

$$b = (r — ak) \mod p$$ ,

where $((k — l)^{-1} \mod p)$ denotes the unique multiplicative inverse, modulo p, of $k — l$. Since there are only $p(p — 1)$ possible pairs $(r, s)$ with $г \neq s$, there is a one-to-one correspondence between pairs $(a, b)$ with $a \neq 0$ and pairs $(r, s)$ with $r \neq s$. Thus, for any given pair of inputs $k$ and $l$, if we pick $(a, b)$ uniformly at random from $Z\_p^\* \times Z\_p$, the resulting pair $(r, s)$ is equally likely to be any pair of distinct values modulo p.

It then follows that the probability that distinct keys $k$ and $l$ collide is equal to the probability that $r \equiv s (\mod m)$ when $r$ and $s$ are randomly chosen as distinct values modulo $p$. ***For a given value of $r$, of the $p — 1$ possible remaining values for $s$, the number of values $s$ such that $s \neq r$ and $s \equiv r (\mod m)$ is at most***$^{\dagger\dagger}$

$$\lceil p/m \rceil - 1 \< ((p + m - 1)/m) - 1$$ $$ =(p-1)/m$$.

The probability that $s$ collides with $r$ when reduced modulo $m$ is at most $((p - l)/m)/(p - 1) = 1/m$.

Therefore, for any pair of distinct values $k,l \in Z\_p$,

$$Pr\\{h\_{a,b}(k)=h\_{a,b}(l)\\}\leq 1/m$$

so that $\mathscr{H}\_{p,m}$ is indeed universal.

---

Doubts:

I could not understand the following statements in the proof:

$\dagger$ :**Each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $r \neq s$, since we can solve for $a$ and $b$ given $r$ and $s$**

why , "we can solve for $a$ and $b$ given $r$ and $s$" $\implies$ "Each of the possible $p(p — 1)$ choices for the pair $(a, b)$ with $а \neq 0$ yields a different resulting pair $(r, s)$ with $г \neq s$"

---

$\dagger\dagger$ : **For a given value of $r$, of the $p — 1$ possible remaining values for $s$, the number of values $s$ such that $s \neq r$ and $s \equiv r (\mod m)$ is at most** $\lceil p/m \rceil - 1 $ .

How do we get the term $\lceil p/m \rceil - 1 $ ?

# Answer
> 1 votes
We want to show that if $k\_1\neq k\_2\in\mathbb{Z}\_p$ then

$\Pr\limits\_{(a,b)\in\mathbb{Z}\_p^\*\times\mathbb{Z}\_p}\[ak\_1+b\equiv ak\_2+b \pmod m\]\le\frac{1}{m}$.

Where both addition and multiplication are preformed in $\mathbb{Z}\_p$.

We start by showing that if $a\sim U(Z\_p^\*)$ and $b\sim U(Z\_p)$ then for all $k\_1\neq k\_2\in \mathbb{Z}\_p$, $(ak\_1+b,ak\_2+b)$ is uniformly distributed over $\\{(x,y)\in\mathbb{Z}\_p^2| x\neq y\\}$ (i.e. $h(k\_1)$ and $h(k\_2)$ are jointly uniform over pairs with different entries, where the randomness is over the choice of $h$). This is immediate from the fact that for all $(c\_1,c\_2)\in\mathbb{Z}\_p^2$ with $c\_1\neq c\_2$, the following system of linear equations:

$ \begin{align\*} & ak\_1+b=c\_1 \\ & ak\_2+b=c\_2 \end{align\*} $

has a unique solution over the variables $(a,b)\in Z\_p^\*\times\mathbb{Z}\_p$. Subtracting the second equation from the first yields $a(k\_1-k\_2)=c\_1-c\_2$, since $k\_1-k\_2$ is nonzero we can multiply both sides by its inverse and obtain $a=(k\_1-k\_2)^{-1}(c\_1-c\_2)$. If $c\_1\neq c\_2$, then this is a nonzero solution for $a$, and we can extract $b$ from any of the two equations. Thus, for each pair $(c\_1,c\_2)$ with $c\_1\neq c\_2$ there are unique $(a,b)\in Z\_p^\*\times\mathbb{Z}\_p$ such that $\big(h\_{a,b}(k\_1),h\_{a,b}(k\_2)\big)=(c\_1,c\_2)$. This settles your first question.

Now, divide $\mathbb{Z}\_p$ into $\lceil p/m\rceil$ buckets, $b\_1,...,b\_{l=\lceil p/m\rceil}$ as follows: $b\_1=\\{0,1,...,m-1\\}, b\_2=\\{m,m+1,...,2m-1\\}$,...,$b\_l=\\{m\lfloor p/m\rfloor, m\lceil p/m\rceil+1,...,p-1\\}$. Note that each bucket except the last is of size $m$, and no two elements in the same bucket are equivalent modulo $m$. We conclude that the number of different pairs in $\\{(x,y)\in\mathbb{Z}\_p^2| x\neq y\\}$ that are equivalent modulo $m$ is at most $p(\lceil p/m\rceil-1)$, since after choosing the first element, you are left with $\lceil p/m\rceil-1$ elements to choose from (you must pick a different bucket and each bucket provides at most one candidate). Recall that $\big(h\_{a,b}(k\_1),h\_{a,b}(k\_2)\big)\sim U(\\{(x,y)\in\mathbb{Z}\_p^2| x\neq y\\})$, so we can finally conclude:

$\Pr\limits\_{(a,b)\in\mathbb{Z}\_p^\*\times\mathbb{Z}\_p}\left\[h\_{a,b}(k\_1)=h\_{a,b}(k\_2)\pmod m\right\]=\frac{p(\lceil p/m\rceil-1)}{p(p-1)}\le \frac{1}{m}$

Note that allowing $a$ to take the value $0$ only makes our analysis easier, since now $\big(h(k\_1),h(k\_2)\big)$ is jointly uniform over $\mathbb{Z}\_p^2$, but there is an additionaly probability of $\frac{1}{p}$ that $a=0$ and our hashes will be equivalent modulo $m$, so in this case we will have to settle for an $O(\frac{1}{m})$ bound on the collision probability.

---
Tags: proof-techniques, hash, hashing
---


# Question
Title: Purpose of randomization/derandomization in basic randomized algorithm for MAX SAT
In Sections 5.1 of The Design of Approximation Algorithms by Williamson and Shmoys, they describe a basic randomized algorithm for MAX SAT and how to derandomize it. The algorithm is just to assign each variable 1 (true) with probability 1/2 and 0 (false) with probability 1/2. In other words, sample uniformly at random from the space of all solutions. They show that this is a 1/2-approximation.

Then in Section 5.2, they describe how to derandomize it using the method of conditional expectations. (I won't describe the process here because it is not very complex and widely known I'm assuming.)

**My question is, why bother derandomizing this way? Or even, why bother making the algorithm random in the first place?**

It seems to me that an equally good algorithm would be the one-liner which deterministically sets all variables to 1. Given some MAX SAT instance as input, it seems to me that you would also expect this to (i.e., "in expectation it would") satisfy half of the clauses. To me, the analysis of the random algorithm really seems to say that any fixed guess is "good." (Rather than showing that our random algorithm is inherently good.) So why go through the process of randomizing and derandomizing in the first place?

Thanks in advance!

# Answer
> 2 votes
The difference is that the randomized algorithm guarantees an expected 1/2-approximation *on any input*. By contrast, it is easy for an adversary to construct an input (i.e. an instance of MAX-SAT) for which the deterministic "set all variables to true" algorithm satisifes zero clauses.

Remember that the sample space for a randomized algorithm is over a set of auxiliary random bits. There is no probability distribution assumed over the *inputs*. The typical goal of randomized algorithm design is for every input to be handled well in expectation. (Analyzing algorithm behavior over an assumed input distribution is called average-case analysis instead.)

## What are auxiliary random bits?

Suppose we have a randomized Turing machine $M\_1$ that runs on instances of length $n$ for no more than $T(n)$ time, during which it makes no more than $R(n) \le T(n)$ random decisions. We can turn this machine into a *deterministic* Turing machine $M\_2$ that has two input tapes: the usual tape that contains the input string $x$ of length $n$, and a tape that contains a string $r$ of length $R(n)$. The string $r$ is our string of *auxiliary random bits*; it determines which "random" decisions the Turing machine is to make. When we say that the randomized Turing machine run $M\_1(x)$ accepts with probability $p$, this is equivalent to saying that the set $$A(x) = \left\\{r\ |\ r \in \\{0, 1\\}^{R(|x|)}, M\_2(x, r)\text{ accepts}\right\\}$$ of $r$ strings that make $M\_2(x, r)$ accept constitutes a fraction $p = |A(x)| / 2^{|x|}$ of the set of all $r$ strings.

You might recognize what is going on here if you've seen the analogous construction for nondeterministic Turing machines. We can think of an NP machine as a nondeterministic machine that branches into exponentially many copies of itself. But we can also think of it as a deterministic *verifier* machine that requires both an input and a "proof" string, with the acceptance criteria that an input string is in the language if *any* proof string makes the machine accept.

It is often easier to think about this down-to-Earth concept of deterministic verifier machines and which subset of proof strings makes the machine accept on a given input, rather than thinking about very abstract ideas like exponentially branching machines and possible worlds. And it makes it easier to define complexity classes such as co-NP, PP, BPP, ⊕P, etc., all of which are essentially "NP with a different acceptance rule." For example:

* NP is the set of languages $L$ for which there exists a polynomial-time verifier machine $M\_2$ such that $x \in L$ if and only if there exists an $r$ string such that $M\_2(x, r)$ accepts (where the length of the $r$ string is bounded by a polynomial $R(|x|)$).
* BPP is the set of languages $L$ for which there exists a polynomial-time verifier machine $M\_2(x, r)$ such that $x \in L$ implies that $M\_2(x, r)$ accepts for at least ⅔ of $r$ strings and $x \notin L$ implies that $M\_2(x, r)$ accepts for at most ⅓ of $r$ strings (where the length of the $r$ strings is bounded by a polynomial $R(|x|)$).

Note: It mostly doesn't matter whether we require the $r$ strings to have length *exactly* $R(n)$ or *at most* $R(n)$, since allowing shorter strings only increases the number of possible strings by a constant factor.

---
Tags: randomized-algorithms
---


# Question
Title: Distance to $k$th nearest neighbor efficiently for arbitrary $k$
**Problem.** Given $X$ a finite metric space of cardinality $n$, construct a data structure in subquadratic time such that the query `distance to the kth nearest neighbor of x` can be resolved in sublinear time (independent of $k$) for arbitrary $k \leq n$ and $x \in X$.

**What I have tried.** I am aware of the existence of kdtrees, ball-trees, and cover trees. Under some assumptions (which I'm willing to make), I know that these structures can resolve the query `distance to the nearest neighbor of x` in sublinear time (often $O(\log(n))$), but I haven't been able to find similar results for the $k$th nearest neighbor for arbitrary $k$.

It seems that, often, one is interested in $k$ values that are small compared to $n$, and that, in those cases, the algorithms mentioned in the previous paragraph can be adapted at the cost of a multiplicative constant of the order of $k$. My problem is that I am interested in $k$ values that are potentially of the order of $n$.

# Answer
For a general metric, you can't. For instance, one can prove it takes at least quadratic time to answer $\Theta(n)$ queries, in the worst case.

For instance, suppose we have $n/2$ query points that are all very far from each other, and $n/2$ target points. We'll ask for the $n/4$-th closest neighbor of each query point. Then each $d(q,t)$ can be set to any distance in $\[1/2,1\]$ for each of the $n^2/4$ pairs of a query point $q$ and a target point $t$, and each can be chosen independently, and you'll have a valid metric. Thus you can imagine the distance being specified by a $n/2 \times n/2$ matrix of distances $d(q,t)$. In $o(n^2)$ time, you can only read $o(n^2)$ of the entries in that matrix, which isn't sufficient to answer all of the queries. You can prove this with an adversarial argument: consider any $q$ where the algorithm has read $d(q,t)$ for fewer than $n/4$ different values of $t$; then whatever the algorithm outputs as the $n/4$-th nearest neighbor to $q$, we can arrange the other unread distances so that the algorithm's output was incorrect.
> 1 votes

---
Tags: nearest-neighbour
---


# Question
Title: Best case "skew height" of an arbitrary tree
Given an arbitrary binary tree on $n$ nodes, choose an assignment $A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $H\_A(\mathsf{nil})=0$ and $H\_A(\mathsf{node}\\;a\\;b)=\max(H\_A(a), H\_A(b)+1)$ if $A(\mathsf{node}\\;a\\;b)=a$ is the favored child and symmetrically $\max(H\_A(a)+1, H\_A(b))$ if $b$ is favored.

The question is: For a fixed tree $T$, what is the minimum skew height over all assignments? I would like to get an asymptotic bound on $f(n)=\max\_{|T|=n}\min\_AH\_A(T)$.

Other variations on this problem I am interested in are when the trees are not binary (but there is still one favored child and all others add one to the height), and when there is sharing (i.e. it is a dag), which doesn't affect the height computation but allows for much wider "trees" while staying under the $n$ node bound.

The obvious bounds are $f(n)=\Omega(\log n)$ and $f(n)=O(n)$. My guess is that $f(n)=\Theta(\log n)$ for binary trees, and $f(n)=\Theta(\sqrt n)$ for dags (with some kind of grid graph as counterexample).

# Answer
For a binary tree, let $H(T)=\min\_AH\_A(T)$, where $A$ ranges over all favored-child assignments of $T$. Call $H(T)$ *the* skew height of $T$.

Here is a simple observation. The skew height of a perfect binary tree of (ordinary) height $n$ is $n$, too.

For a binary tree $T$, an edge is called a passing edge if one of the endpoints has exactly one child. We call a binary tree $M$ a b-minor of $T$ if $M$ can be obtained by removing a subtree or contracting a passing edge repeatedly.

For a binary tree $T$, what is its skew height? Here is a visual characterization.

**The skew height of $T$ is the maximum (ordinary) height of all perfect binary trees that are also b-minors of $T$.** Intuitively speaking, a binary tree is of skew height $s$ $\iff$ it "contains" a perfect binary tree of ordinary height $s$.

**Proof.** Since both removing a subtree and contracting a passing edge do not increase the skew height, $$H(T)\ge \max\_{M\text{ is a b-minor of T}}\mathsf{height}(M),$$ where $\mathsf{height}(\cdot)$ is the (ordinary) height of a tree. On the other hand, by induction on the number of nodes of $T$, we can show that a binary tree of skew height $s$ must contain a b-minor that is a perfect binary tree of ordinary height $s$. $\quad\checkmark$.

---

Recall that $n$ is the number of nodes in $T$. We have, $$H(T) \le \lceil \log\_2(n+1)\rceil - 1.$$ **Proof.** Induction on $n$. The base case, $n = 1$ is easy to verify.

Suppose it is true if the number of nodes in $T$ is smaller than $n$. Consider a binary tree $T$ of $n$ nodes with root node $r$.

* If $r$ has only one child, say, $a$, then $$H(T)=H(\text{the subtree rooted at } a)\le \lceil \log\_2((n-1)+1)\rceil - 1\le \lceil \log\_2(n+1)\rceil - 1.$$
* If $r$ has two children, say, $a$ and $b$. Since the number of nodes in the subtree rooted at $a$ and the subtree rooted at $b$ is $n-1$, one of the subtrees has at most $\lfloor (n-1)/2\rfloor$ nodes. WLOG, suppose it is the subtree rooted at $b$. Then $$H(T)=\max(H(\text{the subtree rooted at }a ) + 1, H(\text{the subtree rooted at } b)) \\ \le \max(\lceil \log\_2(\lfloor(n-1)/2\rfloor+1)\rceil,\lceil \log\_2((n-2)+1)\rceil -1) $$ Since $$ \lceil \log\_2(\lfloor(n-1)/2\rfloor+1)\rceil=\lceil \log\_2(\lfloor(n+1)/2\rfloor)\rceil=\lceil \log\_2(n+1)\rceil-1,$$ we have $H(T)\le \lceil \log\_2(n+1)\rceil-1.$ $\quad\checkmark$

---

Recall that $f(n)=\max\_{T\text{ is a binary tree and }|T|=n}H(T)$. The above section has proved $f(n)\le \lceil\log\_2(n+1)\rceil-1$.

On the other hand, the skew weight of the perfect binary tree with $2^m-1$ node is $m-1$. Hence, $$f(n)=\lceil\log\_2(n+1)\rceil-1.$$
> 1 votes

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


title: Need hint for bipartiteness proof

text:
# Question
Title: Need hint for bipartiteness proof
I am given a graph $G = (V, E)$ with $N$ connected components and $G^\prime = (V^\prime, E^\prime)$, where for each $v \in V$ there is $v\_1, v\_2 \in V^\prime$ and for each $(u, v) \in E$ there is $(u\_1, v\_2), (u\_2, v\_1) \in E^\prime$.

I need to prove:

$$G^\prime \textrm{ has 2N connected components} \Leftrightarrow G \textrm{ is bipartite}$$

I don't know what technique or approach I need to use to prove this in either direction. I have a feeling I can use a direct proof for both directions. I have tried to come up with something but after an hour nothing has come up.

# Answer
Let's do the case $N = 1$.

Suppose that $G$ is a connected graph, and assume first that $G$ is bipartite, with bipartition $X,Y$. Let $X\_1,X\_2,Y\_1,Y\_2$ be the two copies of the two parts in $G'$. Note first that the edges in $G'$ either connect $X\_1$ to $Y\_2$ or $X\_2$ to $Y\_1$, and so $G'$ has at least two connected components.

Conversely, any path from $X$ to $Y$ in $G$ gives rise to a similar path in $G'$ from $X\_1$ to $Y\_2$, implying (after a short argument) that $X\_1 \cup Y\_2$ form a connected component; and similarly for $X\_2 \cup Y\_1$. Thus $G'$ has exactly two connected components.

Now suppose that $G$ is a connected non-bipartite graph. As before, the vertices in $X\_1 \cup Y\_2$ are all in the same connected component of $G'$, as are the vertices in $X\_2 \cup Y\_1$. We will show that $X\_1$ is connected by a path to $X\_2$, implying that $G'$ is connected.

Since $G$ is not bipartite, there is some odd cycle in $G$. Let $x$ be a vertex on this odd cycle. Lifting this cycle to $G'$, we obtain a path from $x\_1$ to $x\_2$.
> 1 votes

---
Tags: graphs, proof-techniques, sets, proof-assistants
---


# Question
Title: Does big-Oh impose an ordered partition on the set of the "usual" functions?
The example in this answer proves the fact familiar to CS students - that the "big-O" is not a total order. However, most algorithm running times analyzed using big-Oh notation are not expressed in piecewise form like this example. In fact, most algorithms I am familiar with have a running time expressed in terms of polynomials, exponentiations and logs.

Consider the recursively defined class of functions which includes $f(n) = c$ for any constant $c$, $f(n) = n$, and any functions of the form $f + g, f \cdot g, \log(f), \exp(f)$ where $f,g$ are in the class. Does $O$ impose an ordered partition on this class of functions? The functions with the same big-$O$ growth is in the same part.

Here are my thoughts:

Note that specifying $f \cdot g$ is actually redundant, since $f \cdot g = \exp(\log(f) + \log(g))$. Since the functions are inductively defined, perhaps there is an inductive proof.

# Answer
> 5 votes
This was shown by Hardy in his monograph Orders of Infinity.

---
Tags: reference-request, big-o-notation
---


# Question
Title: Coloring graph with constraints on assortativity
I have come across the following problem and I would love for your thoughts on an optimal solution or approximate calculations worth trying.

**The formulation of the problem in the form of graph theory:**

Given a weighted graph $G=(V, E)$. In addition, we have $C$ colors and $f(\[C\_1, ...C\_n\])$ the distribution function of vertices in the graph by color (That is, how many nodes of each color are in the graph). Also given an assortativity parameter, $M$. In general, assortativity is the tendency of nodes in the graph to attach to others that are similar in some way. For simplicity, set it to be the number of edges between vertices of the same color (Originally it is a little more sophisticated calculation. But unnecessary for our needs.).

Now, I want to color the graph such that the constraint on the number of vertices of each color is met and in addition, we minimize the expression: $|M-M(G)|$ (recall, $M$ is the desired parameter and $M(G)$ is the parameter as it is calculated on the given coloring). Of course, we are not only interested in the minimum value, but also the coloring that created it.

**This problem also has a parallel formulation for matrices:**

Given symmetric matrix $A$ ($n\times n$) - this is the adjacency matrix of the above graph. The value of the entry $A\_{ij}$ is set to equal the weight of the edge $(i,j)$. Here, too, we are given a distribution function of the rows and the columns in the matrix by color. As before, we have an assortativity parameter, $M$. Now, let's try to find symmetric coloring of rows and columns in the matrix (if any line is colored in a certain color, so is the corresponding column) such that the constraint on the number of rows and columns of each color is met.

In addition, we will try to minimize the expression: $|M-\Sigma(A\_{i,j}|\text{where column } i \text{ and row } j \text{ are in same color})|$ (which means, the difference between the desired $M$ and the sum of all entries that their colum and their row are in same color).

**Epilogue:**

I know that both formulas are completely equal. I hope the two different perspectives help me and others to think about different directions to solve the problem.

For the sake of curiosity, I will say that this problem is part of a challenge I face and it is to generate pseudo-synthetic social networks with real-life constraints. This is a problem that I formulated and not part of an article or a home exercise.

Thanks in advance.

# Answer
Your problem is NP-hard. Consider the special case where $M=0$; then your problem is as hard as the graph coloring problem, which is NP-hard. (Ok, with an additional constraint on the distribution function, but it will still be NP-hard.) In particular, if $M=0$ and the graph is $C$-colorable, then the optimal solution have $|M-M(G)|=0$; if the graph is not $C$-colorable, then the optimal solution will have $|M-M(G)|\>0$. So, if we could find the optimal solution for your problem for arbitrary $M$, we could determine whether the graph is $C$-colorable by setting $M=0$, finding the optimal solution, and checking whether $|M-M(G)|=0$.

One possible approach to finding an approximate solution would be to try local search or simulated annealing.
> 1 votes

# Answer
* for specific values of M it is not necessarily NP-hard.
* so if you have a constraint over M it might be useful.
* also, you are asking for optimization and not the best solution (sometimes optimizing is as hard as solving, but it requires another argument).
* and lastly, regarding NP, it might be practically solvable for large graphs with heuristics (we have SAT solvers)
> 0 votes

---
Tags: algorithms, graphs, approximation
---


# Question
Title: Prove that every regular subset of $a^nb^n$ is finite
How to prove that every regular subset of $L=\\{a^nb^n \mid n\ge0 \\}$ is finite?

I know that every finite language is regular, and it's not true that every regular language is finite.

I also know that $a^n b^n$ is non-regular language.

I can find examples of finite regular subsets of $L$, for example $\\{\epsilon, ab, aabb\\}$, but how do I prove that all regular subsets of $T$ are finite?

# Answer
> 3 votes
This is a simple application of the pumping lemma. Suppose that $L'$ is an infinite subset of $L$. Given $p$, since $L'$ is infinite, there exists some $n \geq p$ such that $w = a^nb^n \in L'$. Let $w = xyz$ be a decomposition of $w$ such that $|xy| \leq p$ and $y \neq \epsilon$. Then $y = a^t$ for some $t \neq 0$, and so $xy^0z = a^{n-t}b^n \notin L'$. Therefore $L'$ is not regular.

One might be tempted to think that this argument generalizes to every $L$ whose non-regularity can be proved using the pumping lemma. However, this is incorrect, as the example of $L \cup c^\*$ shows.

This raises the following intriguing question:

> For which infinite languages $L$ is it the case that all regular subsets of $L$ are finite?

# Answer
> 1 votes
Prove that if your language contains $a^nb^n$ and $a^mb^m$ for n \<\> m then after parsing $a^n$ and parsing $a^m$ you end up in different states. (Proof is trivial).

If there are infinitely many different n, m then the number of states cannot be finite.

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


# Question
Title: Why doesn't relu cause back propegation to get stuck
Say you have a neural net that is being trained using back propagation and you are using relu activation. Say the input to a node is a weighted sum of the previous layer with a bias term and say for a particular data point, this weighted sum plus bias is negative. Then relu returns 0. Notice the change in the loss as a function of the change in one of these weights or the bias is 0. Therefore the network won't improve the bias as the network does back propagation. Why is this not a problem?

# Answer
Normally, any ReLU unit will return 0 for some samples and not for other samples (in particular, it'll probably return 0 for about half of the samples). Because of how SGD works, it won't get stuck: the former samples will yield a contribution to the gradient of 0, but the latter samples will have a non-zero gradient, so the weights and bias will be updated for the latter samples. So it's not a problem; the weights and bias still get updated for many of the samples.

That said, there can be cases where this problem can occur. If the ReLU unit outputs 0 for all (or most) samples, then SGD won't update the weights, and learning for that neuron will get stuck. This is sometimes called the "dying ReLU" problem. See, e.g., https://datascience.stackexchange.com/q/5706/8560 and https://en.wikipedia.org/wiki/Rectifier\_(neural\_networks)#Potential\_problems. Typically we're able to avoid this problem by appropriate initialization of the weights and by suitable choice of learning rate for SGD, so it's usually not a big deal in practice if you choose those appropriately, but it can happen.
> 1 votes

# Answer
> "Typically we're able to avoid this problem by appropriate initialization of the weights and by suitable choice of the learning rate for SGD"

As far as I know, this approach is slightly outdated and is something we are trying to move from.

In various cases, it is recommended to use LeakyRelu, which aims to deal exactly with the issue you mentioned.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Prove or Disprove: an infinite intersection of regular languages is a context-free language
Let $L\_1, L\_2,...$ and $L=\cap\_{k=1}^{\infty}L\_k$ be languages over $\Sigma ^{\*}$.
Prove /Disprove: if $\forall k\in \mathbb{N} $, $L\_k$ is a regular language, then $L$ is a context-free language.

I know that statement is false, but couldn't find an example to disprove it. Would appreciate your help:)

# Answer
"I know that this statement is false, but couldn't find an example to disprove it."

It might come as a surprise to you that, in fact, *every* non-context-free language can be a counterexample. We have the following fact, assuming any fixed alphabet $\Sigma$.

---

Let $L$ be a language. Then there exist regular languages $L\_1, L\_2,...$ such that $L=\cap\_{k=1}^{\infty}L\_k$.

**Proof**. The other answer indicates how to construct $L\_i$. For clarity, here is the construction.

Let $L\_i$ be the words in $L$ with length at most $i$ together with all the words with length greater than $i$. More formally, let $L\_i=\\{w\in\Sigma^\*: w\in L\text{ and } |w|\le i\\}\cup\\{w\in\Sigma^\*:|w|\gt i\\}$. Then $L=\cap\_{k=1}^{\infty}L\_k$.

Each $L\_i$ is regular since $L\_i$ is the union of two regular languages.

* $\\{w\in\Sigma^\*: w\in L\text{ and } |w|\le i\\}$, as a finite set, is regular.
* $\\{w\in\Sigma^\*:|w|\gt i\\}$ is regular.

---

So, even if $\forall k\in \mathbb{N} $, $L\_k$ is a regular language, $L=\cap\_{k=1}^{\infty}L\_k$ can be non-regular, non-context-free, non-context-sensitive, etc.
> 15 votes

# Answer
To add to John L.'s answer, for some intuition: the operations of *infinite* intersection and *infinite* union typically do not preserve any properties of languages. In particular, no nontrivial class of languages is closed under infinite union or infinite intersection: not regular languages, not context free languages, not P, not NP, not Turing computable, not recursively enumerable (Turing recognizable), etc. The list goes on.

This is because infinite union and infinite intersection are just too powerful, so you can usually get every language this way. In particular,

1. **Every language can be written as the infinite union of finite languages**.
2. **Every language can be written as the infinite intersection of "co-finite" languages**, where the term "co-finite" means the complement of a finite language. (That is, the language contains *every* string except for finitely many of them.) This is what John L.'s answer shows.

Now, finite languages and co-finite languages are the very simplest of languages -- they are in particular regular. So every language can be written as the infinite union or infinite intersection of regular languages.
> 8 votes

# Answer
Consider $L\_n = \\{a^2, a^3, a^5 \ldots a^n, a^{n+1} \ldots \\} $ (only prime length strings over $a$ till the length $n$, and all strings over $a$ of length greater than $n$) if $n$ is prime, else $L\_n = \Sigma^\*$. Note that each of these $L\_n$ is regular (Why?).

It’s easy to see that the infinite intersection language would contain the strings over $a$ of prime length, i.e., $L = \\{a^p | p \text{ is prime} \\}$.

It can be proved easily using pumping lemma that this language isn’t context free.
> 4 votes

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


title: How to simplify context free grammar?

text:
# Question
Title: How to simplify context free grammar?
How to simplify this context-free grammar into a similar one with no unit productions and no useless symbols?

$$ S \to ABA \\ A \to aAA \mid aBC \mid bB \\ B \to A \mid bB \mid Cb \\ C \to CC \mid cC $$

Can the simplification result in this CFG?

$$ S \to ABA \\ A \to aAA \\ A \to Bb \\ B \to b $$

# Answer
> 0 votes
The context free language at the top seems to be empty, as there always will be a variable at any time while trying to derive a word! (this is because every transition is from a variable to some a few letters and at least one variable)

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


# Question
Title: Formal definition of non deterministic PDA
How would you convert the following formal definition of deterministic pushdown automata into non deterministic ?

> Deterministic PDAs In general terms, a deterministic PDA is one in which there is at most one possible transition from any state based on the current input. Formally, a deterministic PDA is a PDA where:
>
> for every state $P$, input symbol $\hbox{'}{a}\hbox{'}$ and stack symbol $t$, there is at most one transition of the form $(P,a,t)\mapsto(Q,u)$ for any state $Q$ and stack symbol $u$. Any context-free language that can be converted to a deterministic PDA is called a deterministic CFL.

# Answer
> 1 votes
The same way you would convert the definition of deterministic finite automata to a nondeterministic one:

The transition function would output a **set** of transitions instead of a single one.

This means that if in the deterministic case we have $\delta(p,a,t)=(q,u)$, now it will look like: $\delta(p,a,t)=\\{(q\_1,u\_1),...,(q\_n,u\_n)\\}$ for any $q\_i,u\_i$ we choose.

Formally, the transition function is $\delta:Q\times\Sigma\times\Gamma\rightarrow P(Q\times\Gamma)$ where $Q$ are the states, $\Sigma$ are the input symbols, and $\Gamma$ are the stack symbols

---
Tags: formal-languages, pushdown-automata, nondeterminism
---


# Question
Title: Why this Turing machine can't be an acceptor for the following language?
Given the following language - $L=\left\\{\left\langle M\_{1}, M\_{2}\right\rangle \mid\left\langle M\_{1}\right\rangle \notin L\left(M\_{2}\right) \vee\left\langle M\_{2}\right\rangle \notin L\left(M\_{1}\right) \text { and are TM } M\_{1}, M\_{2}\right\\}$

I know it's in CO-RE but why this is not a good acceptor for the above language?

On input $\<M1,M2\>$

1. In parallel simulate M1 on $\<M2\>$ and M2 on $\<M1\>$
2. if one rejects, accept.
3. if both accept , reject.

according to definition of being acceptor of a language, for any input x that belongs to the language the acceptor accepts which it does it at phase 1. for any input which doesn't belongs to the language we either reject or not halt which is also the case.

what am i missing?

# Answer
You are not considering the fact that $M\_1(M\_2)$ and/or $M\_2(M\_1)$ might not halt. When this happens your Turing machine for $L$ will be stuck executing step 1.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: If $PSPACE^{SAT}=PSPACE$ and $PSPACE \subseteq EXP$, then why does $EXP^{SAT}$ not necessarily equal to $EXP$?
I read the following claim:

* $PSPACE^{SAT}=PSPACE$
* $EXP^{SAT}$ is not necessarily the same as $EXP$

The first claim makes sense; $PSPACE \subseteq PSPACE^{SAT}$ trivially, and for any language $B \in PSPACE^{SAT}$ decided by an oracle machine $M\_B$, we can define a non-deterministic machine $M'\_B$ that works like $M\_B$, except instead of querying an oracle, $M'\_B$ instead guesses a witness and calls $M\_{SAT}$ (a machine deciding $SAT$). It can easily be shown that $M'\_B$ decides $B$ in polynomial space, and so $B\in NSPACE$. But from Savitch's Thoerem, $NSPACE=PSPACE$, and so $B \in PSPACE$. Thus, $PSPACE^{SAT}=PSPACE$.

I assumed that since $PSPACE \subseteq EXP$, then it should follow that $EXP^{SAT}=EXP$ as well. After all, it only needs to be shown that $EXP^{SAT}\subseteq EXP$ to prove the claim, but I can't see where the problem lies.

For that matter, my assumption was that if $X$ was ***any*** complexity class such that $X\subseteq Y$, then $Y^X=Y$. After all, any *X*-oracle doesn't allow Y to decide any language it couldn't already decide. But if the two claims are true, then obviously my assumption is wrong.

# Answer
> 1 votes
The fact that the base class can simulate the oracle does not mean that the oracle does not give additional power. Consider the polynomial hierarchy, $\mathsf{NP,NP^{NP},NP^{NP^{NP}}},...$ at the $i$'th level you get an oracle for the $i-1$ level, so following your line of thought we should not gain additional power. However a naive simulation of the oracle does not suffice, since taking the wrong path may lead us to accept an input outside the language (we need to be sure of the oracle's answers).

A class which is famously not low on itself is $\mathsf{EXP}$, since $\mathsf{EXP^{EXP}=2EXP}$. A naive simulation in your case fails for similar reasons, as a machine in $\mathsf{EXP^{SAT}}$ can ask the about the satisfiability of exponentially long formulas.

---
Tags: complexity-theory, complexity-classes, oracle-machines
---


# Question
Title: Is $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} (un-)decidable?
I have to prove that the language $L\_2:=${$\<M\>$|$L(M)=\overline{A\_TM}$} is (un-)decidable. In a previous assignment we proved that $L\_1:=${$\<M\>$|$L(M)=A\_TM$} is undecidable.

I would say that $L\_1$ is decidable because we can build a decider S.

S="on input w": (rough outlined)

1. breadth first search

(a) if no accept state was found, accept

(b) else reject

Am I wrong with my guess?

$\overline{A\_TM}$={\<M,w\>|M is a TM and does not accept w}

# Answer
> 1 votes
**For $L\_1:$**

It's not decidable.

Define $C=\\{A\_TM\\}$. Now, by Rice's theorem we have that the language $L=\\{\<M\>|L(M)\in C\\}$ is undecidable. (By the extended theorem it's not even semi-decidable.)

But notice $L\_1=L$ and therefore $L\_1$ is undecidable.

---

**For $L\_2:$**

It's decidable, although your solution is **not** correct.

Notice that $\overline{A\_TM}$ is not semi-decidable, and therefore there is no TM $M$ where $L(M)=\overline{A\_TM}$. Thus, $L\_2=\\{\<M\>|L(M)=\overline{A\_TM}\\}=\emptyset$ and thus a TM that always rejects will decide $L\_2$.

---
Tags: turing-machines, undecidability, decision-problem, semi-decidability
---


# Question
Title: Does there exist a problem for which no existing solution can be parallelized on a Turing machine?
I'm asking for problems for which we know there exists a solution for which an equivalent parallel program *cannot* be written on a Turing machine.

Alternatively, have we proven the opposite to be true - that for *every* problem, there exists at least one parallelizable solution?

# Answer
The question is not precisely defined, so it's not really amenable to a precise technical answer at this stage. But a common view/hypothesis/expectation is that there exist problems that are inherently sequential, in the sense that they cannot be substantially sped up on a parallel computer, no matter how many parallel processors you have. A weak version of this view is implied by the conjecture that $NC \ne P$ (see https://en.wikipedia.org/wiki/NC\_%28complexity%29), which is conjectured but not known to hold. In particular, P-complete problems are good candidates for problems that don't benefit much from parallelization. There are stronger versions of this view; for instance, in cryptography, timelock puzzles utilize functions that are believed to be inherently sequential: a parallel processor cannot speed them up very much.
> 1 votes

---
Tags: turing-machines, parallel-computing
---


# Question
Title: Finding the base case for T(n) = T(n - a) + T(a) + cn
I was solving the recurrence using Recursion tree method: $$ T(n) = T(n - a) + T(a) + cn$$

When I started solving I could easily conclude the fact that $T(a)$ would have total cost computation in the form of:

$$h\*ca$$ But I could not figure out on how to solve the base case.

I know that $T(n-a)$ would be at base case when $n=a$.

But how to compute the height $h$ of the recurrence. I know the base case can be defined as: $$n-ia=0$$

I have seen the previous examples in the book **Introduction to Algorithms** which quotes:

> The subproblem size for a node at depth $i$ is $n/4^i$ . Thus, the subproblem size hits $n=1$ when $n/4^i=1$ or, equivalently, when $i = \log\_4 n$

For the recurrence: $T(n)= 3T(n/4)+ cn^2$

So, coming to the point what would be the base case such that the sub-problem size hits $n= ?$ like in the above example.

Would it be $n=a$?

Please correct me if I am wrong. Thank you.

# Answer
Every $0\le k\le a$ yields the base case $T(k)$. If you are trying to solve the big-O of the recurrence, then you may as well assume that there is some $c$ where $T(k)\le c$ for every base case $k$. It will help making the computation a bit easier
> 1 votes

---
Tags: algorithms, recurrence-relation, divide-and-conquer
---


# Question
Title: Does P not NP imply NP COMPLETE disjoint from RP?
According to Wikipedia https://en.wikipedia.org/wiki/RP\_(complexity), $P \ne NP$ implies that $RP$ is a strict subset of $NP$. Does anybody have a reference? Furthermore, am I correct that if this indeed the case, then $NP-COMPLETE \cap RP = \emptyset$ since we can use $NP$ completeness to solve all other $NP$ problems?

# Answer
You have not accurately summarized the statement in Wikipedia. The statement in Wikipedia also needs the extra assumption that $P=BPP$, which is widely conjectured but has not been proven to be true.

With that clarification, no reference is needed -- the reasoning is straightforward and already described on Wikipedia. If $P=BPP$, then $P=RP=co-RP$ (since $BPP=co-BPP$ and $RP \subseteq BPP$ and $co-RP \subseteq BPP$). If additionally $P \ne NP$, then it follows that $RP \ne NP$.

Yes, if $RP \ne NP$, then $NPC \cap RP = \emptyset$.
> 1 votes

---
Tags: complexity-theory, np
---


# Question
Title: Pick elements that don't exhaust any set
The following is an NP-Complete problem:

---

Suppose you have a collection $\mathcal{C}$ of sets, so that $A\_i\in \mathcal{C}$ and $A\_i$ is some set--we can suppose the elements of $A\_i$ are integers. We want some $k$ integers, say $X \subseteq \bigcup\_{A\_i\in \mathcal{C}}A\_i$ where $X$ has $k$ elements, and subject to the constraint that $A\_i \not\subseteq X$ for any $A\_i \in \mathcal{C}$.

---

I primarily am curious whether this is a named problem and if so, what is it's name? I've already figured out how to show that it's NP-Complete by reduction to the Independent Set problem. However I am curious to get some more context to this problem, so I wanted to research it a bit. But I can't find it referenced anywhere.

# Answer
This is the hitting set problem in disguise.

Let $U=\cup\_{A\_i \in \mathcal{C}} A\_i$ be the universe and $\overline{X} = U \setminus X$. Then your problem can be equivalently stated as follows: given $\mathcal{C}$ and $k$, find $\overline{X}$ that has $|U|-k$ elements, and such that $A\_i \cap \overline{X} \ne \emptyset$ for each $A\_i \in \mathcal{C}$. That is exactly the hitting set problem.
> 2 votes

---
Tags: np-complete, decision-problem
---


# Question
Title: How can i compute tag-index-displacement bits of an address if cache size is not a power of two?
How can i compute tag-index-displacement bits from an address if cache size is not a power of two? Intuitively, i would be inclined to think that i can not directly indicate which bits of the address are used to tag, index blocks and displacement. Instead, i think that i should do some conversion such that it appears that the sum of the bits of tag, index and displacement must be greater than the bits of address. This because for the index i need a number i of bits such that i ≥ log\_2(number of blocks), for displacement i need a number d of bits such that d ≥ log\_2(dimension of each block in bytes) if i suppose a byte addressable cache. Some suggestions?

As suggested by maverick1989, i explicate the data of the part of the exercise that give me trouble. I have a cache direct-mapped of 5256KB with 32B blocks. Assume a 32-bit addressing mode. This mean that i have (5256\*1024)/32 = 168192 blocks. Thus, i need log\_2(32)=5 bits of displacement to address a single byte in a block and log\_2(168192)=17.3597... bits of index to address a block in the cache. Obviously i have to use 18 bits instead of 17.35.... Now i have some trouble to find the value of these 18 bits, given the address. And after that, what about tag bits?

# Answer
One way is by having multiple cache banks, each of which **is** a power of two in size. For example, 3 banks of 16kB each. The first 3 (bank\_num) bits can be used with one-hot encoding to decide which bank would need to be checked to access the requested data (or to write to).

The rest of the cache access would proceed as usual (look up TLB to get tag bits, index into cache in parallel, etc.)

However, usually non-powers of two caches are not used because the IPC to cache size curve is such that it you find the sweet spot very close to a number that is a power of two (or you don't lose significantly in IPC by moving to a power of two).
> 2 votes

# Answer
The straightforward manner of indexing and tagging a cache is for the index to be the address (in blocks, i.e., removing the block offset) modulo the way size (in blocks) and for the tag to be the quotient of these numbers. The computational cost of exact division for non-powers-of-two makes this less practical for first level caches, but Mersenne number (2n-1) modulo indexing has been proposed for L2 caches to reduce conflicts under regular strided accesses. The cost of calculating the modulo of a Mersenne number is modest, summing sections of the block address (e.g., block address 0xMMMN\_NNOO\_OPPP with a 4Ki-block way would map to 0xMMM + 0xNNN + 0xOOO + 0xPPP, with 0xfff mapping to 0x000) and only the final sum needs the carry to be propigated. The tag can simply use the bits for a smaller power-of-two-sized cache; one tag bit would encode very little information. (Alternatively, one could guarantee that cacheable addresses never exceed the Mersenne number quotient equal to the highest power-of-two quotient. This leaves a little of the highest portion of the address space as uncacheable, but saves one tag bit.)

IBM's POWER4 L2 cache had three partitions with the partition determined by modulo three of a large number of address bits. This points to the fact that maximally even distribution of blocks to indices is not required.

With an even distribution of accesses across the entire address space, modulo indexing in a non-power of two cache increases conflicts for the smaller indices (for block 0 with Mersenne numbers). Since even distribution is just an appoximate model of actual access behaviors, layering another approximation on top of it need not catastrophically increase the miss rate.

Exploiting approximation, a highly associative cache with ways having a large Mersenne number of blocks could even simply invert an arbitrary indexing bit in each way (one way could avoid this inversion), dropping one in the power-of-two blocks for each way. In an eight-way associative cache with 212-1 blocks per way, eight blocks per 4Ki blocks (less than 0.2%) would be limited to seven-way associativity. This technique could be applied to larger reductions from a power-of-two at the cost of significantly increasing the number of addresses with reduced associativity.

Using skewed associativity (where each way uses a different more complex hash of address bits to determine the index), would further scramble the addresses suffering reduced associativity from high indices not be available, though the miss count increase (compared to a power-of-two way) from the simple bit inversion technique would be modest in high capacity highly associativte caches.

For a direct-mapped cache, using a complex hash of the address to generate an N-bit index and mapping indices to missing blocks to adjacent blocks might be acceptable. The blocks that conflict could be somewhat scrambled.

With set associative caches, one can also use different power of two indices for different ways (which can be viewed as separate caches accessed in parallel). The different ways/caches could also have different allocation and replacement policies. For example, a small highly associative cache (victim cache) might only accept allocation of blocks evicted from the larger less associative cache or a reversal of this allocation policy might be used with selective victims from a small highly associative cache going to a larger less associative cache (HP PA 7200's assist cache plus off-chip direct-mapped cache is an example). Selective allocation could also be used to increase conflicts in accesses with low temporal reuse, allocating non-temporal accesses to a small, modest-associativity cache.

The most straightforward method of providing non-power-of-two cache sizes is to have a non-power-of-two associativity. This allows a single simple indexing function to be used.
> 1 votes

# Answer
Please note, you could use as many bits as you want in tag, though usually (in case cache size is power of two) it does not make sense.

So I think you could use saturation arithmetic here - index will use 18 bits and tag will use 32 - 18 + 1 = 15 bits. that additional single bit in tag at least significant position could serve as a carry for index calculation such that if 18-bit wide index value is greater than 168192 then you subtract that 168192 and use result as index and set that additional least significant bit in tag to 1 otherwise it's zero always.
> 0 votes

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


# Question
Title: How does malware enter the computer and take control on a binary or machine code level?
Malware can enter a computer in various ways, but I would like to know how it is able to simply use 0's and 1's and machine code to take over a computer and how it can stay hidden from antivirus software.

# Answer
This will not be a fully detailed answer, as to explain everything would encompass the material from several years of Computer Science classes. It will need to touch some material from foundational level through to Master material; but not in full detail. What follows would be a road map, or guide to possible explanations (there being more than one way to compromise a machine and stay hidden).

1. All code executed by a computer is ultimately a sequence of 0's and 1's. Although most computer code (including malware) may be written in various computer languages, ultimately the computer memory will contain a translation of that program into a binary pattern in memory. If a computer processor encounters this binary sequence it will perform those actions instructed by the programmer.
The memory will contain anything that needs storing, which can be both data or instructions (known as von Neuman architecture).
This would be covered in a computer architecture course, for example.
2. The hardware features that offer protection, such a virtual memory page registers, memory page protection in hardware, such a read only, execute only properties and how they are used in operating systems.
This might be in a computer systems or operating systems course.
3. The translation of computer programs into sequences of binary is called compilation. It also covers a degree of language theory and the study of parsing and code generation.
This might be covered in a compiler course.
4. The different kinds of computer languages and the runtime protections they offer, such as exception handling (`try ... catch`) and the varieties of languages that do not have run time protection (managed and unmanaged code, for example).
This might be in an advanced programming course, or comparative languages course.
5. The mechanism of the computer stack can be integral to understanding how a machine may be compromised. How computer languages use a stack; the call and return mechanism needs to be explained in order to later understand how that can be usurped to gain control of execution.
This might be covered in a compilers or systems course.
6. The layout of computer memory in a virtual memory model of an operating system needs understanding so the relationship between the positions of code and data in an executing computer program is clearly understood.
This would be in a compiler or computer systems course.
7. Buffer Overflow is a very common way of performing compromise payload injection. One would need to understand what a buffer overflow is, why it occurs in existing computer code (based on the above topics).
8. One would then need to understand how a malware payload might be delivered using buffer overflow mechanisms into a vulnerable system.
9. Understanding how malware might remain hidden you would need to understand how we find malware. You would at least need an understanding of computer POST (Power On Self Test), MBR (Master Boot Record), Root Kits, data encryption and the general details of an operating system.

But I have only scratched the surface, but at least I may have given you a study guide.
> 1 votes

---
Tags: security, binary
---


title: Knapsack problem with a constraint

text:
# Question
Title: Knapsack problem with a constraint
I am familiar with 0/1 knapsack problem. But if the following constraint is imposed... how do I solve the question?

1. If you choose some item 'U' you won't be able to choose another item 'V'.

For example Items are given as \[Name, Weight, Value\]
Items are :
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50

If you choose B then you cannot choose A.
If you choose E then you cannot choose C.
If you choose D then you cannot choose A.
In the similar way the constraints are given.

Please provide me some way to solve the above problem. Any help is highly appreciated.

# Answer
Standard dynamic programming approaches are likely not going to work for this problem, because the extra "this or that but not both" constraints destroy the overlapping subproblems property. So let's break out the sledgehammer.

You can easily encode this as a 0-1 integer linear programming problem and use an off-the-shelf solver. For the given example (and some maximum weight limit $W$), a suitable 0-1 ILP problem is:

maximize $20A + 80B + 30C + 70D + 50E$
subject to
$A, B, C, D, E \in \\{0, 1\\}$
$10A + 50B + 20C + 30D + 50E \le W$
$A + B \le 1$
$C + E \le 1$
$A + D \le 1$

Although, it is not obvious to me that an integer linear programming solver will take full advantage of the structure of the problem. So perhaps a more specialized solution may perform better in practice.
> 2 votes

---
Tags: dynamic-programming, knapsack-problems
---


# Question
Title: Help me understand this Turing-machine Problem concerning $A_{TM}$
I'm a Physics/C.S. student and have been struggling with this particular problem for a few days now. So the task is as following:

---

Consider the following languages:

$\hspace{20pt} L\_1 = \\{\langle M \rangle \\, | \\, L(M) = A\_{TM}\\} \\ \hspace{20pt} L\_2 = \\{\langle M \rangle \\, | \\, L(M) = \overline{A\_{TM}}\\}$

Are these decidable? Prove your decision.

$A\_{TM}$ is defined as $\\{\langle M , w\rangle \\, | \\,\text{M is a TM and M accepts w}\\}$

---

So first off I'm trying to understand the first language $L\_1$. What exactly would it mean for $L\_1$ to be decidable? I understand why $A\_{TM}$ isn't decidable, but what would a TM that decides $L\_1$ actually do?

I feel like I already know the solution to the second problem but would like to know whether my gut instinct is right. So since $\overline{A\_{TM}}$ isn't Turing-recognizable it means that $M$ with $L(M) = \overline{A\_{TM}}$ doesn't exist/is empty. Thus $L\_2 = \emptyset$ and that's easily decidable.

# Answer
Solving the language $L\_1$ means knowing for every TM if it's semi-deciding the $A\_{TM}$ problem.

Your instinct is right - it is empty and therefore decidable. **If** it wasn't empty by any chance, then by Rice's theorem it would have not been decidable
> 0 votes

---
Tags: turing-machines, undecidability
---


# Question
Title: Show that for every language there exists a harder language
I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that:

$$ A \leq\_T B $$

but:

$$ B \not \leq\_T A $$

If it is $A \leq\_TB$ and $B \leq\_T A$, this is easy since we can just let $B := \bar{A}$, but for the above I could not think of anything. Any help ?

# Answer
> 2 votes
There are a few ways to approach this.

You can use a counting argument to show that for every $A$ there exists $B$ such that $B\nleq\_T A$. Let $L\_A=\\{B| B\le\_T A\\}$ denote the set of all languages reducible to $A$. Show that $f:L\_A\rightarrow \mathbb{N}$ that maps languages $B\in L\_A$ to $n$ such that $M\_n$ is a reduction from $B$ to $A$ is an injection, and conclude that there exists a language outside of $L\_A$. Next, you want to make it comparable to $A$. We can get such a language with the join operator:

$A\sqcup B=\\{0w|w\in A\\}\cup\\{1w|w\in B\\}$.

I leave it to you to show that $A\sqcup B$ is the least upper bound for $A,B$, i.e. $A,B\le\_T A\sqcup B$ and additionally for every $L$ such that $A,B\le\_T L$ we have $A\sqcup B\le L$ (you only care about the former). Show that if $B\nleq\_T A$ then $A\sqcup B\nleq\_T A$.

Another way to prove this is to use the jump operator. We need to introduce the notion of oracle machines, and then show that $B=\left\\{\left(M^A,w\right)| \text{$M^A$ halts on $w$}\right\\}$ is a strictly harder language. The proof is identical to the undecidability of the standard halting problem, only that now we show the stronger property that no machine with oracle access to $A$ can decide $B$.

You can also directly construct such a language via diagonalization. define $B=\left\\{n | M\_n(n)\notin A\right\\}$. We constructed $B$ such that any computable function $M\_n$ fails to be a reduction from $B$ to $A$ on at least one input (specifically, the encoding of the reduction). You can now use the join operator to make them comparable.

---
Tags: turing-machines, reductions, undecidability, semi-decidability
---


# Question
Title: Is the Languague which contains all TMs which write the blank symbol at firs by the given input w decidable?
Consider the problem of determining whether a Turing machine M on an input w writes the blank symbol at first. Is this decidable ?

# Answer
> 0 votes
Yes, just simulate $M$ on $w$ and check to see if it wrote the blank symbol at first

---
Tags: turing-machines, undecidability, semi-decidability, turing-completeness
---


# Question
Title: turing machine accepting language {ww} has ω($n^2$)
prove or disprove that any turing machine which accepts language $l=\\{ww | w ∈ \\{0, 1\\}∗ \\}$ has time complexity $ω(n^2)$

# Answer
> 1 votes
A multi-track Turing Machine can accept this language in linear time: (copy the input on the second tape; move the second head to the middle of the word; keep moving both heads right simultaneously and make sure that both heads have the same symbol).

In a single-tape Turing Machine, the time complexity will be at least $\Omega(n^2)$. The formal proof for a similar problem is given in Theory of Computation, Kozen: Theorem 1.1.

**Intuition:** The finite state automata of any Turing Machine can only store a finite amount of information. We can find the middle position of the input in linear time. To accept the input of the form $ww$, the Turing machine will move its head from the left to the right until it reaches the middle position and checks whether the symbols after the middle position are same as the those at the beginning.
When the head reaches the middle position, *it can only bring a piece of fixed finite information about the symbols from the left part of the word*. Hence, for a long enough word, we need to traverse back and forth multiple times. In each traversal from the start to the end, only fixed number of symbols will be verified, and hence, it should be easy to see, that the time complexity will be $\Omega(n^2)$

The two definition that will probably help you modify the proof given in Kozen for this problem are:

1. For $n = 4k$ , define $L\_n = \\{ x\\#^{n/4}x \\#^{n/4} \\; | \\; x \in \\{0,1\\}^{n/4} \\}$.
2. Define the crossing sequence of the word $x$ to be: $C(x) = \\{c\_i(x) \\;| \\; \frac{n}{4} \< i \le \frac{n}{2} \\;\\; \text{ or }\\;\\; \frac{3n}{4} \< i \le n \\}$

---
Tags: complexity-theory, turing-machines, time-complexity, computation-models
---


# Question
Title: Determine if the following problem is decidable or not : Does the read–write head of a TM with the input w leave the word w?
Determine if the following problem is decidable or not : Does the read–write head of a TM with the given input w leave the word w on the tape?

# Answer
> 1 votes
It is not clear if your language $L$ contains the pars $\langle T, w\rangle$ or if $w$ is fixed and $L$ only contains Turing machines. In any case the answer is the same.

Let $T$ be a (single tape) TM that does not leave the word $w$. Let $Q$ and $\Gamma$, be the set of states and the tape alphabet of $T$.

The number of possible configurations of $T$ can be upper bounded as a function of $|w|$, $|Q|$, and $|\Gamma|$ and this upper bound $B\_T$ is computable.

To decide $L$ it suffices to simulate $T$ for $B\_T$ steps. If $T$ ever leaves the word $w$ you can reject. Otherwise either $T$ halted without leaving $w$, or $T$ is stuck in an infinite loop that does not leave $w$. In both cases you can accept.

---
Tags: turing-machines, turing-completeness, turing-test
---


# Question
Title: Average number of exchanges during first partition stage in Quicksort
**I am trying to understand average no of exchanges in Quicksort.**

Here is the code to partition the array -

```
 private static int partition(double[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        double v = a[lo];
        while (true) {

            // find item on lo to swap
            while (less(a[++i], v))
                if (i == hi) break;

            // find item on hi to swap
            while (less(v, a[--j]))
                if (j == lo) break;      // redundant since a[lo] acts as sentinel

            // check if pointers cross
            if (i >= j) break;

            exch(a, i, j);
        }

        // put v = a[j] into position
        exch(a, lo, j);

        // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi]
        return j;
    }

```

To start with in first partition stage -

There are total comparisons as below $ C\_N= N +1 $

so exchanges in worst case should be $ \frac{N}{2} - 1 $

But am not able to deduce number of exchanges in first partition stage which is $ \frac{(N-2)}{6} $

**can someone explain how to deduce this?**

# Answer
> 5 votes
The partition method in the question, `partition(a, lo, hi)` is called Hoare’s partition scheme, which is the most classic partition scheme used in quicksort.

Here is the situation. There are $n$ numbers that are non-equal pairwise. Array $a=(a\_0, a\_1, \cdots, a\_{n-1})$ is a uniformly-random permutation of those $n$ numbers. We will run the method `partition(a, 0, n-1)`. What is the number of exchanges executed inside the loop `while(true)`? (Note that the exchange `exch(a, lo, j)` outside the loop is not counted.)

WLOG, let the $n$ numbers be $1, 2, \cdots, n$.

Suppose the first element of $a$ is $p$ (for **p**ivot). Excluding that first element, split $a$ into one segment of $p-1$ numbers followed by another segment of $n-p$ numbers.

$$a = (p,\ \underbrace{a\_1,\ a\_2,\ \cdots,\ a\_{p-1},}\_{p-1\text{ numbers}}\ \ \underbrace{a\_p,\ a\_{p+1},\ \cdots\ a\_{n-1}}\_{n-p\text{ numbers}})$$

Observe the number of elements greater than $p$ in the front segment is always the same as the number of elements smaller than $p$ in the back segment. (Proof: let the two numbers be $x$ and $y$ respectively. The total number of elements greater than $p$ in $a$ is $x + ( n-p-y)$. On the other hand, the total number of numbers greater than $p$, which are $p+1, p+2, \cdots, n$, is $n-p$. That means, $x+(n-p-y)=n-p$, which means $x=y$.)

In the while loop of `partition(a, 0, n-1)`, the first element greater than $p$ in the front segment is exchanged with the last element smaller than $p$ in the back segment. Then the second element greater than $p$ in the front segment is exchanged with the second last element smaller than $p$ in the back segment. And so on, until we have exhausted elements greater than $p$ in the front segment (and, in the meantime, we have exhausted elements smaller than $p$ in the back segment as well). So the number of exchanges made is equal to the number of elements greater than $p$ in the front segment.

To calculate the average number of exchanges made, let us run `partition(a, 0, n-1)` as $a$ ranges over all permutations of $1, 2, \cdots, n$. Then

$$\text{total number of exchanges}=\sum\_{p=1}^n\sum\_{a\_0=p}\text{number of exchanges on }a\\ =\sum\_{p=1}^n\sum\_{x}^{}x\cdot(\text{number of permutations that starts with }p\text{ with }x\text{ exchanges performed})$$

As we have explained above, for a permutation that starts with $p$, $x$ exchanges will be performed on it if and only if that permutation has $x$ elements greater than $p$ in its front segment of $p-1$ elements. The number of such kind of permutations is the product of the following four factors.

$$ \underbrace{\binom{n-p}{x}}\_{\text{the number of ways to choose }\quad\ \ \\x\text{ elements out of all }n-p\\\text{numbers that are greater than }\ \\p \text{ for the front segment}} \underbrace{\binom{p-1}{p-1-x}}\_{\text{the number of ways to chose }\\p-1-x\text{ elements out of all}\\p-1 \text{ numbers that are smaller }\quad\ \ \\\text{than }p\text{ for the front segment}} \underbrace{(p-1)!}\_{\text{the number of ways}\\\text{to permute all }p-1\\\text{elements in the}\\\text{front segment}}\quad\ \ \underbrace{(n-p)!}\_{\text{the number of ways}\\\text{to permute all }\\n-p\text{ elements in}\\\text{the back segment}}\\ $$

So,

$$\begin{aligned}&\quad\text{total number of exchanges}\\ &=\sum\_{p=1}^n\sum\_{x=0}^{\min(n-p, p-1)}x\binom{n-p}{x}\binom{p-1}{p-1-x}(p-1)!(n-p)!\\ &=\sum\_{p=1}^n\left((p-1)!(n-p)!\sum\_{x=0}^{\min(n-p, p-1)}x\binom{n-p}{x}\binom{p-1}{p-1-x}\right)\\ &=\sum\_{p=1}^n\left((p-1)!(n-p)!\sum\_{x=1}^{\min(n-p, p-1)}(n-p)\binom{n-p-1}{x-1}\binom{p-1}{p-1-x}\right)\\ &=\sum\_{p=1}^n\left((p-1)!(n-p)!(n-p)\sum\_{y=0}^{\min(n-p-1, p-2)}\binom{n-p-1}{y}\binom{p-1}{p-2-y}\right)\\ &\stackrel{\bigstar}{=}\sum\_{p=1}^n(p-1)!(n-p)!(n-p)\binom{n-2}{p-2}\\ &=\sum\_{p=1}^n(p-1)(n-p)(n-2)!\\ &=(n-2)!\left((n+1)\sum\_{p=1}^np-\sum\_{p=1}^nn-\sum\_{p=1}^np^2\right)\\ &=(n-2)!\left((n+1)\frac{n(n+1)}2-n^2-\frac{n(n+1)(2n+1)}6\right)\\ &=n-2)!\\,\frac{n(n-1)(n-2)}6=n!\\,\frac{n-2}6.\\ \end{aligned}$$

The average number of exchanges is $$\frac{\text{total number of exchanges}}{\text{number of permutations}} =\frac n6-\frac13 \color{#d0d0d0}{\quad\text{for } n\ge2}.$$

---

You might wonder the equality above that is marked with a $\bigstar$. It can be established by splitting into two cases, when $n-p-1\lt p-2$ and when $n-p-1\ge p-2$, and then using Vandermonde's identity.

Another way to prove it uniformly is to rewrite the Vandermonde's identity as, for any non-negative integer $m, n, k$, $$\sum\_{r=-\infty}^{\infty}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r},$$ where we extend the definition of the binomial coefficient $\binom nk$ so that for all $n\ge0$ we have $\binom nk=0$ for all $k\lt 0$ or $k\gt n$. Note that the summation on the left-hand-side ranges is well-defined, since it contains, in fact, only finitely many non-zero items. We have, $$\sum\_{y=0}^{\min(n-p-1, p-2)}\binom{n-p-1}{y}\binom{p-1}{p-2-y}=\sum\_{y=-\infty}^{\infty}\binom{n-p-1}{y}\binom{p-1}{p-2-y}\\\=\binom{(n-p-1)+(p-1)}{y+(p-2-y)}=\binom{n-2}{p-2}.$$

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


# Question
Title: In general, how does a DFA know how to successfully process a string the intended way?
Suppose we have:

$$A\text{ }\colon=\\{x, y, z\\}$$

$$M\text{ }\colon=\text{some DFA using A}$$

$$S\text{ }\colon=xyzxyzxyz$$

Intuitively, one might say $S$ is fed to $M$ on a *per-character* basis.

This means that somehow we have an undisclosed mechanism that can tell where a symbol starts and ends.

One might say, simply use the maximum valid substring similar to how Lexers tokenise plaintext. To that I say, suppose instead that we defined $A$ as: $$A\text{}\colon= \\{x, xx, xxx\\}$$

Now we have 3 unique symbols, that, as it so happens, using the maximum valid substring will yield in a restriction to what our our $M$ can actually process, because any string longer than 2 characters will always be assumed to start with $xxx$ rather than perhaps, $x$ and $xx$.

One way I see around this is to actually have a character synonymous to a symbol. That is, $x$ and $xxx$ (from $A$) are both a single character each.

Thoughts?

**EDIT**

In the case my question is unclear:

The extended transition function is defined so as to extend the processable input of a DFA from simply one alphabetic character at a time, to an arbitrary amount. Usually we go about defining it as follows for a string **wa**:

$$\hat{δ}(q,w) = δ(\hat{δ}(q, x), a)$$

My issue is: What is converting the input from a string to a partition? Whatever this object may be, it has to follow some lexing rules, does it not? Are there any conventions that go about this?

# Answer
The transition function of a DFA has the type $\delta : (Q \times \Sigma) \rightarrow Q$. That is, it's a function that takes a state (from the set of states) and a symbol (from the set of symbols) and returns another state.

This function doesn't have to know anything about tokenization. It's given a single symbol, and that's all it cares about.

Similarly, the input to a DFA is generally defined to be an ordered series of symbols: this is what "a string over the alphabet $\Sigma$" means mathematically. If it helps, think of it as a "list" rather than a "string" in programming terms. So if the alphabet were $\\{x, xx, xxx\\}$, then the input might look something like $\[x, xx, xxx, x, xx, xxx, x, xx, xxx\]$. No ambiguity there.

In practice, most real-world DFA implementations (like foma) *do* have to care about tokenizing. But the details of how to do that are up to the implementation; the definition of a DFA doesn't care one way or the other.
> 2 votes

# Answer
Your $A$ (usually called $\Sigma$) are the letters in languages. Obviously, a letter cannot be compromised of other letters. This means that you are not allowed to have $xxx\in A$, as it simply not one letter - but rather a word of 3 letters.

It does not really matter how you name the elements in $A$, and as far as we are concerned, the naming is only meaningful for humans - so pick something **you** will be able to interpret properly.

A DFA will think of every element in $A$ as a different letter and the naming only affects how us humans read it
> 1 votes

---
Tags: finite-automata
---


# Question
Title: Is finding solution to a system of 2SAT equations seperated by OR (DNF form) in NP
I want to know if finding solution to a specific number of 2SAT equations sepearted by OR gate (DNF form as below) is in P or NP.

The equation has total n variables and each clause is a 2SAT equation in itself in a subset of variables from 1 to n. Example:

**F = \[(x1 || x2 ) && ( !x2 || x3) && (x3 || x4)\] || \[(x2 || x5) && (x3 || x6) && (!x4 || !x6)\] || ....**

The equation F is a DNF of 2SAT equations, which has say m clauses. Is finding a solution to this in NP? If yes how?

Also, specifically I also want to know if finding False instances of equation F is in P or NP as well.

# Answer
* First, let me note that the question's title is a bit misleading, because $P$ is a subset of $NP$. See also Yuval Filmus's comment. I assume what you *intended* to ask is whether it's in $P$ or in $NP \setminus P$.
* Also, the name "DNF" specifically refers to a disjunction of **elementary** conjunctions, not a disjunction of arbitrary functions. What you are describing is not a DNF, but a disjunction of CNFs.

With that out of the way, here's my answer.

---

1. To satisfy a disjunction of 2-CNFs, all you need is to satisfy **one** of them. So, if you apply the 2-SAT algorithm to the first of the CNFs and get a "yes", then the answer to the whole problem is "yes". Otherwise, you just move on to the second one, and so on. Shouldn't take long, since you only have *m* of them. If none of them can be satisfied individually, i.e. they are all constant zeroes, then obviously the entire thing is a constant zero.

So the answer to the first part is: the problem is in P, with the following decision algorithm:

For every 2-CNF, apply the "normal" 2-SAT algorithm (the resolution rule) to determine if it's satisfiable or not. If "yes", just return "yes". If you went through all of them without finding a "yes", then return "no".

---

2. Now, finding the "False" cases of that formula (also known as the problem of tautology) is another question entirely. For one thing, tautology for ORs of ANDs of ORs is equivalent to satisfiability for ANDs of ORs of ANDs, by De Morgan's rule. But that's just a more general case of an already general SAT problem, isn't it?

Consider what happens when you restrict the set of possible formulas to those in which every two-element disjunction is really just one element, repeated. So it is a formula like $$ F = \[(x\_1 \vee x\_1 ) \\& ( \neg x\_2 \vee \neg x\_2) \\& (x\_3 \vee x\_3)\] \vee \[(x\_2 \vee x\_2) \\& (x\_4 \vee x\_4) \\& (x\_5 \vee x\_5)\] \vee ... $$ which is equivalent to $$ F = \[x\_1 \\& \neg x\_2 \\& x\_3\] \vee \[x\_2 \\& x\_4 \\& x\_5\] \vee ... $$ which is just a normal DNF. After the De Morgan transformation, you get a normal CNF, whose satisfiability is known to be NP-hard. Therefore, any problem that includes this one *as a subset* will also be at least NP-hard.

Obviously, the problem in question won't be *outside* NP, because it is still polynomially verifiable. So the answer to your second question is "in NP, but not in P".
> 1 votes

---
Tags: time-complexity, complexity-classes
---


# Question
Title: TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$
Input: complete, undirected graph $G=(V,E)$ and cost function $c$ Assume for all nodes $x,y,z \in V$: $c(x,z)\le c(x,y) + 100\cdot c(y,z)$

Find a 200-approximation polynomial time algorithm for the input.

I've seen the regular 2-approximation algorithm for a graph that satisfies the triangle inequality.

1. Find the MST $T$ for the graph
2. Find Euler Cycle by doubling the edges in $T$
3. Find Hamiltonian Cycle by removing each vertex that appears more than once

If $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ , then $c(x,z)\le c(x,y) + c(y,z)$ , so I figure we can use the same approximation algorithm. But I'm not sure how to prove that this gives a 200-approximation.

# Answer
> 1 votes
This is not true.

> If $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ , then $c(x,z)\le c(x,y) + c(y,z)$

However it is true that, for $x,z \in V$ with $x \neq z$, you have $c(x,z) \le 100 d(x,z)$. To see this let $P$ be a shortest path from $x$ to $z$. The proof is by induction on the number of edges $|P|$ of $P$.

If $|P|=1$ then $c(x,z) = d(x,z) \le 100 d(x,z)$.

If $|P| \ge 2$ then, let $y$ be the vertex immediately preceding $z$ in $P$. By inductive hypothesis $c(x, y) \le 100 d(x,y)$ and you have $$ c(x,z) \le c(x,y) + 100 c(y,z) \le 100 d(x,y) + 100 c(y,z) =100 d(x,z). \quad \square $$

Consider a MST $M$ of $G$ and let $T$ be a Euler tour of $M$, starting from an arbitrary vertex. Let $v\_0, v\_1, \dots, v\_{n-1}$ be the vertices in $V$ in the order they appear for the first time in $T$ and let $v\_n = v\_0$. Consider the tour $T'$ that visits $v\_0, v\_1, \dots, v\_n$ in this order.

For $i=0, \dots, n-1$ let $T\_i$ be the portion of the tour between the first occurrence of $v\_i$ in $T$ and the next occurrence of $v\_{i+1}$ in $T$. Given any graph $H$, let $c(H)$ be the sum of costs of the edges in $H$. Let $T^\*$ an optimal tour of $G$.

You have: $$ \begin{align\*} c(T') &= \sum\_{i=0}^{n-1} c(v\_i, v\_{i+1}) \le 100 \sum\_{i=0}^{n-1} d(v\_i, v\_{i+1}) \le 100 \sum\_{i=0}^{n-1} c(T\_i) \\ &\le 100 c(T) \le 200 c(M) \le 200 c(T^\*). \end{align\*} $$

---
Tags: complexity-theory, approximation, traveling-salesman
---


# Question
Title: Clustering a set of point by affine transform
We are given a set of $n$ points on the plane $a\_i = \\{x^a\_i, y^a\_i\\}$ and $b\_i = \\{x^b\_i, y^b\_i\\}$.

Assume that the points b are an affine transform of the points a, we can find a matrix $M$ and vector $t$ such that $\sum\_{i=0}^{n-1} ||M a\_i + t - b\_i ||^2$ is minimized, in fact, we can even do so analytically.

Assume however that the points a\_i are composed of different subsets to which a different affine transform was applied.

Let $\epsilon$ be a small, tolerance value. A partition $\cup\_{j=0}^m P\_j = \[1\ldots n\] \wedge \forall j, k, P\_j \cap P\_k = \emptyset$ is said to be admissible iff

$$\forall j,~ \exists M\_j, t\_j,~ \forall i \in P\_j,~ ||M\_j a\_i + t\_j - b\_i||^2 \< \epsilon$$

Simply speaking, we partition the points into different subsets each of which is sent to $b$ with its own affine transform.

An admissible partition always exists because it's always possible to sent a to b exactly if each point is given its own affine transform (in fact, every 3 points can be sent to any other 3 points).

We want to cut up the points in as few pieces as possible: an admissible partition is *minimal* when it has fewer or equal subsets than any other admissible partitions.

How would one go about finding an admissible partition? Heuristics and approximate solutions are welcome. One approach would be to consider the transformation defined by every triplet of points and try to cluster those together, but this requires looking at $O(n^3)$ transforms.

# Answer
I would suggest you try using RANSAC. Randomly pick a triplet of $a$ points and $b$ points, find an affine transformation that maps the former to the latter, find all other points that it maps well, and create that as a candidate cluster those. Repeat many times, and keep the best cluster. Remove the points in that cluster, and then repeat.

This might perform better than your $O(n^3)$ time solution if you expect to have a few large clusters (but probably it is not better if you expect to have many small clusters).
> 1 votes

---
Tags: computational-geometry
---


# Question
Title: Do we have to calculate time for declaring statement in RAM model?
Do we have to calculate time for declaring statement, in my case `int num3` statement. The following question was asked by professor as a post-lecture quiz. I selected `t(n)=3`, but the correct answer was `t(n)=4`.

```
What is the time taken by following algorithm on RAM model ?

```

```
t(n)=3
t(n)=4
t(n)=5
None of the above

```

# Answer
There is no standard answer, so you'll have to go by whatever convention is used in your course.
> 2 votes

---
Tags: time-complexity, runtime-analysis, computation-models
---


# Question
Title: I am unable to understand the logic behind the code (I've added exact queries as comments in the code)
Our local ninja Naruto is learning to make shadow-clones of himself and is facing a dilemma. He only has a limited amount of energy (e) to spare that he must entirely distribute among all of his clones. Moreover, each clone requires at least a certain amount of energy to function (m) . Your job is to count the number of different ways he can create shadow clones. Example:

e=7;m=2

ans = 4

The following possibilities occur: Make 1 clone with 7 energy

Make 2 clones with 2, 5 energy

Make 2 clones with 3, 4 energy

Make 3 clones with 2, 2, 3 energy.

Note: \<2, 5\> is the same as \<5, 2\>. Make sure the ways are not counted multiple times because of different ordering.

**Answer**

```
int count(int n, int k){
    if((n<k)||(k<1)) return 0;
    else if ((n==k)||(k==1)) return 1;
    else return count(n-1,k-1)+ count(n-k,k);   // logic behind this?
}

int main()
{
    int e,m;            // e is total energy and m is min energy per clone
    scanf("%d %d", &e, &m);
    int max_clones= e/m;
    int i,ans=0;
    for(i=1;i<=max_clones;i++){
        int available = e - ((m-1)*i);   // why is it (m-1)*i instead of m*i
        ans += count(available, i);
    }
    printf("%d",ans);
    return 0;
}

```

# Answer
```
Count (energy, clones, min_energy):
    If enregy < min_energy or clones == 0: return 0
    If energy == min_energy or clones == 1: return 1
    Else:
            cnt = 0
            For every cur_energy from min_energy to energy:
                   cnt += Count(energy - cur_energy, clones - 1, cur_energy)
    Return cnt

```

I am pretty sure the algorithm above works just fine. Notice that i have passed to the recursive call cur\_energy to avoid counting the same thing multiple times

The idea here is to "choose" the energy each clone takes
> 0 votes

# Answer
The count routine only produces 1 or 0. The else line you refer to is the sum of all these values calculated by recursion.

The (m-1)\*i is a mechanism to reduce the total amount of available energy to be what would remain if you paid for all but 1 unit of the cost of a close. This cause all clones to have an equivalent production cost of 1 unit of energy.

For example: if you paid all but \\$1 of a purchase and you still had \\$1 or more dollars in your pocket, then you know you could pay for the whole thing. The count() routine assumes clones cost 1 unit so we reduce our total appropriately before using it.
> 0 votes

---
Tags: combinatorics, recursion
---


title: CPU Registers and Computation

text:
# Question
Title: CPU Registers and Computation
How exactly does the control unit in the CPU retrieves data from registers? Does it retrieve bit by bit?

For example if I'm adding two numbers, A+B, how does the computation takes place in memory level?

# Answer
Let’s say you have a processor with sixteen 32-bit registers and a unit that can add 32 bit integers. A very simplified way to add register x and register y and store the result in register z is this:

First, you build hardware that given a number x, can pick the first bit of register x and move it to the 1st bit of “operand1”. This is actually quite complicated because x could be one of 16 values, and the hardware must be capable to read the first bit of any of the 16 registers.

Second, you take this hardware and make 32 copies of it, one copy for each bit in a register. Now we have some quite complex hardware that can move 32 of 512 bits.

Third, we duplicate all of this with the appropriate changes to move register y to “operand2”.

Fourth, we build hardware that can add operand1 and operand2 and store the sum in a 32 bit location “output”

And fifth, we build the hardware that can take the value in “output” and store it into register z.
> 1 votes

# Answer
The CPU has direct access to registers. If *A and B* are already in the registers then the CPU can perform the addition directly (via the Arithmetic Logic Unit) and store the output in one of the registers. No access to memory is needed. However, you may want to move your data *A and B* from memory or the stack into the registers and vice-versa. These are separate operations.

Registers can be of different sizes 8 to 64 bits, this depends on your CPU architecture. On a *x86-64* CPU registers are 64bit thus addition of two 64bit numbers is a single operation.
> 2 votes

# Answer
(*CPU registers* are considered part of the CPU more often than of memory. Strikingly, addressing is very different.)
The *control unit* does not generally access values from general purpose registers:
it controls feeding register values to, e.g., the ALU. By the *word*.
(There *have* been things like the DEC PDP-8/S or Motorola 14500.)

There is *architecture* (*"logical" registers*), and there is *implementation*, where register renaming abstracts logical registers from physical registers.
Two-operand instructions give rise to multiple *read ports*.
(Next, there is instruction-level parallelism, *multiple write ports*, too).
> 0 votes

---
Tags: cpu, memory-access, assembly
---


# Question
Title: Big-endian systems and the smallest memory address
I read on en.Wikipedia that "Big-endian systems store the most significant byte of a word at the smallest memory address and the least significant byte at the largest. A little-endian system, in contrast, stores the least-significant byte at the smallest address."
But I don't know what is "the smallest memory address", and how does "Big-endianness is the dominant ordering in networking protocols, such as in the internet protocol suite, where it is referred to as network order, transmitting the most significant byte first", in those type of protocols, the first is accessed the smallest memory address and in little-endian system is accessed the memory address?

# Answer
> 2 votes
If the map of memory bytes were arranged from left to right in incremental address order, the smallest address is on the left. The largest address is on the right.

Let's say you are storing the 32-bit value, 19088743, which is `0x01234567` in hex, at address `0x1000`. Hence, the 4-byte value will span over the 4 bytes at memory address `0x1000`, `0x1001`, `0x1002`, and `0x1003`

In big endian, the `01` is stored at `0x1000` (the smallest address) and the `67` is stored at `0x1003` (the largest address). Exactly how you would think of it if you had never heard of little endian.

In little endian, the `01` is stored at `0x1003` (the largest address) and the 67 is stored at 0x01000 (the smallest address).

Big Endian and Network Byte Order generally mean the same thing.

**Big Endian**

```
|===================================|
| 0x1000 | 0x1001 | 0x1002 | 0x1003 |
|-----------------------------------|
|  0x01  |  0x23  |  0x45  |  0x67  |
|===================================|

```

**Little Endian**

```
|===================================|
| 0x1000 | 0x1001 | 0x1002 | 0x1003 |
|-----------------------------------|
|  0x67  |  0x45  |  0x23  |  0x01  |
|===================================|

```

# Answer
> 1 votes
Say you have a computer with one GiB of memory, that is with $2^{30}$ bytes. You will have some mental image how this memory is arranged, from left to right, from right to left (People who are used to writing from left to right usually don’t do that), from top to bottom, or from bottom to top. That’s purely in your mind (or a drawing on paper), but whatever mental image you have, there’s a first and a last byte.

Usually you have a mapping from integer to memory bytes. In that case, you would likely associate the lowest number wit the first byte. Note that the lowest number is often not 0.

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


title: Is this language with prefix regular?

text:
# Question
Title: Is this language with prefix regular?
Is this language regular? ${w ∈ (a + b)∗ : |u\_{a}|\>= 2009 · |u\_{b}|}$ for every non empty prefix $u$ of string $w$} I think it's non-regular. I tried concatenation of $L\_{prefix} $={${ u : |u\_{a}|\> 2009 · |u\_{b}|}$} and $L\_{2}= a^\*b^\*$. $L\_{2}$ is regular. I tried to show that $L\_{prefix}$ is non-regular using pumping lemma. for string z= $a^{2009n} b^n$ pumping 'a' for i=0 : $$ z=uv^iw $$ $$z= uv^0w $$ $$z=a^{2009n-p} b^n$$ so there is less 'a' than 2009'b'

pumping 'b' for i=2 $$z=uv^2w $$ $$z=a^{2009n} b^{n+p} $$ again to much 'b' and less 'a' than should be. So this is non-regular language and concatenation of this two also is non-regular . Is it correct? Or maybe it's somehow regular?

# Answer
> 1 votes
Let $k=2009$ and $L = \\{w : |u\_a| \ge k\cdot |u\_b|$}. I think it is easier to prove using Myhill-Neorde's Theorem.

Consider the strings $a^k, a^{2k}, a^{3k} \ldots$, we claim that all of these have a $L$-distinguishable suffix. Consider $a^{lk}$ and $a^{mk}$ with $l \< m$. Let $x = b^m$. We have $a^{lk}b^m \notin L$ but $a^{mk}b^m \in L$ (Why?). Therefore, there are infinitely many $L$-equivalence classes, which proves that, by Myhill-Nerode's theorem, that $L$ is non-regular.

---

Your argument is almost correct:

Assume, for the sake of contradiction, that $L$ is regular. Therefore, by closure property of regular languages, $L' = L(a^\*b^\*) \cap L$ will also be regular. Notice that all the words in $L'$ will be of the form $a^{n\_1}b^{n\_2}$ s.t. $n\_1 \ge kn\_2$.
Now, consider a word $w = a^{kn}b^{n}$ in $L'$. Using pumping lemma, for a sufficiently large $n$, there should exist a partition of this string $w = xvy$ such that $v \ne \epsilon$. Now, three case arises:

1. If $v$ lies in the part $a^{kn}$: pumping down will lead to a contradiction
2. If $v$ overlaps both the $a$'s and $b$'s parts: $v$ should be of the form $a^{m\_1}b^{m\_2}$. Pumping up will result in a string of the form $a^{kn}b^{m\_2}a^{m\_2}b^{m\_2 + n}$, which doesn't belong to $L'$ (why?)
3. If $v$ lies in the part $b^n$: pumping up will lead to a contradiction

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


# Question
Title: Databases and B-Trees: What are Keys and how are they related
I confused about the description & definition of "key" occuring as terminology for databases and b-trees.

In first case dealing with theory of databases a key is defined as a choice for a in certain sense minimal (see below) subset $K \subset A := \\{A\_1,A\_2,...,A\_n\\}$ of a fixed set of attributes $A\_i$ parametrizing a data table (consisting of relations; a single relation is abstraction of a row in the table), where each attribute is literally a column specifying a property of objects = relations.

A key is characterized by property that there exist no two different relations (a relation is a row) which have exactly the same values for all attributes **which belong to the key**. And a key is a **minimal subset with this property**, ie there not exist a proper smaller subset of attributes contained in the key and having the property described in last sentence. Clearly keys are not unique. So the set of a keys is certain subset of the power set $\Omega(A)$ of the set attributes $A\_i$. See also here: https://en.wikipedia.org/wiki/Unique\_key

On the other hand the key concept occures as well for b-trees: https://en.wikipedia.org/wiki/B-tree#Definition

Here keys are a priori numbers or integers and different knots of b-tree contain different totally ordered subsets of keys where the total order on the space of keys is inherited from the order "$\ge$" for integers $\mathbb{Z}$. Especially the set of keys is a totally ordered subset of integers.

Question: How are the two concept of 'key' related to each other? My first idea was that if we consider in light of for definition (as elements of power set of attributes), we can simply randomly enumerate all the keys (that is associate to each key an number; formally speaking to specify an injection $f:\mathcal{K} \to \mathbb{Z}, K \mapsto f(K)$ where $\mathcal{K} \subset \Omega(A)$)

and then treat them as numbers when working with b-trees. Is this exactly the correct connection or is there another deeper one and my approach is wrong?

# Answer
> 1 votes
There's an indeed a relation that maps the database keys to the B-trees keys $K\_d \mapsto K\_b, K\_b \in \mathbb{Z}$

The B-Tree keys are not random though, they represent the physical location of data stored for that key. At the leaf level there are multiple ( up to the order of the tree) database $K\_d$s associated with a single $K\_b$ key. The relation is thus not an injective function.

---
Tags: trees, database-theory, databases, searching, b-tree
---


# Question
Title: Difference between linear bound automata and a Turing machine
Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a Turing machine?

# Answer
Notice that linear bounded automata are precisely all TM's who use $O(n)$ space.

Now, by the space-hierarchy theorem, for any $f$ where $n=o(f)$ (for an extreme example, $f(n)=2^n$) we would have $DSPACE(O(n))\subsetneq DSPACE(O(f))$.

Thus there are languages who require space complexity bigger than $O(n)$, and therefore are not solveable by linear bounded automata but can be solved by a ($O(f)$ space) turing machine.
> 2 votes

---
Tags: turing-machines, automata, context-sensitive, linear-bounded-automata
---