title: Intersection of regular and not regular

text:
# Question
Title: Intersection of regular and not regular
$L\_1=\\{a^n\mid n\ge1\\}$ is regular and $L\_2=\\{a^{n^2}\mid n\ge1\\}$ is non-regular. We know that $L\_1\cap L\_2$ is regular but, here $L\_1\cap L\_2=L\_2$; and $L\_2$ is not regular. How is this possible?

# Answer
To expand a bit on David's answer, you are confusing between the next two claims.

**Claim 1** if $L\_1,L\_2$ are regular, then $L\_1 \cap L\_2$ is also regular.
(proof: construct the product DFA, e.g., here)

**Claim 2** if $L\_1$ is regular, but $L\_2$ is not, then $L\_1\cap L\_2$ can be either regular or not-regular.
(proof: Let $L\_2$ be some non-regular language. If $L\_1=\Sigma^\*$ then $L\_1\cap L\_2=L\_2$ which is non-regular by its definition. On the other hand, if $L\_1=\emptyset$ then $L\_1\cap L\_2=L\_1=\emptyset$ which *is* regular)
> 3 votes

# Answer
If $L$ and $L'$ are both regular then, yes, $L\cap L'$ is regular. But, if $L'$ is not regular, then all the bets are off, as your example shows.
> 1 votes

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


# Question
Title: Automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$
How can I produce an automaton accepting $\\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\\}$? I am essentially confused about exactly what the $2i$ and $2k$ mean. Does that mean that the automaton only accepts strings where the number of $a$'s and $b$'s are multiples of $2$ and there is one occurrence of $b$ between $a$ and $c$? Any help is greatly appreciated, thanks.

# Answer
The language $L=\\{a^{2i}bc^{2k} \mid i,k \in\mathbb{N}\\}$ contins all the string of the form $aaa..abcc..c$ such that the number of $a$'s is even and the number of $c$'s is even (possibly different than the number of $a$'s).

To see it, choose $i,k$, say $i=1,k=2$ now $a^{2i}$ means $2i$ times $a$, so we get $aabcccc$ for the above $i,k$. For any possible $i$ and $k$ we get exactly all the strings with even number of $a$s, then a $b$, then an even number of $c$'s.
> 0 votes

# Answer
Yes, it means exactly that. $i$ and $k$ are arbitrary natural numbers, so $2i$ and $2k$ are arbitrary even natural numbers.
> 0 votes

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


# Question
Title: Is finding the smallest collection of subsets so that the number of elements among the subsets is <= the number of subsets NP-hard?
Given a collection of non-empty subsets of $\\{1,2,\ldots,N\\}$ ($N$ not fixed), the problem is to find the smallest non-empty collection of subsets so that the number of distinct elements appearing among the union of subsets is less than or equal to the number of subsets chosen. This seems like an NP-hard problem but I can't prove it. Any help?

# Answer
> 2 votes
This is too long for a comment but is not really a full answer.

Let's re-formulate the problem setting slightly as a bipartite graph $G$, with $\\{1,2,\ldots,N\\} = X$ as one set of vertices and the collection of subsets (say, $Y$) as the other set of vertices, with an edge between $i \in X$ and $J \in Y$ iff $i \in J$. For any set of vertices $W$ in $Y$, define $N(W)$ to be the neighborhood of $W$ in $G$ -- namely, the set of all vertices in $X$ that are adjacent to at least one vertex in $W$.

Then, the problem asks to find a minimal subset $W \subseteq Y$ such that $|N(W)| \leq |W|$. However, if we change the criterion slightly to $|N(W)| \lt |W|$, we find that such a subset exists if and only if there does not exist a matching between $X$ and $Y$ that covers $Y$, for it is exactly equivalent to Hall's Marriage Theorem.

Since such matchings are findable in polynomial time (e.g.: via Hopcroft-Karp), I think this version of the problem should probably be relatively easy but I'd have to do some more work to figure out if and how the standard algorithms for bipartite matching expose these deficient sets and whether or not *minimal* deficient sets can also be obtained easily. Furthermore, I can't tell right away how much harder the original version of the problem (which allows $|N(W)| = |W|$) is than this modified version.

# Answer
> 0 votes
You can reduce from Clique. Create a set for each vertex, each with n-1 elements corresponding to the n-1 other vertices, with the element for v in set u being equal to the element for u in set v (but not equal to any other element) if {u, v} is an edge, and a unique element otherwise. Then we can choose k strings that together contain k(n-k) + k(k-1)/2 elements if an only if there is a clique of size k. We then only need to add the correct number of one-element sets containing the same element such that the number of sets selected and elements collected is the same.

---
Tags: np-hard
---


# Question
Title: Constructing a random Hamiltonian Cycle (Secret Santa)
I was programming a little Secret Santa tool for my extended family's gift exchange. We had a few constraints:

* No recipients within the immediate family
* Nobody should get who they got last year
* The whole thing should be a cycle (Sandy gives to George, George to Tom, Tom to Susan, Susan back to Sandy)

So at this point, I think what I'm looking at is a directed graph, and I want to find a random ~~Eulerian~~ Hamiltonian Cycle.

Naively, I would say:

* Start with a random vertex
* Randomly choose a neighbour that hasn't been hit yet
* Recurse until you reach a cycle (solution) or find a node with no neighbours (backtrack and choose a different random neighbour)

But this doesn't give all permutations equal weight. Flipping a coin to choose the first neighbour could greatly limit subsequent possibilities, like in the graph below:

```
A -> [B, C]
B -> [C, D, E]
C -> [A, D, E]
D -> [A, B, E]
E -> [A, B]

```

If in the example above I start with A, I could choose B or C at 50% probability each.

* If I choose B, the only cycle is 1) `A->B->C->D->E->A`
* If I choose C, there are multiple paths: 2) `A->C->D->B->E->A`, 3) `A->C->E->B->D->A`

So with my naive approach, I would choose cycle 1 50% of the time, and 2 and 3 25% of the time each.

The route I ended up taking this year was to shuffle all of the vertices, and then check if it was in fact an admissable cycle. But this gets less efficient as there are more constraints.

Is there an efficient way to generate a random Hamiltonian Cycle where each cycle has equal probability?

## Edit:

By "efficient" I mean more efficient in runtime and/or space than generating the set of every Hamiltonian Cycle, and then choosing one at random.

# Answer
You can do slightly better on space by using reservoir sampling. The overall approach we take is the same as suggested by @jnalanko, and it only works well for small enough $n$. We generate each permutation of $\\{1,\ldots,n\\}$, but only keep one solution $X$ stored. At the end, $X$ will satisfy the property of being sampled uniformly at random from the set of all solutions. This is fairly straightforward to show by induction.

This is easy to describe in pseudocode:

```
S := {1,...,n}
i := 1
X := {}
while(not visited each permutation of S)
  if S is a valid solution
    set X to S with probability 1/i
    i := i + 1
  S := next permutation of S

```
> 3 votes

# Answer
I'm not sure what you mean by an efficient algorithm, but the problem of finding any Hamiltonian path is NP-complete, which means that it is very unlikely that a polynomial time algorithm exists for your problem.

If the number of people $n$ is small, say less than 10, then it is feasible to solve the problem by brute force. Generate all $n!$ permutations of the people. Remove all permutations from the list that do not form a Hamiltonian cycle and do not satisfy your additional constraints. The time and space complexity is $O(n! n)$. Then pick a random permutation from the list.
> 4 votes

# Answer
**Observations:**

Consider the trivially simple ConstraintMap:

```
constraints =  fromList [ ("a", ["b","d"])
                        , ("b", ["a","c","d"])
                        , ("c", ["a"])
                        , ("d", ["b","c"])
                        ]

```

There are only two Hamiltonian cycles satisfying the ConstraintMap:

```
"c" -> "a"     "c" -> "a"
 ^      |  and  ^      |
 |      v       |      v
"d" <- "b"     "b" <- "d"

```

There are $4! = 24$ permutations but only $2$ are valid Hamiltonian cycle solutions. Therefore we should devise an algorithm which only uses the significantly smaller search space of valid Hamiltonian cycles!

*We can do this by viewing all the possible constructions as a **tree***

We select an arbitrary element as the root node (*WLOG* `"a"`). Then the branches of this element are it's recipients elements, minus any recipient element in it's parental line. We apply this structure recursively to depth $d = length(\\;constraints\\;)$ to construct all valid Hamiltonian cycles.

```
        "a"
      /     \
   "b"       "d"   -- Note no "a" in "b"'s children because "a" is "b"'s parent
  / | \     /   \  -- The same rules of excluding the parental line follows for all nodes!
"c" X "d" "c"   "b"
 |   / |   |   / | \
 X  X "c"  X  X "c" X
       ^         ^
       +---------+--- Valid terminal nodes because "c" maps to "a"

```

As you can see, we have in fact constructed all $2$ valid Hamiltonian cycles:

```
        "a"
      /     \
   "b"       "d"
      \         \
      "d"       "b"
       |         |
      "c"       "c"

```

We can select a single uniformly random valid Hamiltonian cycle by preforming a depth limited search over a uniformly randomized search space. We do this in a manor similar to the tree construction above.

**Algorithm:**

* We first fix an arbitrary element as the root node.
* We then populate the branches of this element with the possible recipients elements, minus any recipient element in it's parental line.
* We then randomly permute the branches of the element and begin a depth limited search on the first element in the permutation.
* We apply this recursively to depth $d = length(\\;constraints\\;)$.
* We return the first path of depth $d$ which satisfies the Hamiltonian constraints.

This runs in $\mathcal{O}(n)$ memory and $\Omega(n)$ & $\mathcal{O}(n!)$ time.

*Best Case Complexity:*

* Linear time to generate a valid solution in the first few attempts

*Worst Case Complexity:*

* Factorial time to generate all possible solutions and determine none satisfy constraints

*Average Case Complexity:*

* I don't know, but for my test battery of real world familial constraints with arrangement histories my Haskell implementation returns a valid cycle instantaneously ($time\\;\<\\;\frac{1}{20}\\;sec$).

**Implementation:**

My Haskell implementation is viewable here:

**Imperative Pseudocode:**

```
List<String> selectCyclicArrangement(Map<String,Set<String>> constraints) {
  root = chooseRandom(keys(constraints));
  height = length(constraints);
  return lazySelectArrangement( root
                              , height
                              , constraints
                              , constraints
                              , 1
                              , root);
}

List<String>? lazySelectArrangement(String root
                                    , int height
                                    , Map<String, Set<String>> originalConstraints
                                    , Map<String, Set<String>> constraints
                                    , int depth
                                    , String key) {
  if(depth == height) {
    if(originalConstraints[key].contains(root))
      return (new List<String>()).add(key);
    else
      return null;
  }
  branches = constraints[key];
  randomlyPermute(branches);
  if(branches.length == 0)
    return null;
  reducedConstraints = constraints.removeFromAll(key);
  result = null
  foreach(branch in branches) {
    result = lazySelectArrangement( root
                                  , height
                                  , originalConstraints
                                  , reducedConstraints
                                  , depth+1
                                  , branch);
    if(result != null)
      break;
  }
  if(result != null)
    return result.add(key);
  else
    return null;
}

```
> 0 votes

---
Tags: algorithms, graphs, randomized-algorithms, sampling, hamiltonian-path
---


title: Tournament graph

