# Question
Title: Is there a tactic to help resolving existential quantifiers in Coq?
I am working on Software Foundations Volume 1 on my own it is its 2019 version by the way, and I have reached to its lesson **Inductively Defined Propositions**, and there, for almost one month I have been stuck on an exercise **re\_not\_empty** expressed like this in Coq (the exercise itself begins at Fixpoint):

```
Inductive reg_exp {T : Type} : Type :=
  | EmptySet
  | EmptyStr
  | Char (t : T)
  | App (r1 r2 : reg_exp)
  | Union (r1 r2 : reg_exp)
  | Star (r : reg_exp).

Inductive exp_match {T} : list T → reg_exp → Prop :=
  | MEmpty : exp_match [] EmptyStr
  | MChar x : exp_match [x] (Char x)
  | MApp s1 re1 s2 re2 (H1 : exp_match s1 re1) (H2 : exp_match s2 re2) :
      exp_match (s1 ++ s2) (App re1 re2)
  | MUnionL s1 re1 re2 (H1 : exp_match s1 re1) :
      exp_match s1 (Union re1 re2)
  | MUnionR re1 s2 re2 (H2 : exp_match s2 re2) :
      exp_match s2 (Union re1 re2)
  | MStar0 re : exp_match [] (Star re)
  | MStarApp s1 s2 re (H1 : exp_match s1 re) (H2 : exp_match s2 (Star re)) :
      exp_match (s1 ++ s2) (Star re).

Notation "s =~ re" := (exp_match s re) (at level 80).

Fixpoint re_not_empty {T : Type} (re : @reg_exp T) : bool Admitted.

Lemma re_not_empty_correct : ∀T (re : @reg_exp T),
  (∃s, s =~ re) ↔ re_not_empty re = true.
Proof. Admitted.

```

Although I am obliged not to tell anything about solutions but to get help I have to say at least about Fixpoint that is defined like this:

```
Fixpoint re_not_empty {T : Type} (re : @reg_exp T) : bool :=
  match re with
  | EmptySet => false
  | EmptyStr | Char _ => true
  | App re1 re2 => re_not_empty re1 && re_not_empty re2
  | Union re1 re2 => re_not_empty re1 || re_not_empty re2
  | Star re => re_not_empty re
  end.

```

I could prove the backward case easily. For the forward case I stuck at `Star re` there is a `∃ s, s =~ Star re` in the evidences or context and a `∃ s', s' =~ re` in the goals. The most probable thing to pass it is using inversion on that evidence but how to tell Coq with destruct to put `s1 ++ s2` instead of `s` and put the results in the context instead of in the goals?

# Answer
I was similarly stuck on this problem. I believe your Fixpoint for Star re should just be true. In regular expressions, the empty string is always accepted under star.
> 1 votes

# Answer
Maybe you can consider changing your definition of `re_not_empty`.

My definition is shown below.

```
Fixpoint re_not_empty {T : Type} (re : @reg_exp T) : bool :=
  match re with
  | EmptySet => false
  | EmptyStr | Char _ => true
  | App re1 re2 => re_not_empty re1 && re_not_empty re2
  | Union re1 re2 => re_not_empty re1 || re_not_empty re2
  | Star re => true
  end.

```

According to my definition, the `s ~= Star re` situation can be proved easily.

But the problem is, why does `re_not_empty Star re` is always true? You can look up the definition of `exp_match`, then you will find that `forall re, [] =~ (Star re)`. So no matter what exactly `re` is, even it is `EmptySet`, there always be a `[]` to match it.

I was also stuck on this problem for a long time. Wish my answer can help you.
> 1 votes

---
Tags: coq
---


# Question
Title: Could the halting problem in theory be solved for any finite set of Turing Machines?
Suppose there's a program A that decides whether or not every program halts.

Then we could construct program B that invokes A and does the opposite. Do I halt? If so, loop. Do I loop? If so halt.

That shows we cannot construct program B.

HOWEVER, that assumes B can be embedded in A.

Could there exist a program B that decides all programs of length N or less - their halting, such that B is greater in length than N?

In other words, the "halter decider" is necessarily bigger than the programs it's proving.

Trivially, there exists a computer program that decides the halting of all programs of length 100 or less. There's 2^100 programs of length 100 or less (assuming programs are encoded in base-2). Therefore there's a base-2 number with length 2^100 where each bit corresponds to whether or not the program halts.

Thus, you can solve the halting problem for any arbitrary length or less.

In general, given a finite set M of Turing Machines, there exists a Turing Machine that decides the halting problem for M

Anything wrong with this logic?

# Answer
Your logic is *somewhat* correct. I will start by discussing the new definition you tried to give for the halting problem, and then move on to explain the finite set of TMs.

---

## Halting problem, with size less than the TM that solves it

This idea is certainly interesting, but it has some inherent problems with it.

First is a syntax problem. What language is here? Since $N$ is not bounded, this cannot be expressed as a usual computational problem with TMs. In order to formalize this you might want to create a new definition.

The second problem, is a bit more subtle: How do you define the "size" of a TM? For example, if you decide to define it as the running time of the algorithm, then obviously is such a $B$ for every $N$ (just do a loop that does nothing for $N-1$ steps and after that accept). But if you define it as the length of the code plus the length of the inputs, then you can show that there is no such $B$ for big enough $N$. (the formal halting problem gets two inputs $A,X$ where $A$ is a program code and $X$ is some string, and you create a new TM that simulates it with only one input instead of two, reducing the size)

Those examples are obviously two opposite sides of a wide spectrum. You want to **formally** define the problem and the definition of the size of a TM before you can think of whether or not its possible.

---

## Finite set of TM

The formalization of the halting problem $H$ is as follows: $H=\\{\langle M, x \rangle : M \text{ is a TM }\land M(x)\text{ halts}\\}$

With this definition, even if you restrict it so $M$ would be in a predefined finite set of TMs, and even if this set contains only one TM, this is an undecidable problem! The counterexample, is $U$ \- the universal TM. We will use a slightly different version of it, since we dont need its full power. $U$ (in this context) gets one input, which is a string representing a TM, and $U$ simulates this TM with the input $\epsilon$. Then solving whether $U$ halts on some input or not, is undecidable, since its equivalent to the problem called $H\_\epsilon$ which is known to be undecidable.

However, if you would restrict the $H\_\epsilon$ problem itself for only a finite set of TMs, the problem becomes decidable, and even more! It becomes a regular language. This is because for each $TM$ in this finite set we know beforehand whether or not it halts, and we dont have to actually do any computation apart from assigning each of those $TM$ the correct label we already know.
> 3 votes

---
Tags: halting-problem
---


