title: How does MAC layer back-off work?

text:
# Question
Title: How does MAC layer back-off work?
How does it help avoid frame collisions? Are there any rules for when the back off is allowed, especially in the case of wireless networks?

# Answer
> 1 votes
Warning: the following is based on a presentation I created for a graduate course that I took in March 2008 (Chionglo 2008a; 2008b). Thus some ideas or terms may not be up to date.

I will assume that you are referring to the IEEE 802 standard method of organizing networking components because you used the acronym “MAC”.

“How does a MAC layer back-off work?” (2016) is a broad question because there is more than one method for performing the functions at the MAC layer. The IEEE 802.3 MAC is an example of a standard that describes a method for operating at the MAC layer. It has two components: transmit frame component and receive frame component. Transit frame component has three parts: deference process, normal operation, and collision handling procedure. For the collision handling procedure, if the Physical Layer indicates to the MAC layer that a collision has occurred then the IEEE 802.3 MAC layer responds to the indication by

1. Suspending its transmission.
2. Sending out a jamming signal.
3. If the number of attempts to resend the frame is less than 16 then waits an additional period of time before attempting to resend the frame (back-off).
4. If the number of attempts to resend the frame exceeds 15 then it aborts the transmission and indicates to its client (the Logical Link Control Layer) than an error has occurred.

## References

Chionglo, J. F. (2008a). IEEE 802.3 Media Access Control \[Graduate course presentation\]. FIS 2166 Telecommunications for Information Systems, Faculty of Information \[Studies\], University of Toronto. Delivered on March 25, 2008.

Chionglo, J. F. (2008b). IEEE 802.3 Media Access Control \[Graduate course presentation: text of speech\]. FIS 2166 Telecommunications for Information Systems, Faculty of Information \[Studies\], University of Toronto. Delivered on March 25, 2008.

How does MAC layer back-off work?” (2016). Computer Science Stack Exchange.

---
Tags: computer-networks
---


# Question
Title: Algorithm to find shortest lightest path in a graph from source
Given a directed graph $ G = (V,E)$ with non-negative(zero and positive) weights on the edges, and a vertex $ s \in V $

**Problem:** Find the lightest path from $s $ to each and every vertex $v \in V$ and that's from the shortest paths from $ s$ to all $v \in V$

*Length of a path* is the number of edges in the path.

*Weight of a path* is the sum of all weights of the path's edges

**-------- Edit: Elaborating the question: --------**

Suppose there are $x$ different paths between $s$ and some $v \in V$. Each path has its own weight. Among those $x$ paths, there are $y$ shortest paths(pay attention $ y \subseteq x$ and all the paths in $y$ have the same **length**).

*What I'm trying to find*: The lightest path among the above $y$ paths. Also, i want to calculate that weight for **every** vertex in $V$.

Initially, i thought about this algorithm:

1. run **BFS** on $G$ from source $s$
2. run **Dijkestra** on the BFS tree from `step 1`

However, i ran into this problem:

With source vertex $A$, the red path and the black path, both lead to the same vertex $D$.

Pay attention how $ A\rightarrow B\rightarrow D$ and $A \rightarrow C \rightarrow D$ are both of length 2 Although they are both the shortest paths from $A$ to $D$, the red path is lighter than the black one.

**I thought about 'tweaking' BFS:**

Each time i arrive at a vertex $v$ which i already discovered, i check whether the "new" path i already walked to $v$ is lighter than the one already set to $v$.

However, i don't want to change in the algorithm, because i need to prove that it actually work from the start.

How can i modify my algorithm so that the problem i pointed won't pop-out?

# Answer
The whole point about **Dijkestra** is that it finds the best path on it's own. You don't need **BFS**. In fact, Dijkestra is sort of a BFS.

Use **tuples** as weigths. Then your question becomes simply "find the lightest path".

How it works on your graph:

Start with a lists of undiscovered vertices and discovered ones. I labeled the unlabeled vertices `E` and `F`. I use tuples `length, edgeweigth` as weigth in terms of Dijkestra.

```
undiscovered
[B, C, D, E, F]

discovered (length, edgeweigth)
A (0, 0)

Enumerate all paths from discovered vertices to undiscovered ones along with the resulting weigth

A -(1)-> B (1, 1)
A -(1)-> C (1, 1)
A -(0)-> E (1, 0)  <

```

Find the best one according to your objective function. In your case: smaller length, on equal length smaller edgeweight. Add it to the discovered vertices.

Iteration 1

```
undiscovered
[B, C, D, F]

discovered (length, edgeweigth)
A (0, 0)
E (1, 0)

Paths
A -(1)-> B (1, 1)  <
A -(1)-> C (1, 1)

```

Iteration 2

```
undiscovered
[C, D, F]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
E (1, 0)

Paths
A -(1)-> C (1, 1)  <
B -(10)-> D (2, 11)

```

Iteration 3

```
undiscovered
[D, F]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
E (1, 0)

Paths
C -(1)-> D (2, 2)
C -(0)-> F (2, 1)  <
B -(10)-> D (2, 11)

```

Iteration 4

```
undiscovered
[D]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
E (1, 0)
F (2, 1)

Paths
C -(1)-> D (2, 2)  <
B -(10)-> D (2, 11)

```

Iteration 5

```
undiscovered
[]

discovered (length, edgeweigth)
A (0, 0)
B (1, 1)
C (1, 1)
D (2, 2)
E (1, 0)
F (2, 1)

No more undiscovered vertices -> we're done.

```
> 3 votes

# Answer
A single BFS suffices. No need to use Dijkstra's SSSP algorithm (wiki). In the following, I suppose that you are somewhat familiar with the *"white-gray-black"*, *queue-based* framework for BFS. If not, please refer to CLRS or this online lecture note. The explanation of the pseudocode is included in the comments.

```
Enqueue(Q,s)
while (Q not empty)
  do u <- Dequeue(Q)                   // focus on node u
    For each v in adj[u]               // for each adjacent node v of u, do the something below according to its color (i.e., state)
      do if color[v] == White          // first discovered
         then   d[v] = d[u] + w(u->v)  // calculate path weight for v; which may be updated later; see below
                color[v] = Gray        // color v Gray
                Enqueue(Q,v)           // enqueue v
        elseif  color[v] == Gray       // already in the queue
                d[v] = min(d[v], d[u] + w(u->v))  // update path weight for v if necessary
        else    // color[v] == Black  // has been finished
                do nothing
   color[u] = Black                   // finished u

```
> 2 votes

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


# Question
Title: Distribution of IEEE 754 single precision floating point over number line
> "*What is the maximum and minimum difference between two successive real numbers representable in IEEE 754 Single Precision and Double Precision Floating Point Representations respectively?*"