text:
# Question
Title: Tournament graph
I have to prove the following assertion: given a tournament graph with $n$ vertices, $n\geq 5$, there can be made an arrangement of the arcs such that between any two vertices exists at least one way of length at most $2$. Any ideas? Thank you!

# Answer
> 3 votes
You asked the question in a little vague way, so let me go over the notions you use. A tournament is a directed graph so that between every two vertices there exists one directed edges. Now, we can thing of the vertices as the numbers $1$, $2$, $\dots,n$. If we direct the edges from $i$ to $j$ whenever $i \< j$ then between any two vertices $i$ and $j$ where $i\<j$ there is one directed path (what you call "way") of length 1 and unless $j=i+1$ there is one or more paths of length 2. You can start with this example and think what edges to reverse to get the property you want.

(Another more advanced idea would be to look what is happening when you direct the edge between $i$ and $j$ at random. This should work to show what you want, but making this proof works for $n \ge 5$ in a natural way may be very challenging.)

I hope this is helpful.

---
Tags: graphs
---


# Question
Title: if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC?
if 3 SAT is reduced to A, as well as A is reduced to 3SAT, then is A in NPC ?

If yes then how can we generate a polynomial time verifier algorithm for the same ?

# Answer
A polynomial from $3SAT$ to $A$ shows that $A$ is $NP$-hard.

A polynomial reduction from $A$ to $3SAT$ shows that $A$ is in $NP$.

So, the answer is yes.

You can construct a polynomial verification algorithm for $A$ by first reducing $A$ to $3SAT$, and then using the verification algorithm for $3SAT$.
> 4 votes

---
Tags: np-complete
---


# Question
Title: Can the effective branching factor be negative?
I've implemented A\* algorithm in Python, after that I calculated **the effective branching factor $ B^\* $**

$$ T+1=1+B^\*+(B^\*)^2+\dots +(B^\*)^L$$

where $T$ is the number of expanded nodes.

My question is: is it possible in theory that the effective branching factor calculated is negative? And if not possible, is the solution to take only positive root?

# Answer
I don't know what *effective branching factor* is, but let me make a few comments anyway:

1. Presumably the effective branching factor is a parameter such that if the branching factor is constant, then it should equal the effective branching factor. It is some kind of average branching factor. Under this interpretation, a negative branching factor makes no sense.
2. You should focus on understanding what the effective branching factor is before calculating it. It is pointless to calculate something whose significance you don't understand. In real life you don't just "plug and chug" – you have a goal in mind. In this case, presumably the goal in mind is to estimate how difficult the problem is – the larger the effective branching factor is, the shallower you can afford to explore the corresponding tree. You estimate the effective branching factor in order to estimate how deep you can go, and in order to compare the difficulty of various problems. The formula itself is less important.
3. As $B^\*$ increases monotonically from $0$ to infinity, so $1+B^\*+\cdots+(B^\*)^L$ increases from $1$ to infinity. Therefore your equation has a unique positive root (assuming $T \> 0$).
4. If $B^\*$ is "large", then you can estimate $1+\cdots+(B^\*)^L$ by just the last term $(B^\*)^L$, and so roughly speaking, $B^\* \approx T^{1/L}$. You can use this estimate as a basis for an iterative algorithm for calculating $B^\*$. The formula for the sum of a geometric series might be useful here.
> 3 votes

---
Tags: algorithms, artificial-intelligence, search-algorithms, branch-and-bound
---


title: Process scheduling confusion

text:
# Question
Title: Process scheduling confusion
I've got a confusion in the following section of a book. Here we taking about FCFS Scheduling. I feel that calculation table is incorrect in the book. Because P3 got completed at time 7, it's turnaround time should be 7-3 because third process arrival time is 3 so why they take 1? Remember turn around time = t(process completed)-t(process submitted)

For P4 it's 11-4 which I feel wrong again. Further for P5. So I want to know whether I'm wrong in understanding this all or the following is really a wrong calculation. Can someone please explain. Thanks! Check the fallowing links for book scan: https://i.stack.imgur.com/oGtva.jpg https://i.stack.imgur.com/mVP03.jpg

# Answer
> 1 votes
Converting Vor's comment into an answer:

the table looks incorrect.

Specifically: for P3, P4, P5 the table wrongly reports (completion time - processing time) instead of (completion time - arrival time).

---
Tags: scheduling
---


title: Separability of languages in RE

text:
# Question
Title: Separability of languages in RE
Say that a language $C$ is a *separator* for disjoint languages $A$ and $B$ if $A \subseteq C$ and $B \subseteq \bar{C}$.

I need to find two languages $A,B\in \mathrm{RE}$ that have no recursive separator $C$.

# Answer
Hint: Such sets $A,B$ (sans the requirement of recursive enumerability) are called *recursively inseparable*. According to Wikipedia "it is possible for $A$ and $B$ to be recursively inseparable, disjoint, and recursively enumerable", and Wikipedia might have relevant examples. (Even if not, now you know what term to look for in the vast sea of internet.)

Extra hint: Wikipedia does indeed provide two such examples:

1. $A$ is the set of encodings of TMs whose output is $0$, $B$ is the set of encodings of TMs whose output is $1$.
2. $A$ is the set of provable tautologies, $B$ is the set of refutable contradictions.
> 2 votes

# Answer
So, this is what I came up with:

$A=\left\\{ \left \langle M \right \rangle \ | \ \left \langle M \right \rangle \in\ L(M)\right\\}$

$B=\left\\{ \left \langle M \right \rangle \ | \ \left \langle M \right \rangle \notin\ L(M)\right\\}$

Now, let's assume there exists such a $C \in R$ s.t. $B \subseteq C$ and $A \subseteq \overline{C}$

Let $M\_C$ be a TM such that $L(M\_C)=C$.

Now, consider $M\_C(\left \langle M\_C \right \rangle)$

If $M\_C$ accepts, then $\left \langle M\_C \right \rangle \in A$ by A's definition. Because $A \subseteq \overline{C}$, we get that $\left \langle M\_C \right \rangle \notin C$ so $M\_C$ rejects.

On the other hand, if $M\_C$ rejects, then $\left \langle M\_C \right \rangle \in B$ so we get $\left \langle M\_C \right \rangle \in B \subseteq C$ so we get that $\left \langle M\_C \right \rangle \in C$, so $M\_C$ accepts.

Contradiction.
> 0 votes

---
Tags: computability
---


# Question
Title: Closed-form solution to recurrence equation
I have a recurrence relation of the form:

$f(0) = f(1) = 1, f(2) = 2$ (initial conditions).

$f(2n) = f(n+1) + f(n) + n$ for $n\>1$.

$f(2n+1) = f(n) + f(n-1) + 1$ for $n\>1$.

I have been able to simplify this equation a little bit, but I can't seem to find a closed-form solution (and neither can Mathematica with `RSolve`).

The first few values of $f(n)$ for $n = 0$ to $10$ are:

\[1, 1, 2, 3, 7, 4, 13, 6, 15, 11, 22\]

# Answer
Define $$ \begin{align\*} A(x) &= \frac{1}{x^2} + 1 + x + x^3, \\ B(x) &= \frac{x^3}{1-x^2} + \frac{x^2}{(1-x^2)^2} - \frac{1}{x^2} - 1 - 2x^2 \\ &= -\frac{1}{x^2} -1 - x^2 + \sum\_{m=0}^\infty x^{3+2m} + \sum\_{m=0}^\infty (2+m) x^{4+2m}. \end{align\*} $$ Then the generating series $F(x) = \sum\_{n=0}^\infty f(n) x^n$ satisfies the identity $$ F(x) = A(x) F(x^2) + B(x), $$ and so in some sense is given by the "formula" $$ F(x) = B(x) + A(x) B(x^2) + A(x) A(x^2) B(x^4) + A(x) A(x^2) A(x^4) B(x^8) + \cdots. $$ Unfortunately, this formula holds only in the sense of analytic continuation.

If we use Dirichlet series instead of ordinary generating series, we can probably compute the asymptotics of the sequence, along the lines described here. We leave that as an exercise to the reader.
> 3 votes

---
Tags: recurrence-relation
---


# Question
Title: How is Turing's Solution to the Halting Problem Not Simply "Failure By Design"?
I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer.

Here is my understanding of the Halting Problem:

> Let $M$ be the set of all Turing Machines.
>
> Let $i$ be the set of all inputs for all the Turing Machines in $M$.
>
> Let every element in $M$ be an element in $i$.
>
> Let the boolean values $true$ and $false$ be elements in $i$.
>
> Let $h(M,i)$ be a function that returns:
>
> * $true$ if and only if $M(i)$ halts
> * $false$ if and only if $M(i)$ does not halt
>
> Let $p(M)$ be a Turing Machine in $M$ that:
>
> * calls $h(M,M)$
> * halts if and only if $h(M,M)$ returns $false$
> * doesn't halt if and only if $h(M,M)$ returns $true$
>
> What happens when we call $p$ by passing $p$ to itself, $p(p)$?

The part I take issue with is implementing $p(M)$ so that it will not halt when $h(M,M)$ is $true$. My gut understands this approach as follows:

> Given a method $h()$ that works, and a method $p()$ designed to break $h()$, when we combine these methods to build a machine, that machine is broken.

I understand proof by contradiction is a valid approach to problem solving in formal logic, but this particular application of proof by contradiction seems flawed somehow.

What am I missing?

# Answer
> 11 votes
In what follows, I'll distinguish a machine $M$ from its description, denoting the description of $M$ by $\langle M\rangle$.

**Specification of the halt tester program, $H$**

> $H$ takes as input a pair $(\langle M\rangle, i)$, where $\langle M\rangle$ is the description of machine $M$, and $i$ is the input required by $M$.
>
> $H$ halts on **any** input pair $(\langle M\rangle, i)$ and returns the correct answer, namely:
>
> $H(\langle M\rangle, i)$ returns *true* if and only if $M$ halts on input $i$.

Now, assuming that there is such a machine $H$, we can use $H$ as a subroutine to construct a program $P$ as follows:

**Specification of the "perverse" program $P$**

> $P$ takes as input a description, $\langle M\rangle$, of a machine $M$.
>
> $P$ works correctly on **any** input $\langle M\rangle$, namely
>
> $P(\langle M\rangle)$ halts if and only if $M$ doesn't halt when given input $\langle M\rangle$.

The key to this argument is that *if* we can define a machine $H$ that satiffies the specification above, *then* we can build a machine $P$ that satisfies the second specification.

However, $P$, when given $\langle P\rangle$, exhibits impossible behavior,

$\qquad\qquad\qquad P(\langle P\rangle)$ halts if and only if $P(\langle P\rangle)$ doesn't halt.

So $P$ fails to meet its second requirement *on at least one input* and consequently it must be the case that $H$ cannot satisfy its requirement, so consequently we cannot make $H$ as specified.

Now $H$ might very well behave as specified on lots of inputs $(\langle M\rangle, i)$, but the point is that no halt tester can be built that works on **all** possible inputs.

# Answer
> 5 votes
You say:

> The part I take issue with is implementing $p(M)$ so that it will not halt when $h(M,M)$ is $true$. My gut understands this approach as follows:
>
> > Given a method $h()$ that works, and a method $p()$ designed to break $h()$, when we combine these methods to build a machine, that machine is broken.