# Question
Title: Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma?
$\\{a^mb^nc^n\mid m,n \ge 1\\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to prove a language is non-regular. In reference to the Wikipedia article linked (see "Use of Lemma"), every string I have tried doesn't give a contradiction. For example, a string like $a^1b^pc^p$ (where $p$ is the pumping length) seems to nicely split into $x = \varepsilon$, $y = a^1$, $z = b^pc^p$. What am I missing here?

# Answer
> 4 votes
You've forgotten that $y$ can be pumped any number of times, including zero. The string $xy^0z = b^pc^p$ is not in the language.

# Answer
> 0 votes
Yes. Say $N$ is the constant of the pumping lemma, and consider $\sigma = a b^N c^N \in L$ and $\lvert \sigma \rvert = 2 N + 1 \ge N$. By the lemma, you can write $\sigma = \alpha \beta \gamma$, such that $\lvert \alpha \beta \rvert \le N$ with $\beta \ne \epsilon$ such that for all $k \ge 0$ it is $\alpha \beta^k \gamma \in L$. Now $\beta$ must be composed of only one symbol (in this case, as $\lvert \alpha \beta \rvert \le N$, it has to be only $a$ or some $b$s) as otherwise $\alpha \beta^k \gamma$ for $k \> 1$ isn't of the right form ($a$s followed by $b$s followed by $c$s). Now $\alpha = \epsilon$, $\beta = a$ is impossible, because in that case you's have $\alpha \beta^0 \gamma = b^N c^N \notin L$. But $\beta$ just $b$s with $k \ne 1$ gives a string with number of $b$s and $c$s different, thus not in $L$. No division into $\alpha, \beta, \gamma$ works, the language fails the pumping lemma, it can't be regular.

Make sure you understand the lemma and it's use. Your proof is by contradiction, you need to prove the lemma *doesn't* apply. The lemma states that there is a constant $N \> 0$ (i.e., you *can't* assume anything about $N$, just know it is positive) such that *all* strings in the regular language that are longer than $N$ (to get a contradiction, you can pick *any* convenient string that is long enough) *can* be divided into three parts with the given restrictions (i.e., you don't get to pick a convenient division, you have to prove *none* works), for that division *all* $k \ge 0$ pumpings belong to the language (given any division, you can pick some $k \ne 1$ that makes the pumped string not in the language).

# Answer
> 0 votes
The pumping Lemma is very abstract, yet very obvious if you check where it comes from.

If L is a regular language then there is a finite state machine with exactly P states. If you examine a string w of P or more symbols, then after processing P symbols you must have entered the same state twice. Say the first state entered twice is X, then w = axb where the string a moves from the initial state S to X, x moves from X back to X, and if w is in the language, then b moves from X to an accepting state. And the length of ax is at most P.

Processing ab would also move from S to X to an accepting state. axxb would move from S to X to X to X to an accepting state and so on. And that’s the pumping Lemma: If w is long enough then you must have entered a loop, and the string causing the loop can be repeated any number of times.

That’s why $ab^nc^n$ gives a counter example: Because the loop must contain a sequence of b’s or c’s; since one a is needed, it cannot be part of any loop. And that’s why $a^2b^nc^n$ doesn’t give a counter example: Because the second a forms a loop and therefore can be repeated any number of times, including zero times.

# Answer
> -1 votes
$S = a^Pb^{PM}c^{PM}$. It can be divided in $S = xyz$ where $x = \epsilon, y = a^P, z = b^{PM}c^{PM}$ which satisfies the following conditions: $$ |xy| \le P $$ $$ xy^iz \in L $$ $$ |y| \>= 1 $$ The middle condition is satisfied because the length of a is irrelevant to the length of b and c.

But, this doesn’t mean that a language is regular. The pumping lemma in simple words only says that: each regular language that can be represented with an automaton that has |finiteStates| = $x$, and the sequence it accepts is of length \> $x$ then according to the pigeon-hole theorem, at least one state is looping.

The pumping lemma does not work both ways. Therefore a language that satisfies it is not necessarily regular. It only means that the ones with variable length that don't satisfy it are irregular.

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


# Question
Title: Is $n^2 \log n$ in $O (n^2)$ am confused
I graphed the functions and when $n\_0$ is greater than $3$, $cg(n)$ is always greater than $n^2 \log n$ so it would seem to me by definition that $m^2 \log n$ is in $O (n^2) $. I tried to prove it by dividing both sides of inequality by $n^2$ . The $c \ge \log n $. As n tends to infinity there will be values of c that are \> than logn . I have to say if $n^2 \log n $ is in $O(n^2)$ . My classmate says it isn't to me it looks like it is. It is 6.00 am here and my brain is mush so apologies if this is a really trivial questions and you are all laughing at my stupidity. It is a little confusing I admit. It seem to me that $n^2 \log n$ above $n\_0= 3$ is always greater than $n^2$

# Answer
> 1 votes
$n^2\log(n)$ **isn't** $O(n^2)$. You need to have a **constant** $c$, so since $\log(n)$ tends to infinity, for any fixed $c$ you will choose, at some point $\log(n)$ will pass $c$, that is: $\forall n\>n\_0: c \< \log(n)$ for some $n\_0$. This directly means that $\forall n\>n\_0: cn^2 \< n^2 \log(n)$ which means that $n^2 \log(n)$ is asymptotically bigger than $cn^2$.

# Answer
> 0 votes
Main error is in sentence:

"As n tends to infinity there will be values of c that are \> than logn".

Under $c$ we have **constant** in definition of big-$O$, while for $a \gt 1$ function $\log\_a n \to +\infty$ and we cannot bound it by constant.

So, for any constant $c\gt 0$ and $a \gt 1$ we can solve $\log\_a n \gt c$ and have $n \gt a^c$.

For correct answer is enough to note, that $n^2 \log n \gt n^2$, when $\log n \gt 1$ and we have $n^2 \log n \in \Omega(n^2)$.

---
Tags: asymptotics
---


# Question
Title: Prove that the worst-case running time of heapsort is $\Omega(n\lg n)$
I'm trying to prove the running time of heapsort on an array sorted in decreasing/increasing order is $\Theta(n\lg n)$ in order to show that the worst-case running time of heapsort is $\Omega(n\lg n)$

The site here https://courses.csail.mit.edu/6.046/fall01/handouts/ps2sol.pdf mentions :

> The running time of HEAPSORT on an array A of length n that is sorted in decreasing order will be $\Theta(n\lg n)$. This occurs because even though the heap will be built in linear time, **every time the max element is removed and the HEAPIFY is called it will cover the full height of the tree.**

It's the last line which I can't understand. I tried the array A \<7, 6, 5, 4, 3, 2, 1\>. The first time MAX-HEAPIFY is called, the full height of the tree is covered and I get \<6, 4, 5, 1, 3, 2\> 7. However, the second time itself the full height of the tree is not covered and I get \<5, 4, 2, 1, 3\> 6, 7. How does that statement hold then?

Also I see people writing on similar lines saying each call to MAX-HEAPIFY performs **full $\lfloor \lg k \rfloor$** operations, where k (I'm assuming) is the number of nodes in the modified heap in each iteration, thereby obtaining the summation. $$ \sum\_{i=1}^{n-1}\lg{(n-i)}= \lg\Big((n-1)!\Big) = \Theta(n\lg{n}) $$

Can someone help me realize this. I just want to understand how MAX-HEAPIFY covers the **full height** of the tree each time it is called.

**UPDATE**: I'm trying to obtain a proof for the running time to be $\Theta(\lg n)$. During HEAPSORT, if each node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree, that would mean that each call to MAX-HEAPIFY won't perform full $\lfloor \lg k \rfloor$ operations but $ \Theta(\lg k) $ operations, right? (I know $\lfloor \lg k \rfloor $is also $\Theta(\lg k)$ but all I need is for MAX-HEAPIFY to perform $\Theta(\lg k) $ operations each time) $$ \sum\_{i=1}^{n-1}\Theta( \lg{(n-i))} = \Theta\Big(\lg\Big((n-1)!\Big)\Big) = \Theta(n\lg{n}) $$ But that statement doesn't hold as pointed out in the comments. Now I don't have anything to work with. How can I guarentee that MAX-HEAPIFY will perform $\Theta(\lg k) $ operations each time?

# Answer
> 1 votes
Edit: This proof is insufficient as pointed out in comment.

I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree.

Since the heap is a complete tree, it means that its leaves are all on the two last levels of the tree. So even if the full height of the tree is not covered, the difference with the full height will be at most 1 (like in the second case of your example), and that is why it does not change the asymptotic complexity.

# Answer
> 0 votes
No comparison based sorting algorithm can be faster than $\theta(n \log n)$. On the other hand, both building the initial tree and removing items and rebalancing take at most log n steps per item.

---
Tags: algorithms, time-complexity, data-structures, runtime-analysis, heap-sort
---


# Question
Title: About the connection of pipelined execution and latency
Let's consider we want to calculate `a[i]=a[i]*c` for a vector the size of `N=12` on some random processor.

We do assume that `c` is some given constant already present in the register. We do not consider any superscalarity or vectorization. We also know the latencies for the following instructions:

* Load operand to register (4 cycles)
* Multiply `a(i)` with `c` (2 cycles); (`a[i],c` in registers)
* Write back result from register to mem./cache (2 cycles)
* Increase loop counter as long as `i` less or equal `N`(0 cycles)

The result my class gives me for the pipelined execution of this is the following, where each line represents **one** CPU cycle:

**Why is this correct? Or is this even correct?**
If we consider the first load (`load a[1]`) shouldn't it block my only load unit on the processor for `4` cycles? How can I even load `a[2]`in cycle `2`then?

Or is latency only the time to that is needed to send information that something is e.g. loaded, and the actual load unit is only busy for one cycle for each load operation?

# Answer
> 1 votes
In a processor that would nowadays be considered simple, you need two numbers for an instruction: what is the total execution time (for example 4 for load) and how long you need to wait before another independent operation can be issued - it seems that someone assumed 1 cycle between instructions for load. A different processor might only allow a load every two cycles, and your numbers would be totally different.

The PowerPC 603 was interesting in that a multiplication took 4 cycles, but it couldn’t start four multiplications in a row, so your multiplications would have started at cycles 4, 5, 6, 8, 9, 10, 12 etc.

Things get more interesting when you have multiple independent execution units; like you assume at least three units capable of load, store, and multiplication. And more interesting if you have limits decoding instructions, dispatching to execution units etc.

---
Tags: computer-architecture, efficiency, cpu, cpu-pipelines
---


# Question
Title: Can I simplify log(n+1) before showing that it is in O(log n)?
Had a question about the following:

$$\log (n+1) \in O(\log n)$$

Can the left side be simplified any further or do I need to just go ahead and find a ***c*** and ***n*** that hold?

# Answer
> 6 votes
Simplifying the left-hand side is a good strategy. You aren't going to find a simpler expression that's equal to $\log(n+1)$, though. However, since you're only interested in proving that $\log(n+1)$ is “not too large”, it can be a good strategy to find an intermediate step that's larger than $\log(n+1)$ but still not too large. That is, try to find a function $f$ such that $\log(n+1) \le f(n)$ (for sufficiently large $n$), and $f(n) \in O(\log n)$.

(Easy exercise: prove that this is true — if you've found a such a function $f$ then $\log(n+1) \in O(\log n)$.)

So you can try to fill in the statement $\log(n+1) \le \ldots$ with something simpler on the right-hand side. “Simpler” meaning that in the end it'll be simpler to prove that this is in $O(\log n)$. So keep the definition of $O$ in mind: you'll need to prove that $f(n) \le C \log n$ for some $C \gt 0$.

This suggests trying to find $f$ of the form $C \log(n)$.

Hint:

> $x + 1 \le x + x$

Hint #2:

> You can say that again.

Of course this approach works for other functions and other bounds.

Exercise (open-ended): can you generalize this to $\Omega$? To $\Theta$? To $o$?

# Answer
> 2 votes
Simplify is only necessary if you can show the same with less steps. Here simplifying will not spare you something.

You can either find a $c$ and $n$ or you could use **limit** value.

$$ v = \lim\_{n\to\infty}{\frac{\log(n+1)}{\log(n)}} $$

and if the limits exist ($v \< \infty$) then $\log(n+1)\in O(\log(n))$.

# Answer
> 1 votes
You can simplify the expression as following:

$$\log(n+1)=\log(n)+\log \left(\frac{n+1}{n}\right)$$

It shouldn't be to hard to show that $\log \left(\frac{n+1}{n}\right)\<\log(n)$ for $n\geq 2$.

But it doesn't necessarily help to make the process shorter.

However, to solve the problem, you need to rewrite something. This can be done with inequalities or with equalities. In this case, I'd personally prefer to start out with inequalities.

# Answer
> 0 votes
$n+1 ≤ n^2$ for $n ≥ 2$, therefore $\log(n+1) ≤ \log (n^2) = 2 \log n$ for $n ≥ 2$, which by definition means $\log(n+1) = O(\log n)$.

“Simplifying” is difficult. Let $f(n) = 2^{2^n}$, then $f(n+1) ≠ O(f(n))$. Same for $f(n) = n!$ Or more difficult to prove when $f(n) = \left|\sin(n)\right|$.

---
Tags: asymptotics, proof-techniques, landau-notation
---


title: Vertex cover of minimal graph

text:
# Question
Title: Vertex cover of minimal graph
I'm looking for algorithm that, for given undirected graph $G=(V,E)$, find graph $G'=(V,E')$ with minimal amount of edges that have same vertex cover as G. I mean, vertices $U$ are vertex cover of $G$ iff they are vertex cover of $G'$.
I understood that a polynomial algorithm exists, it's mean without finding the vertex cover of $G$, but I found only a non-polynomial one.

# Answer
> 1 votes
The algorithm to compute $G'$ is really easy: just return $G$.

Indeed, given any $G=(V,E)$ the only graph $G'=(V, E')$ such that $U \subseteq V$ is a vertex cover of $G$ iff $U$ is a vertex cover of $G'$ is $G$ itself.

To prove this you can show that we must simultaneously have $E \subseteq E'$ and $E' \subseteq E$.

**Proof that $E \subseteq E'$**: Suppose towards a contradiction that $E \nsubseteq E'$. Then $\exists (u,v) \in E \setminus E'$. The set $U = V \setminus \\{u,v\\}$ is a vertex cover for $G'$ but not for $G$.

**Proof that $E' \subseteq E$**: Suppose towards a contradiction that $E' \nsubseteq E$. Then $\exists (u,v) \in E' \setminus E$. The set $U = V \setminus \\{u,v\\}$ is a vertex cover for $G$ but not for $G'$.

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


# Question
Title: If X is in NP then $\overline{X}$ is in NP. True, false or "we don't know"? Why?
If X is in NP then $\overline{X}$ is in NP.

True, false or "we don't know"? Why?

# Answer
The answer is unknown. If $X\in NP$ and $\bar X\in \mathcal{NP}$ than by definition it's a so called "co-NP" problem ($X\in \mathcal{coNP}$). It's still an open problem if $\mathcal{NP} = \mathcal{coNP}$.

**An example:**
Some problems are known to be in coNP. E.g. to decide if two number $n,m$ have a common divisor $\>1$. This problem is in $\mathcal{NP}$ because there exists a polynomial verifier to check if a "proof" that some $n,m$ have common divisor $\>1$ exists. The verifier accepts e.g. a number $p$ if $p\>1$ and $p|n \land p|m$ the verifier accepts the proof. Now lets show that the complement of this language is also in $\mathcal{NP}$. We need to construct a verifier that accepts a proof that two numbers don't have a common divisor $\>1$. You might notice that this is a bit more difficult but it can be done. The verifier accepts the prime factorization of $n$ and $m$ and checks that these are really the prime factorization of $n$ and $m$ and then that they don't have a common element.

**Now try SAT...**
Now if you take e.g. the $SAT$ problem and you try to find a verifier for $\overline{SAT}$ you have to find an algorithm that can given a certain proof verify that a boolean expression **does not** have a solution in polynomial time. If you think about it this is quite tricky (some how you have to deduce from the proof that none of the exponentially many variable assignments is valid) and it's currently not known whether $SAT\in \mathcal{coNP}$.
> 4 votes

# Answer
To give you an idea of the “why”: A yes/no problem is an NP if you can prove the answer is “yes” by making an incredibly lucky guess, plus some moderate amount of work.

For example: Can I make a tour connecting the capitals of the 48 main states of the USA in at most 10,000 miles? If the answer is “yes” then I make a lucky guess in which order to visit the 48 capitals, and then just add up the distances. But if the answer is “no” then no such guessing will work. If I guess one order that takes 10,100 miles, that doesn’t prove there isn’t a better order.

The questions look very similar, but checking that an x exists is easy if you can guess x; checking that no x exists often cannot be helped by guessing. Or at least we haven’t figured out a way yes.
> 0 votes

---
Tags: complexity-theory, terminology, complexity-classes, p-vs-np
---


# Question
Title: Designing less than and less than or equal operators for Map with value being a Set
I am trying to come up with less than and less than or equals operators for a Map where values are Sets. These are the hints I was able to get from the Professor.

```
{A -> {1,2}, B -> {3,4}} < {A -> {1,2}, B -> {3,4}, C -> {5,6}}

{A -> {1,2}, B -> {3,4}} < {A -> {1,2}, B -> {3,4,5}}

```

My solution was this:

```
val v_compare = (x, y) => (x.keySet intersect y.keySet).forall(key => x(key) subsetOf y(key))

val v_compare_equal = v_compare

```

I am wondering can I get some hints? I don't know what should the "\<=" be

# Answer
> 1 votes
I think that actual code is off-topic here. In general you can define a strict total order relation on (sub)sets of a known universe $U$: pick an arbitrary order for the elements of $U$ then, given two distinct subsets $X,Y$ of $U$, you can compare $X$ and $Y$ by first sorting the elements of $X$ (resp. $Y$) and then comparison the sorted version of $X$ with the sorted version of $Y$ lexicographically.

In your particular example the sets seem to contain integers, so you can just sort the set using the standard "less than" relation between integers.

To extend this total order to a map you can notice that a map is essentially a container of pairs of the form (key, value). We just defined a linear order over the values (sets), and you probably already have a natural order over the keys. Then two (key, value) pairs can be again compared lexicographically.

---
Tags: linear-algebra
---


# Question
Title: Proving that a preorder traversal of a rooted tree can be performed in linear time
**Definition:**

Let $T(V, E)$ be a rooted tree with root $r$.

If $T$ has no other vertices, then the root by itself constitutes the *preorder traversal* of $T$.

If $\lvert V \rvert \> 1$, let $T\_1, T\_2, \dots, T\_k$ denote the subtrees of $T$ from left to right. The *preorder traversal* of $T$ first visits $r$ and then traverses the vertices of $T\_1$ in preorder, then the vertices of $T\_2$ in preorder, and so on until the vertices of $T\_k$ are traversed in preorder.

**Question:**

How does one prove, using the above definition, that a preorder traversal of a rooted tree $T(V, E)$ can be computed in $O(\lvert V \rvert)$ time? Since $T$ is a tree, $\lvert E \rvert = \lvert V \rvert - 1$, and so showing that a preorder traversal algorithm simply visits the vertices and edges of $T$ a constant number of times and does constant work on each visit would do it. Obviously this is true, but how does one prove this formally?

# Answer
> 2 votes
You can prove that formally by using structural induction. The structure of the proof is as follows:

* Observe that a preorder traversal of a tree with $1$ vertex requires constant time.
* Then, assume that a preorder traversal of a tree with up to $i \ge 1$ vertices can be performed in time at most $c \cdot i$, for a suitable constant $c$, and show that the preorder traversal of a tree $T$ with $i+1$ vertices requires at most $c \cdot (i+1)$ time. Here you use the induction hypothesis and the definition of the traversal. In particular, notice that the subtrees of $T$ that are rooted in the children of the root have at most $i$ vertices.

# Answer
> 1 votes
You have to do three things:

1. Exhibit an algorithm.
2. Prove that it is correct (it outputs the right value).
3. Prove that its running time is $O(|V|)$.

@Steven describes one way to prove the running time.

One can probably prove correctness using structural induction as well.

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


# Question
Title: How to calculate the number of weights for a CNN?
Can somebody help me with the formula needed to calculate the number of weights for a CNN, using the following sample question as the basis for it?

> Suppose we have a convolutional neural network with a 5x5x1 input volume, followed by one convolutional layer with 5 filters that have a 2x2x1 receptive field, followed by one fully connected output layer with 5 neurons. How many weights does the network have in total?

Any help appreciated because I keep getting the wrong answer. I think the first part is:

`5 * (5 * 5 * 1) + 5`

And this gives 130, it might be completely wrong anyway I am doing:

`filters * (5 x 5 x 1) + filters`

For the second part (2 * 2 * 1) with five filters I get:

`filters * ( 2 * 2 * 1) + filters = 25`

So now I have a total value of `155` and after this I am unsure how to factor in the output neurons and arrive at the answer (which I know is `430`).

# Answer
Each receptive field of a filter has a weight. Furthermore, the whole filter has a single bias. This gives for a single filter: 2\*2\*1+1 = 5 weights per filter. 5 filters * 5 weights = 25 weights for all filters.

The conv layer produces shape (4, 4, 5) if we assume the stride is 1.

The fully connected output layer (dense layer) has 5 neurons. Each of them is connected to the output of the conv layer. So it's (4\*4\*5) * 5 neurons = 400 connections. Each of these connections has a weight. Each neuron in the dense layer also has a bias, so there are 5 more weights.

To sum up: 25 parameters for conv layer, 405 parameters for dense layer. 430 in total.
> 2 votes

---
Tags: neural-networks
---


# Question
Title: Find the recurrence relation for the following algorithm
The question requests to find the recurrence relation of the following algorithm and solve it using the characteristic equation.

\begin{align} &\text{SORT}(A\[0\dots n-1\])\colon\\ &\quad \text{if } n = 2 \text{ and } A\[0\] \> A\[1\] \text{ then} \\ &\quad\quad \text{swap}(A\[0\],A\[1\]) \\ &\quad \text{else if } n \> 2 \text{ then} \\ &\quad\quad m=\lceil 2n/3 \rceil \\ &\quad\quad \text{SORT}(A\[0\dots m-1\]) \\ &\quad\quad \text{SORT}(A\[n-m\dots n-1\]) \\ &\quad\quad \text{SORT}(A\[0\dots m-1\]) \end{align}

The recurrence equation that I found is $T(n) = 2 \cdot T(2n/3) + T(n/3) + 1$ with base case $T(2) = 5$.

The base case is $T(2) = 5$ because of 2 comparisons in the if statement plus 3 statements in swap() function.

I'm not sure whether what I've tried is correct or not. All help is appreciated!

# Answer
> 0 votes
Your recurrence relation is almost correct. Here are some small issues with it:

* The length of the array $A\[n-m\ldots n-1\]$ is $m$, not $n-m$.
* Your recurrence only holds when $n$ is divisible by 3. The exact length of the arrays in the recursive calls is $m = \lceil 2n/3 \rceil$.
* You are not handling arrays of length $1$.
* You are trying to count operations, but without a precise model of computation, this is really impossible. There are two common options here: either you count specific operations, for example only comparisons and swaps, or you just give up and replace everything with $O(1)$. Both options are common.

Accordingly, here are some more accurate solutions are:

* When counting only comparisons of array elements, the recurrence is $T(1) = 0$, $T(2) = 1$, and $T(n) = 3T(\lceil 2n/3 \rceil)$ for $n \geq 3$.
* When counting only swaps, the recurrence is the same as in the first bullet. Note that $T$ is actually an *upper bound* on the *worst-case cost* of your procedure.
* When counting both comparisons of array elements, the recurrence is the same as in the first bullet, with "$1$" replaced by "$2$".
* When counting the running time on a RAM machine (the standard computation model for analyzing algorithms), the recurrence is $$T(n) = \begin{cases} O(1) & \text{if } n \leq 2, \\ 3T(\lfloor 2n/3 \rfloor) + O(1) & \text{otherwise.} \end{cases}$$

One fine point is that except when counting comparisons, the recurrence $T$ is for an upper bound on the cost. The exact cost depends on the instance, and often we are interested in estimating the worst-case cost as a function of the input length (in this case, $n$). However, the recurrence for $T$ isn't even guaranteed to compute the worst-case cost: it could be too pessimistic. For example, it could be that no input causes all possible swaps to be performed. Nevertheless, $T(n)$ does upper-bound the cost of the procedure on any input of length $n$.

---
Tags: algorithms, recurrence-relation
---


# Question
Title: Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$
I have been working on the following homework question, and I just can't seem to make any progress:

> Construct a finite automaton having fewer than 36 states that recognizes the language $\\{s \in a^\* : \operatorname{gcd}(|s|, 504) \geq 6\\}$, where $|s|$ is the length of $s$.

So far I have been trying to figure out a regular pattern in $504$ and have broken it down to the prime factorization $504 = 2^3 \cdot 3^2 \cdot 7$, which means that all divisors must be multiples of 2, 3, or 7. However I don't know how to create the finite automaton (NFA or DFA). Any help is appreciated!

# Answer
> 5 votes
The number $504$ has $4\cdot3\cdot2=24$ divisors: $$1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 18, 21, 24, 28, 36, 42, 56, 63, 72, 84, 126, 168, 252, 504$$ Out of these, $20$ are at least $6$: $$ 6, 7, 8, 9, 12, 14, 18, 21, 24, 28, 36, 42, 56, 63, 72, 84, 126, 168, 252, 504$$ For an integer $n$, $\operatorname{gcd}(n,504) \geq 6$ iff $n$ is a multiple of one of these numbers. To check this, we don't really need to go over all $20$ possibilities. For example, if $n$ is divisible by $12$ then it is also divisible by $6$, so we can remove $12$ from the list. The list narrows down to only $4$ options: $$ 6,7,8,9 $$ That is, $$ \operatorname{gcd}(n,504) \geq 6 \Leftrightarrow 6 \mid n \text{ or } 7 \mid n \text{ or } 8 \mid n \text{ or } 9 \mid n $$ You can check the condition on the right using an NFA with $6+7+8+9 = 30$ states (or $31$ states if you do not allow multiple initial states).

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


# Question
Title: How do I assign homes to hospitals based on locality? (clustering, kmeans?)
I have a large set of $(X)$ hospitals and $(Y)$ homes, where $(Y)$ is much larger than $(X)$, and their respective coordinates. Each hospital can handle any home within a 50 mile radius, and up to 10,000 homes. Homes can be assigned to one hospital. How do I create assignments of homes to hospitals such that as many homes can be assigned a hospital? Performance doesn't matter that much.

I was thinking of potentially getting each hospital to do a breadth first search to reach as many homes as possible near it. For this, I was thinking of calculating the distance to all homes from each hospital, then going through each home and matching with the nearest hospital until all homes are filled or can't be any more.

Would this be a good approach? What would a better approach be? Are there clustering algorithms that could help here such as kmeans?

# Answer
Construct a graph $G=(V,E)$ where $V$ contains two nodes $s$ and $t$, a node $u\_x$ for each hospital $x \in X$, and a node $v\_y$ for each home $y \in Y$.

There is an edge between $s$ and each $v\_y$ of capacity 1. There is an edge of capacity $10000$ between each $u\_x$ and $t$. Moreover, there is an edge $(v\_y, u\_x)$ if an only if $y$ is within $50$ miles from $x$. Edges $(v\_y, u\_x)$ have unbounded capacity.

Compute a maximum flow $f$ from $s$ to $t$. The value $|f|$ of the flow tells you the maximum number of homes that can be assigned to some hospital. Moreover, $f$ itself tells you a possible assignment: assign $y \in Y$ to $x \in X$ if and only if $f(v\_y, u\_x)=1$.
> 0 votes

---
Tags: optimization, clustering
---


# Question
Title: Showing that T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)
I am doing an exercise which says that this is true: T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)

So I tried to solve it by substitution, but I am getting a non-sense result. So would really appreciate some pointer in the right direction.

So I want to show it for $\frac{n}{4}$ (sub-question, I am picking $\frac{n}{4}$ to show it for because the recurrence has $T(\frac{n}{4})$, but this might not be the correct way to go always?)

I substitute $T(n/4)$ for $c\sqrt{n}$ in the original equation and get

T($\frac{n}{4}$) $\leq$ 2 + 2(c $\sqrt{\frac{n}{4}}$) =

2 + 2c$\frac{\sqrt{n}}{\sqrt{4}}$ =

2+2c$\frac{\sqrt{n}}{2}$ =

2+c$\sqrt{n}$ $\leq$ c$\sqrt{n}$

Which is clearly not true.

# Answer
Since the OP made a writing mistake in the question, I will keep the first answer and add onto it the correct one.

---

## For $T(n)=2+2T(n/2):$

I believe that the recurrence relation is **not** $O(\sqrt{n})$, and in fact is $\Theta(n)$.

We can see this easily using the master theorem, where here $a = 2, b = 2, f(n)= 2$, and then $T(n) = aT(n/b) + f(n)$.

Since $f(n)=O(n^{\log\_b (a)})=O(n)$ then by the first case in the master theorem we have $T(n) = \Theta(n^{\log\_b (a)}) = \Theta(n)$.

---

## For $T(n)=2+2T(n/4)$:

As I have mentioned in the previous proof, the master theorem is useful for solving such recurrence formula. In our case, we have $a=2,b=4,f(n)=2$ and thus $\log\_b(a)=\log\_4(2) = 0.5$

By the first case of the master theorem, since $f(n)=O(n^{\log\_b(a)})=O(n^{0.5})=O(\sqrt n)$ then we will also have $T(n) = \Theta(\sqrt n)$
> 3 votes

---
Tags: recurrence-relation
---


# Question
Title: Cardinality of sets and strings -> confused
I have a question regarding the cardinality of sets and strings.

If $ \Sigma^\* $ is empty, the cardinality is 1, because the empty word $ \varepsilon $ is counted.

If $ \Sigma^+ $ is empty, the cardinality is 0, because the empty word is excluded from the set.

If $ \Sigma $ includes at least one symbol, the cardinality of $ \Sigma^\* $ is inifite.

If I use a string without the definition of $ \Sigma $, for example to define a variable, then I have problems to understand the cardinality. So if I set a variable to a string: $ a = "a" $, the cardinality of the string is 1. But if I set a variable to an empty string: $ a = "" $, the cardinality is also 1, because "" is the same as the empty word $ \varepsilon $.

The first time I noticed this was in a book whereas the definition of Pumping Lemma allows $ i=0 $ for the pumped word-part $ y $. Which means for me that $ y^0 = \varepsilon $ is allowed, because $ \varepsilon $ counts with 1. At the same time, others sources mention that it's not allowed to define $ y = \varepsilon $ for the Pumping Lemma.

Is the book wrong with allowing $ i = 0 $, or are the other sources wrong by disallowing $ y = \varepsilon $? Or do I completely misunderstand this?

Thank you!

# Answer
> 0 votes
In the Pumping Lemma (for regular languages) we consider a division $w = xyz$ for a long enough world $w$.

In the Lemma it is required that $y\neq \varepsilon$ (or equivalently $|y|\> 0$). The reason is very practical. When $y=\varepsilon$ no letters are pumped, and $y^i = \varepsilon$ for all $i$, and then in fact $xy^iz = w$ belongs to $L$ for all $i$. That makes the statement of the Lemma of no value: it is always true.

In the iteration $y^i$ we may take $i=0$. Practically that means that a piece of the string is deleted, rather than iterated. The proof of the Lemma holds in that case (repeating a loop in the automaton $i$ times), and moreover there are situations where taking $i=0$ in when applying the Lemma to non-regular languages leads to an easy contradiction.

As for one of your other observations, please note the difference between cardinality and length. A string has a length (the number of its letters) and a set of strings has a cardinality (the number of its elements). It is confusing to talk about the cardinality of a single string, in my opinion.

# Answer
> 1 votes
You are confusing the size of a set of things and the size of the things the set contains.

The empty set contains nothing. Its size (or cardinality of you want to be sesquipedalian) is 0.

A set of containing one thing has size 1. It doesn't matter whether the one thing is an elephant, a flea, or a string. If there is one thing, the cardinality is 1. That thing could even be a set, even the empty set. The empty set is a thing which contains nothing but it is not nothing. It is a thing, so it can be the element of another set.

A string is not a set, even though it consists of elements of a set of letters. It differs from a set in that its elements are ordered, and therefore might repeat. When we count the size, we count each repeated element too. But both a string and a set can be empty. The empty set has size 0 but it's also one thing. The empty string has size 0, and it is also a thing. (A different thing).

So, $$\begin{align}\mid\\{\\}\mid&=0\\ \mid\\{\\{\\}\\}\mid&=1\\ \mid\\{“”\\}\mid&=1\\ \mid\\{“”, \\{\\}\\}\mid&=2\\ \end{align}$$

We usually talk about the *length* of a string (or other sequence) rather than its *cardinality*, but the two concepts are shown with the same operator (the pair of vertical bars above, also used for "absolute value"), because they are easily related. In fact, we can think of a string (or sequence) as a set of *mappings*, each integer in a contiguous finite range is mapped to a single character (or element of the sequence). Even though the two characters are the same, the mappings in $\\{\<1\to a\>, \<2\to a\>\\}$ differ (because the integers differ), and the two mappings clearly denote the string $aa$. The cardinality of the set of mappings is 2, just as is the length of the string.

The empty string corresponds to an empty set of mappings (as one might expect), so its cardinality is 0. (As we saw above, this is different from the cardinality of a *set* containing the empty string.)

---

Finally, your question about the pumping lemma is a different confusion, but still a confusion having to do with emptiness.

The pumping lemma states that $|y|\>0$, so it is clear that $y$ cannot be $\epsilon$. But it allows you to pump $y^i$ for any non-negative $i$. There is no contradiction here. $y^0 = \epsilon$ for any $y$, by definition. So the pumping lemma lets you produce a string where $y$ has been replaced with $\epsilon$ (in other words, deleted). That has nothing to do with the fact that the $y$ being eliminated actually existed in the original string. (Or perhaps it does, since eliminating nothing is a no-op.)

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


# Question
Title: Why do these functions satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n))?
I don't understand what these function are like and why they satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n)).