In order to answer this question, I am unable to visualise how Floating Points are spread over the real number line, assuming the precision of real numbers is same as that of IEEE 754 single precision & double precision respectively.
So I am looking for graphs of the following two functions based on IEEE 754 single precision representations.
$f\left ( x \right ) = \left\\{\begin{matrix} 0 & ,\text{if x can't be represented in IEEE 754 single precision.} \\ 1 & ,\text{if x can be represented in IEEE 754 single precision.} \end{matrix}\right.$
$f\left ( n \right ) = \left\\{\begin{matrix} d, & \text{where d is the diffrence between n-th and (n-1)th floating points representable in IEEE 754 single precision. }\\ 0, & \text{if n-th or (n-1)th floating point number does not exists in IEEE 754 single precision representations.} \end{matrix}\right.$ Considering only normalised values and zero. and not considering Infinities, NaN and denormalised numbers.

Could anybody please help me out with these graphs so that I can understand floating points properly.

# Answer
> 3 votes
The idea is that a (not denormalized) floating point number is stored as $2^x \times 1.m\_0 \ldots m\_{k-1}$ (in binary), where $x$ is the exponent and $m\_0 \ldots m\_{k-1}$ is the mantissa of length $k$. Two successive numbers with this exponent differ by $2^{x-k}$, since this minimal difference is $2^x \times 0.0\ldots01$, with $k-1$ zeroes after the dot. The minimal and maximal differences (among not denormalized numbers) are attained for the minimal and maximal $x$.

---
Tags: floating-point, number-formats
---


# Question
Title: Trouble understanding how to create a grammar parse tree
I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it. Here are the exact instructions:

> To verify that a string of characters belongs to a language defined by a grammar, we must create a parse tree that shows that the string can be generated by the grammar.

```
<list> -> <item> , <list> | <item>
<item> -> <left> <item> <right> | <left> <right>
<left> -> A| B | C
<right> -> x | y | z

```

> Choose a string that is in this language and create a parse tree that demonstrates that your claim is true. Identify another string that contains some of these terminals symbols but is not in the language.

I think I know how to get started, but I keep getting confused by examples in the book and examples online. Is there a general method to use when approaching this?

I began it this way:

```
            <list>
         /          \
      <item>      <list>
    /    |    \
<left> <item> <right>
  |    /
  A  <left>

```

But I get confused on the next iterations of the `item`. Any hints?

# Answer
> 3 votes
Before expanding a grammar into a parse tree, we should first try to understand it at a higher level.

```
<list> -> <item> , <list> | <item>
<item> -> <left> <item> <right> | <left> <right>
<left> -> A| B | C
<right> -> x | y | z

```

First, `<list>` is a list of `<item>`, separated by commas if there are multiple ones.

Second, an `item` is either a pair of alphabets (the `left` is one of `A | B | C`; the `right` is one of `x | y | z`) or recursively, an `item` surrounded by such a pair.
Thus, an `<item>` is a word composed of, say $n$, upper-case alphabets from `A | B | C`, followed by the same number, $n$, of lower-case alphabets from `x | y | z`.

> ***$Q\_1$:*** Choose a string that is in this language and create a parse tree that demonstrates that your claim is true.

`ABCxyz,ACyz` is in this language; can you generate a parse tree for it?

> ***$Q\_2$:*** Identify another string that contains some of these terminals symbols but is not in the language.

`AyCz` is not in this language; can you explain why?

---

In addition, when you are searching for *any* string in a grammar by expanding the grammar into a parse tree, you can push the tree into its leaves as fast as you can, by choosing the *non-recursive* rules whenever possible.

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


# Question
Title: How to treat ϵ-productions in table-driven predictive parsing?
Here:
https://www.cs.rochester.edu/~nelson/courses/csc\_173/grammars/parsing.html
in chapter Driver Procedure, it's shown how table-drive predictive parsing works.

The predict table however can involve $\epsilon$-productions (which leads to including a production in the symbols of $FOLLOW(w)$, where $w$ is a non-terminal/row, in addition to $FIRST(w)$) and I cannot find how these should be treated. I.e. how should the parser decide whether it predicts for an $\epsilon$-production or non- $\epsilon$-production. I.e. e.g. how should the end of the string be handled by the Driver.

---

Case example:

Such production involving the $\epsilon$ could be e.g.

$$A \rightarrow \text{B | c | $\epsilon$}$$ where c is a terminal and B is a non-terminal.

The remaining input could be "".
So how should the driver decide to match with the $\epsilon$ and not e.g. something that the non-terminal $B$ leads to.

A guess would be that it tries all of the symbols between the $|$s but fails in other than the $\epsilon$.

# Answer
It will predict $A\rightarrow B$ if the look-ahead is in $FIRST(B)$, it will predict $A\rightarrow c$ if the look-ahead is $c$, it will predict $A\rightarrow\epsilon$ is the look-ahead is in $FOLLOW(A)$.

If the prediction is ambiguous, the construction of the tables should either have failed or used another way to resolve the conflict (for instance you could get a generator which allow ambiguity in the productions and resolve them using precedence -- using associativity to solve conflicts in a predictive parser is harder).
> 1 votes

---
Tags: algorithms, formal-grammars, parsers, ll-k
---


title: What would we call this datastructure?

text:
# Question
Title: What would we call this datastructure?
Suppose we have a datastructure that is a list containing elements that are either a leaf or another layer of the datastructure (recursively defined). What would we call this? It isn't a tree, since it has variable number of leaves and branches on each node. It isn't a forest, since it doesn't consist of a list of trees. I'm not exactly sure what to call it.

For context, the specific structure I'm designing is used as part of a compiler. The language is indentation structured, so blocks of code are grouped by their indentation level.

I have an Indentation\_______, which is a list of nodes where the node is either a statement in the program, or a new Indentation\_______ containing the next nested indentation level.

Any ideas?

# Answer
> 13 votes
A tree is not restricted to a certain branching factor. A n-ary tree may only have a branching factor of n (or less), but in an unrestricted tree, each node may contain an arbitrary number of subnodes.

A tree is a connected graph without cycles, so your datastructure still satisfies that definition.

Alternatively you could call your structure something like "nested lists".

# Answer
> 4 votes
The set of

* rooted trees with
* arbitrary numbers of children
* the order of which matters

is typically called the set of *plane trees* or simply *ordered trees* (the absence of further restrictions characterises the set sufficiently).

So feel free to use "tree" provided you clarify (once) which kind you mean exactly. The only possible point of confusion is the separation from graph-theoretic trees, which are not necessarily rooted.

---
Tags: terminology, data-structures
---


# Question
Title: Does the conservative two phase locking protocol produce cascadeless schedules?
Let us consider the following schedule :

\begin{array}{lcr} \mbox{$T\_1$} & \mbox{$T\_2$}\\ \\ \mbox{lock-exclusive(a)} \\ \mbox{lock-exclusive(b)} \\ \mbox{read(a)} \\ \mbox{a=a+50} \\ \mbox{write(a)} \\ \mbox{unlock(a)} \\ \mbox{} & \mbox{lock-exclusive(a)}\\ \mbox{} & \mbox{read(a)}\\ \mbox{} & \mbox{a=a+50}\\ \mbox{} & \mbox{write(a)}\\ \mbox{} & \mbox{unlock(a)}\\ \mbox{read(b)} \\ \mbox{b=b+100} \\ \mbox{write(b)} \\ \mbox{unlock(b)} \\ \end{array}

Since in the schedule the lock on $a$ is released, it is possible for the transaction $T\_2$ to acquire the lock on $a$. Now the transaction $T\_2$ reads the value of $a$ which was written by transaction $T\_1$. This implies that if the transaction $T\_1$ aborts, the transaction $T\_2$ must be aborted for consistency purposes. Does it mean that even though a conservative two phase protocol is used, the schedules may not necesssarily be cascadeless?

# Answer
Yes, the **conservative 2PL** does not garantuee cascadelessness. Requesting all locks at the beginning of the transaction is used to prevent deadlocks.

If you want to prevent cascading rollbacks, you need to have a look at how the locks are released. There are two versions of the 2PL-Protocol that garantuee cascadeless schedules: the **strong 2PL** and the **rigorous 2PL**, which is even stricter.

Schedules that satisfy the strong 2PL may release read-locks at any time and all write-lock at the end of the transaction. Schedules that satisfy the rigorous 2PL may only release all locks at the end of the transaction.

Lets have a look at what happens to your schedule if you use the conservative and rigorous (or strong) 2PL.

\begin{array}{lcr} \mbox{$T\_1$} & \mbox{$T\_2$}\\ \\ \mbox{lock-exclusive(a)} \\ \mbox{lock-exclusive(b)} \\ \mbox{read(a)} \\ \mbox{a=a+50} \\ \mbox{write(a)} \\ \mbox{read(b)} \\ \mbox{b=b+100} \\ \mbox{write(b)} \\ \mbox{unlock(a)} \\ \mbox{unlock(b)} \\ \mbox{} & \mbox{lock-exclusive(a)}\\ \mbox{} & \mbox{read(a)}\\ \mbox{} & \mbox{a=a+50}\\ \mbox{} & \mbox{write(a)}\\ \mbox{} & \mbox{unlock(a)}\\ \end{array}

Because $T\_1$ is not allowed to do $\mbox{unlock(a)}$, $T\_2$ can not request the lock and therefore can not start. $T\_1$ continues until the end and releases its lock. Now $T\_2$ can start.

You can also see here that a conservative, rigorous 2PL leads to a serial execution of Transactions that access the same variables.
> 2 votes

---
Tags: concurrency, database-theory
---


# Question
Title: Know when we have a cache default and if it loads
I have an exercise about cache memory, first the cache is empty :
I have a cache memory with 16 lines and each lines have 16 octet, the address is 16 bits

So I know that the INDEX will be composed of 4 bits and the offset will be composed of 4 bits too So i will have this :

bits number : (15 ... TAG... 8)(7.. INDEX.. 4) (3 .... OFFSET .... 0 )

Now if have to say if there is cache default or NOT and say if it will Loads or Not. Adress that I have :

3000 : tag = 30 / index = 0 , offset 0

2040 : tag = 20 / index = 4 , offset = 0

3001 : tag = 30 / index = 0 , offset = 1

2404 : tag =24 / index = 0 , offset = 4

3002 : tag = 30 / index = 0, offset = 2

20C4 tag = 20 / index = 12 , offset =4

3003 tag = 30 / index= 0 , offset =3

24C4 tag = 24 / index = 12 , offset = 4

If someone can explains me how I know if it loads and if I have a cache default, I would be very happy. Thanks

# Answer
* Starting with an empty cache.
* Assuming direct map

Tag memory will contain for the 16 indexes the addresses \[15:8\] and a "valid" bit

```
3000 : Miss -> Load 30 into tag 0 and fill line (3000..300F)
2040 : Miss -> Load 20 into tag 4 and fill line (2040..204F)
3001 : Hit : Already in the cache
2404 : Miss -> Load 24 into tag 0 and fill line (replaces 3000..300F -> 2400..240F)
3002 : Miss -> Load 30 into tag 0 and fill line (replaces 2400..240F -> 3000..300F)
20C4 : Miss -> Load 20 into tag C and fill line (20C0..20CF)
3003 : Hit : Already in the cache
24C4 : Miss -> Load 24 into tag C and fill line (24C0..24CF)

```

Very few hits here, would greatly benefit from a two ways set-associative cache.
> 0 votes

---
Tags: cpu-cache
---


# Question
Title: Algorithm to solve job assignment problem
Can someone suggest an algorithm to solve job assignment problem with condition?

With condition means that some jobs cannot be done by some workers. For example table as shown below:

In this table x - means that it is impossible to do. For example, worker 1 cannot do jobs 1,3 and 5.

I encountered such situation and there may be cases as shown above when usual Hungarian algorithm seems cannot solve such task because there is no way to complete all tasks by distributing one task per worker.

However, my main case it is allowed that one worker wil do several tasks (tasks, which worker can do). Main task is to complete all jobs using existing workers, but it is desirable that, all workers do roughly same number of tasks.

So is there some solution of such problem? May be any algorithms do exist?

# Answer
> 2 votes
Instead of putting x, put some very high cost values in those cells. Then the Hungarian algorithm avoids selecting those cells automatically (if that's possible).

---
Tags: algorithms, optimization, linear-programming, scheduling, assignment-problem
---


# Question
Title: An obvious approach to explaining NP != coNP, how far has it been pushed?
A recent question made me think about an obvious approach for circumventing the "algorithm is allowed to do anything" problem, when proving lower bounds. Instead of starting with a simple looking NP-complete problem, start with a powerful looking logical deduction system.

Then try to find a reasonable general term expression problem, such that equality of the terms can be decided by the logical deduction system, and inequality of the term expressions is NP-complete. (For example, Boolean algebra term expressions would work.) Then start to prove that the logical deduction system cannot efficiently prove equality of specific term instances, unless it has access to specific higher order features, like the cut-rule.

And then the goal would be to push up the required higher orders features as far as possible, i.e. beyond the cut-rule towards fully impredicative higher order logic. But already proving that you need the cut-rule would seem like a nice achievement. How far has such an approach to explaining NP!=coNP actually been pushed in the past?

# Answer
> 6 votes
Not very far. The approach that you are describing is known as *proof complexity*, and it is covered by several surveys and lecture notes. There are several kinds of proof system being considered:

* Frege systems. These are systems in which a proof consists of a sequence of formulas or circuits (depending on the system), and there is a fixed set of derivation rules.
* Algebraic proof systems such as the Polynomial Calculus and Nullstellensatz. Here each line is a polynomial.
* Cutting planes, in which each line is a linear inequality.

There are also other proof systems such as the Hajos calculus, a proof system for proving that a graph isn't 3-colorable.

We have strong lower bounds for some of these systems, but in the Frege front, the best lower bound is for bounded depth Frege, in which the depth of all lines in the proof is bounded by some constant. This lower bound is similar in some regards to AC0 lower bounds for circuits, but is otherwise more complicated. We have no lower bound for the version in which the depth is bounded but we allow mod $p$ gates; the algebraic methods used to prove lower bounds on circuits don't seem to work, and the problem seems related to derandomizing polynomial identity testing, a notoriously difficult problem in algebraic complexity theory.

The Frege proof system itself has as lines arbitrary formulas, and Extended Frege has arbitrary circuits as lines. It is thought that Extended Frege is stronger than Frege. Other proof systems are conjectured to be stronger than even Extended Frege. It is not clear currently whether there is a "super" proof system, which is optimal up to polynomial factors compared to *any* proof system. Thus even if we do manage to prove lower bounds for progressively more general proof systems – which is expected to be harder than proving corresponding circuit lower bounds – we wouldn't necessarily be able to prove that NP is different from coNP in this way.

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


# Question
Title: Prim's Algorithm - Building the Priority Queue
Suppose we were using a priority queue (PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then set to $0$. All of the vertices are then inserted into the PQ.

1. Does that mean that we can insert the vertices in any order into the PQ?
2. Given that we can insert the vertices in any order, suppose we have a graph with the following vertices $a$, $b$ and $c$ and the following weights $w(a,b)=1$, $w(a,c)=2$. Once we set `a.key = 0` and then extract a from PQ, we have `b.key = 1` and `c.key = 2`. Given the answer to (1) was yes, my understanding would be that in a binary tree representation of the heap, $b$ would now be the root and $c$ would be a child of $b$. However, depending on the order in which the $a$, $b$ and $c$ were added to the heap, $c$ could be either the left or right child of $b$, right?
3. Suppose now that the graph has vertices $a$, $b$, $c$, $d$ and edges $(a, b)$, $(a, c)$, $(a, d)$. Suppose they were inserted into the heap in the order $a$, $b$, $c$, $d$. The binary tree representation of the heap should then be:
$a$ is the root, $\operatorname{left}(a) = b$, $\operatorname{right}(a) = c$, $\operatorname{left}(b) = d$

So, that would mean that the parent-child relationships do not correspond to the parent-child relationships in the original graph and they don't have to, right?

# Answer
> 1 votes
1. Assuming your PQ is backed by a heap (as you refer to it later). Since the only invariant in a heap is that the parent must be $\<$ the children (heap property) you can see there can be no ordering between children of a single parent. A priority queue will always return you the minimal element regardless of order, just think about how $\min$ works: $\min\\{1,2,3\\}=\min\\{2,3,1\\}=\min\\{3,2,1\\}$.
2. Because a heap is represented in a continous array, you'll have $\[b, c\]$ after removing $a$ which means that $c$ will always be the left child. Look at the heap image on Wikipedia and notice it's leaning left.
3. Yes, that's the order they'll be in a usual heap, because all their weights are $\infty$. But any other structure (regardless of insertion order) would be acceptable as long as $a$ is the root, because it wouldn't hurt the heap property.

> parent-child relationships \[in PQ's heap\] do not correspond to the
> parent-child relationships in the original graph

That is absolutely correct. Just because your PQ is backed by a heap which encodes a tree you can't assume that the graph structure will have anything to do with the heap tree's structure. Just think about a non-tree graph with cycles and multiple edges between vertices: how would that be reflected in the heap's tree? There isn't even a correspondence with the partial MST.

Another argument: the whole structure correspondence breaks big time as soon as you modify just one key in the heap and sift it to it's place. For example:

```
     a(0)                            a(0)
   b(∞) c(∞)   --- d.key = 1 -->   d(1) c(∞)
 d(∞)                             b(∞)

```

even before modifying the key $d$ was the child of $b$ which wasn't true in the graph and is not even reachable. The same is true after modification for the reverse.

---

The best is to think of a PQ as:

```
interface PriorityQueue {
    add(node, cost)
    update(node, cost)
    (node, cost) popMin()
}

```

the fact that it's implemented as a heap shouldn't be of a concern, just assume that the PQ does `add` and `update` in $\mathcal{O}(n\log{n})$ and `popMin` in $\mathcal{O}(1)$ to get quasilinear runtime of Prim's algorithm. Even when you implement it you should separate the algorithm from the PQ implementation.

# Answer
> 1 votes
Prim's algorithm considers edges in increasing cost, and once an edge is added (or not) it isn't considered again, and it's cost isn't changed at all. No need for a priority queue's complications, just sort and be done.

---
Tags: algorithms, graphs, spanning-trees
---


# Question
Title: Could PRNGs make use of more internal state?
In the context of our class on combinatorial algorithms we have been discussion randomness. One student said (paraphrasing):

> Pseudo-random number generators (PRNGs) must have a period since they only have finitely many internal states.

At least for the PRNGs we see in the class, this is certainly a valid argument (assuming a finite target interval). But it begs the question: why do they not use more memory resp. internal state?

Going through this list, it seems to be the case that all PRNGs do indeed use only a few numbers from the target interval (plus some magic constants).

* Most use one to $\approx$ 5 of the most recently generated numbers.
* Some have parameter that controls how many values to store ("$r$-lag").
* A few use rather many numbers (but still constantly many).

The one I can't quite place is Naor-Reingold; I can't tell how it would be used to generate an actual sequence of pseudo-random numbers.

So while the memory usage (i.e. internal state size) of known/used PRNGs depends on the target interval and internal constants, it does *not* on the amount of (already) generated numbers.

Have there been any attempts to use more memory in order to obtain better generators? If so, why does it not help or not work at all?

# Answer
> 4 votes
Because, for any practical purpose, a PRNG with sufficiently, but finitely many states is indistinguishable from one with infinitely many. Mersenne Twister has a period of $2^{19937} - 1$, \[insert your favorite argument about why $2^{19937}$ is a somewhat large number here\].

# Answer
> 2 votes
Once the internal state is large enough, the period is long enough to be infinite for all intents and purposes. Besides, larger state means more memory used (important if you need very many completely independent random number streams, some applications use tens of thousands), more state means more data to maul to get the next state and random number (makes the generator slower).

---
Tags: algorithms, reference-request, randomness, pseudo-random-generators
---


# Question
Title: Turing machine - infinite tape - does that thing exist?
Can we use a Turing machine with infinite tape as a basis to prove anything disregarding the fact that such a thing can never exist? Do we have the right to regard a machine (a construct) in the same way we regard a number or a set (an abstract)?

If yes could I similarly use a Turing angel with infinite scroll instead, would that be ok?

EDIT: since I cannot comment. This question is somewhat different from infinity in mathematics because a set even infinite can have a finite representation. On the other hand there is no finite representation for an infinite tape  That is the algorithm that generates the output.

Computation requires resources, that means that it takes place in a time-space, not in an abstract timeless dimension. While it could be ok to draw on demand more time for the computation pushing on to infinity, space has a cap on the amount of information it can hold, and before reaching that point the tape would revert to write only, that is implode into a black hole. So even if an algorithm is "finite" its output could be big enough to become "unreadable". For example lets say we have a machine that counts all numbers at some Number H when trying to add more information on the tape the tape colapses forms a black hole and number H+1 becomes unreadable. Counting up to H+2 is a finite process but cannot be completed. One could argue that space and time restrictions should not concern us but I m not convinced that is true when dealing with objects embedded in spacetime

I could accept a definition of a machine with sufficiently large tape. But I think that the size does matter. Can for example 2 Turing machines with different tape-size considered equivalent?

# Answer
The tape is not infinite. It is *unbounded*. There is an important difference. We don't need infinite memory. We only need to be able to add more memory over time as needed. This is actually pretty close to what people do in practice. When a program needs more memory it asks the operating system and receives more memory. If we see that a computer is short on memory we increase its memory. It is becoming even easier with cloud computing. So the assumption is not that the machine has infinite memory. The assumption is that we can increase the memory as needed.

If your question is about the limit where the needed memory reaches the limit of information that can be stored in the universe (assuming that it is finite and bounded by some fixed number) then yes, we will not be able to add any more memory at that point. In fact, if you assume that the amount of information is bounded by a fixed number then the world is a finite state machine. However that is not the usual case.

However if you try to design programs as finite state machines you are going to have a very difficult time because the number of states is huge. The number of states for a Turing machine with $m$ bits of memory would be something like $2^m$. Turing machines (and other similar models) simplify things. This is a rather common thing in sciences. It is important to know the limits of a model but the fact that a model is not a completely accurate representation of the world doesn't imply it is useless.
> 15 votes

# Answer
In some sense, your question has been answered by switching from computability theory to computational complexity theory. In the latter, we care mostly about problems which a Turing machine can solve in polynomial time. In particular, such machines only use polynomial space. This is more realistic than the unrestricted Turing machine model.

However, even computational complexity suffers from similar problems, since we only care about the asymptotic behavior of Turing machines, whereas in real life we only care about the behavior on inputs of a certain size. Nevertheless, empirically computational complexity has shown some predictive power in some (but not all) cases.

A similar issue happens in classical mathematics – the natural numbers are potentially unlimited, and some people don't like it. They are called ultrafinitists.
> 8 votes

---
Tags: computability, turing-machines, computation-models
---


# Question
Title: Is a single string enough to prove regular expressions inequivalent?
> Which of the following regular expressions generate a language that is different from the rest?
>
> 1. (a+b)$^\*$a(a+b)$^\*$(a+b)$^\*$
> 2. b$^\*$ab$^\*$a(a+b)$^\*$
> 3. (a+b)$^\*$ab$^\*$ab$^\*$
> 4. b$^\*$ a(a+b)$^\*$ab$^\*$

RE 1 generates a language that contains the string 'a' which no other language among 2,3,4 contains, so can I say this language is different from all others? Does it suffice to show that a single string is not present in the language and hence its different from the rest?

# Answer
> 8 votes
> Does it suffice to show that a single string is not present in the language and hence its different from the rest?

Yes. It's actually a very neat proof.

Formally speaking, you have found $w \in \\{a,b\\}^\*$ with $w \in L\_1$ but $w \not\in L\_2,L\_3,L\_4$. That is sufficient to show that $L\_1 \neq L\_2$, $L\_1 \neq L\_3$ and $L\_1 \neq L\_4$.

You have *not* shown that $L\_2 = L\_3 = L\_4$. The phrasing of the question seems to suggest as much (MC questions are *boring*!) but you may want to prove that as an additional exercise.

> *Hint:* Translate into NFA, determinize, minimize, check for isomorphy.

# Answer
> 5 votes
A language is just a set of strings. To show that sets $X$ and $Y$ are different, it's always enough to show that $X$ contains something that's not in $Y$ or vice-versa. This is because two sets are defined to be equal exactly if they have the same elements.

---
Tags: formal-languages, proof-techniques, regular-expressions
---


# Question
Title: Algorithm to convert decimal number to binary
I am reading this material to understand the basics of number system. I am stuck at a point in that material where it writes the algorithm to convert a decimal number to binary number. The heading of that part where I am stuck is `Decimal to Base` The algorithm (may be presented less than faithfully, please refer the link) it mentions there is:

> 1. Let $p = \lfloor \sqrt{V} \rfloor$
> 2. Let $v = \lfloor \dfrac V {B^p} \rfloor$
> (v is the next digit to the right)
> 3. Make $V = V − v * B^p$
> 4. Repeat steps 1 through 3 until $p = 0$

It is explaining by taking an example of converting decimal number 236 to binary.

I am not getting how it is calculating the 1st step, i.e. to get the value of p.

It writes that p = int(square root of V)

Now, square root of 236 = 15.36229149573721635154

As per point number 1, p = integer part of 15.36229149573721635154 So, I remove the decimal part and p then becomes 15. But the material there says it is 7.

I can't get what is happening here. I am stuck.

# Answer
> 5 votes
Just converting the comment into a short answer:

$7 = \text{int}(\log\_{2} 236)$. Generally, $p = \text{int}(\log\_{B}V)$.

---

As other people pointed out, this algorithm is needlessly complicated and not practical; it is not easy to calculate $\log\_B V$ for large $V$ by pencil and paper. Instead, use the other algorithm which is also mentioned in the article you are reading:

From decimal to binary

* Step 1: Check if your number is odd or even.
* Step 2: If it's even, write 0 (proceeding backwards, adding binary digits to the left of the result).
* Step 3: Otherwise, if it's odd, write 1 (in the same way).
* Step 4: Divide your number by 2 (dropping any fraction) and go back to step 1. Repeat until your original number is 0.

# Answer
> 1 votes
In Cisco academy for doing the math by heart we know the powers of two, to allow us to do calculations by head. Note that the algorithm only is efficient once you can do it on your head, as it is mostly subtractions once you are familiar with the procedure.

The algorithm works roughly this way:

* you pickup the power of two immediately lower to your value
* do
* number lower power == 0
* number greater power == 1 ; and number = number - power
* go down to next power of 2
* while number not 0

If the number comes to 0 before the power end, you fill out the others with 0.

So for your value of 236, I know the powers bellow are: 128 64 32 16 8 4 2 1

So, lets see the powers of 2^n

(7) 236\>128==1, number=236-128=108
(6) 108\>64==1, number=108-64=44
(5) 44\>32==1, number=44-32=12
(4) 12\>16==0
(3) 12\>8==1, number=12-8=4
(2) 4\>=4==1, number=4-4=0 number==0 ends calculations
(1) ==0
(0) ==0

So 236 is 11101100 in binary.

---
Tags: algorithms, number-formats, base-conversion
---


# Question
Title: Why is Hamming Weight (in the CRC context) independent from the data?
I'm designing a communication protocol for 24 to 52 bits (typically 32 bits) data including the CRC-8 for error detection. I'm trying to select the best polynomial for this kind of application.

In the paper Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks Koopman, et. al. gives a very nice method to select a CRC polynomial depending on the needs of the application. The paper proposes that if Hamming Distance of two or more polynomials are equal, select the minimum Hamming Weight for a given bit length and error bits. Also Koopman kindly makes all these calculations and information publicly available in his site: http://users.ece.cmu.edu/~koopman/crc/index.html

As he also suggests "Don’t blindly trust what you hear on this topic", I've also verified his results for some of the 8-bit CRC polynomials using my own software. But here is what I failed to understand:

In the paper 32-Bit Cyclic Redundancy Codes for Internet Applications he defines the Hamming Weight as

> A weight $W\_i$ is the number of occurrences of a combination of $i$ error bits, including bit errors perturbing the CRC value, that would be undetected by a given polynomial for a given data word length.

Also, he explains why the Hamming Weight is independent from the data as follows:

> Consider the fact that a data corruption is undetectable if and only if it transforms one codeword (some payload with its valid FCS value) into a different valid codeword. But because CRCs are linear, this means that the faulty bits that have been flipped from the original codeword have to themselves form a valid codeword. (In other words, the bits flipped in the message payload have to be compensated for by bits flipped in the FCS field, and the only way this can happen is if the entire set of bits flipped is itself a valid codeword.) This means that the actual data in a message payload is irrelevant in computing error detection abilities, which simplifies things greatly.

I also tried to calculate the Hamming Weight for different data and indeed obtained the same results. But I don't understand why this is the case. A rigorous proof or any different insights are greatly appreciated.

**Edit:** *The example for Hamming weight given in the paper:*

Suppose we have a codeword of length 12144 bits. So we have

$$ \pmatrix{12144 \\ 4} = \frac{12144!}{12140! ~ 4!} = 906 \times 10^{12} $$

possible bit errors. Hamming Weight is the number of undetected 4 bits error out of all possible 4 bits errors. So it is calculated for 802.3 CRC polynomial to be $W\_4 = 223059$. This means $223059$ of $906 \times 10^{12}$ errors go undetected and this number does not change with the used codeword.

# Answer
Define the sets

$$\begin{align\*} P(d) &:= \\{ p ~|~ \deg(p) \leq d \\}\\ A\_i(d) &:= \\{ p \in P(d) ~|~ s(p) = i \\} \end{align\*}$$

where $s(p)$ is the number of $1$ coefficients of the polynomial $p$. For a given CRC generator polynomial $g$, define

$$ U\_i(d) := \\{ p \in A\_i(d) ~|~ \exists q, p = q g \\} $$

So $U\_i(d)$ is the set of all undetected errors of length $i$ for data length $d$ using $g$. Now select an $x \in P(d)$ such that $x = q g$ for some $q$ and define the set

$$ U(x) := x \oplus U\_i(d) := \\{x \oplus p ~|~ p \in U\_i(d) \\} $$

Because of the linearity, all elements of $U(x)$ is dividable by $g$. We need to show that $U\_i(d)$ and $U(x)$ has the same number of elements. This is obvious since $x \oplus p\_1 = x \oplus p\_2 \iff p\_1 = p\_2$.
> 2 votes

# Answer
Let us call a data vector of some fixed length together with its CRC a *codeword*. Since CRC is a linear code, the set of codewords is closed under XOR (this is the definition of linear code).

Let $x$ be a codeword, and suppose that $y$ is a noisy version of $x$ which is also a codeword. Since CRC is linear, $x \oplus y$ is also a codeword. If $D$ is the minimum Hamming weight of a non-zero vector in the code, then the Hamming weight of $x \oplus y$ is at least $D$, that is, $y$ differs from $x$ in at least $D$ positions. This shows that at least $D$ errors need to occur in order for the errors to go undetected.

Conversely, let $w$ be a codeword of Hamming weight $D$. Then $y = x \oplus w$ is another codeword which differs from $x$ in $D$ positions. That is, $D$ errors (in appropriate locations) are enough for an error to go undetected starting from $x$. Note that $x$ here is completely arbitrary. This is why the minimum number of errors is independent of the data.
> 3 votes

---
Tags: coding-theory, error-correcting-codes
---


# Question
Title: Is the set of regular expressions over an alphabet equal to Σ*?
Are the following two sets equal? One the set of regular expression over an alphabet, and the other set is the set of all strings which can be generated by using the symbols of an alphabet(Σ\*)?

# Answer
> 4 votes
> Are \[...\] the set of regular expression\[s\] over \[$\Sigma$\] \[...\] and the set of all strings \[in $\Sigma^\*$\] equal?

Since the *types* of objects don't even match, clearly not!

Going back to the definitions, regular expressions have a certain syntax. They contain symbols from the fixed alphabet $\Sigma$, but also operators *not* in $\Sigma$ like $+$, $\mid$, $^\*$, and others. Their *interpretations* are formal languages over $\Sigma$. That is, if $R$ is a regular expression over $\Sigma$ then $L(R) \subseteq \Sigma^\*$.

# Answer
> 1 votes
Regular Expression:

1. a, for some a in the alphabet Σ.
2. λ.
3. Empty set.
4. r + s
5. r | s
6. r\*.

What is Σ\* ?

> Given an alphabet Σ, we can apply the Kleene Star operator * on it to get the set Σ\* (read Σ-star), called the Kleene closure of Σ. The set Σ\* is the set of all possible strings of all possible lengths on Σ including λ, the empty string, and is therefore infinite (if Σ is nonempty). Source

( 5 + 3 ) x 4 is an arithmetic expression, whose value is 32. Similarly, a regular expression is something, whose value is a language, i.e. which describes a language (set of strings).

So, **all possible** regular expressions, over an alphabet Σ ***describe*** Σ\*.

References: Intro to Theory of Computation by Sipser. Chapter Automata & Languages -\> Regular Expressions.

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


# Question
Title: Basic idea behind error recovery in recursive-descent parsers
I see that modern SW basically dominated by recursive descent parsers. These parsers try grammar production and back track to an alternative one in case of failure. Suppose BNF is

```
program = (declaration)* "begin" (statement)*
declaration = type_declaration | variable_declaration | function_declaration
type_declaration = "range" name "to" name | "enum" (name)*
variable_declaration = name ":" type_name
statement = ...

```

and suppose that user has entered user entered "range 10 to '15'" when declaration expected. The parser has failed to match the first type pattern but it also failed to match other alternatives and declarations and failed to parse the program. How do you recover? Should you track the "best match", which would be location of the "range 10 to '15'" and look for keywords met afterwards or what? Which mechanisms are used in practice, in popular parser combinators and generators like JavaCC?

# Answer
One (crude) technique is to just discard input until a *synchronizing token* is found, one that could legally follow what we were trying to match, and which is unlikely to be omitted by the user. Like e.g. ';' in languages like Pascal or C.

Another is to add productions for typical errors in some constructs, e.g. handle `a b` as if it was `a * b` in case of expressions in a compiler for newbies.
> 1 votes

---
Tags: parsers
---


# Question
Title: Terminology for a graph with ports on its nodes
A Graph is a well-defined concept in mathematics, computer science and engineering disciplines that depend on them. However, oftentimes a practical implementation of a (directed) graph in a certain domain or application requires that edges don't merely connect vertices, but instead connect ports that exist on these vertices. In a directed graph, this would imply separation between input ports and output ports, wherein typically an edge starts at an output port and arrives at an input port.

Examples are easy to find: shader design tools, signal flow graphs in compiler theory, electronic schemas, high-level ETL scripting... all these tools require that vertices have named or distinct inputs and outputs.

Now for my question: is there any theory and nomenclature on these kinds of graphs, or is this considered to be an "implementation problem" of the engineering sciences? As you notice from my question, I can't quite pinpoint what this kind of thing is called ("A Graph With Node Ports"), and I'd love to see that answered.

# Answer
I was wondering the same thing. It seems that there are a number of publications revolving around this idea, most of them at the TERMGRAPH workshop. They are usually called “port graphs” there.

Tracing the related work of a random sample of papers yields that the following might be the prime paper that introduces this formalism:

> Andrei, O. and H. Kirchner, A Rewriting Calculus for Multigraphs with Ports., in: Proceedings of RULE’07, Electronic Notes in Theoretical Computer Science 219, 2008, pp. 67–82.

One that I find particularly interesting is

> Sandra Alves, Maribel Fernández, and Ian Mackie. A new graphical calculus of proofs. In TERMGRAPH, volume 48 of EPTCS, pages 69–84, 2011
> 6 votes

---
Tags: graphs, terminology
---


# Question
Title: How can I calculate the effective bandwidth of a memory system?
I am currently doing my homework for my Computer Architecture class. One of the questions asks:

> A computer has a 64-bit data bus and 64-bit-wide memory blocks. The memory devices have an access time of 35 ns. A clock running at 200 MHz controls the computer and all operations take an integral (i.e. whole number) of clock cycles. What is the effective bandwidth of the memory system?

The problem is, there's pretty much nothing in my textbook that explains how to figure this out. Searching online doesn't return much help either. I'm not asking anybody to answer the actual homework question for me, but if you could explain to me how to figure it out, or point me in the right direction I'd really appreciate it!

# Answer
An N-bit wide data bus can transfer N bits in one clock cycle, **after** a latency of `d` clock cycles (or `t` seconds).

I think the above sentence has everything you'd need to solve this problem.
> 2 votes

---
Tags: memory-management, memory-hardware, memory-access, clocks
---


# Question
Title: DFA for w|w has a length multiple of 2 or 3
I am trying to create a DFA and a regex for this kind of exercise:

$A = \\{w ∈ \\{0, 1\\}^\* |\text{length of w is a multiple of 2 or 3}\\}$. I tried to do one for $2$ and one for $3$ and then combine them, but it didn't seem to work cause I miss some cases for example $6,7$ or so. Any help would be gratefully received :D

# Answer
Creating a state machine for each and combining the two is not a bad idea. To create a state machine accepting words having length `N` you can have each state represent the current length `mod N`.

After creating the two machines you can add a state having two epsilon transitions to the starting states of both machines. This gives a NFA accepting your language.

In a final stage you use the subset construction algorithm to convert the NFA you got into a DFA.
> 0 votes

# Answer
> 2 4 6 8 10 12 14 16 18...
>
> .3 .6 .9 ... 12 .. 15 .18

Observe, that multiples of 2 and 3 meet after 6 numbers. So, you can think of resetting the 'counter' for every 6 symbols.

0 is the start state. For every 6 symbols, it resets to 0.

Constructing individually for 2 and 3, and then combining works well for "NFA". But, you need to convert that NFA back to DFA.

Regular Expression, in case of NFA will be (0|1+0|1)\*|(0|1+0|1+0|1)\*.

In case of DFA will be, ... not so early.

Constructing the regular expression from it a bit hectic. You need to follow the rules. (See here and here). The concept is called *state removal method.*
> 0 votes

# Answer
**Hint:**

buid the unity automata between those two, the first one accepts all the words with even length, and the second one accepts all the words above the alphabet such that $|w|\bigg|\_{3}$
> 0 votes

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


# Question
Title: Which sorting has a complexity of $n \log n$ if you compare two elements?
I want to ask just a quick question. If I have an array, which sorting method will have a complexity of $n \log n$ if I compare two objects in that array? I can't decide between `divide-and-conquer`or `insertion-sort`. And how would the iterative solution look like in pseudocode?

# Answer
> 0 votes
Insertion sort has a worst case complexity of $O(n^2)$. "Divide and conquer" is a strategy for designing algorithms, not a sorting method. There are several possible ways to use that for sorting, their complexity isn't always $O(n \log n)$, and the respective pseudocodes are wildly different.

# Answer
> 0 votes
This question is a complete mix-up of terminologies. However, I will try to cover all the possibilities I can.

> Which sorting has a complexity of $n \log n$ if you compare two elements?

Are you asking about worst-case complexity or average-case complexity? What do you mean by *element*? Do they refer to two sorting algorithms, or two elements of a collection? If they are elements of a collection, then you cannot do sorting without comparing two elements.

> If I have an array,

The complexity of an algorithm does not change if you have an array, a set or a list, as long as it is a reasonable data structure.

> I can't decide between `divide-and-conquer` or `insertion-sort`

What decision do you aim to make? What will effect your decision? The complexity of an algorithm will not change with your decision. Moreover, deciding between divide-and-conquer and insertion sort is like deciding between "buying a sports car" or "going to the cinema by bus". The former is an algorithm type, the latter is a specific algorithm to solve a specific problem.

> And how would the iterative solution look like in pseudocode?

An iterative solution to *what*? Almost all sorting algorithms can be implemented both ways.

Regarding to your question, I think what you ask is

> which sorting algorithms run in $O(n \log n)$ in the worst case?

As can be seen here, there are several sorting algorithms that work in $O(n \log n)$ in the worst case. Merge sort, Heapsort, Introsort, Timsort, Cubesort, Patience sorting, Smoothsort, Tournament sort, Block sort, and Binary tree sort

Although, there are more algorithms whose average case are $O(n \log n)$.

---
Tags: algorithms, sorting
---


title: Direct mapping cache with LRU

text:
# Question
Title: Direct mapping cache with LRU
I'm studying computer architecture and I'm doing an experiment. Does LRU make sense in a direct mapping cache? I'm quite confused. Thank you.

# Answer
> 3 votes
LRU only applies if the cache is set-associative and you need a hint as to in which set you write new data. In a direct mapped cache, here is only one place to put data.

---
Tags: cpu-cache
---


# Question
Title: Methods for proving upper bound on a-approximiation algorithms?
I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance.

For example, there's a simple randomized algorithm for the *MAX-E3SAT* problem, where there are $m$ clauses each consisting of three distinct 3 variables in $\\{x\_1, ..., x\_n \\}$.

There's a theorem that if there exists an algorithm which is $(\frac{7}{8} + \epsilon)$-approximation, then $P = NP$.

What method can and should I use for proving such theorems? Could you please provide an example?

More over, regarding the *MAX-E3SAT* problem, what method can and should I use to prove such claim:

For any instance of *MAX-E3SAT* the optimum is at least $\frac{7m}{8}$ ? I'm not looking for the proof of this claim, just the method for proving it.

Thanks a lot

# Answer
> 2 votes
You mention two results giving tight bounds on the approximability of MAX-E3SAT: an upper bound (algorithm) and a lower bound (hardness). The upper bound is much simpler than the lower bound in this case. Indeed, using basic probability you can show that a random assignment satisfies $7/8$ of the clauses in expectation, which gives an approximation algorithm whose approximation ratio is at least $7/8$ in expectation. If you don't like randomized algorithms, this algorithm can be derandomized using the method of conditional expectations.

The other direction is much harder, and relies on the PCP theorem and Raz's parallel repetition theorem. It was shown by Håstad in his seminal paper Some optimal inapproximability results. This is all described in Arora and Barak's textbook, but I warn you that the textbook is quite advanced.

---
Tags: approximation, randomized-algorithms, online-algorithms
---


title: What is the XNOR of 3 or more inputs?

text:
# Question
Title: What is the XNOR of 3 or more inputs?
We know that for 3 variables (A=0,B=1,C=1), f$\_1$ = (A XNOR B XNOR C) = 1, since the input has even number of 1's.

But if we were to do this step by step, f$\_2$ = (A XNOR (B XNOR C)) = (A XNOR (1 XNOR 1))

Now, 1 XNOR 1 = 1. So, f$\_2$ = (A XNOR 1) = 0 XNOR 1 = 0.

Why is f$\_1 \neq$ f$\_2$ ?

Also, which is true : "XNOR operation gives a value of 1 for " : Even number of 1's in the input OR Even number of 0's in the input. (Sorry, but a certain professor implied the later, so have to confirm).

# Answer
> 4 votes
There is no standard definition for the XNOR of more than two inputs (indeed, nor is there a standard definition for *less* than two inputs). Since XNOR is associative, one possible definition is $$ A\_1 \text{ XNOR } A\_2 \text{ XNOR } \cdots \text{ XNOR } A\_n = A\_1 \text{ XNOR } (A\_2 \text{ XNOR } (A\_3 \cdots )\cdots). $$ Another reasonable definition defines the XNOR of $A\_1,\ldots,A\_n$ as the negation of the XOR of $A\_1,\ldots,A\_n$. Both definitions agree with the usual definition of XNOR when $n = 2$, or indeed when $n$ is even, but give complementary results when $n$ is odd.

The XOR of a given number of inputs is $1$ if the number of $1$s in the input is odd. Given that you can work out a similar formula for the XNOR of any number of inputs, under both definitions.

---
Tags: arithmetic, boolean-algebra
---


# Question
Title: Remove contiguous subsequence so the remaining numbers will created a sorted sequence
> You are given $N$ numbers. Remove contiguous subsequence of those numbers, so the remaining numbers will create a sorted sequence. For example, if the sequence is $5$, $7$, $8$, $2$, $1$, $9$ then we have to remove subsequence $2$, $1$. I am only interested in the minimal amount of numbers removed. If this task wasn't about removing contiguous subsequence, then I would find longest non-decreasing subsequence in O(n log n) and output $N$ - $L$, where $L$ is length of this subsequence.

This task was taken from an old programming competition. I am asking this question, because I'm practising and got really stuck on this one.

# Answer
Let the original sequence be $a\_1,\ldots,a\_n$. After removing a contiguous subsequence $a\_{i+1},\ldots,a\_{j-1}$, we are left with $a\_1,\ldots,a\_i,a\_j,\ldots,a\_n$ (possibly $i = 0$ or $j = n+1$). In particular, if $a\_1 \leq a\_2 \leq \cdots \leq a\_I \> a\_{I+1}$ then $i \leq I$, and if $a\_{J-1} \> a\_J \leq a\_{J+1} \leq \cdots \leq a\_n$ then $j \geq J$. In other words, we can remove all elements $a\_{J+1},\ldots,a\_{I-1}$. Renaming elements, we are left with two non-decreasing sequences $$a\_1,\ldots,a\_s,b\_1,\ldots,b\_t.$$ Merge both sequences, and consider all places in the merged sequence in which a $b$-element follows an $a$-element, say $a\_i,b\_j$. This corresponds to the sorted sequence $a\_1,\ldots,a\_i,b\_j,\ldots,b\_t$ of length $i+t-j+1$. Go over all such places and choose the one maximizing the length of the corresponding sequence. (You also need to consider some corner cases, which I leave to you.)

This algorithm runs in linear time, and so is asymptotically optimal.
> 4 votes

---
Tags: algorithms, optimization, dynamic-programming, subsequences
---


# Question
Title: Why are computable functions also called recursive functions?
In computability theory, computable functions are also called recursive functions. At least at first sight, they do not have anything in common with what you call "recursive" in day-to-day programming (i.e., functions that call themselfes).

What is the actual meaning of recursive in the context of computability? Why are those functions called "recursive"?

To put it in other words: What is the connection between the two meanings of "recursiveness"?

# Answer
> 17 votes
**Define some basic functions:**

* zero function

$$ zero: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto 0 $$
* successor function

$$ succ: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto x + 1 $$
* projection function

$$p\_i^n: \mathbb{N}^n \rightarrow \mathbb{N} : (x\_1, x\_2, \dots, x\_n) \mapsto x\_i $$

From now on I will use $\bar{x\_n}$ to denote $(x\_1, x\_2, \dots, x\_n)$

**Define a composition:**

Given functions

* $g\_1, g\_2, \dots, g\_m$ each with signature $\mathbb{N}^k \rightarrow \mathbb{N}$
* $f : \mathbb{N}^m \rightarrow \mathbb{N}$

Construct the following function:

\begin{align} h: \mathbb{N}^k \rightarrow \mathbb{N}: \bar{x\_k} \mapsto h(\bar{x\_k}) = f ( & g\_1(\bar{x\_k}), g\_2(\bar{x\_k}), \dots, g\_m(\bar{x\_k}) ) \end{align}

**Define primitive recursion:**

Given functions

* $ f: \mathbb{N}^k \rightarrow \mathbb{N} $
* $ g: \mathbb{N}^{k+2} \rightarrow \mathbb{N} $

Construct the following (piecewise) function:

$$ h : \mathbb{N}^{k+1} \rightarrow \mathbb{N} : \\ (\bar{x\_k}, y + 1) \mapsto \begin{cases} f(\bar{x\_k}), & y + 1 = 0 \\ g (\bar{x\_k}, y, h(\bar{x\_k}, y)), & y + 1 \> 0 \end{cases} $$

---

All functions that can be made using **compositions** and **primitive recursion** on **basic functions**, are called **primitive recursive**. It is called that way by definition. While a link with functions that call themselves exists, there's no need to try and link them with each other. You might consider recursion a homonym.

This definition and construction above was constructed by Gödel (a few other people were involved too) in an attempt to capture all functions that are computable i.e. there exists a Turing Machine for that function. Note that the concept of a Turing Machine was not yet described, or it was at least very vague.

(Un)fortunately, someone called Ackermann came along and defined the following function:

* $Ack : \mathbb{N}^2 \rightarrow \mathbb{N}$
* $Ack(0, y) = y+1$
* $Ack(x+1, 0) = Ack(x, 1)$
* $Ack(x+1, y+1) = Ack(x, Ack(x+1,y))$

This function is computable, but there's no way to construct it using only the constructions above! (i.e. $Ack$ is not primitive recursive) This means that Gödel and his posse failed to capture all computable functions in their construction!

Gödel had to expand his class of functions so $Ack$ could be constructed. He did this by defining the following:

**Unbounded minimisation**

* $g : \mathbb{N}^k \rightarrow \mathbb{N}$
* IF $\left\[f(\bar{x\_k}, y) = 0 \text{ AND } \\f(\bar{x\_k}, z) \text{ is defined } \forall z \< y \text{ AND } \\f(\bar{x\_k}, z)\neq 0\right\]$
THEN
$g(\bar{x\_k}) = y$
ELSE
$g(\bar{x\_k})$ is not defined.

This last one may be hard to grasp, but it basically means that $g((x\_1, x\_2, \dots, x\_k))$ is the smallest root of $f$ (if a root exists).

---

All functions that can be constructed with all the constructions defined above are called **recursive**. Again, the name **recursive** is just by definition, and it doesn't necessarily have correlation with functions that call themselves. Truly, consider it a homonym.

Recursive functions can be either **partial recursive functions** or **total recursive functions**. All partial recursive functions are total recursive functions. All primitive recursive functions are total. As an example of a partial recursive function that is not total, consider the minimisation of the successor function. The successor function doesn't have roots, so its minimisation is not defined. An example of a total recursive function (which uses minimisation) is $Ack$.

Now Gödel was able to construct the $Ack$ function as well with his expanded class of functions. As a matter of fact, every function that can be computed by a Turing machine, can be represented by using the constructions above and vice versa, every construction can be represented by a Turing machine.

If you're intrigued, you could try to make Gödel's class bigger. You can try to define the 'opposite' of unbounded minimisation. That is, **unbounded maximisation** i.e. the function that finds the biggest root. However, you may find that computing that function is hard (impossible). You can read into the **Busy Beaver Problem**, which *tries* to apply unbounded maximisation.

# Answer
> 20 votes
The founders of computability theory were mathematicians. They founded what is now called computability theory before there was any computers. What was the way mathematicians defined functions that could be computed? By recursive definitions!

So there were recursive function before there were any other model of computation like Turing machines or lambda calculus or register machines. So people referred to these function as recursive functions. The fact that they turned out to be exactly what Turing machines and other models can compute is a later event (mostly proven by Kleene).

We have the simple definition of a recursive function which is now called primitive recursive function. There were not general enough (e.g. Ackermann's function) so people developed more general notions like $\mu$-recursive functions and Herbrand-Gödel general recursive functions that did capture all computable functions (assuming the Church's thesis). Church claimed that his model of lambda calculus captured all computable functions. Many people, and in particular Gödel, were not convinced that these capture all functions that can be computed. Until Turing's analysis of computation and introduction of his machine model.

The name of the field used to recursion theory. However there has been a successful push in recent decades to change the name to something more appealing from recursion theory to something more computer sciency (vs. mathy). As a result the field is now called computability theory. However if you look at books, papers, conferences, etc. in the early decades they are called recursion theory and not computability theory. Even the title of Soare's own 1987 book (who was the main person behind the push to change the name to computability theory) is "Recursively Enumerable Sets and Degrees".

If you want to know more about the history a fun and good place to read about it is the first chapter of Classical Recursion Theory by Odifreddi.

# Answer
> 8 votes
Robert Soare wrote an essay about this issue. According to him, the term (general) recursive functions was coined by Gödel, who defined them using some sort of mutual recursion. The name stuck, though later on other equivalent definitions were found.

For more information, I recommend Soare's essay.

# Answer
> 0 votes
instead of putting a long comment decided to add an answer:

Because they are **defined recursively**, i.e "*more complex functions are defined in terms of previously defined, simpler functions*"

This kind of *iterative* or *incremental* procedure creates well-defined functions (in the mathematical sense)

This is the meaning of *recursiveness* in mathematical parlance. See below how this relates to recursion in programming parlance.

Compare this procedure with techniques and methods like (mathematical) induction which is also an example of recursiveness in mathematics.

Programming has a mathematical vein as well as an engineering one.

This (usualy constructive) procedure is also refered as "*bootstrapping*" in Operating Systems parlance.

**However** a *runtime recursion* of the same function (i.e *caling itself during its runtime*), since it must (hmm, should) happen on already computed values (or arguments), or in other words, in the **part of the result set already computed**, is also recursive in the above sense, i.e "*defined w.r.t previously defined functions (and their values)*"

Else is not well-defined, and leads to such things like Stack Overflow :))))

To give a further example from Operating Systems, a runtime recursion (calling itself) can be taken as the analog of an *operating system rebooting after a certain update* (e.g core update). Many OSes do the following procedure:

1. an initial boot to load low-level routines (e.g I/O)
2. do the necessary updates (using the low-level routines)
3. re-boot (effectively, re-calling itself), but this time loading the more complex routines (or even the whole system)

Auberon's beautiful answer demonstrates a procedure of this kind in more detail.

---
Tags: computability, terminology, history
---


# Question
Title: Why use minhash instead of directly computing Jaccard coefficient?
Minhash is said to estimate the Jaccard coefficient - supposedly because it's faster to compute. Given two sets $A$ and $B$, minhash (with k hash functions) takes $O(k\*(|A|+|B|))$ time to compute.

But isn't it possible to also compute the Jaccard coefficient $\frac {|A \cap B|} {|A \cup B|} $ in $O(|A|+|B|)$ time by simply doing :

```
1  Given collections A' and B', create hash set datastructures A and B from them.
2. foreach(a in A){ if(a in B)sizeOfIntersection++; }
3. sizeOfUnion = A.size() + B.size() - sizeOfIntersection;
4. Jaccard = sizeOfIntersection / sizeOfUnion;

```

Assuming \[an ammortized\] O(1) hash set membership lookup, the complexity of the above is O(|A|+|B|), which is less than with k hash-function minhash.

So how is Minhash more efficient, and what benefit does it provide?

# Answer
If you only have two sets $A,B$, then you are right: there is no point computing the minhash.

But now suppose you have sets $A\_1,A\_2,\dots,A\_n$, and you want to know whether there exists any pair $A\_i,A\_j$ with high Jaccard similarity. It's more efficient to compute the minhash of each $A\_i$ once, and then use that to help you look for a pair that hash high Jaccard similarity. As a trivial observation, once you've already computed the min-hashes of them all, then estimating the Jaccard similarity of $A\_i,A\_j$ can be done in $O(k)$ time using the existing minhashes, which can be significantly faster than the naive $O(|A|+|B|)$-time method.

(In fact, once you have the minhashes of all of the sets, there are even cleverer ways to look for pairs $A\_i,A\_j$ with large similarity.)

This is even mentioned on the Wikipedia page for Minhash: see the section labelled Time analysis. However, you do have to read it pretty carefully to get the point.
> 4 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sets
---


# Question
Title: Expected number of common edges for a given tree with any other tree
So I am working on a problem where I have a set of (labeled) nodes and I have a tree structure (rooted) over that set of nodes. The goal for me is to automatically generate that tree structure. To find the performance of my algorithm, I am trying to use the score as the fraction of edges that I have common in the generated tree and the given tree. I want to compare this score with an expected value of the fraction if we generate the tree randomly (equal probability for all tree structures). What should be my approach to find this? Is there a computable efficient method for this? The brute force method (with some optimizations so that I only iterate on the structure without the labels) usually fails over n\>10.

I understand if there is some efficient method to find no. of trees with k common edges then my problem is solved to much extent, but I am having a hard time to solve this as well.

EDIT: The edges are considered to be directed, towards the root.

# Answer
> 2 votes
Let $T$ be your reference tree (on $n$ vertices), and let $R$ be the random tree. Label the edges of the tree randomly from $1$ to $n-1$. Let $X\_i$ denote the event that the $i$th edge of $R$ is an edge of $T$. Linearity of expectation shows that the expected size of $T \cap R$ is $\sum\_i \Pr\[X\_i\]$. Each $X\_i$ is a uniformly random edge, and so it belongs to $T$ with probability $|T|/\binom{n}{2} = 2/n$. Hence the expected size of the intersection is $(n-1) \cdot 2/n = 2(1-1/n)$.

---
Tags: algorithms, graphs, machine-learning, trees, data-mining
---


# Question
Title: What is the difference between $\log^2(n)$, $\log(n)^2$, $(\log n)^2$, $\log (n^2)$ and $\log \log n$?
In research articles (e.g. this one's abstract), I often see the complexity of an algorithm expressed using a somewhat ambiguous notation:

* $\log^2(n) = ?$
* $\log(n)^2 = ?$
* $(\log n)^2 = (\log(n)) \times (\log(n))$
* $\log(n^2) = \log(n \times n)$
* $\log \log n = \log(\log(n))$

The last three case are easy enough to understand, but what about the first two? The operator precedence is unclear. Do they mean $\log(n \times n)$, or do they mean $(\log(n)) \times (\log(n))$, or do they mean $\log(\log(n))$?

Citing a reliable source would be a plus, so that I can confidently add this information to Wikipedia.

Note I'm asking about the meaning of big-O or about $O(\log n)$ complexity. I'm interested in what the $^2$ means (square the $n$, square the result of $\log(n)$, or $\log^2$ = $\log \cdot \log$).

# Answer
> 8 votes
Regarding the operator precedence, as specified the other answers:

```
log²(n) : possibly ambiguous
              most commonly 'log(n) * log(n) '
              but possible that some writers intend 'log(log(n))'

log(n)² : ambiguous, log(n) * log(n) or 2log(n)

```

---

Now, you asked about their meaning in the context of asymptotic behaviour and, specifically, Big-O notation. Below follows a note regarding seeing research articles state that the time complexity of an algorithm is `log(n²)`, which is, in the context of Big-O notation, somewhat of a misuse of the notation.

First note that

```
 log(n²) = 2log (n)

```

If some some arbitrary function `f(n)` is in `O(log(n²)) = O(2log(n)`, then we can show that `f(n)` is in `O(log(n)`.

From the definition of O(n), we can state the following

```
f(n) is in O(g(n))

=> |f(n)| ≤ k*|g(n)|, for some constant k>0                 (+)
                      for n sufficiently large (say, n>N)

```

See e.g. this reference covering Big-O notation.

Now, if `f(n)` is in `O(2log(n)`, then there exists some set of positive constants `k` and `N` such that the following holds

```
    |f(n)| ≤ k*|log(n)|, for n>N

<=> |f(n)| ≤ k/2*|2log(n)|, for n>N                          (++)

```

Hence, we can just choose a constant `k2=k/2` and it follows from `(++)` that `f(n)` is in `O(log(n)`.

**Key point:** The purpose of this explanation is that *never* should you see an article describe the asymptotic behaviour of an algorithm as `O(log(n²))`, as this is a redundant way of saying that the algorithm is in `O(log(n))`.

---

For explanations regarding what different `O(log(n)` variations means with regard to the algorithms behaviour, see e.g. the links provided by other answers, as well as the numerous threads on SO covering these subject (e.g. time complexity of binary search, and so on).

# Answer
> 5 votes
For the first one, you can find an answer here:

> (log(n))² means log²(n)

And from this question for example you can guess that:

> log(n)² = (log(n))²

So both the first and the second essentially mean

> (log(n)) × (log(n))

*(Unfortunately, not with more reliable sources than stackexchange...)*

# Answer
> 3 votes
$\log^kn = \log^k(n) = \left(\log(n)\right)^k = \underbrace{\log (n)\* \log (n) * \dots * \log (n)}\_{\text{k times}}$

$\log n^k = \log (n^k) = \log (\underbrace{n * n * \dots * n}\_{\text{k times}})$

I think $\log (n)^k$ is a bad notation, since $\log(\cdot)$ is a function and brackets must be used in order to resolve ambiguity. However, my intuitions say that

$\log (n)^k = \left(\log(n)\right)^k$

Additionally, I suggest this video.

# Answer
> 2 votes
`log²(n) = log(n) * log(n)`

`log(n)²` is indeed ambiguous, it could mean either `log[(n)²]`(i.e. `2log(n)`) or `[log(n)]²` (i.e. `log(n) * log(n)`).

# Answer
> 2 votes
The following is the opinion of the authors of "Concrete Mathematics" (Section 9.3 "$O$ Manipulation"; formatting added by myself):

> Equation (9.27) (i.e. $O(f(n) g(n)) = f(n) O(g(n))$) and (9.23) (i.e. $f(n) = O(f(n))$) allow us to derive the ***identity*** $O(f(n)^2) = O(f(n))^2$. This sometimes helps *avoid parentheses*, since we can write $O(\log n)^2$ instead of $O((\log n)^2)$. Both of these are preferable to $O(\log^2 n)$, which is ***ambiguous*** because some authors use it to mean $O(\log \log n)$.
>
> Can we also write $O(\log n)^{-1}$ instead of $O((\log n)^{-1})$?
>
> No! This is an abuse of notation, since the set of functions $1/O(\log n)$ is neither a subset nor a superset of $O(1/\log n)$. We could legitimately substitue $\Omega(\log n)^{-1}$ for $O((\log n)^{-1})$, but this would be awkward. So we'll restrict our use of "exponents outside of the $O$" to constant, positive integer exponents.

---
Tags: notation, mathematical-foundations
---


# Question
Title: How to choose the number of HOG pyramid layers?
Reading Histograms of Oriented Gradients for Human Detection, I cannot see any discussion of how many layers there should be in the HOG pyramid. OpenCV offers a scaling factor of 1.05 which would mean 15 layers between each halving and Object Detection with Discriminatively Trained Part Based Model suggests 10 layers, but that is for their specific algorithm, I believe.

However, with 1280 x 960 source images these values become prohibitively expensive regarding performance. How does decreasing the number of layers affect detection rates? What exactly am I trading off?

# Answer
That's a good question!

All of this will depend in your application and camera setup. Usually, it works like this: if you have a say 128x128 detector template you will be able to detect the object at this size and greater dimensions. When you go up at the pyramid the image size is smaller, but the detected object (w.r.t the original image) is bigger).

One of the main ways to reduce computational time is to reduce the number of pyramid levels. With all things kept unchanged, this will make you not detect very large objects. By the way, a common trick in object detection is to resize the image such that the object in the scene appear at the right scale w.r.t the pyramid.

If, you change the pyramid step, some object could be missed if their scale does not match any of the pyramid levels. In summary, as I said, it will depend on the setup (e.g. if you have a camera send people from a distance, usually you will need fewer leves of the pyramid).

I recently wrote a paper on using the camera calibration to estimate the best scales for people detection in a surveillance scenario. It could help you:

Fuhr, G.; Jung, C.R., "Camera Self-calibration Based on Non-Linear Optimization and Applications in Surveillance Systems," in Circuits and Systems for Video Technology, IEEE Transactions on , vol.PP, no.99, pp.1-1
> 2 votes

---
Tags: computer-vision
---


# Question
Title: How does the Weibull distribution work as fault model in wireless sensor networks?
I am a little bit confused with the concept of using the Weibull distribution or other distribution for fault model. As I understand, in simulation this distribution is often used for modelling a fault in components.

On the other hand when designing systems we often assume some components might become faulty and we use fault detection method to know where the distinct component is faulty or not.

I want to categorize faulty sensor in 5 groups: transmitter circuit/battery condition/micro controller/receiver circuit and sensor circuit fault and correlated these kinds we can have different attribute in network.

The question is, how can i write the Weibull distribution function to produce these kinds of fault in a wireless sensor networks?

# Answer
Step 1: Fit a Weibull distribution to all transmitter circuit faults (with one set of parameters). Fit a Weibull to battery condition faults (with another set of parameters). You get five different Weibull distributions.

Step 2: During simulation, randomly draw one number from each of the Weibull distributions. This gives you the time until the first transmitter circuit fault, the time until the first battery condition fault, and so on. Pick the smallest number; that's the fault that occurs first. Simulate a fault of that type, at that time. (You can continue the simulation to simulate multiple faults if you want.)
> 0 votes

---
Tags: computer-networks, randomness, modelling, fault-tolerance
---


# Question
Title: primitive recursion on untyped lambda calculus
Does a definition of primitive recursion exist for the untyped lambda calculus? Does the definition of primitive recursion require typing for natural numbers?

The only definitions I can find are for the typed lambda calculus: http://www.math.nagoya-u.ac.jp/~garrigue/lecture/2013\_tenbo/recfun\_en.pdf. Perhaps if I just ignore the types it will still be valid?

# Answer
Famously, the fixed-point operator $Y$ of the untyped $\lambda$-calculus, which has the property that $$ Y\ F=\_{\beta}F\ (Y\ F)$$ for every term $F$, is enough to implement primitive (and indeed, non-primitive!) recursion.

Given any encoding of the natural numbers which allows decrementing, if you have an expression $$ e(n)=C\[e(n-1)\]$$ where $C$ is some programatic context, you can create a term, $P\_e$, defined by: $$ P\_e\equiv\lambda F\ n.C\[F\ (n-1)\] $$

Now it's easy to show that $$(Y\ P\_e)\ n = P\_e\ (Y\ P\_e)\ n= C\[(Y\ P\_e)\ (n-1)\]$$ and so it makes sense to define the function $e$ as $Y\ P\_e$.
> 4 votes

---
Tags: lambda-calculus, primitive-recursion
---


# Question
Title: Recurrence relations when function call is made inside loop
```
int fun (int n)
{
  int x=1, k;
  if (n==1) return x;
  for (k=1; k<n; ++k)
     x = x + fun(k) * fun(n – k);
  return x;
}

```

> What is the value of fun(5)?

I find it difficult to realize a recurrence tree when the functions are called inside loops so I decided to go with the recurrence relations.

This is what I came up with :

However, the recurrence relation given in the solution book is slightly different:

I don't understand where I went wrong. I included **`1`** inside the summation since **`x`** loops with every iteration. So why is the **`1`** in the second equation outside?

# Answer
First, those two summation are not equivalet, the reason that the $1$ is outside is because this line in your code:

```
 int x=1,k;

```

Try to run this "by hand" and you will understand why you are addidng $1$ only once.

$\text{fun}(1)=1\\ \text{fun}(2)=2\\ \text{fun}(3)=5\\ \text{fun}(4)=15$

$$\Longrightarrow \text{fun}(n)=\begin{cases} 1;&&&&&&&&n=1\\ \color{red}1+\displaystyle\sum\limits\_{k=1}^{n-1}\text{fun}(k)\times \text{fun}(n-k)&&&&&&&&n\>1 \end{cases}$$

---

EDIT:

**Step by step for n=3:**

```
int fun (int 3)
{
  int x=1, k;
  if (3==1) return x;
  for (k=1; k<3; ++k)
     x = x + fun(k) * fun(3 – k);
  return x;
}

```

First loop $k=1:$

$x=\color{green}1+\underbrace{\text{fun(1)}}\_{=1}\times \underbrace{\text{fun(3-1)}}\_{=2}=\color{red}3$

Second loop $k=2:$

$x=\color{red}3+\underbrace{\text{fun(2)}}\_{=2}\times \underbrace{\text{fun(3-2)}}\_{=1}=\color{blue}5$
> 3 votes

# Answer
fun(1)=1

fun(2)=2

To understand, fun(3), just run the loop from k = 1 to 2.

At k = 1, fun(1) * fun( 3 - 1 ) will be called, whose values we already know are fun(1) and fun(2), i.e. 1 and 2 respectively.

At k = 2, fun(2) * fun( 3 - 2) will be fun (2) * fun(1), again which equal to 2\*1 = 2;

So, adding them up, 1 + (1\*2) + (2\*1) = 1 + 2 + 2 = 5.

Similarly, try running the for loop within the limits and go on substituting the values of funs which you already know.

Similarly, for fun (4) will be , 1 + (fun(1)\*fun(2)) + (fun(2)\*fun(2)) + (fun(3)\*fun(1)) = 1 + (1\*5) + (2\*2) + (5\*1) = 15.

To understand the code, in the loop we can see that every time the loop runs, the value fun(k) * fun(n-k) is being added to previous value of x. Where x started from 1.

If you have to imagine a recurrence tree, every node whose value is n will have (n-1)\*2 calls to fun as their children, except fun(1).
> 2 votes

---
Tags: algorithms, algorithm-analysis, recurrence-relation, recursion, loops
---


# Question
Title: Simple Bayesian classification with Laplace smoothing question
I'm having a hard time getting my head around smoothing, so I've got a very simple question about Laplace/Add-one smoothing based on a toy problem I've been working with.

The problem is a simple Bayesian classifier for periods ending sentences vs. periods not ending sentences, based on the word immediately before the period. I'm collecting the following counts in training: number of periods, number of sentence-ending periods (for the prior), words and counts for words before sentence-ending periods, and words and counts for words before not-sentence-ending periods.

With add-one smoothing, I understand that

$$P(w|\text{ending}) = \frac{\text{count}(w,\text{ending}) + 1}{\text{count}(w) + N},$$

where $P(w|\text{ending})$ is the conditional probability for word $w$ appearing before a sentence-ending period, $\text{count}(w,\text{ending})$ is the number of times $w$ appeared in the training text before a sentence-ending period, $\text{count}(w)$ is the number of times $w$ appeared in the training text *(or should that be the number of times it appeared in the context of any period?)*, and $N$ is the "vocabulary size".

The question is, what is $N$?

Is it the number of different words in the training text? Is it the number of different words that appeared in the context of any period? Or just in the context of a sentence-ending period?

# Answer
The correct formula is

$$P(w|\text{ending}) = \frac{\text{count}(w,\text{ending}) + 1}{\text{count}(w) + N},$$

where $N$ is the number of possible values of $w$. Here $w$ ranges over the set of all words that you'll ever want to estimate $P(w|\text{ending})$ for: this includes all the words in the training text, as well as any other words you might want to compute a probability for. For instance, if you limit yourself to only computing probabilities for English words in a particular dictionary, $N$ might be the number of words in that dictionary.

---

The intuition/idea behind add-one smoothing is: in addition to every occurrence of a word in the training set, we imagine that we see one artificial "occurrence" of each possible word too -- i.e., we augment the training set by adding these artificial occurrences (exactly one per possible word), and then compute probabilities using the ordinary unsmoothed formula on this augmented training set. That's why we get $+1$ in the numerator and $+N$ in the denominator; $N$ is the number of artificial occurrences we've added, i.e., the number of possible words.
> 2 votes

---
Tags: machine-learning, classification, bayesian-statistics
---


# Question
Title: How does the CPU know to get data from or send data to a peripheral device?
We were talking today, in Intro to Programming, about machine language. I know it's a bunch of 0's and 1's. Let's say I compile the following C++ program on an x86 machine:

```
 #include <string>
 #include <iostream>
using namespace std;
int main()
{
cout << "Enter something";
string input;
cin >> input;
return 0;
}

```

Now, cin - as I understand - is an input stream. The computer gets input from the keyboard and places it in cin to be read by the program. My question is, how does the CPU know it's supposed to get input from the keyboard when, at the end of the day, the program is just 1's and 0's?

My understanding is that the machine code is kind of broken up.

# Answer
> 3 votes
Keyboard input is handled through an interrupt – a signal sent to the CPU by the motherboard in response to your pressing a key. The CPU maintains a table of functions to call for each type of interrupt, and the operating system sets this so that control passes to it whenever a key is pressed.

The operating system maintains a buffer of pressed keys, and passes on this event to the software currently capturing the keyboard (if any), causing the call of an *event handler* set by the piece of software. If you run your program from a terminal, then the terminal is the relevant piece of software. It stores the keystrokes in its own buffer, which the C standard library has access to. (In terminal-based operating systems such as DOS or a Unix shell, this is handled by a *system call*, which is a function executed by the operating system.) The C++ iostream library, which is what your program actually uses, is a wrapper of the C standard library.

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


# Question
Title: Should Kolmogorov complexity include all resources or just program size?
I've been thinking about pi and Kolmogorov complexity (Kc).

As the digits of pi are randomly distributed (and infinite) , they can't be compressed with a typical compression program. Through the prism of Kc, it would seem that a generating program (e.g. Gauss-Legendre algorithm) is much smaller than the output sequence hence characterising pi as **not random**.

The usual semantics revolving around Kc only mention program size so the above definition holds. Running the Gauss-Legendre algorithm comes at the cost of huge storage, processing power and some electricity. These resources increase (towards infinity) in some relation to the number of digits generated. If Kc is redefined as overall resources and not program size, pi becomes **random**.

Should Kc be restated as being resource based and not solely program size based, or is that an abstraction too far?

P.S. This is not a question of whether pi is random, but about a definition of Kolmogorov complexity.

# Answer
> 6 votes
> Should Kc be restated as being resource based and not solely program size based?

No. If you change the definition like that, you get a different concept, and the different concepts deserves its own different name. If you want to examine that concept, you should give it its own name. Kolmogorov complexity is a standard term with an accepting meaning; trying to "change" its meaning would only cause confusion.

Instead, if you want to study that alternative concept, give it a new name, and then study its properties. There's no need to change the existing definition of Kolmogorov complexity: Kolmogorov complexity is an interesting and useful concept to have in one's vocabulary. Removing it from our mental toolbox would only make our intellectual scope poorer.

To give you an analogy: If curves of the form $y=ax^2+bx+c$ are more useful in a practical application than lines, should we re-define the term "linear" to mean a function that can be expressed as $y=ax^2+bx+c$? No, that would only cause confusion. Instead, we give a different name (quadratic) to the different concept.

---
Tags: randomness, kolmogorov-complexity
---


# Question
Title: Connecting an unconnected forest of subtrees in a graph?
If I have a weighted graph $G=(V,E)$ and three subgraphs $T\_1$, $T\_2$ and $T\_3$ in $G$ which are trees and all unconnected from each other.

What is the best way to connect these three trees such that the resultant connected tree is of minimal cost?

If it helps, I have already used the floyd-warshall algorithm to calculate the total distance matrix of $G$.

I was thinking of just iterating over all pairs of vertices $(T\_1,T\_2)$, $(T\_1,T\_3)$ and $(T\_2,T\_3)$ in the distance matrix and find two values from two of those groups that sum to the least. But that feels like it would be very inefficient.

essentially iterating over every vertex almost twice to get the distance values, and then iterating over those values twice again to find the smallest sum. Ending up with a complexity of like $\mathcal{O}(V^3)$ or $\mathcal{O}(V^4)$ or something (forgive me, its been a few years since i did any complexity theory)

Is there a simpler, more efficient solution that I am missing?

**EDIT:**
I have previously worked out a solution (not necessarily very efficient), to the problem if there are only two trees. Using the distance matrix, I iterate over every pair of vertices in $T\_1$ and $T\_2$, and then use dijkstra's algorithm to find the shortest path that joins the pair of vertices with the lowest value in the distance matrix.

Am I on the right track at least for the instance where there are only 2 trees? This method seems to get a lot trickier and much less efficient when there are more than 2 trees.

**CLARIFICATION:**
There seems to have been a bit of confusion (in a subsequently deleted comment) about what I am asking, so I will be more explicit.

The subgraphs $T\_1$, $T\_2$ and $T\_3$ are trees in $G$, but are not connected to eachother.

here is an example:

I am trying to work out a good method of connecting all three trees such that it results in the smallest total cost

From the example I have given, it is pretty trivial to connect $T\_2$ and $T\_3$, just find an MST over the union of their two vertex sets because they share a single edge. However my problem stems from trying to connect $T\_1$ to the rest; there are a lot of ways in which I can draw a path from $T\_1$ to the other two, but I want to find the shortest one.

The only way I have thought of so far is to iterate over all the vertices in $T\_1$ and see which one is closest to the vertices in $T\_2$ and $T\_3$ and then use dijkstra to find the shortest path. But this becomes pretty inefficient with very large scale graphs.

So I am looking for a more efficient method of doing this.

I hope that is more clear.

**UPDATE:**
In response to @D.W.'s answer to my related question here on solving a simplified version of this problem with only two vertex sets.

In order to extend that solution to this, more complicated, instance of the problem with three distinct vertex sets. Do I just need to create 3 *dummy* vertices $\\{t\_1,t\_2,t\_3\\}$in $G$ with edge lengths 0 that link to $T\_1$, $T\_2$ and $T\_3$ respectively, and then run dijkstra 3 times: $t\_1 \rightarrow t\_2$, $t\_1 \rightarrow t\_3$ and $t\_2 \rightarrow t\_3$, to find the minimum path $p\_1$ that joins two of the three vertex sets; then if, say, the shortest path lay between $t\_2$ and $t\_3$ then run dijkstra again to find the shortest path $t\_1 \rightarrow t\_4$ where $t\_4$ is a dummy vertex with 0 edge cost linking to the set $\\{T\_2 \cup T\_3 \cup p\_1\\}$?

Or is that making things too complicated?

# Answer
> 2 votes
Your problem is known as the group Steiner tree problem, and it is NP-hard. More specifically, in this problem we are given a weighted graph $G=(V,E)$, and $k$ (vertex-disjoint) sets $S\_1,S\_2,\ldots,S\_k \subseteq V$, and asked to find the minimum cost tree that uses at least one vertex from each $S\_i$, where $i \in \[k\]$.

But don't fall into despair yet. Luckily for you, you have a very small number of "terminal trees", specifically three. The good news is that the problem is solvable in polynomial-time for fixed $k$. Moreover, it can be solved in something called FPT time, in fact there is an algorithm solving it running in $2^k n^{O(1)}$ time. When $k = 3$ is fixed, this is polynomial time. Let me shortly describe the idea, or at least give the pointers for a possible algorithm.

Misra et al. \[1\] observe that group Steiner tree reduces to the so-called directed Steiner out-tree problem. This, in turn, is solvable in a certain time bound using the idea of branching walks (of Nederlof) and inclusion-exclusion. The added nice thing is that the algorithm (as usual with such an inclusion-exclusion approach) needs only polynomial space. Moreover, there is evidence such algorithms are practical too. The Misra et al. \[1\] paper gives the necessary references.

---

\[1\] Misra, N., Philip, G., Raman, V., Saurabh, S., & Sikdar, S. (2012). FPT algorithms for connected feedback vertex set. Journal of combinatorial optimization, 24(2), 131-146.

---
Tags: graphs, trees, shortest-path
---


# Question
Title: Class C can have _______ 1s with the remaining bits 0s
> A subnet mask in class C can have \_______ 1s with the remaining bits 0s.

MyApproach:

Class C subnet is 255.255.255.0.So, accordingly it has 9 1s on first byte,9 1s on second byte and 9 1s on third byte.etcSo total 27 1s but the Ans is 25

@Edit

For 255 it has 8 1s on first byte,8 1s on second and 8 1s on third.=24 How 25?

> Can anyone guide What I am doing wrong?

# Answer
Check again your count of how many 1's are in the binary representation of 255. Beyond that, there's nothing wrong with your reasoning. The answer "25" is wrong.

Some examples are available in Wikipedia: https://en.wikipedia.org/wiki/Subnetwork
> 1 votes

---
Tags: computer-networks
---


# Question
Title: Segmenting a human body point cloud into limbs
I have a human body point cloud taken through a Kinect (v1). Now, I want to segment the point cloud into different parts, namely hands, lower arms, upper arms, torso, upper legs, lower legs, feet and head.

Here's the method I'm currently using:

* I get the approximate skeleton from the point cloud using OpenNI
* I take those points from the point cloud that are at a distance **d** from the line that is the bone (obtained from OpenNI). This distance **d** is currently set differently for different parts, based on observations only.

The problem with the above method is that it's not very robust. The parameter **d** can be different for people with different body types and also this is prone to errors since at the joints, the points within the circle of radius **d** will lie in both the parts.

Is there a better way of segmenting the point cloud?

---

**Edit:** This is what I get from OpenNI

The blue portion is the lower arms segmented using the above algorithm.

# Answer
> 3 votes
Suggestion: for each point $P$ in the point cloud, find which bone it is nearest to, and associate it with that bone. In other words, find which point $Q$ on the skeleton is closest to $P$, and associate $P$ with $Q$. Now associate $Q$ with a particular part of the skeleton (e.g., arm, leg, etc.); that will let you associate $P$ with a particular part of body (e.g., arm, leg, etc.). Do this for each point in the point cloud.

Try that -- it's a very simple approach, and it might just work.

# Answer
> 1 votes
I would try the following:

**for** **each** joint $j$:

1. $p\_1 \gets$ closest extreme point to $j$ in direction $\vec{d}$
2. $p\_2 \gets$ closest extreme point to $j$ in direction $-\vec{d}$
3. Draw vector $\vec{p\_1p\_2}$
4. Let $\vec{N}, -\vec{N}$ be two normal vectors of $\vec{p\_1p\_2}$
5. Draw two rays $a\_1$, $a\_2$ in the direction of $\vec{N}$ and $-\vec{N}$ respectively.
6. Let $i\_1$ and $i\_2$ be the points belong to another area (such as gray area or another body part) which are closest to the origin of $a\_1$ and $a\_2$ respectively.
7. $p\_3 \gets$ closest extreme point to $i\_1$ in direction $\vec{f}$
8. $p\_4 \gets$ closest extreme point to $i\_1$ in direction $-\vec{f}$
9. $p\_5 \gets$ closest extreme point to $i\_2$ in direction $-\vec{g}$
10. $p\_6 \gets$ closest extreme point to $i\_2$ in direction $-\vec{g}$
11. Mark the area $(p\_1, p\_2, p\_3, p\_4, p\_5, p\_6)$ as body part.

I am not familiar with KINECT nor OPENNI, but given the green circles, representing joints, I would use above algorithm.

---
Tags: algorithms, computer-vision, graphics
---