The problem is that $p()$ is NOT designed to break $h()$, it is designed to **use** $h()$ -- and the usage is valid AND works! Except, it doesn't work when the input is $p()$, which proves that it doesn't work for **all** input.

Which means that $h()$ doesn't exist, at best $hminus()$ exists. It's not important that $p()$ is broken, what is important is that $h()$ doesn't exist.

If someone says they have written $h()$ you know they are mistaken or lying, if they want to work on creating $h()$ they are wasting your money, and so forth.

It establishes boundaries for what can and cannot be decided and the resources needed to do so.

If someone asks the question: can we determine if $p()$ halts given this input? The possible answers to that are: (a) yes — it does, (b) yes — it doesn’t (c) yes —- but we currently don’t know whether it does or doesn’t, and finally (d) no —- it is impossible to prove one way or the other.

Being able to quickly determine if the answer is (c) or (d) can be extremely useful. Remember Halting doesn’t say we can’t prove a specific $p()$ halts, Halting says we can’t have a general solution that will work for any input. Restrict either $p()$ or the input and the answer is quite frequently yes, that’s trivial.

# Answer
> 4 votes
Here is how a logician might approach the problem:

> $h(M,i)$ is the general case solution to the Halting Problem by definition.
>
> $(1)$ $h(M, i)$ *must* be able to determine whether or not $M$ halts for *all* $M$ ( i.e. an *unrestricted* set of $M$ ).
>
> $p(M)$ is an element in $M$.
>
> $(2)$ The following statements are equivalent:
>
> * $p(M)$ halts if and only if $h(M,M)$ returns $false$
> * $p(M)$ halts if and only if $p(M)$ doesn't halt
>
> $(3)$ Additionally, the following statements are equivalent:
>
> * $p(M)$ does not halt if and only if $h(M,M)$ returns $true$
> * $p(M)$ does not halt if and only if $p(M)$ halts
>
> Both $(2)$ and $(3)$ are contradictions.
>
> $h(M,i)$--*the general case solution to the Halting Problem*--cannot properly determine whether or not $p(M)$ halts, contradicting $(1)$. Therefore, the general case solution for the Halting Problem does not exist.

# Answer
> 3 votes
You shouldn't think about it in terms "brokenness" because there are pleny of perfectly legitimate programs that are designed to run forever, so running forever isn't necessarily "broken" behaviour.

`p` is the following simple algorithm, assuming that we already have a function `h(X,Y)` that returns `true` if machine `X` halts with input `Y` and returns `false` if it doesn't.

```
function p(M)
    if (h(M,M)) then
        while (true) do
        endwhile;
    return;

```

# Answer
> 3 votes
There is another proof by contradiction which you might like better, modelled after Berry's paradox. For a Turing machine $T$, let $N(T)$ be the output of the Turing machine when run on an empty tape, interpreted as a number; possibly $N(T)$ is undefined, if the machine never halts. Let $X\_n$ be the smallest number which cannot be produced by a Turing machine having at most $n$ states (such a number exists since there are finitely many such Turing machines). Suppose the halting problem were solvable. Then we could construct a Turing machine implementing the following algorithm:

1. Write the binary encoding of $n$ on the tape.
2. Go over all Turing machines having at most $n$ states, and for each of them that halt, calculate the number they compute.
3. Output the smallest number not appearing in step 2, which is $X\_n$.

The latter two stages can be implemented using a fixed Turing machine having $C$ states, and the first using an extra $\log\_2 n$ states. In total, we obtain a Turing machine having $\log\_2 n + C$ states that calculates $X\_n$. When $n$ is large enough, we reach a contradiction since $\log\_2 n + C \leq n$: on the one hand, $X\_n$ shouldn't be computable using a Turing machine having $n$ states; on the other, the machine above computes it using only $\log\_2 n + C \leq n$ states.

I heard this proof from Ran Raz.

# Answer
> 0 votes
The point of the halting problem is that it is impossible decide with an algorithm whether a given algorithm halts. Sure, you can give algorithms that will always halt (for all given input). However, you cannot decide this for all algorithms (for example $p$) with one algorithm, hence no algorithm $h$ can exist.

Given $p(p(A)))$, for a given algorithm $A$. If $h$ tells you $A$ halts, then the inner $p$ will not and the outer $p$ will return false . If $M$ does not halt the inner $p$ will not halt, but the outer $p$ will return false. Therefore, h cannot decide whether p will halt.

---
Tags: computability, halting-problem
---


# Question
Title: What do CS students face in their school exams?
To what degree does learning computer science require memorisation?

I know this depends on subjects and maybe things are different in each college but could someone put an example, e.g. In Xxx class, I had to answer this question or accomplished this task. I was/wasn't allowed to use books or notes.

I'm planning to enrol in a German college.

# Answer
Many computer science courses are project based, which means that they may not involve an exam at all or the exam will be worth only a small fraction of the final grade.

Exam questions that are purely about memorisation are not particularly good. You may encounter them in early years, but if you understand the material, the facts you are asked to memorise will be second nature to you.
> 1 votes

# Answer
No. Students are not asked to memorize lines of code. Memorization plays very little part in computer science degrees and computer science exams, at reputable institutions. Computer science is about much more than just programming or writing code. It's certainly not about memorizing lines of code.

So, you can rest comfortably. If you don't enjoy memorization, no problem! That's not a barrier to studying computer science.
> 2 votes

# Answer
As other answers have pointed out, *the amount of memorization required varies course to course and institution to institution.* I thought it would be helpful to provide some examples:

1) First midterm exam in the intro CS course at Princeton (this is usually the first exam CS students will take)

2) Final exam in the "Algorithms and Data Structures" course at Princeton. This is usually the second or third course a CS student will take.

Again, note these examples are only from a single institution in the US, but hopefully they provide a little insight into what CS exams are like at the undergrad level.

Note: **both of these exams are closed-notes, but in each case you were allowed to bring in a one-page "cheat sheet"**
> 2 votes

---
Tags: books
---


title: Heuristic for Tournament Scheduling

text:
# Question
Title: Heuristic for Tournament Scheduling
I am holding a bi-yearly tournament in my city, for which I want to write a program that gives me (nearly-)optimal pairings, and waiting time. The setup is as follows:

```
-Up to 42 groups of 2 persons each.
-3 groups will be paired to be one team
-a game is played between 2 teams (6 groups) and takes 20 minutes
-3 games will be played at the same time, there will be 12 rounds of 3 games
-Every group has the same amount of games
-after every game, the teams change
-What I want to optimize:
 minimize the amount of times a group gets put in a team with another group
 they have already played with (if they played against them it is ok)
 Bonus: Minimize the games a group has to wait until their next game
 (Since only 3 games can be played at once (so 6x3 = 18 groups), there are a lot of
 groups who have to wait for the next round of games.)

```

I want the program to give me the pairings of the groups and a schedule, if possible. I am giving the exact numbers, because if it can't be done in polynomial time, but the instance is small enough so exponential time does not matter too much, it is fine with me. The solution does not have to be optimal, but should be close.

What is a good algorithm or heuristic for my problem?

# Answer
I would suggest that you use an integer linear programming (ILP) solver or a SAT solver. This will probably be easier to formulate as ILP, so start there.

Let's check whether it is possible to ensure that no group ever gets teamed up with another group more than once. (We'll ignore the bonus condition.) Define a zero-or-one integer variable $x\_{g,t,r}$, with the intent that $x\_{g,t,r} = 1$ if group $g$ plays in team $t$ during round $r$, and $x\_{g,t,r} = 0$ otherwise. Now we can write some linear inequalities to capture the constraints on a valid solution:

* $0 \le x\_{g,t,r} \le 1$ ensures that each $x\_{g,t,r}$ is zero or one.
* $\sum\_g x\_{g,t,r} = 3$ ensures that exactly 3 groups are assigned to each team in each round.
* $\sum\_t x\_{g,t,r} \le 1$ ensures that no group is assigned to more than one team in any given round.
* Arbitrarily choose 36 groups to play 5 games; for those groups $g$, the linear equality $\sum\_{t,r} x\_{g,t,r} = 5$ ensures they will play 5 times. The other 6 groups will play 6 games; for them, enforce the linear inequality $\sum\_{t,r} x\_{g,t,r} = 6$.
* For each pair of groups $g,g'$, we enforce the linear inequality $x\_{g,t,r} + x\_{g',t,r} + x\_{g,t',r'} + x\_{g',t',r'} \le 3$ for all $t,r,t',r'$; this ensures that $g,g'$ never play together on the same team more than once.

Feed this system of inequalities to an ILP solver. If it has a feasible solution, then you have found a valid schedule for your tournament.

If it has no feasible solution, next check whether there's a feasible tournament where no group ever gets teamed up with any other group more than twice. Do this by replacing the last set of inequalities above with the following:

* For each pair of groups $g,g'$, we enforce the linear inequality $x\_{g,t,r} + x\_{g',t,r} + x\_{g,t',r'} + x\_{g',t',r'} + x\_{g,t'',r''} + x\_{g',t'',r''} \le 5$ for all $t,r,t',r',t'',r''$; this ensures that $g,g'$ never play together on the same team more than twice.

If this doesn't have a feasible solution, check whether there's a way to do it where no group ever gets teamed up with any other group more than three times. Do a linear search until you find the best solution.

Once you've found the best solution, now you can try to handle the bonus condition. Let's say you want to see whether there's a way to do it where no group gets teamed up with another group more than once, *and* (here's the bonus condition:) no group has to wait more than three games. The bonus condition is easy to enforce: for each $r$, simply add the linear inequality $\sum\_t x\_{g,t,r} + \sum\_{t'} x\_{g,t',r+1} + \sum\_{t''} x\_{g,t'',r+2} \ge 1$. Now test whether that's feasible. Of course, you can vary the waiting time (it doesn't have to be three games) to find the smallest waiting time possible.

I'd expect this might find a solution to your problem. Modern ILP solvers are surprisingly good at solving many ILP instances, if there is sufficient structure -- and in this case I suspect there might be enough structure that off-the-shelf ILP solvers might work well.

There are variations possible to speed up the ILP solver, but I suspect that this straightforward formulation might just work with no tweaks or optimizations needed. Give it a try! It shouldn't be too hard to test out and see if it works.
> 1 votes

# Answer
You want to choose 36 games so you have 216 group slots to fill from 42 groups so your limitation of 'Every group has the same amount of games' makes your problem infeasible because 216 is not divisible by 42.. In contrast many groupings/games seem to satisfy everything else so yes you have room for good or even optimal heuristics (if your infeasibility is lifted).

**More good news** is that looking at your problem this way i.e. slots to fill for your end result 'games' -which is your lowest dimension- probably makes the problem quite solvable. (If you looked at it from the all possible games perspective you would be looking at 65,889,460 possible games and their permutations/scheduling for your delay part)

**Even more good news**: your delay constraint is satisfied well by having each team wait the same amount rounds (minimum delay equals uniform delay - otherwise if a team waits less the wait is paid by another team maximizing the minimum delay) This gives us a fast heuristic - no need to run NP-hard exhastive solution on scheduleing/permutations.

**Even better news**: I am giving you a sort of heuristic to look at and solve this extremely fast! Looks like following this way you can get a lot of heuristics for your problem due to the large feasible space as outlined above so here is how you would go about it:

***So first let's lift the infeasibility*** by increasing your maximum number of groups to 54. You can just have 42 if you like as your requirement with the same algo but the equal games will never work as aforementioned.