Where is x?

\begin{eqnarray} f(x)= \begin{cases} k^{2k}, &x\in(2,2+1)& \\ k^{2k+1}, &x\in(2+1,2+2)& \end{cases} \end{eqnarray}

\begin{eqnarray} g(x)= \begin{cases} k^{2k-2}, &x\in(2,2+1)& \\ k^{2k+2}, &x\in(2+1,2+2)& \end{cases} \end{eqnarray}

Also, could you teach me how to write these functions in Grapher on MacOS? Cuz I want to know what they are like.

# Answer
Let's firstly imagine function $f$: for $k=2$ we have two intervals $(4,5)$ and $(5,6)$ and for $k=3$ we have two intervals $(6,7)$ and $(7,8)$. Accordingly for $f$ we have:

$$\quad\quad\quad x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\ f(x)\quad 2^4\quad\quad 2^5\quad\quad\quad 3^6 \quad\quad3^7$$ for function $g$ we have: $$\quad\quad\quad x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\ g(x)\quad 2^2\quad\quad 2^6\quad\quad\quad 3^4 \quad\quad3^8$$ So, as you see both $f$ and $g$ are increasing, but alternately one is more then other with more then constant factor, so they cannot be big-$O$ of each other.

To get an idea of an example you can take a look at DNA molecule chain  and imagine, that $f$ is one line and $g$ another.
> 1 votes

---
Tags: time-complexity
---


title: multicasting in ethernet

text:
# Question
Title: multicasting in ethernet
I am learning this topic and there is a concept that LSB ( bit ) of MSB ( byte ) should be set to 1 for multicasting . But why we need to do so as multicast address is unique so why can't we assign any multicast address which is not present in that network.

# Answer
Without a flag that tells you whether an address is a group address or a host address, you can't tell whether it's a group address or a host address.

Remember, a switch only sees the source address and the destination address. It does not have any extra information. So, it needs to be able to tell *just by looking at the address* whether to multicast the frame or not.
> 0 votes

---
Tags: computer-networks
---


# Question
Title: Fine-grained versioning of entities in programming languages
I have a question related to design, implementation of programming languages. I hope it fits here and apologize if it doesn't.

All or most programming languages version modules (aka packages, libraries, crates). All the entities in a module (types, functions, variables and other information) share the same version with the module. However usually only some parts of a module change between a version and the next.

When two different modules use different versions of the same third module, this creates an incompatibility.

* Some programming languages (for instance C and C++) ignore the problem altogether. They don't care about the version but only about the name and signature of entities. They accept programs that may crash or misbehave when executed, if different pieces of such programs expected different versions of a same entity that changed.
* Other programming languages (for instance Rust or Node.js) trait different versions of the same entity as two completely different entities. This avoid crashes, but introduces unnecessary incompatibilities between entities that did not change.

This can be a big problem for modules that define many different entities and that lots of other modules depend on, for instance the standard library of a programming language. Most programming languages use special tricks for their standard libraries: for instance they tie the standard library's version to the compiler version and require to recompile everything when the compiler version changes.