***Now schedule your first 3 rounds*** (STEP=1) Groups 1 ...54 in a row meaning Game 1 is Team of Groups 1 2 and 3 vs 4 5 and 6, Game 2 is 7 6 and 8 vs 9 10 and 11 and so on until 54

***Now for STEP=2 schedule your next 3 rounds*** (why 3 at a time? because 3 is uniform delay ensures min max delay per group -see note above) Replace each Group by the Group + 3\*Group modulo 55 so looking at them in a row your Round 4 becomes 4 8 and 12 vs 16 20 and 24 and so on. For example Group 1 will play with 52 and 5 against 9 13 and 17

***Now for STEP=3 schedule your next 3 rounds*** Replace each Group + 3 * Group modulo 55 again (using group numbers from the previous round) For example your Round 7 has 16 32 and 48 vs 9 25 and 41 and Group 1 will play with 17 and 33 vs 49 10 and 26

***Now for STEP=4 schedule your final 3 rounds (12 rounds scheduled after this step)*** Do the same as above! So Round 10 has 9 18 and 27 vs 36 45 and 54. Group 1 will play with 10 and 19 vs 28 37 and 46

Of course the above is a loop so you can have as many rounds/groups as you want (or your numbers allow)

Now for sanity check that your constrains are all met by the scheduling heuristic provided (I only checked a few seems ok if not just change the modulo equation to include more variables STEP, Round, Game number etc - but again due to your large feasibility space this simple equation seems to also work, replace it just to get different schedules if you want more than one - although with one schedule you can schedule any tournament per note 2 below)

**NOTE 1:** I have the whole schedule here for now but it is probably too much to post.

**NOTE 2:** You can use the same schedule every time (just assign Group numbers to people and your new schedule is done each time)

**NOTE 3:** You seem to have room for even more groups or rounds if you want. To find out just continue the loop above until one of your constrains is not met.
> 0 votes

---
Tags: algorithms, polynomial-time, heuristics, scheduling
---


title: Shortest walk that covers $k$ nodes

text:
# Question
Title: Shortest walk that covers $k$ nodes
I have the following problem, I would like to know an efficient algorithm to solve it.

Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex $s$ and visits at least once every vertex of $K$ such that the distance is minimized.

There is **no** constraint on repeated nodes or edges in the walk found and is not guaranteed that the graph does not contain cycles. Some people have suggested me that it maybe NP-Hard due to a reduction from TSP, but there is no restriction of visit vertices exactly once, and is well known that TSP have that.

# Answer
> 1 votes
There is a simple reduction from Hamiltonian path. Suppose we are given a graph $G$ on $n$ vertices, and want to know whether it contains a Hamiltonian path. Adjoin a new vertex $s$ and connect it to all other vertices. The new graph $G'$ contains a walk of length (at most) $n$ starting at $s$ and covering all vertices if and only if the original graph $G$ contains a Hamiltonian path.

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


# Question
Title: Constructing non intersecting segments from distinct sets of points
Given 2 sets of points in the plane, $A$ and $B$, each of size $n$, I need to construct n line segments of the form ($a$–$b$) ($a$ in $A$, $b$ in $B$) such that none of them intersect.

The coordinates are comparable signed reals (no constraints here about that) and no 3 points are on the same line. There can be no segments sharing an end point because we need to construct $n$ pairs of points from $2n$ points, and there are no duplicate points.

I tried to sort each of the sets according to $x$ or $y$, and pair the appropriate points from each of the sorted sets, but I found a counterexample for that: a set of points whose sorted $x$ order was $(a\_1,b\_1,a\_2,b\_2)$ and sorted $y$ order was $(a\_2,a\_1,b\_1,b\_2)$.

# Answer
> 3 votes
Here is a quote from

> Kaneko, Atsushi, and Mikio Kano. "Discrete Geometry on Red and Blue Points in the Plane—A Survey." *Discrete and Computational Geometry*. Springer Berlin Heidelberg, 2003. 551-570.
>
> ---

---

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


# Question
Title: kth nearest vertex in a unweighted graph
Given an unweighted undirected graph $G$ with $10^5$ vertices and a subset $S$ of *special* vertices and an integer $k$, I want to find the $k$th nearest *special* vertex for each vertex. What algorithm can I use for this problem?

I'm actually thinking of algorithm for finding shortest paths from every vertex to all other vertices (like Floyd-Warshall algo, but in our case graph is unweighted and we need much better performance).

# Answer
> -1 votes
Letting $G = (V,E)$, and $|V| = N$, your problem essentially boils down to computing a portion of the shortest path tree for every vertex in $G \setminus S$, where the shortest path tree is truncated after the $k$th "special vertex."

You mention the Floyd-Warshall algorithm; however, that algorithm seems inappropriate here, since it's designed for *weighted* graphs, and only returns the lengths of the *shortest* paths between every pair of vertices.

A more natural approach might be to run BFS on every vertex in $G \setminus S$, halting when you reach the $k$th "special vertex." Since you'd be running BFS on every vertex in $G \setminus S$, your worst-case runtime would be $O(N' \cdot |E|)$, where $N' = N - |S|$. (I'm assuming you only want the $k$th nearest special vertex for the non-special vertices.)

You would be able to improve the performance slightly by caching the portions of the shortest-path trees you compute on each call of BFS, but those changes wouldn't shift the worst-case performance. I believe any known shortest-path algorithm will have complexity dependent on $|E|$, so I'm not sure that you could solve this problem in $O(NlogN).$

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


title: What is an ordered array?

text:
# Question
Title: What is an ordered array?
I am not able to find a clear explanation about Ordered Arrays. All I know is

> The array is 1-ordered it is in the usual order. (For the 1st must be less than the 2nd which in turn must be less than the 3rd which ... which must be less than the $n$th.)

But what is 2-ordered, 3-ordered... so on array?

Can someone guide me?

# Answer
> 0 votes
Borrowing the definition from Gaurang Tandon's question:

> An array $A\[1...n\]$ is said to be k-ordered if $$A\[i - k\] \leq A\[i\] \leq A\[i + k\]$$ for all $i$ such that $k \< i \leq n - k$.
>
> For example, the array $A = \[1, 4, 2, 6, 3, 7, 5, 8\]$ is 2 ordered.

I must also say that I've never seen a similar definition before (and I find it to be quite un-useful, but maybe it is important somewhere).

Another definition I have seen, extends the ordering to $k$-dimensional objects. For instance, with two dimensions:

> Given vectors $v=(v\_1,v\_2)$ and $u=(u\_1,u\_2)$, we say that $v\>u$ in a 2-ordering if
> $$v\_1 \> u\_1$$ or if $$ v\_1=u\_1 \text{ and } v\_2\>u\_2$$

Then, an array of vectors $v\[1...n\]$ is $2$-ordered if for every $i$, $v\[i\]\<v\[i+1\]$ via the above 2-ordering.

---
Tags: arrays
---


# Question
Title: Perform an operation on an array in O(n)
I'm required to perform the following operation on an array in O(n): P\[1..n\] is an array of positive integers. For each index 'i' in the array, I must find how many "cells" I can advance toward the beginning of the array until I reach an element whose value is greater than P\[i\], or reach the beginning of the array. The output of the function should be an array S\[1..n\] that contains these values.

For example, if:

```
 P = [ 4, 3, 6, 1, 2, 7, 9 ]

```

Then I must create this array:

```
 S = [ 1, 1, 3, 1, 2, 6, 7 ]

```

If I start at P\[3\] (=6), I can advance 3 cells until the beginning of the array, and therefore S\[3\] = 3; but if I start at P\[5\] (=2) I will advance only 2 cells and reach P\[3\] (=6 \> 2), so S\[5\] = 2.

Implementing such algorithm in O(n^2) is trivial, but I'm required to do so in O(n). I was hinted to use a stack.

# Answer
> 1 votes
Yes, you can perform this operation in $O(n)$ using a stack $\mathbb{S}$.

Before presenting the algorithm directly, I would like to give you an illustration using your example. It is not difficult for you to discover the basic idea on your own.

For your example, I give the states of the stack $\mathbb{S}$. Element $P\[i\]$ and its $S\[i\]$ are denoted by a pair `(P[i], S[i])`. The stack reads from left (bottom) to right (top).

*Notice which elements are popped before (when) $P\[i\]$ is pushed and how (and why) $S\[i\]$ is computed (described as `//` comments)*.

```
initialization: empty
P[0] = 4: (4,1)
P[1] = 3: (4,1), (3,1)
P[2] = 6: (6,3)    // 3 = 1 + 1 + 1
P[3] = 1: (6,3), (1,1)
P[4] = 2: (6,3), (2,2)  // 2 = 1 + 1
P[5] = 7: (7,6)   // 6 = 2 + 3 + 1
P[6] = 9: (9,7)   // 7 = 6 + 1

```

---

Here is the basic idea.

Stack $\mathbb{S}$ stores the elements $P\[i\]$ in array $P$ and its corresponding (already computed) $S\[i\]$.

*Initialization:* $\mathbb{S}=\emptyset; \quad \forall i: S\[i\]=0.$

For each element $P\[i\]$ in array $P$ in order:

1. $\textsf{Pop}$ the elements in stack $\mathbb{S}$, until it encounters a bigger one than $P\[i\]$. This step simulates the "advance toward" procedure. Meanwhile, compute the *sum* of the $s$ values of all elements that are popped by $P\[i\]$. Then, $S\[i\]$ for $P\[i\]$ equals $1$ plus this sum.
2. Then $\textsf{Push}$ $P\[i\]$ and its corresponding value $S\[i\]$ (just computed) into $\mathbb{S}$.

# Answer
> 1 votes
The following algorithm is $O(n)$ and uses a stack, the stack have the elements that have not found an answer to the problem, the idea is to iterate the array backwards and in each iteration while the i-th element is greater than the popped element from the stack then the i-th element is the closest greater element (to the left) to the element that was popped.

These are the steps:

First initialize the $P$ array with these values:

* $P\[0\]$ = 1 , thats it because it can't go further to the left.
* $P\[1\]$ = 1, no matter what if the first element is greater than the second one it is a move, if not it stills moving until reach to the beggining so in any case is *always* 1.
* $P\[i\] = i +1$, $\forall\_{1\<i\<n} $

That initialization is the "worst possible case" where there is no element greater to the left, in other words when a strictly increasing array is given as an input.

**The algorithm:**

1. Initialize the stack with the last element of the array.
2. Iterate backwards from the size-2 position, lets call the i-th element $current$.
3. While $current$ is greater than the popped element do the following: lets call the popped element "prev", $P\[prev.index\] = prev.index - i$. Here we are saying that $current$ is the closest element to the left greater than $prev$, so we put the number of steps is has to be moved, namely $prev.index - i$.
4. Now, if $prev$ is greater than $current$ it means that there has not been an answer to $prev$ so far, so we push it to the stack *again*.
5. After each iteration push $current$ to the stack, so its answer can be computed further in the algorithm.

**Correctness**

The loop invariant is that in the stack there is always the element for whom the algorithm hasn't found answer yet, so we keep pushing and if we found a element that is greater than the popped element we assign the answer as shown. In this sense we can say that this is a **Greedy Algorithm**, because it relies on as soon as we found a element greater than the popped element we put the answer "locally" without comparing further (Which of course would make it $O(n^2)$), is guaranteed that it is the correct answer because as we are going backwards the first time we see a element that is greater than the elements in the stack is going to correspond to number of times that the element has to be moved. If after the main loop of the algorithm is done there still elements in the stack it means that those elements are greater than all the elements to *their* left, and since we initialized $P$ with the "worst possible case", then the algorithm is correct.