A better solution to this problem could be versioning every entity independently instead of whole modules. The GNU implementation of the standard library of C and C++ do this. I have seen some Rust crates do this too by importing their previous version and re-exposing all the symbols that didn't change. But these processes are very tedious and easy to get wrong, hence very few pieces of software adopt similar practices.

Do we know of any good way to version entities in a fine-grained way?

Has there been any research on this problem?

## A practical example

If the problem I described isn't clear, let me explain it with a practical example.

A module "time 1.0.0" defines loads of entities related to time. Among many others, it defines these two types:

```
type UnixTime   = uint32_t; # seconds from 1970 Jan 1
type UnixTimeNS = uint32_t; # nanoseconds from 1970 Jan 1

```

After "time 1.0.0" is out, we realize that `UnixTimeNS` is too small: it needs to be an `uint64_t`. We change that type and release "time 2.0.0" since we did an incompatible API change. Nothing else changed in the whole "time" module besides that `UnixTimeNS` type.

Two other modules "logger" and "totp" depend on "time". The former was developed on "time 1.0.0", while the latter uses "time 2.0.0". They both only use `time::UnixTime` and nothing else. This type did not change between the two version. But the compiler can't know that and treats `time_1.0.0::UnixTime` and `time_2.0.0::UnixTime` as different, incompatible types. It's now very hard to use both "logger" and "totp".

Imagine if they make a similar change to the standard library of any existing language: it could result in a tremendous split between new and existing modules, something as catastrophic as the switch from Python 2 to Python 3. All for a very minor change that affects 0.1% of the existing code.

I developed a rust crate (https://github.com/BlueNebulaDev/rust-version-test) and a Node.js package (https://github.com/BlueNebulaDev/node-version-test/) to show this problem in action. The names used in these projects differ from the ones in the example described here, but the meaning is the same.

# Answer
> 3 votes
The *Unison* programming language is based around two simple fundamental ideas:

What does that mean? Code being immutable means just what it sounds like: since code is immutable, it will never change. You can only ever add new code to the system, but you can never change or remove existing code.

Code being content-addressed means that all addresses (references) are based on the content of the code, not any names. And computing the content address is invariant under α-conversion by using De Bruijn indices in the code database.

This has some interesting implications: since you only reference functions, types, modules, variables, etc. by their content address and the content address is based on a name-less representation, you can rename anything and everything to your heart's desire, and never break any code. Also, since all references are based on content, and content never changes (remember, code is immutable), code that works at one time, will always continue to work until all eternity.

This poses an interesting question, though: How do you fix bugs?

One part of the puzzle is how names are handled in Unison. I wrote above that Unison's code model is based on addresses, but that doesn't mean that there are no names at all. It would be very annoying to write code like

```
#1uekd4 = #lle0xy #5q17cp #h8i067

```

instead of

```
fullName = concat firstName lastName

```

and having to remember all the addresses.

Instead, Unison also stores a mapping of names to addresses in its code database. This is similar to how Unix filesystems work: in a Unix filesystem, a file has no name, it only has a *file serial number*. However, there are *directories* (which are also files) which map names to serial numbers (which could point to regular files or to another directory). Also, Git works in a similar fashion. There are *blobs*, which only have content, and there are *trees* which assign names to addresses (which could be blobs or trees).

If you want to fix a bug, then you create a new version of the buggy function which doesn't have the bug. But all existing code still references the old function! (Remember, all addressing is based on content, not names.) So, you have to update every function that references the old function. And you have to update every function that references a function that references the old function.

Obviously, this gets tedious really fast. This is where *names* come in. After updating the function (really creating a new function), you also update the name database (really creating a new database) with a version where the name now points to the new, fixed, function.

Unison will notice this update, and will automatically propagate this name change through all existing functions. So, it will automatically update all functions that reference the buggy function to now reference the fixed function, then it will update the functions which reference the functions it just updated, and so on.

Where "automatically propagate" can mean one of two things:

* If the new function has the same type as the old one, Unison will automatically apply the update.
* If the new function has an incompatible type, Unison will create a to-do list with all the places that need to be changed.

Once the change is made, regardless of whether it was done aumatically or it required manual intervention, this change is recorded in a *patch* and becomes part of the code database as well. So, anybody else who pulls in the changes will benefit from the fact that you already resolved the issue and they can pull in the patch as well.

Bringing this to your example: since the *content* of `time::UnixTime` hasn't changed, it still has the same address, and since code is immutable, it is guaranteed that this address will refer to this type for all eternity. And since both `logger` and `totp` only refer to it by its address, which will never change, they, too, will continue to work unchanged for all eternity.

---
Tags: programming-languages
---


# Question
Title: Trust in online platforms dealing with virtual goods
I am implementing an online platform, where third-parties sell virtual goods to clients on a subscription basis. Let's take for example ebooks as a virtual good in this case.
How can the third-parties trust my platform? How can they know that I don't cheat with the number of subscriptions I report back to them? Do any solutions exist for this or some papers? I can't possibly be the first with this kind of problem. The problem is I even don't know what to search for.

# Answer
> -1 votes
As far as I know, sellers can't fully verify that the platform is behaving honestly, so you'll need to trust the platform. A malicious platform could always sell a copy to someone without giving the seller their cut.

# Answer
> -1 votes
Platforms stealing from sellers ? No way...

You could imagine a following scheme, encouraging random testing :

* Each time someone subscribes to something, you give a notification to the seller
* You encourage them to create dummy accounts/contact friends/random strangers with an account, and verify that their subscription is indeed notified
* To motivate these dummy subscriptions, you cancel these subscriptions for free on demand of the seller (so that they didn't have to pay the commission just to verify you're not scamming them)

This isn't foolproof (you could theoretically have algorithms to detect which subscriptions might be "test" subscription, typically brand-new accounts) ; but it's a good start, this kind of security means that you couldn't be scamming a lot of people (the biggest the platform, the more probable it is that someone would detect it).

---
Tags: game-theory
---


# Question
Title: Does the O(n) algorithm always run faster than the O(n^3) algorithm? Why?
Assuming that the time complexity of the two algorithms $A\_1$ and $A\_2$ to solve the same problem are $O(n^3)$ and $O(n)$ respectively. If you write programs for these two algorithms and run them in the same environment, does the program of algorithm $A\_2$ run faster than algorithm $A\_1$ for sure? why?

# Answer
$O(f(n))$ means: There is a constant c \> 0, and an integer $n\_0$, so that for every $n \> n\_0$ the time is less than $c \cdot f(n)$.

Note that the integer $n\_0$ could be very, very large. And the constant c could be very, very large. If $n ≤ n\_0$ then we know nothing whatsoever about the time; the $O(n)$ algorithm could be slower than the $O(n^3)$ algorithm until n is really large. And the constants could be very different. You could have an algorithm that takes $n$ years, and another that takes $n^3$ nanoseconds.

Just for fun, try to figure out for which n the O(n) algorithm is faster, and how long it runs when it runs faster. For example with n = 1,000,000 the first algorithm takes a million years, the second takes $10^{18}$ nanoseconds = $10^9$ seconds \< 32 years.

PS. When you look closely at the definition of $O(f(n))$, it doesn't actually say that our function must be anywhere near f(n). For example, $n^{1/2} = O(n^3)$ according to the definition. You'll often see $\Theta(f(n))$ (big-Theta) which means your function isn't just less than c * f(n) but between c1 * f(n) and c2 * f(n). And there are situations where a function doesn't behave the same for all values. Say sometimes it's close to n^3, but at other values n it's much smaller. If f(n) cannot be replaced with a smaller function then we call it "asymptotic O(f(n))".

So you could have f(n) = n if n is even, 1 otherwise. And g(n) = 1 if n is even, n^3 otherwise. For even n, f(n) is larger, for odd n, g(n) is larger.
> 4 votes

# Answer
$O(n)$ is subset of $O(n^3)$ i.e. $O(n) \subset O(n^3)$, which means, that algorithm which have $O(n)$ complexity also have $O(n^3)$. To be sure that one algorithm runs slower, then another, we need it to be in $O(n^3) \setminus O(n)$ or $O(n^3) \cap \Omega(n)$.

For explanation let's think about big-$O$ as about inequality - to be less then $n$ always mean to be less then $n^3$. To be less, then $n^3$ does not guarantee to be less then $n$, unless we explicitly require it.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: How can I verify a solution to Travelling Salesman Problem in polynomial time?
So, TSP (Travelling salesman problem) decision problem is **NP complete**.

But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is no way to find the optimal solution in polynomial time (which is because the problem is not in P)?

Anything that might help me see that the verification can in fact be done in polynomial time?

# Answer
To be more precise, we do *not* know if TSP is in $\mathsf{P}$. It is possible that it can be solved in polynomial time, even though perhaps the common belief is that $\mathsf{P} \neq \mathsf{NP}$. Now, recall what it means for a problem to be $\mathsf{NP}$-hard and $\mathsf{NP}$-complete, see for example my answer here. I believe your source of confusion stems from the definitions: an $\mathsf{NP}$-hard problem is not necessarily in $\mathsf{NP}$.

As you and the Wikipedia page you link states, the *decision problem* is $\mathsf{NP}$-complete: *given the costs and an integer $x$, decide whether there is a tour cheaper than $x$*. One way of seeing the problem is in $\mathsf{NP}$ is to see that given a solution, it is easy to verify in polynomial time whether the solution is cheaper than $x$. How can you do this? Just follow the tour given, record its total cost and finally compare the total cost to $x$.
> 22 votes

# Answer
The crux is that you have to consider the *decision* problem:

> **Travelling Salesman Problem (Decision Version).** Given a weighted graph *G* and a target cost *C*, is there a Hamiltonian cycle in *G* whose weight *is at most C*?

For a 'yes' instance, the certificate is just some Hamiltonian cycle whose weight is at most *C*. If you could solve this problem efficiently, you could find the cost of a minimum tour by binary search, starting with the weight of the entire network as an upper bound.
> 37 votes

# Answer
You are probably thinking of the problem of determining whether a given solution to the TSP is the **best** solution. However, there is no known polynomial solution for this, which means that this problem is in NP-hard, but not necessarily NP-Complete.

The TSP *Decision Problem* is actually about determining whether the weight of any solution in a graph `G` is at most cost `C` (as explained better in Niel's answer), which is certainly verifiable in polynomial time.
> 6 votes

# Answer
You can show that it is optimal given an oracle that solves the decision problem (see other answers) in polynomial time by querying if there exists a shorter solution. If your goal is to construct an optimal solution given the oracle, proceed as follows. Find the minimum total weight via binary search (or if there are non-integer edge weights, find a total weight which differs from the minimum by less than the min difference between two edge weights). Call this value $M$. For each edge in the graph, remove the edge, and query the oracle to see if there is still a solution of at most $M$. If so, leave the edge out, and continue. If not, put the edge back in, and continue. When you've processed all the edges, you'll be left with a Hamiltonian cycle of minimum weight.
> 2 votes

# Answer
In your first sentence you mixed up "decision problem" and "optimality problem". They are different problems. One is: Given a list of cities and a distance d, can you visit all cities with a tour of length ≤ d? This is easily verified in linear time if I give you a sorted list of the cities. The other is: Given a list of cities, what is the shortest possible tour to visit all cities? Or the cities, and a tour, is that tour the shortest possible tour?

The first is a decision problem clearly in NP. The second is not a decision problem. The third is a decision problem, but not known to be in NP. (It is in co-NP).
> 1 votes

---
Tags: complexity-theory, np-complete, traveling-salesman
---


# Question
Title: Interesting Speedup & Amdahl's law problem
I have found a problem on my Computer Architecture textbook which I have some issues with:

> We have a process which spends its time in the following way:
>
> * **50%** of the time, it executes common arithmetic (non-floating point) instructions
> * **10%** of the time, it executes floating point instructions
> * **40%** of the time, it executes a function which has **4816896** instructions, **which is 60% of the total of instructions**
>
> After improving the function's algorithm, we end up with **983040 instructions** executed on the function instead.
>
> Assuming that **each instruction is executed in one cycle**, it asks about the performance improvement after this instruction number reduction.

By calculating the speedUp in CPI before and after in the improved functions (4,9), and then using Amdahl's law, we get an increase of 46,7% in performance.

After this, it asks to calculate the speedUp again, but this time by checking the increase in **MFLOPs**.

How could this be done if we don't know anything about execution times?

# Answer
> 1 votes
You can calculate the *speedup* in MFLOPs. Speedup is a dimensionless quantity, so you don't need to know the execution time to calculate it.

You need to know the old execution time only if you need to find out the improved execution time.

---

In this problem, we can calculate the increase in MFLOPS by dividing the ratio of Floating point instructions to total number of instructions after improvement by the ratio of Floating point instructions to total number of instructions before improvement, since the Cycles Per Instruction is 1 and clock cycle time remains the same.

Increase in MFLOPS = $\dfrac{(Ratio\ of\ Floating\ point\ instructions\ to\ total\ number\ of\ instructions\ after\ improvement)} {(Ratio\ of\ Floating\ point\ instructions\ to\ total\ number\ of\ instructions\ before\ improvement)} $

---
Tags: computer-architecture, performance
---


title: When LP solution is ILP solution?

text:
# Question
Title: When LP solution is ILP solution?
For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x\_i \in \\{0, 1\\}$ we allow $x\_i \in \[0, 1\]$. In certain cases, the original problem is an integer linear programming (ILP) problem, and its relaxed version becomes a linear programming (LP) problem, which we can efficiently solve.

**Questions:** Are there common techniques which show that, for a particular problem:

1. An LP solution will always be an ILP solution?
2. There exists an LP solution that is also an ILP solution?
3. A particular LP algorithm (e.g. simplex method) finds an ILP solution.

By "solution", I, of course, mean a vector on which the objective reaches its optimum.

# Answer
Consider a linear program of the following form: maximize $c^Tx$ over $Ax \leq b$, where $x \in \mathbb{R}^n$ and $b$ has integer entries.

The simplex algorithm finds a solution of the form $x = A\_S^{-1} b\_S$, where $A\_S$ is a submatrix consisting of $n$ rows, and $b\_S$ are the corresponding entries of $b$. Each entry of $A\_S^{-1}$ is a ratio of two determinants: the determinant of some $(n-1)\times(n-1)$ submatrix of $A$ (namely, minors of $A\_S$), and the determinant of some $n \times n$ submatrix of $A$ (namely, $A\_S$). If the entries of $A$ are integers and every $n \times n$ submatrix has determinant $0,\pm 1$, then $A\_S^{-1}b$ is integral.

The condition that any square submatrix has determinant $0,\pm 1$ is known as total unimodularity. If the constraint matrix $A$ is totally unimodular, then the simplex algorithm will always find an integral solution.

A more general condition is total dual integrality, which just states that for every integral $c$, the linear program has an integer optimal solution. If the system satisfies TDI then the simplex algorithm is also guaranteed to find an integral solution.
> 1 votes

---
Tags: linear-programming, integer-programming
---


# Question
Title: OS: Why is it necessary to have hardware support for implementing Preemptive Scheduling Strategies?
I think, Preemption can easily be done in kernel mode, where it just have to call the Context-Switch procedure. Also, based on algorithm we can select the new process from the ready queue as well...

I'm unable to think and find Why and where the role of timers come and what exactly are significance of Hardware in preemptive scheduling.

Can we not do preemptive scheduling without hardware support?

Why I didn't ask on Stack-overflow?

=\> I need the theoretical point, although I'll appreciate if someone mentions the actual implementations of Unix.

# Answer
> 3 votes
A preemptive scheduler must stop a program that is looping and not calling any operating system function. The program is not triggering any fault as division by zero. We are assuming that the interrupt are enabled and assuming single core processor. Only a timer interrupt can succeed to regain control of the processor. The rate set by this timer gives you the maximum switching time for the scheduler. The preferred value is 1000 Hz which gives 1 ms resolution. For computers not fast enough to allow so many timer interrupt per second, the next popular values were: 60 Hz, from the video card refresh rate 18 Hz, from a 16 bit overflow of IBM PC original timer chips ; color TV cristal of 3.59 MHz / 3 / 65536

Other option: cooperative multitasking. This is how apollo computer managed to run many tasks... As well as Windows 3.1 You call a lightweight scheduler everywhere your code perform long loops. The lightweight scheduler usually just decrement an integer and immediately return if the value still not zero. For the rare case where the integer reach zero, immediately set that integer to the default value and perform the next tests to decide if a new task with higher priority needs to be executed. If a precise timing is needed, then at this point, reading a hardware timer counter and comparing the value with the previous one allow to evaluate precisely the elapsed time.

---
Tags: process-scheduling, os-kernel
---


# Question
Title: How do computers *really* work? (at the most basic level)
While learning about computers I will read about RAM and Storage and the CPU, and while these explain the architecture of a computer and how parts of a computer work together, I still don't understand the fundamental workings of a computer program.

Let me take an example.
I'm on the web on a mac right now. When I push two fingers away from me on the trackpad, I understand that the trackpad is made up of a capacitive touch screen that, when your finger is placed on it, draws current and the trackpad detects that and converts it into data that explains the movement of my fingers up the screen.

However, when you have this data in binary form, or machine code, it goes through logic gates and other things to make it in scroll down on the page. But what is actually happening here? How would the computer have physical things that operate differently based on the input? What operations are carried out on the machine code that says "if data looks like 01001010 10101010... send instruction 10010010... to CPU that tells computer to scroll down". Surely if you had some logic gates that turned input x into output y, yes they would give different outputs based on the input, but unless you somehow redirected the current to the right set of logic gates every time the action was carried out, how would it go to the correct one? To me this step is still magic. Especially with computers now that have no moving parts it seems even more alien.

Could someone explain this to me?

# Answer
> 5 votes
This is a complex matter. To begin with, when you move your mouse, there is so much going on at once, that I cannot even begin to explain everything here. So, I will focus on the most fundamental thing: How does the computer actually compute?

As you are probably familiar with, computers have memory called RAM, and a CPU that is able to execute "commands". Commands, are essentially some form of data, that allows the computer to decide which logic gates to pass the input to.

At its core, this is the work of the ALU in the CPU. ALU stands for Arithmetic Logic Unit, and it had *three* inputs, contrary to what you may think. The first two inputs are normal inputs for the operations, for example: two numbers $a,b$ that we want to sum up. The third input, decides what operation to do on them. For example, you can encode that "0001" means we want to sum the two numbers, while "0010" might mean multiplication and "0011" is division. This ALU does this magic!

This "magic" that decides based on the third input which operation to do, is done via applying a multiplexer circuit to take the output from the correct series of logic gates in the ALU.

Basically, an $n$-to-$1$ multiplexer is given $n$ "normal" inputs, and one "special" input that decides which of the $n$ inputs to output. Yes, it simply outputs one of its inputs without changing anything. Basically, if we think of its inputs as an list $inp$, and the "special" input is called $s$, then the output is $inp\[s\]$.

The ALU takes this, and gives to it as the $inp$ the list of all possible operations on the two numbers $a,b$, and thats how the ALU knows which operation to apply when.

# Answer
> 0 votes
The microprocessor has to read an I/O port that is connected to the mouse or track pad. The information is probably using more than one byte (8 bit) or one 'word' (32 bit), so the processor either read the same port many times or has other way to get the position of your fingers on the device. The information must be saved in RAM because the internal memory in the processor is too precious to waste with that kind of information. Now, you mention that, on your Mac computer, touching that device trigger printing something of the screen. So, as the processor finished to read the data from the trackpad, the next operation performed by the operating system or the app is to call a function which uses a input parameter the new position if your finger on the trackpad. The function compare with the previous position to decide which pixels to erase and which pixels to add on the screen. When ready, the function call a function to print. That function look at the X/Y position to make sure it is visible on the window. It also check if other window are sitting on top. If all conditions are good, the processor must send so many write commands to the video card controller to specify every pixels to repaint. The video controller save that information to its own video RAM, then do nothing else. Meanwhile, an independent group of digital circuit is reading asynchronously the video RAM to refresh the LCD display. Eventually, after one full scan vertically, the new position of your finger becomes visible on the monitor.

---
Tags: computer-architecture, logic, cpu, binary
---


# Question
Title: Efficient way to implement periodic events
I need to implement a system that can schedule and dispatch periodic jobs and needs to support a very high load (millions of jobs per second). Each job in the system has a period that is some multiple of 15 seconds, with the maximum allowed period being 1 day.

The system needs to support adding new jobs and removing / replacing existing jobs. However, these occur relatively infrequently (aside from when the system starts up and has to add the initial batch of jobs), so it is okay to make trade-offs with regards to insertion / deletion time.

Jobs scheduling times should be spread out so as to avoid "spikes" in number jobs dispatched. For example, if we had a million jobs that all had a period of 15 seconds, we wouldn't want to dispatch all of them at the exact same time every 15 seconds, and then wait another 15 seconds not doing anything before doing it again. It would be better to spread them out so around 60-70k jobs are dispatched every second, as long as each job is still scheduled to run 15 seconds apart.

Currently, around 10% (maybe less) of the jobs in the system have a period of 15 seconds (the minimum possible), while the remaining jobs have periods between 30 seconds and 1 day.

Our current implementation uses something like a hashed timer wheel, which has 15,000 buckets representing the number of milliseconds in every 15 second interval. Jobs are added to a random bucket in the wheel, and on every tick of the wheel, we iterate through every job in the bucket, dispatching the ones that are "expired" and incrementing a counter for the remaining jobs. For example, a job with a 60 second period would only be dispatched once every 4 turns of the wheel, even though it is iterated over on every turn of the wheel. The problem here is that on each tick of the wheel, the majority of the jobs in the next bucket are not actually ready to be dispatched, but we have to iterate over them anyways to increment their counter.

Is there a better algorithm / data structure I can use to make this more efficient? I am considering implementing hierarchical timing wheels, so that the only times we need to iterate over a job are when it is re-inserted into a lower wheel, or when it is ready to be dispatched. My concern with this approach though, is that unlike the current hashed timer wheel approach, we need to remove and re-insert the job every time its period expires.

# Answer
A standard approach for scheduling is a priority queue of future jobs: each job has a time at which it should be dispatched, and that time is the key for the priority queue.

When a new job arrives, pick a random time within its period, and schedule it to occur at that period. For instance, if a job arrives with a period of 75 seconds, pick a random number $t$ in the range \[0,75), then schedule it to be first dispatched $t$ seconds from now. To schedule it, add it to the priority queue with its dispatch time as the key.

Each second, retrieve all jobs scheduled to be dispatched in this second, delete them from the priority queue, and dispatch them. Also schedule each to occur at a time in the future based on its period (thus inserting it back into the priority queue with a later dispatch time).

The randomization should ensure a reasonable balance of jobs, especially when you have a large number of jobs to schedule, and the priority queue should make it efficient to insert, delete, and dispatch jobs. In particular, all of those operations can be done in $O(\log n)$ time, where $n$ is the number of jobs.

You could check whether that will meet your requirements. If not, that should help clarify your specific requirements.
> 2 votes

# Answer
Your current design is already very efficient in both CPU time and memory usage. One way to increase performance at the cost of memory is to create a few copy of the hash table, each one containing objects sorted by range of remaining time. For example, one hash table contains every objects with more than 1 hour remaining time. Once an hour, you scan the entire hash table and subtract one hour to each (240 units of 15 second). If the new count brings the remaining to one hour or less, move it to the original hash table. Using only two hash table would speed up your process by a factor of 240 in the worst case or about 120 if the distribution is random.

Since we are just performing integer operation in a compact array, the timing of updating the second hash once an hour very low. Moving the objects to the first hash at least one hour before they expire also warranty no sudden rush of large amount of.process to dispatch once per hour.
> 1 votes

---
Tags: algorithms
---


# Question
Title: CFG of all regular expressions over a binary alphabet
I'm working on creating a rather difficult CFG and I am getting stuck on finishing it. The CFG in question is meant to contain all valid regular expressions using the alphabet {0, 1, (, ), \*, +, e} (e for epsilon).

Some examples I know that should be accepted are things like:

* e
* 0
* 01
* 1010
* 0\*1\*0\*1\*
* 0\*11+(10)\*+(e+1\*0\*)
* ((100\*)\*(10\*)\*)\*

While things such as these would be rejected:

* ee
* )(e+1\*)\*
* (10)\*++(

et cetera

I've been building up case by case and I have this rather ugly looking CFG that prevents most incorrect cases, but it does not come close to getting all the correct ones

S → (N) | M+M | N | (N)\*

M → 0N | 1N | 0*N | 1*N | (N) | (N)\* | M+M | e

N → 0N | 1N | 0*N | 1*N | ɛ

Apologies if this has been asked before, I tried searching everywhere here and on Google and I was not able to find someone else trying to create the same or similar CFG, but if this is a repeat I'd appreciate being pointed to the original!!

If helpful, I've been using this tool to test my CFG: https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/

# Answer
> 1 votes
You are quite close to the solution. We will use a few variables, each corresponding (intuitively) to some other "thing". Specifically, we will use the variables $S,E,A,B$.

$S$ is the starting variable. $E$ is a variable that will produce a valid regular expression (its called $E$ as short for "expression"). $A$ will be some valid string over the alphabet $\\{0, 1\\}$, and $B$ will be a non-empty string over that same alphabet.

The CFG will now be:

$S\rightarrow E$

$E \rightarrow (E)(E) \space | \space E+E \space|\space E^\* \space | \space (E) \space|\space A$

$A\rightarrow B\space |\space e$

$B \rightarrow 0B \space | \space 1B \space | \space 0 \space | \space 1$

I hope this CFG is what you are looking for! (I don't know if it is, since you didn't state the definition of the syntax of a regular expression using this alphabet, so I have only tried to go by the examples)

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


# Question
Title: Longest common subsequence solution reconstruction during DP is wrong
I've implemented longest common substring in `python`. I know the usual way to reconstruct the path. But, I am reading my algorithm many times, I don't understand why it doesn't work for some test-cases. I am trying to construct the solution while the longest path is being made through dynamic programming.

```
def lcs(s1, s2):
    n = len(s1)
    m = len(s2)

    trow = [0] * (m+1)
    table = [trow] * (n+1)

    srow = [""] * (m+1)
    solution = [srow] * (n+1)

    for i in range(1, n+1):
        for j in range(1, m+1):
            if s1[i-1] == s2[j-1]:
                table[i][j] = table[i-1][j-1] + 1

                # Adding this character to the solution
                solution[i][j] = solution[i-1][j-1] + s1[i-1]

            elif table[i][j-1] > table[i-1][j]:
                table[i][j] = table[i][j-1]

                # Choosing the solution related to the longer path
                solution[i][j] = solution[i][j-1]

            else:
                table[i][j] = table[i-1][j]

                # Choosing the solution related to the longer path
                solution[i][j] = solution[i-1][j]

    return solution[n-1][m-1]

```

```
lcs('amin', 'kahmjiknln')
# Returns 'amin'

lcs('amin', 'aaaakahmjiknln')
# Returns 'aaaaamin'

```

# Answer
Lets deal with the issues one at a time, since there are a few of them.

## Problem 1

Take a look at those lines of code:

```
trow = [0] * (m+1)
table = [trow] * (n+1)

srow = [""] * (m+1)
solution = [srow] * (n+1)

```

The problem with this code, is that the *same* list is being placed a few times. This means, that every list in $table$ must be all identical to $trow$ **at all times.** By changing one of the values in there, it will change all of them. For example, if $m=n=1$, then `table == [[0,0],[0,0]]`. Now, assume we somehow did this update: `table[0][1] = 9`. Then, we will have `table == [[0, 9], [0, 9]]` since $table$ contains the *same* list *twice*. This is essentially caused because lists are just pointers, and thus if you just copy the value in them it will just copy the pointer. A similar behavior can be seen in this code:

```
a = 5 # a == 5
b = a # a == 5, b == 5
b = 10 # a == 5, b == 10

A = [0, 1] # A == [0, 1]
B = A # A == [0, 1], B == [0, 1], A is B
B[0] = 9 # A == [9, 1], B == [9, 1], A is B

```

Here, the same thing happened: $a$ is not a list and therefore was copied as expected, but $A$ is a list and thus only the pointer to it was copied to $B$. A change in $B$ changed $A$ as well.

Back to your question. How to fix it, you ask? Like so:

```
table = [[0 for _ in range(m + 1)] for _ in range(n + 1)]

solution = [["" for _ in range(m + 1)] for _ in range(n + 1)]

```

## Problem 2

You have a slight problem with the indices. Since $solution$ is an $(n+1)$-by-$(m+1)$ matrix, you want `solution[n][m]` instead of `solution[n - 1][m - 1]`
> 1 votes

# Answer
Programming questions are off-topic here. Anyway your matrices `table` and `solution` are not properly initialized as they contain references to the same objects. Try:

```
    table = [[0]*(m+1) for j in range(n+1)]
    solution = [ ["" for i in range(m+1)] for j in range(n+1) ]

```

Moreover, the returned string should be `solution[n][m]` and not `solution[n-1][m-1]`.
> 1 votes

---
Tags: dynamic-programming, python
---


# Question
Title: Representation of unsigned integer on a little endian, big endian computer
This is a GATE 2021 exam question.

> If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer, which of the following choices represent(s) the unsigned integer on a little endian computer?
>
> A. 0x6665
> B. 0×0001
> C. 0×4243
> D. 0×0100

According to me, answer should be A,D. But according to some of my colleagues, answer is B,C.

My logic for answer being A,D :
The question is asking “which of the following choices represent(s) the unsigned integer on a little endian computer?”

Take Option “0x6665” :

The question is saying that 0x6665 is the representation of some integer on a little endian computer, so, it means that the original number must have been 0x6566.
So, for the original number 0x6566 :
On little endian(LE) : 0x6665
On Big endian(BE) : 0x6566

Clearly, LE = 255 + BE

Similarly, for 0x0100. Take 0x0100 :
He is saying that 0x0100 is the representation of some integer on a little endian computer, so, it means that the original number must have been 0x0001.

So, for the number 0x0001 :
On little endian(LE) : 0x0100
On Big endian(BE) : 0x0001

Clearly, LE = 255 + BE

Similarly for 0x4243 and 0x0001, They do not satisfy “LE = 255 + BE” condition , So, answer should be option A,D.

For Reference, Refer Slide 26 in the below article :
https://www.cs.utexas.edu/~byoung/cs429/slides2-bits-bytes.pdf

# Answer
> If the numerical value of a 2-byte unsigned integer on a little endian computer is 255 more than that on a big endian computer

According to the dictionary, the definition of "numerical value" is "a real number regardless of its sign", in other words absolute value. Since the integer is unsigned, its numerical value is itself, and that will not change no matter how the integer is stored, little or big endian style, written on a napkin with lipstick in base seven, notches on a bedpost, or whatever. Therefore, the first line of the question is meaningless, which is always a nice start.

Additionally, the question confuses memory representation and integers. Two bytes in memory that look like (0x00,0x01) represent the integer 0x0100 in little-endian mode, but you can't say "let's add 255 to (0x00,0x01)" because (0x00,0x01) is not the number 0x0001 although it looks like it.

A correctly worded question would be:

"There are two bytes in memory. A big-endian cpu reads them with a uint16 load instruction and gets an uint16 value. A little-endian cpu reads the same two bytes and gets an uint16 value that is 255 higher than the big-endian cpu's value. What are the two bytes in memory?"

(One could also ask what uint16 one of the cpus gets)

Then it's pretty simple:

```
Memory    uint16     uint16
dump      read by LE read by BE
0x66 65   0x6566     0x6665
0x65 66   0x6665     0x6566    correct
0×00 01   0x0100     0x0001    correct
0×01 00   0x0001     0x0100
0×42 43   0x4342     0x4243    correct
0×43 42   0x4243     0x4342

```

> According to me, answer should be A,D. But according to some of my colleagues, answer is B,C.

Having nuked the question, let's play jeopardy and try to figure out what question you and your colleagues are answering.

Basically, to misquote a famous crook, you're having a disagreement over what the word "represents" represents. One thinks it is the memory representation in little-endian (although it is written wrong in the question, and honestly if the word "memory" was mentioned it wouldn't hurt for ease of comprehension) and the other thinks it's the integer itself (probably because the 0x values are written as integers not bytes). So you're both picking from a different column of my table above.

We will have to wait for the end of the war between little endians and big endians to know what the peace treaty says about who's right.

Another way to not fix the question would be: **If the memory representation** of a 2-byte unsigned integer on a little endian computer **looks like** it is 255 more than that on a big endian computer **to a human reading the memory bytes in big endian order**, which of the following choices represent(s) the unsigned integer?

However, this reveals to all the rampant systemic endianness supremacy asserting that humans of the wrong endianness are lower-class citizens. This implicit endianness bias and oppression must stop! As of today, the DIE commitee dictates that everyone will switch to the more inclusive and safe middle-endianness, and both-endians colonizers will be sentenced to pay reparations to native middle-endians.
> 5 votes

# Answer
In little endian, the least significant byte is the first you read. It means that 0x6665 (LE) should be read as $$0\text{x}6665 \text{ (LE)} =(0\text{x}66) + (0\text{x}65) \times 256 = 102 + 101\times256 = 25958$$ If you read 0x6665 in big endian, you read the most significant byte first, and you get : $$0\text{x}6665 \text{ (BE)} = (0\text{x}66) \times 256 + (0\text{x}65) = 102\times 256 + 101 =26213= 25958 +255$$ We have LE = BE - 255, so answer A is incorrect. The right answers are B and C.
> 1 votes

# Answer
What’s interesting is that you don’t even need to know how bigendian and littlendian numbers are stored in memory, just that they are stored in opposite order!

Assume that two bytes aa and bb are stored in memory, and interpreting these bytes as a littleendian 16 bit integer gives a value of 0xaabb = 256a + b. Interpreting the same two bytes as bigendian would give a value 0xbbaa = a + 256b.

You are told the first value is 255 larger than the second, so 256a + b = a + 256b + 255, or 255a = 255b + 255, or a = b + 1. 0x0100, 0x4342 etc. would be solutions.

That said, whoever wrote the question is showing a very muddled thinking about what bigendian and littleendian means. Numbers are not bigendian or littleendian. They are just numbers. The same number will have the same value on any computer. On a computer where you can access memory in units less than 16 bits, you can store a 16 bit integer and read the bytes individually. The result is called the “representation” of the integer. This representation can be different, the numbers are not. And there is no reason why computers would be restricted to just two representations. A computer could store all the even bits in one byte and all the odd bits in the other byte, for example.
> 0 votes

# Answer
The way the question is framed, I do not agree with the concept at all.

> A number is after all a number, be it big endian or little endian.

The main concept of Big endian or little endian is as follows:

**Big Endian**: In computer system which is big endian, the lower order byte of the data in the memory maps to the higher (big) order byte of the registers in CPU. (see figure below)

**Little Endian**: In computer system which is little endian, the lower order byte of the data in the memory maps to the lower (little) order byte of the registers in CPU. (see figure below)

As such, the whatever be the system type (Big or little endian) the number should actually be the same in the registers in the CPU, as the ALU knows one and only one representation of a number which is binary equivalent of a number.

The difference arises in the way the number is STORED IN THE MAIN MEMORY.

This makes the things a bit ambiguous.

Assuming they are talking about the representation of the number in main memory. (memory dump)

i.e. $ \text{Memory\[0\]Memory\[1\]}$ \[A complete word\] (see figure below)

This ambiguity can be resolved by the way the question is asked.

From the above concept we can see that: what ever be byte sequence we assume for LITTLE ENDIAN, that byte sequence shall be reversed for BIG ENDIAN.

Option A: $$0x6665–0x6566=FF=(255)\_{10}$$

Option D: $$0x0100–0x0001=FF=(255)\_{10}$$

In other cases, (option B or C, assuming the given option and reversing the byte sequence gives a number greater than the option, as per the question the little endian value is greater)
> 0 votes

# Answer
2,3 is answer.

If you split hex number into bytes.. In hexa representation, each digit corresponds to 4 binary digits.... (I.e 2 hex digits =8 bits= 1 byte).

If little endian representation is

(byte-n).....(byte-2)(byte-1) then

Big endian representation is

(byte-1)(byte-2).....(byte-n)

With in the byte no change in bit sequence.

A) 0x0001