**Running time**

For each element there is only 4 possible operations: The first insertion into the stack, pop the element in order to check if $current$ is greater than $prev$, put the element back if $prev$ \> $current$, and finally pop the element when the answer is found. That would give us $4n$ in the worst case and indeed that is $O(n)$.

**Last but not least, some python code**

```
def f(A):
stack = [ (A[len(A)-1],len(A)-1) ]

ans = [-1]*len(A)
ans[0] = 1
ans[1] = 1
i = 2
while i < len(ans):
    ans[i] = i + 1
    i = i + 1

i = len(A)-2
while i >=0:
    current = A[i]
    if len(stack) > 0:
        prev = stack.pop()
        while current > prev[0]:
            ans[prev[1]] = prev[1]-i
            if len(stack) > 0:
                prev = stack.pop()
            else:
                break

        if prev[0] > current:
            stack.append(prev)

    stack.append( (current, i) )
    i = i - 1

return ans

```

---
Tags: algorithms, arrays
---


title: Variant to the Vertex Cover Problem

text:
# Question
Title: Variant to the Vertex Cover Problem
Suppose that we are given an undirected graph, and we know that the maximum edges covered by $k$ vertices is $n$. If we let the greedy algorithm choose these $k$ vertices for us, I am told that it is capable of covering at least $n/2$ edges. Is there a way to prove this? If so, how should it be done?

Since the greedy algorithm removes the vertex with the maximum degree still left in the original graph (along with its incident edges) in each iteration, is it possible to find a connection between the minimal number of edges removed each time by the greedy algorithm to the optimal solution $n$?

I am truly clueless about how such a problem should be solved.

Hints or references are both welcome. Many thanks.

# Answer
You haven't fully specified the greedy algorithm, so let's assume that at each step you select a vertex covering the most new edges. In that case, this is the greedy algorithm for the more general problem of *Maximum Coverage*, whose approximation ratio is known to be roughly $1-1/e$, which is even larger than $1/2$. For a proof, see for example here. There is also a less classical proof that doesn't use elements at all, but only the monotonicity and submodularity properties of the coverage function (the function getting ass input a set of vertices and outputting the number of edges covered).

There are somewhat better algorithms that use the fact that each edge is covered by only two vertices. Examples are the LP-based algorithm and the non-oblivious local search algorithm. It is also possible that the greedy algorithm performs better in this case.
> 0 votes

---
Tags: algorithms, graph-algorithms
---


title: Size of framebuffer lookup table

text:
# Question
Title: Size of framebuffer lookup table
> If the frame buffer has 8 bits per pixel and 8 bits are allocated for each of the R, G, B components, what would be the size of the lookup table? a) 24 bytes b) 1024 bytes c) 768 bytes d) 256 bytes

I read about **Framebuffer** and what I understood is

"*It stores the color values (in case of color frame buffer) in indexed form. So if we have $8-bit$ color, then possible colors are* $2^8$\*So frame buffer would store color values for each pixel on screen and it's size would depend on screen resolution. Corresponding actual color values (or codes) would be stored in lookup table"

So, Lookup table would have $2^8 = 256$ entries, which is $256$ bytes, since each entry is of 8-bits = 1 byte.

But that is not the correct answer to above question. So, can anyone tell, **where am I going wrong ?**

Also, question says `frame buffer has 8-bit per pixel and 8-bits are allocated for each RGB` , This means for each pixel, frame buffer has $8,8,8,8$ bits allocated ?

# Answer
Assuming that by *framebuffer* they really mean *palette table*, then the table consists of 256 entries, each encoding an RGB color ("true color"). An RGB color takes 24 bits (3 bytes), 8 bits per color component, so in total we need 256$\times$3=768 bytes. That said, it may be easier to access the table if each color takes up an entire dword (32 bits, 4 bytes): for example, indexing could be for free in certain processors. In that case the table would take up 256$\times$4=1024 bytes. However, given the data at your disposal, the best guess would be 768 bytes.

Palette tables are most celebrated for their use in the popular GIF format. GIF uses a color palette consisting of 256 colors (in its most popular version), one possibly being reserved for "transparent", and the colors themselves are stored separately, usually as "true color" 24-bit values. The color table indeed uses 3 bytes per color, for a total of 768 bytes.
> 1 votes

---
Tags: memory-management
---


title: A Proof for NP-completeness

text:
# Question
Title: A Proof for NP-completeness
I think the following question is a mix of the Traveling Salesman Problem and the Subset-sum Problem, which makes it really hard (for me) to solve... .

The problem is stated as follows:

> There are a total of $n$ cities.
>
> The salesman must start his journey at a certain city, and return to that specific city at the end of his tour.
>
> Whenever the salesman reaches a city he hasn't been to, he can earn $r\_i$ dollars there. $r$ is a positive real number, and $i$ denotes the city number.
>
> The salesman can visit the same city more than once, but he cannot earn extra cash there.
>
> The salesman **does not** have to visit every city.
>
> By traveling from city $i$ to city $j$, a cost of $f\_{ij}$ is incurred **everytime**. $f\_{ij}$ is a positive real number. (This is like a negative weighted edge.)
>
> The problem asks whether there exists a route for the salesman to earn a net revenue of **at least** $k$ dollars.

This problem is clearly in NP, but how should I prove that it is NP-complete?

Since the salesman can wonder around the same cities, can I still map this question to the 3-SAT problem (like the subset-sum case) and prove that it is NPC?

Many thanks.

# Answer
**Hint.** Reduce Hamiltonian path to this problem. Use the rewards $r\_i$ to say that you have to visit each city, use the costs $f\_{i,j}$ to say that you can't use more than one edge per city and set the target $k$ to an appropriate value.
> 2 votes

---
Tags: complexity-theory, np-complete, graph-algorithms
---


# Question
Title: P2P and C/S, is it possible to determine which one is more bandwidth consuming?
In peer-to-peer (P2P) networks nodes are interconnected with each other. In client/server (C/S) networks clients talks to the server. If in a C/S network clients also want to talk with each other (such as in a multiplayer online game), then clients would have to communicate through the server.

Given these, is it possible determine which architecture is more bandwidth consuming?

# Answer
> 1 votes
One would say that P2P is better. But in reality, you cannot tell by the information you provided.

For instance, the bandwidth depends on queuing delays. Therefore, assume that one of the nodes in the P2P network has a very small queue (or overloaded), while our server is super powerful and its queue is hugly big ! Similarly, it depends on the latency of the nodes.

It depends on the bandwidth of the channels in the network. It depends on the round trip time. Therefore, P2P peers may be very far away from each other ! (China, Iran, Venzuela for example). etc ..

# Answer
> 0 votes
It depends on what you are measuring. A well-designed P2P network will spread the load among the members evenly, so the maximal load is just a fraction of the case in an C/S system (where all traffic goes to the server). In terms of total traffic, P2P uses more, as there is no guarantee that the answer to a question is at the node asked, and that node will have to find one that has the answer and get it before answering.

# Answer
> 0 votes
It is a general question so let's answer equally generally:

A P2P network structure once established will always have the potential to consume less bandwidth than a client-server approach. To see this just think that the client-server is one given structure (clients all send their data to the server and the server responds back). P2P can generally form any structure including the above if it thinks it is good for what it wants to accomplish. So it could always be at least as good as C/S or better.

On the other hand a P2P network will have some overhead to form and maintain its structure. So if its life is long enough (e.g. a file download is large enough) only then is the gain worth it.

Regarding bandwidth let's also think that consuming bandwidth is not a problem if enough bandwidth is available (the cables do not mind if data is passing through them or not). Consuming bandwidth is only a problem when there is not enough bandwidth for everyone. This brings us to a more important benefit of P2P. Client-server connections create bottlenecks as more traffic is concentrated the closer to the server we get. A P2P structure typically aims to avoid traffic concentration ponts, not to mention single point such as a server.

There are also more considerations than bandwidth you should take into account when selecting a P2P or C/S model.

---
Tags: computer-networks, network-topology
---


# Question
Title: Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol?
Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol? Say f is the transition function, why does having

```
f(qi, 1, 0)       -> (qj, 0)
f(qi, epsilon, 0) -> (qj, 0)

```

cause nondeterminism?

I would understand that if I had

```
f(qi, 1, 0) -> (qj, 0)
f(qi, 1, 0) -> (qz, 0)

```

it would cause nondeterminism, because looking at the same input symbol I can choose to move to either qj or qz, that's nondeterminism to me. However the former doesn't make sense at all... This is what Michael Sipser says in his book.

# Answer
> 3 votes
Nondeterminism, means the machine has a choice. In both your examples, it indeed has a choice.

Let's assume the stack has an 1 on its top, and the next input symbol is 0. The PDA can *choose* whether to take the transition $f(q\_i,1,0)\to(q\_i,0)$ or $f(q\_i,\epsilon,0)\to(q\_i,0)$. Note that the effect is different: in the first it deletes the 1 in the stack and puts a 0 instead of it. In the second it adds a 0 on top of the 1 without removing it.

Therefore, there are two (different) paths the machine can go from this points, hence the nondeterminism.

Just to clarify: the definition for Deterministic-PDA is clear-cut: at any moment, and for any input/stack/state configuration there is only **one** possible transition. If this is not the case, the PDA is non-deterministic *even if multiple transitions lead to the same configuration*. It's just a matter of definition.

However, in the question above, the two transitions may actually lead to different configurations, which makes the nondeterminism even more clear.

---
Tags: finite-automata, pushdown-automata, nondeterminism
---


# Question
Title: What do I need to study in order to understand and design a programming language?
What do I need to read in in order to :

1. understand the specs of an already made programming language
2. Design a programming language
3. Design a compiler and assembler for that language
4. make an architecture of a processor

# Answer
I know you mean, it is not an easy task, yet you can do it.

**For point 1:** You can do that by:

1. Quick reading the documentation of the programming language you want to learn.
2. Practice on the topics you want to get the maximum benefits of.
3. Mainly all of the programming languages have a lot of common specs, you can map the language you want to learn to a language you already learned.
4. From my experience, each programming language has its own uniqueness, the thing it is adding. I think you should focus on that spec of the language. Like C and pointers, Ruby on Rails and Meta Programming, ... etc

**For point 2:** Designing a programming language is not an easy task, you need to consider what your programming language will add, are what it adds already there in another programming language? Why people will use it? What is the problem your programming language will solve?.
If you answered all of the above questions, then let's move on to see wow are you going to make it.
There are a lot of online courses about programming language design.

1. First of all the structure; will it use compiler or interpreter, will it have a virtual machine or it will will run natively on the OS, what will be the steps of building and running the code
2. Does the programming language will be high level or low level or middle?
3. Does it will be OOP or Structural programming, or a good mux like Scala?
4. What will be the syntax like? How to terminate the line?
5. Handling call by reference and call by value
6. A lot of aspects remaining, honestly I don't know all of them...

**For point 3:** If you want to design a compiler, then there is a whole life out there, this science already settled, you will have to make the grammar tree and the dependency. You studied Assembler before, there is another course for compiler, it is basicly the same concept but it is harder because you will have grammar here.
Many many courses are out there specially for the purpose you want, just search with keyword compilers.

**For point 4:** This point is out of the above scope, it is on the other side, if you are concerned about creating a new programming language, then you shouldn't worry about the processor architecture unless your language is a low level programming language. Mainly, it is another track if you want to design your own architecture, there are many steps to design a processor's architecture:

1. Thinking about the design itself, is it will be dual or single core, down this processes based on pipeline, ...etc.
2. Drawing the design.
3. Writing the design with one of hardware describing language like VHDL, Verilog.
4. Synthes the design and make sure it will work
5. Simulation phase
6. Deploy the design on FPGA (There may be other boards...) This will allow you to test your design on hardware too not only software tests.
7. You are done and you can start making the specific hardware for your design
8. There are courses for this matter, you should first study architecture courses, then studying VLSI, people are pursuing master degree in the VLSI and how to design the architecture

I am not an expert in all of that, but I answered it from my humbled experiences, I hope I benefits you, if I have anything more, I will edit the answer to add it isA.
Please feel free to discuss anything with me.
> 1 votes

# Answer
I do not understand what is your intended meaning in "*understand the specs of an already made programming language*". There are always many things to be understood in a complex entity, and any understanding must be related to a purpose.

If your purpose is just to understand how to program with this language, understanding how it is implemented is not, and should not be your problem. Certainly not at first. What you have to understand is the high level concepts used in the language, and that may depend very much on the language. You need to understand the style of programming the language is promoting. All that comes to some extent with the manuals and tutorials. But some concepts may require advanced knowledge, some of which may be general, and some which may be very specific. What you should learn will be clear from the manuals and tutorials.

If you want general knowledge on language architecture, on the role of syntax and semantics, on the main techniques useful to write compilers and interpreters, you should get a book on compiler writing. Many will do. The most popular is probably the Dragon Book in one of its successive edition.

To design a programming language, there is no specific study, other than a good understanding of the structure and concepts used generally in programming languages (see above). A good knowledge of logic and mathematical style cannot hurt. Knowing many programming languages with preferably very different styles is probably a prerequisite. The hard part is knowing why you want to do it, and what for. A language is a vehicle for communication. Hence, if you are alone using it you are wasting your time (unless it is a proof of concept, which is usually related to some advanced theoretical work). You have to have a purpose for your language, and an idea that it is better for that purpose than other languages that may already exist. If you still have to read what is useful for designing it (other than general knowledge - see above), you are not ripe for designing one. The needed knowledge must precede the intent to design a language. It must be the expression of a need, before it becomes a will. Actually this is often true of creative activity.

Languages are not necessarily general purpose languages. They may be very useful without having Turing power. A language must be thought to express some concepts in a given domain of discourse. For example, languages like HTML, or TeX. are intended to express textual layout of documents. They can be very sophisticated, but not intended to write graph algorithms or matrix processing. Other languages may appear like weak algorithmic languages because they have been designed to posses specific properties that more general languages will not have, such as automatic analysis of their computational characteristics. Some languages may use specific kinds of parallel processing that are easier to analyze and optimize.\`Some of these specific languages, or some features of more general languages require high mathematical sophistication in specific domains. Naming them here would just be name dropping.

Regarding processor architecture, I cannot help you. It is largely a different topic, though it does matter for some aspects of compiling, and I am not competent.

If you want to see an interpreter written in half a page, that implement a general purpose programming language that was actually used a lot (in more sophisticated versions, to be honest), look for the Lisp 1.5 interpreter. It is somewhere in this old book.
> 1 votes

---
Tags: programming-languages, compilers, semantics, interpreters, syntax
---


title: Using all the entropy in an biased bit

text:
# Question
Title: Using all the entropy in an biased bit
Suppose we have $n$ bits of random-looking data, and we want to encode it in such a way that instead of 1/2 the bits being 1's, we have (say) 3/4 the bits being 1's. The entropy of each bit in the new encoding is $-0.75\log\_2(0.75)-0.25\log\_2(0.25)\approx 0.81$, so we should be able to do it in about $1.23n$ bits.

(By 3/4 the bits being 1's, I mean that each bit should be indistinguishable from an event that happens with probability 3/4; as opposed to a long block of unbiased random bits followed by an equal length block of 1's.)

We could try, for each bit, put the next bit of the original data with probability 1/2, and put a 1 with probability 1/2. Then somehow include extra information about which bits encode the original data, and which are filler. But this reqiures at least $2n$ bits, well above the theoretical minimum. So how can the minimum actually be achieved?

# Answer
Suppose you want exactly $3/4$ of the bits to be 1. If the encoded vector is of length $m$, it can be identified as a subset of $\\{1,\ldots,m\\}$ of size $(3/4)m$, of which there are $\binom{m}{(3/4)m}$. If $\binom{m}{(3/4)m} \geq 2^n$ then you can encode every $n$-bit string as such a subset using the technique of *binomial encoding*. Since $\binom{m}{(3/4)m} \approx 2^{mh(3/4)}$, this works as long as $m \gtrsim n/h(3/4) \approx 1.23n$.

Binomial encoding relies on Pascal's identity $$ \binom{a}{b} = \binom{a-1}{b-1} + \binom{a-1}{b}. $$ To encode a number $x$ in the range $\[0,\binom{a}{b})$, we act as follows:

1. If $x \< \binom{a-1}{b-1}$ then we recursively encode $x$ as a subset $S$ of $\\{1,\ldots,a-1\\}$ of size $b-1$, and output $S \cup \\{a\\}$.
2. If $x \geq \binom{a-1}{b-1}$ then we recursively encode $x - \binom{a-1}{b-1}$ as a subset $S$ of $\\{1,\ldots,a-1\\}$ of size $b$, and output $S$.

The procedure can easily be reversed (exercise).
> 1 votes

---
Tags: probability-theory, randomized-algorithms, information-theory, entropy
---


# Question
Title: Computing FOLLOW sets for LL(1) grammar. Stuck on question
> Calculate the FOLLOW sets for all the non terminals:
>
> $S \rightarrow bEx \mid Db \mid b \mid F$
>
> $D \rightarrow EDc \mid Y$
>
> $E \rightarrow dED \mid dDY$
>
> $Y \rightarrow ab \mid aDx \mid \varepsilon$

So I know that:

FOLLOW($S$) = $\\{\\$\\}$ since it doesn't appear anywhere

FOLLOW($D$) = $\\{b, a, x, c\\}$, since it is followed by terminal $b$ in $S$, $c$ in $D$, FIRST($Y$) in $E$ which is $\\{a\\}$ ($\varepsilon$ not included), and $x$ in $Y$

FOLLOW($E$) = $\\{x, c, a, d\\}$, since it is followed by terminal $x$ in $S$, FIRST($D$) in $D$ which is $\\{a, d, c\\}$

but how do I calculate FOLLOW($Y$)? It isn't followed by anything. I'm guessing since it's at the end of $D$ and $E$ its the union of their follow sets including $\\$$ since there's an $\varepsilon$?

Have been stuck on this for a while, any help is HIGHLY appreciated. Thanks in advance for any input

# Answer
> 0 votes
For posterity, the FOLLOW set of any non-terminal can be computed with the following rules (an example using these rules can be found here):

1. $\\$$ (the end of input symbol) is in FOLLOW($S$) where $S$ is the start symbol.
2. If $A \rightarrow \alpha B\beta$, then everything in FIRST($\beta$) except $\varepsilon$ is in FOLLOW($B$).
3. If we have $A \rightarrow \alpha B\beta$ as before *and* $\varepsilon$ is in FIRST($\beta$), then all of FOLLOW($A$) is in FOLLOW($B$).
4. If $A \rightarrow \alpha B$, then all of FOLLOW($A$) is in FOLLOW($B$).

So for $Y$, we need to apply rule $4$ (as you correctly guessed), so FOLLOW($Y$) $=$ FOLLOW($D$) $\cup$ FOLLOW($E$) $= \\{a,b,c,d,x\\}$ (I'm trusting your working on the two follow sets).

# Answer
> 1 votes
> $FOLLOW\ (Y) = FOLLOW\ (D)$
>
> $FOLLOW\ (Y) = FOLLOW\ (E)$

A general Rule of thumb is, for any grammar

1. S -\> XAB
2. A -\> BC
3. X -\> Bt

$ Follow (B) = Follow (S) $ (Since there isn't anything after B in Production-1)

$Follow (B) = First (C) $ (Since C follows B in Production-2 and is a non-terminal)

$Follow (B) = t $ (since it follows B in Production-3 and is a terminal)

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Proving Infinite Turing Machine Language (with finite subset) is Recursively Enumerable
I'm trying to answer this question:

> Let $S$ be the strings $\langle P \rangle$ accepted by the Turing Machine $P$ with input alphabet $\\{a,b\\}$, where $P$ accepts an infinite number of strings beginning with $a$ and a finite number of strings beginning with $b$.
>
> 1. Is $P$ RE?
> 2. Is $P$ co-RE?

# Answer
Regarding your first question, a reduction from the halting problem only shows that a problem is *hard*, not that it's *easy*. If the halting problem reduces to some problem $P$, then you know that $P$ isn't co-computably enumerable. So if you manage to reduce the halting problem to $L$, then this shows that $L$ is *not* co-computably enumerable. Perhaps that can inform your guess on the answer.

Regarding your second question, if you show that $L$ is c.e. but not computable, then indeed it follows directly that $L$ is not co-c.e. This is because a language that is both c.e. and co-c.e. is computable.

Let me give you a hint. Every Turing machine can be modified so that it accepts only strings beginning with 0: the new machine accepts $0x$ iff the old machine accepts $x$. Such a Turing machine belongs to $L$ iff it accepts infinitely many strings. Similarly, a machine which only accepts strings beginning with 1 belongs to $L$ iff it accepts finitely many strings.
> 2 votes

---
Tags: computability, turing-machines, semi-decidability
---


# Question
Title: Can Shortest Job First Scheduling be subject to convoy effect?
Look at the below table for example :

Look at the **Non-Preemptive SJF** table
Suppose if the ***burst time*** of process $P\_1$ was a very large number compared to $7$, the processes $P\_3,P\_2$ and $P\_4$ have to wait for a large amount of time till $P\_1$ frees the CPU.
No book or article that I've read mentions of SJF being a subject to convoy effect?
Why not?

# Answer
> 2 votes
I think you're not using the same terminology as the books and articles you're reading. Non-preemptive schedulers suffer from *priority inversion*, not *convoy effects*.

Most scheduling disciplines (FIFO, SJF, LJF, Nearest-deadline-first, ...) can be reframed as *highest priority first* schedulers, where what changes from discipline to discipline is the priorities assigned to the jobs. So first-in-first-out (FIFO) scheduling assigns priorities according to their order of arrival. Shortest-job-first (SJF) assigns priorities according to the burst time. In preemptive shortest-job-first the scheduler is always running the job with the highest priority. In non-preemptive shortest-job-first scheduling if a short job arrives after a longer job already starts, then the scheduler will be running the lower priority job instead of the high priority job for a while.

A convoy effect is a different problem where jobs that need many different kinds of service get clumped up together because of decisions you have made elsewhere in the system. It applies to things like schedulers that deal with jobs that have more than one burst (separated by time when those jobs are waiting for i/o, or when jobs are waiting for a lock). For the lock case there's a wikipedia article: http://en.wikipedia.org/wiki/Lock\_convoy.

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


# Question
Title: Find a quarrel-free seating order with a greedy algorithm
I'm revising for an Algorithms exam and looking at a sample question it says :

> A group of n teenagers $t\_1, \dots, t\_n$ are to sit in a single row of n chairs watching a particulary boring comedy movie. Some teenagers quarrel with each other all the time. The Problem is to devise a seating arrangement for the group in such a way that teenagers sat next to each other do not quarrel.
>
> Propose a solution to this problem using the Greedy approach. Estimate the complexity of the resulting algorithm.

In lectures for greedy problems we've only covered Knapsack Problems so Next Fit/Best Fit for Bin Packing. I can't seem to understand how these methods have any relevance to coming up with a solution for the question.

Obviously I don't expect anyone to answer this, since I've not even made an attempt. But in honesty I don't know where to start. If you guys could give me some sort of hints or just general advice because I'm pretty stranded at the minute.

# Answer
I don't know if i understood your exercise. But pick a arrangement with n students in n positions is a permutation, so there are n! possible arrangements. So, it's look like a Hamiltonian path problem, where each student is a graph's vertex and there's an edge i,j if the student i can sit next to student j, with no quarrel. If you can find some Hamiltonian path, you have a arrangement. For greedy algorithm you can propose a heuristic that visit first the vertex with low degree (number of edges incident to the vertex), meaning that the most annoying student will be chosen to sit on the first place of the row.
> 0 votes

---
Tags: algorithms, optimization, greedy-algorithms
---


# Question
Title: Introduction to Linear Optimization: Driving the artificial variables out of the basis (case: no entries in the $j$-row are nonzero)
Reading the book Introduction to Linear Optimization by Bertsimas and Tsiklisis, I've come across the following subject: **Driving the artificial variables out of the basis**.

The description is as follows: suppose an artificial variable $x\_{B(j)}$ is in the basis, then examining the $j$-row of the simplex tableau there are two cases:

Either the $j$-row of $B^{-1}A$ contains a nonzero element (I understand this case !), otherwise all elements in the row are equal to $0$, which imply that the rows of $A$ are linearly independent and it is shown that the constraint $a\_j x = b\_j$ is redundant.

The book then suggest we delete the $j$-row of the simplex tableau and continue from there. **Why is this possible** ? By deleting the $j$-row of the tableau, we remove the $j$-basic variable from the basis. Also, deleting the $j$-row of the simplex tableau corresponds to deleting the $j$-row of $A$, form the basis of the basic variables, not including the $j$'th basic variable (now one dimension smaller), and then forming the simplex tableau corresponding to these ?

Now, how can we be sure the vectors corresponding to the basic variables excluding the $j$'th are **linearly independent** and form a basis ($j$-element is removed from these vectors) ? How do I know the simplex tableau with the $j$-row removed is actually a real simplex tableau and what vectors and basis matrix does it correspond to ?

Please give me advice and tell me whether I'm wrong and what to do, I've been really thinking over this, but haven't come to a conclusion.

# Answer
The Proof is on Theorem 2.5 of the section 2.3. If you consider the polyhedron with artificial variables and redundant equality constraints as P and original with no artificial variables and no redundant equality constraints as Q. As you may see, they assumes that the l(th) basic variable is an artificial variable, so remove it will not affect original polyhedron. On the Example 3.8, the last tableau with artificial variables shows a case where a row becomes zero. If this happens with non artificial variable we have a degeneracy case.
> 2 votes

---
Tags: optimization, linear-programming
---


# Question
Title: 2's complement addition with ZF/Carry/Overflow
> Consider addition of two numbers when CPU uses $2's$ complement form: $$ 1\ 1\ 0\ 0\ 0\ 0\ 1\ 1\\0\ 1\ 0\ 0\ 1\ 1\ 0\ 0\\\-------\\0\ 0\ 0\ 0\ 1\ 1\ 1\ 1\\\------- $$

$$Carry\ = 1,\ Overflow = 0, \ Zero Flag = 0$$

**My Reasoning:**

* Zero Flag isn't set because the *result isn't zero*
* Overflow isn't set because *Carry in = Carry out*

**However, the answer says that Zero Flag is set $(ZF = 1)$, Am I going wrong ?**

---

Note:

* Got ZF/Carry/Overflow info from Here

# Answer
> 0 votes
> However, the answer says that Zero Flag is set (ZF=1), Am I going wrong ?

No, you are correct. If the result is not zero, and in this case it is not, the zero flag is not set.

---
Tags: computer-architecture
---


# Question
Title: consider a base 16 adder how to modify the adder so that it can perform a base 8 addition?
Consider a base 16 adder. How can I modify the adder so that it can perform a base 8 addition?

I expect this question will appear in my exam tomorrow; if anyone can give me a hint or a solution, I'd be grateful. I've tried searching the net and my textbook to get some insight, but nothing is clicking.

my textbook digital design 5th morris mano

# Answer
> 2 votes
Assumptions/Statements: A base 16 adder: an adder that adds two 4-bit binary numbers I1 and I2 and outputs the 4-bit result R and a carry bit C

To use as a base 8 adder (as above) discard the Most Significant Bit from both I1 and I2 (i.e. ground/zero them). Now your inputs are base-8. From the output discard the Carry bit C it will always be zero. Your new Carry bit will be the Most Significant Bit from result R. Your new result will be the 3 least significant bits from R.

Please check Assumptions/Statements are in accordance to your book!

---
Tags: boolean-algebra
---


# Question
Title: Find non-overlapping scheduled jobs with maximum cost
> Given a set of n jobs with \[start time, end time, cost\] find a subset so that no 2 jobs overlap and the cost is maximum.

Now I'm not sure if a greedy algorithm will do the trick. That is, sort by cost and always take the next job that doesn't intersect and with max cost between the two.

Is this equivalent to a knapsack problem? How could I approach it?

# Answer
> 8 votes
The graph of overlapping jobs is an interval graph. Interval graphs are perfect graphs. So what you are trying to do is find a maximum weight independent set (i.e., no two overlap) in a perfect graph. This can be solved in polynomial time. The algorithm is given in *"Polynomial Algorithms for Perfect Graphs"*, by M. Grötschel, L. Lovász, and A. Schrijver.

There are a number of special cases of perfect graphs for which people have discovered simpler and more efficient algorithms for this task. I don't know whether interval graphs fall into one of these special cases.

# Answer
> 6 votes
Greedy algorithm can't help in that case. And it couldn't be compared with both fractional or 0-1 knapsack problems. The first could be resolved by greedy algorithm in O(n) and the second is NP.

The problem you have could be brute-forced in O(2^n). But you could optimize it using dynamic programming.

1) Sort intervals by start time.

2) Initialize int\[\] costs = new int\[jobs.length\] with Integer.MIN\_VALUE (or any negative value);

3) Define follow recursive routine (here is Java):

```
private int findCost(Job[] jobs, int k, int[] costs) {
   if(k >= jobs.length) {
      return 0;
   }
   if(costs[k] < 0) {
     int x = findNextCompatibleJob(jobs, k);
     int sumK = jobs[k].cost + findCost(jobs, x, costs);
     int sumK1 = findCost(jobs, k + 1, costs);
     costs[k] = Math.max(sumK, sumK1);
   }
   return costs[k];
}