Little endian 0x0001 gives you 01 as first byte and 00 as second byte.... So corresponding big endian representation is 0x0100. Hex (0x0001) is equal to 1 in decimal Hex(0x0100) is equal to 256 in decimal. Their difference is -255.

B) 0x6665

Little endian 0x6665 gives you 65as first byte and 66 as second byte.... So corresponding big endian representation is 0x6566. Hex (0x6665) is equal to 26213 in decimal Hex(0x6566) is equal to 25958 in decimal. Their difference is 255.

C) 0x0100

Little endian 0x0100 gives you 00 as first byte and 01 as second byte.... So corresponding big endian representation is 0x0100 Hex(0x0100) is equal to 256 in decimal. Hex (0x0001) is equal to 1 in decimal

Their difference is 255.

D)0x4243

Little endian 0x4243 gives you 43 as first byte and 42 as second byte.... So corresponding big endian representation is 0x4342 Hex(0x4243) is equal to 16963 in decimal. Hex (0x4342) is equal to 17218 in decimal. Their difference is -255.

So...2,3 is answer

( tip: the little endian value of a 4 digit hexnumber is more, if number formed by first 2 hex digits is more than the number formed by the last two digits of the number)
> 0 votes

# Answer
The answer is A and D. The 16 bit values are printed by the LE machine. The extra 255 is visible.only on the big endian machine. The question could have been made more confusing by inducing doubt about nibble (4 bit) location, but the teacher carefully avoided all ambiguity by using a difference where two consecutive nibble are identical. In other words, 255 is chosen so that all 8 bits, whether seen as D7-D0 or D15-D8 are the same, namely all "1" in binary. 0x6665,0x65,0x66+0x00FF=0x6665 0x0001,0x01,0x00+0x00FF=0x01FF 0x4243,0x43,0x42+0x00FF=0x4441 0x0100,0x00,0x01+0x00FF=0x0100