private int findNextCompatibleJob(Job[] jobs, int k) {
   int finish = jobs[k].finish;
   for(int i = k + 1; i < jobs.length; i++) {
     if(jobs[i].start > finish) {
        return i;
     }
   }
   return Integer.MAX_VALUE;
}

```

4) Start recursion with k = 0;

I have implemented only recursion routine while other parts are trivial. I considered that any cost is \>= 0. If there could be negative cost jobs we need to add check for that and just pass that jobs without consideration.

# Answer
> 5 votes
One could implement this in O(nlogn)

Steps:

1. Sort the intervals based on end time
2. define p(i) for each interval, giving the biggest end point which is smaller than the start point of i-th interval. Use binary search to obtain nlogn
3. define d\[i\] = max(w(i) + d\[p(i)\], d\[i-1\]).

initialize d\[0\] = 0

The result will be in d\[n\] n- the number of intervals.

Overall complexity O(nlogn)

```
import java.util.*;
class Interval {
  public int start;
  public int end;
  public int cost;
  public Interval(int start, int end, int cost){
    this.start = start;
    this.end = end;
    this.cost = cost;
  }
}
public class BestCombinationFinder {
  public int getBestCombination(List<Interval> intervals) {
    if (intervals == null || intervals.size() == 0) {
      return 0;
    }
    Collections.sort(intervals, new Comparator<Interval>() {
      public int compare(Interval i1, Interval i2) {
        if (i1.end < i2.end) {
          return -1;
        }
        else if (i1.end > i2.end) {
          return 1;
        }
        return 0;
      }
    });
    return findBestCombination(intervals);
  }
  private int findBestCombination(List<Interval> intervals) {
    int[] dp = new int[intervals.size() + 1];
    for (int i = 1; i <= intervals.size(); i++) {
      Interval currInt = intervals.get(i - 1);
      int pIndex = find(intervals, currInt.start, 0, intervals.size() - 1);
      dp[i] = Math.max(dp[pIndex+1] + currInt.cost, dp[i - 1]);
    }
    return dp[intervals.size()];
  }
  private int find(List<Interval> intervals, int target, int left, int right) {
    if (left > right) {
      return right;
    }
    else {
      int mid = (left + right) / 2;
      if (intervals.get(mid).end == target) {
        return mid;
      }
      else if (intervals.get(mid).end > target) {
        return find(intervals, target, left, mid - 1);
      }
      else {
        return find(intervals, target, mid + 1, right);
      }
    }
  }
}

```

# Answer
> 0 votes
Yes, it is equivalent to a knapsack problem. Consider job's end time and prepare the table like a knapsack. Before reading following solution please check out knapsack problem and its solution.

```
// Input:
// Jobs (stored in array jobs)
// Number of jobs (n)

find the maximum end time from given n jobs => max_end

for j from 0 to max_end do
         table[0, j] := 0
end for

for i from 1 to n do
    for j from 0 to max_end do
        if jobs[i].end <= j then
           table[i, j] := max(table[i-1, j], table[i-1, jobs[i].start] + jobs[i].cost)
       else
           table[i, j] := table[i-1, j]
       end if
    end for
 end for

```

You can also print the scheduled jobs by traversing the table:

```
j := max_end;
for i from n to 1 do
    if table[i][j] != table[i-1][j]
        print jobs[i]
        j = jobs[i].start;
    end if
end for

```

Complexity is same as knapsack problem.

---
Tags: algorithms, scheduling, greedy-algorithms, knapsack-problems
---


# Question
Title: Why does packet data don't need trailer/footer while frame needs it?
Why does packet don't need trailer/footer while frame needs it?

I am trying to understand networking concept regarding OSI & TCP/IP layering. I have googled a bit and it says that the footer in data link layer pdu (frame) is needed as a mark of the end of the pdu.

But why does packet data etc in the layers above it doesn't need footer to mark the end of the pdu as well?

# Answer
OSI Layer 2 is usually tasked with getting the information from the upper layers, provided in octets (bytes), into bits suitable for sending over the physical link (OSI Layer 1). On the receiving side, the bits need to be converted back into bytes.

Links do not usually have the nice property of sending an exact sequence of 0 and 1. There is timing to consider (e.g. on a TTL line, scan the voltage *n* times per second). shifting (especially in parallel lines), bit damage, etc. Also, on asynchronous lines (most ones, except ATM (asynchronous transfer mode), textbook example for a synchronous protocol, always makes me smile), there are periods of no data transfer. This means that the sender and recipient somehow have to signal beginning and end of “transfer blocks”.

This is all rather difficult, so the frame header and trailer do not necessarily have to be full numbers of 8-bit blocks. They often include some easily-recognised bit patterns, such as a large-ish number of either all-zeroes or all-ones, followed by a toggle sequence such as 010101, and only then followed by data; this allows the recipient to synchronise on the sender better. Even DCF77 works like that, so receivers can synchronise to the exact beginning of a minute.

Going further, Layer 2 switches often operate in “fast pass-through mode”, in which they only need to have received the header (containing the target (and often source) address) to decide where to send the frame, not needing to fully buffer the entire frame for this decision, leading to faster throughput (less latency). On the other hand, the sending side may, indeed, wish to calculate the checksum on the fly and append it, in the trailer, which is only needed on the recipient side, not on the switches in between. This all allows for cost reduction in hardware.
> 2 votes

# Answer
A frame includes a checksum which can be calculated by the sender while sending, so it is added as a trailer. Note that Ethernet frames are sent on the wire. On the fly calculation of CRC results in better performance. The IP checksum doesn't contain an IP body, so it doesn't need to be calculated on the fly. Similarly, other layers have logic for not using a trailer.
> 0 votes

---
Tags: computer-networks, communication-protocols
---


title: Why escape and escape in byte stuffing?

text:
# Question
Title: Why escape and escape in byte stuffing?
Denoting the two special bytes as FLAG and ESC, and any other as X, where FLAG denotes the start and end of the message and ESC is used to escape any flags within the original message, if the original message was for example,

`X FLAG ESC FLAG FLAG ESC ESC FLAG X X`

this can be byte stuffed as,

`**FLAG** X **ESC** FLAG ESC **ESC** FLAG **ESC** FLAG ESC ESC **ESC** FLAG X X **FLAG**`

where the added bytes are in bold. I don't think it is necessary to escape the escapes. In the receiving side, only FLAG comming after ESC together will be changed to FLAG and when any other bytes come after ESC, that ESC will be ESC as is. For example, if you see the ESC byte at the 5th byte of the received message, since ESC comes after ESC, the 5th ESC will be interpreted as ESC and nothing more. I thought about this, and I think it also works this way. But every resources I can find including my networks book says that an escape should be escaped as well as the flags when originally contained in the message. Why so?

# Answer
> 4 votes
Think of a message (ending in) FLAG. You need to escape it, of course, so your message looks like: **FLAG** (rest) ESC escaped-FLAG **FLAG**

Now think of a message (ending in) ESC. If you do not escape it, your message looks like this: **FLAG** (rest) ESC **FLAG**

Now, “ESC FLAG” and “ESC escaped-FLAG” are undistinguishable. So, that last ESC needs to be escaped.

Now you can go backwards, again and again, until you find that, if one ESC has to be escaped, they all need to be escaped, from the first one.

---
Tags: computer-networks
---


# Question
Title: Lazy lists with call-by-value reduction strategy
I am currently writing lists with lazy semantics in the pure lambda-calculus with call-by-value reduction strategy.

I tried to construct pleasant to use and relatively efficient "lazy" functions on lists. As in the Church encoding I identify list with its right fold function, but with some differences. Here is `nil` and `cons`:

```
nil       = \_ _ z. z
cons x xs = \_ f z. f (\_. x) (\f' _. force xs f' z)

```

This representation of `cons` gives a simple way to get the tail of a list, which is O(1):

```
tail xs = \_ f z. force xs (\_ r. force (r f)) z

```

You just discard the first argument of `f` in `cons` and force the second after applying it to function `f`, which the `tail` function receives. But it brings some problems with `foldr`. Consider

```
cons (s z) (cons (s (s z)) nil)

```

After call-by-value and full beta-reduction (it reduces a term to a readable form) it becomes

```
\_ f z. f (\_ s z. s z) (\f' _. f' (\_ s z. s (s z)) (\'f' _. z))

```

To fold this term with one function, e.g. `plus`, you need to wrap and replicate it a little:

```
(\x r. plus (force x) (force (r
(\x r. plus (force x) (force (r _))))))

```

'\_' means "there is no difference, what term to choose". Then you add a default value `z` and after call-by-value and full beta-reduction the whole term

```
force (cons (s z) (cons (s (s z)) nil))
    (\x r. plus (force x) (force (r
    (\x r. plus (force x) (force (r _)))))) z

```

reduces to

```
\s z. s (s (s z))

```

`foldr` is the generalization of this idea and defined as

```
foldr f z xs = force xs (fix (\rec x r. f x (r rec))) z

```

For example

```
sum = foldr (\x r. plus (force x) (force r) z

```

"Wrapping and replicating" is defined by `fix`, which is Z-combinator:

```
fix f = (\x. f (\y. x x y)) (\x. f (\y. x x y))

```

Having the `head` and `tail` functions it's easy to define `take`:

```
take = fix (\take n xs. if (eq0 n) nil (ifNullNil xs
    (\xs. consC (\_. head xs) (take (pred n) (tail xs)))))

```

`ifNullNil` returns `nil`, if the `null` function (an emptiness test) returns `true` for its first argument, or applies the second to the first and wraps the result into the thunk otherwise:

```
ifNull    = \xs z f. if (null xs) z (\_. force (f xs))
ifNullNil = \xs. ifNull xs nil

```

`consC` receives a thunk instead of a value and defined as

```
consC = \x xs _ f z. f x (\f' _. force xs f' z);

```

Finally you can define infinite lists:

```
nats = fix (\rec n _. force (cons n (rec (s n)))) z

```

And compose them with usual functions on lists:

```
sum (take (s (s (s z))) (cons (s (s (s z))) nats))

```

It reduces to

```
\s z. s (s (s (s z)))

```

and equals to Haskell's

```
sum $ take 3 $ 3:[0..] -- 3 + 0 + 1 + 0 = 4

```

**Edit2**

You need an extra '\_' in the arguments of cons because it allows you to compose ordinary functions with functions, that generate infinite lists. Consider

```
nats = fix (\rec n _. force (cons n (rec (s n)))) z

```

It reduces to

```
nats = \_. force (cons z (fix (\rec n _. force (cons n (rec (s n)))) (s z)))

```

So list, which cons receives, should be "forceable". So list, which cons produces, should be "forceable" too, because you want to compose conses.

So my question is: are there some sources, from where I can learn more about such a representation or a better representations, that allow you to write programms with lazy semantics in languages with eager evaluation, especially in the pure lambda-calculus?

# Answer
> 4 votes
Have a look at Wadler et al's How to add laziness to a strict language without even being odd. It presents a number of techniques (for Standard ML) and provides a good survey of the literature of the time.

The most naive way is to delay the evaluation of term $t$ by making it, using a term such as $\text{delay }t=\lambda ().t$, and to force the evaluation of such a term by applying it, using a term such as $\text{force }t=t~()$. For less naive/more systematic approaches, integrated into programming languages, read the paper.

# Answer
> 2 votes
This representation doesn't allow efficient lists deconstructing actually. While the `tail` function is O(1), every call to it increases the size of a term instead of decreasing. This leads to quadratic complexity for the `zipWith` function for example. Boehm-Berarducci encoding has the same problem. One another option is to represent a list as its right fold, but with passing an accumulator from left ro right. This approach is quite more readable, than Boehm-Berarducci encoding, but has the same problem with lists deconstructing.

Scott encoding solves the problem (this version doesn't contain explicit thunking):

```
nil          = \_ z. z
cons    x xs = \f z. f xs x (xs f z)
head    z xs = xs (\_ x _. x) z
tail      xs = xs (\xs' _ _. xs') nil
foldr f z xs = xs (\_. f) z

```

Emulating tagged unions also solves the problem.

Neither approach is nice. Pattern-matching mixed with normal-order reduction strategy is a bless.

---
Tags: lambda-calculus, functional-programming, lists
---


# Question
Title: Do I require loading in this example of load store architecture?
I'm currently revising for my Concurrent Programming exam and I'm going through the past papers and one question poses the following process:

```
Process P1
 integer x;
1a: x = a + a;
1b: b = x;
end P1;

```

and asks the following question:

> Rewrite processes P1 to take into account execution using a ‘load/store’ architecture.

For `1a` I have broken it down into this:

```
load a into R
add a to R
store R into x

```

Where `R` refers to the register as per my notes.

My trouble lies in `1b`. Do I need to `load x into R` before I `store R into b` or can I simply bypass the register and `store x into b`.

# Answer
You need to load x into R before you store R into b

wikipedia says:

In computer engineering a load/store architecture only allows memory to be accessed by load and store operations, and **all values for an operation need to be loaded from memory and be present in registers**. Following the operation, the result needs to be stored back to memory.

In your case, x is still in memory and has to be loaded into a register.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Limiting capacity of knapsack to a polynomial function of elements in the Knapsack problem
I saw somewhere that if we limit the capacity (weight) of the knapsack to a polynomial function of elements then the class of the problem changes to P, but it didn't say why. I can't figure out why is it true....

I think a found a solution but i'm not sure if it is completely right. The time complexity of the knapsack problem is equal to $O(W \cdot n)$, where $W$ is the capacity of the knapsack, so if we limit it to a polynomial function of $n$ then the complexity will change to $O(P(n) \cdot n)$ which is a polynomial complexity...

# Answer
Since knapsack admits pseudo-polynomial time solution running in $O(nW)$, where $W$ is the bag size, if $W=O(n^c)$for some fixed $c$, then the pseudo-polynomial algorithm runs in $O(n^{c+1})$ which is polynomial in $n$.
> 1 votes

---
Tags: complexity-theory, knapsack-problems, weighted-graphs
---


# Question
Title: Do $s$-$t$ cuts partition contingent vertices?
The definition of an $s$-$t$ cut is a partition of the set of vertices $V$ into $2$ sets $(A, B)$ with $s$ in $A$ and $t$ in $B$. My understanding of set partitions is that the positioning of elements in the graph does not matter.

However, if this is the correct notion of partitioning, then can construct a pathological example. Consider the following network. $$s \to B\_1 \to A\_1 \to B\_2 \to A\_2 \to t.$$Let each of the edges have a capacity of $1$. Then the max flow is clearly $1$. If we let the $s$-$t$ cut be such that set $A$ consists of $s$, $A\_1$ and $A\_2$, and $B$ is the rest, then the capacity of the cut is $3$ since there is a flow of value $1$ exiting each of the $3$ vertices in $A$. This contradicts the max-flow-min-cut theorem.

Is my understanding right then that the $s$-$t$ cut is not a partition of a set but a graph? By this I mean, that the resultant two sets have to be contiguous?

# Answer
The example is correct: in this $s$-$t$ cut the capacity of the cut is indeed $3$. However, the min-cut in the max-flow min-cut theorem talks about the capacity of the *minimum* $s$-$t$ cut. So one must take an $s$-$t$ cut that gives minimum capacity: what you have in your example is not one of them.
> 4 votes

---
Tags: algorithms, graphs
---