The question appears as clear as cristal\* to me. \*California says cristal may contain lead which can be harmful if you are pregnant. Ask your doctor if you can have little endian mixed with your big endian.
> 0 votes

---
Tags: computer-architecture, operating-systems
---


title: Algorithm to travel all edges only once

text:
# Question
Title: Algorithm to travel all edges only once
I have a directed, unweighted graph that obeys the following rules:

* The number of nodes and edges is finite
* Each node can eventually be reached from any other node by some path
* Each node has an equal number of incoming and outgoing edges

Like this:

I am trying to develop and algorithm that starts in any node and travels each edge of the map once and only once but I'm struggling to come up with anything.

I've thought about finding an algorithm to hit each node and then following it out and back but this can easily be done without traveling every path. (In the graph above you could go a-\>d-\>g-\>e-\>b-\>c-\>f-\>c-\>b-\>e-\>g-\>d-\>a but never hit the paths connecting d to e or the paths connecting e to f)

I've also tried to come up with something like the corn maze solution where you always take the left most available path, but this too has the potential to leave out large chunks of the graph. (you could go a-\>d-\>a and think you were done)

I think in order to do this I probably need to be keeping track of which nodes I've already visited and how many remaining untraveled edges it had and always choose to travel to the node with the max remaining untraveled edges. But I feel like this has errors too where I could trap myself into part of the graph  though I haven't found a good example where it does so. Any way to prove the correctness of this or find a counterexample (and in that case maybe thoughts on a new possibility) would be greatly appreciated! I've found a counter example:

Consider the following graph with moves marked in red and remaining count at each node marked in blue, at this point, you are in node b, and can move to either a or c because they are equally weighted, if you move to a, you have effectively cut yourself off from ever traveling the b-\>c paths.

So now I'm at even more of a loss :/

# Answer
> 4 votes
You are trying to find an Euleran path in a graph.

Observe, that if each node has equal number of incoming and outcoming edges, every time you enter a node using an edge you have not used before, there is an unused outgoing edge. The only vertex that does not have this property is the starting vertex. Therefore, *any* path that starts in vertex $v$ can either be easily extended or end in $v$, resulting in a cycle.

The only problem we now have to take care about is covering all the edges. After you finish a cycle and can't proceed, take any vertex $t$, which is in your cycle and has some unused edges. Start a new cycle from $t$, obviously using only unused edges. Connect the new cycle with the old one. Iterate until finished.

# Answer
> 2 votes
Though this is from 4 years ago, another way to solve this is by finding the Hamiltonian Path of the Line Graph of G. Just convert each edge to a vertex and connect those vertices if the corresponding edges shared a vertex in G. (Respecting the directions in this case.)

So the line graph would look like this, each vertex is labeled with the direction of the edge in G. So finding the hamiltonian path of this directed graph, gives the Eulerian path of G.

---
Tags: algorithms, graphs
---


title: CYK algorithm in theory of computation

text:
# Question
Title: CYK algorithm in theory of computation
For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n.

Doubt: I marked it false in a national level exam.I think it should be any null-free context free grammar and not any cfg because we first have to convert cfg to cnf but only null free cfg can be converted to cnf.

Is this statement correct?

# Answer
It's true.

If the CFG is not null free, and the input sentence is not null, you can remove the null from the CFG and then parse the input sentence with the resulting grammar. You already know how to do that in cubic time.

If the CFG is not null free, and the input sentence is null, you can immediately tell whether the input sentence is accepted by the CFG.
> 3 votes

---
Tags: context-free, parsers, chomsky-hierarchy
---


# Question
Title: Does loop invariant has nothing to do with termination?
Consider the following program fragment:

```
var x, y: integer;
x := 1;
y := 0;

while y < x do
begin
    x := 2*x;
    y := y+1
end;

```

For the above fragment, which of the following is a loop invariant?

(A)x=y+1

(B)x=(y+1)^2

(C)x=(y+1)2^y

(D)x=2^y

(E)None of the above, since the loop does not terminate

As per my solution, the loop never seems to terminate. I came with the answer E but the D is the answer to the above questions. Isn't the loop invariant affected by the nontermination of the loop?

# Answer
The loop invariant is just a proposition which holds on each iteration of the loop (in your question, the relationship between $x$ and $y$ holds regardless, so no, it is not affected by loop nontermination). It doesn't inherently say anything about termination. It is potentially something that you can use to argue about termination.

The Wikipedia article on correctness additionally describes the difference between partial and total correctness. For partial correctness, we don't require a program terminates, only that the result is correct if it is returned.
> 2 votes

---
Tags: loop-invariants
---


# Question
Title: Efficient algorithm to compute the diameter of a convex set?
Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?

It is possible to do it efficiently for a set of points, but imagine that the set is described by the intersection of linear equations in high dimensional space, so the number of vertices of the set can be exponential in the number of inequalities.

Given a direction, we can easily compute the distance of furthest points along that direction using linear programming. The question is how do we find that direction?

# Answer
> 3 votes
I suspect that if the points in your set are expressed as $Ax \le b$ and you're considering the Euclidean distance, then you can solve the following quadratic program with the ellipsoid method:

$$ \max \sum\_i (x^2\_i+y^2\_i-2x\_i y\_i) \\ Ax \le b \\ Ay \le b. $$

Where we used the fact that optimizing $|x-y|$ is the same as optimizing $ \frac{1}{2} |x-y|^2 = \frac{1}{2} \sum\_i (x\_i-y\_i)^2 = \frac{1}{2} \sum\_i (x\_i^2+y\_i^2 - 2x\_iy\_i)$. The objective function can also be written as $\frac{1}{2} z^T Q z$, where $z=(x,y)$ and: $$ Q= \begin{bmatrix} I & -I \\ -I & I \end{bmatrix}. $$

---
Tags: complexity-theory, optimization, computational-geometry, linear-programming, convex-hull
---