title: Asymptotic Improvements in Hardware?

text:
# Question
Title: Asymptotic Improvements in Hardware?
One of the main benefits of algorithm analysis, is that it offers asymptotic improvements to complexity as opposed to hardware, which offers only constant improvements. E.g switching to a super computer from a workstation might give a $\times 1,000,000$ increase in speed, but if that supercomputer is running a linear search on a sorted array, it will eventually be trumped by a desktop running a binary search for large enough problem sizes.

My question is this:

> Are there any improvements in hardware(theoretical or practical) that could offer an asymptotic speedup over pre-existing hardware?

In this case pre-existing refers to at least 3rd generation computing technology. I'm not really interested in speedups over vacuum tubes.

# Answer
Quantum computers, if they ever get built, will be asymptotically faster than existing computers in certain tasks. Limited quantum computers might already exist, though this is a contentious issue.
> 6 votes

# Answer
Three-dimensional memory systems can improve the asymptotic complexity.

Suppose the CPU is in the center of the world, and the rest of the world is filled with memory cells. The CPU broadcasts a request to memory and waits a finite amount of time for a response.

If the memory is in the form of a 2-dimensional plane, then the CPU waiting $n$ nanoseconds can reach $\Theta(n^2)$ memory cells.

But if the memory is in the form of 3-dimensional space, then the CPU waiting the same $n$ nanoseconds can reach $\Theta(n^3)$ storage cells.

When a program needs to use $m$ memory cells for its execution, the 2D memory technology has a latency of $\Theta(\sqrt\[2\]{n})$ per operation, whereas the the 3D memory has a latency of $\Theta(\sqrt\[3\]{n})$.
> 6 votes

# Answer
As long as you stay in the realm of real, classical computation (i.e. a finite, discrete symbol set; finite control; finite memory): *no*. Real machines do not have any asymptotic nature so you can not speed them up asymptotically, either.

If you allow different theoretical computation models, the answer is trivially *yes*: different models imply different complexities for the same problem. Just compare TMs with RAMs.
> 1 votes

---
Tags: asymptotics, computer-architecture
---


title: Find sets with given union

text:
# Question
Title: Find sets with given union
We are given positive integers $n$, $m$ and a set $S$ of subsets of the set $\\{1,2,...,n\\}$ with $|S| = m$.

For example:

$n = 5,\\,\\, m = 4,\\,\\, S = \\{\\, \\{1,2\\}, \\{1,3\\}, \\{4,5\\}, \\{2,3\\} \\,\\}.$

What is the fastest way to find the minimal subset $S'$ of $S$ such that the union of sets in $S'$ is equal to $\\{1,2,...,n\\}$.

In our example, there are 3 possible answers:

$S' = \\{\\,\\{1,2\\}, \\{1,3\\}, \\{4,5\\}\\,\\} \\ S' = \\{\\,\\{1,2\\}, \\{2,3\\}, \\{4,5\\}\\,\\} \\ S' = \\{\\,\\{1,3\\}, \\{2,3\\}, \\{4,5\\}\\,\\}$

# Answer
This is related to the Hitting-Set-Decision-Problem:

> Given $U=\\{1,\ldots , n\\}$ and $S\subseteq 2^U $, integer $k$
>
> Decide whether $C\subseteq S $ exists s.t. $\cup\_{X \in C} X = U$ and $|C| \leq k$

The problem is NP-COMPLETE and thus we do not know whether a polynomial algorithm exists. The optimization problem which you refer to is NP-hard. There are approximation algorithms (see wikipedia).
> 2 votes

---
Tags: algorithms, time-complexity
---


title: Delta formal definition for DFA

text:
# Question
Title: Delta formal definition for DFA
How can I formally define * for a **dfa** with multiple initial states? I know that the δ formal definition for NFA is δ: Q × ∑ → 2^Q and for DFA it's δ : Q × Σ → Q but what should I do if there is multiple initial states?How can I take into consideration all the options for the initial state?It seem like it should combine the NFA definition and DFA definition.. δ: 2^Q × ∑ → Q maybe?but it doesn't seem right neither.

I would appreciate any help I can get on this matter

# Answer
If you have multiple initial states, then this automata is non-deterministic.
> 1 votes

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


title: NFA automata with ϵ moves proof

text:
# Question
Title: NFA automata with ϵ moves proof
let's say L is a regular language. And there in an NFA automata with epsilon moves A,in which for every accepting state δ(q,σ)=Ø. How can I prove that there must be an automata A as defined for L?

# Answer
I will give you some intuition how to build such NFA.

Because L is a regular language, then we can find deterministic finite automata F which accepts this language. Based on that we will build our NFA. Let's add epsilon transitions from all F's accepting states to new state which will be the only accepting state in our NFA. You can now prove, that such automata will accept L.
> 1 votes

---
Tags: automata, finite-automata, proof-techniques
---


# Question
Title: Can FPSPACE give exponentially long outputs?
I can't comment on this question, so I ask it here as a new question:

Ricky Demer states there in a comment to the first answer

"\[...\] since FPSPACE can give exponentially long outputs \[...\]"

How can this be? How can an algorithm in FSPACE give an exponentially long output? Does this mean, that we do not count the output space in the definition of FSPACE (contrary to what I have believed so far)?

# Answer
> 8 votes
Space classes always only include working space: the model is that we have a read-only input tape and write-only output tape, plus a read-write work tape (or multiple such tapes) on which we're only allowed to use a bounded amount of space. This definition is necessary for something like LOGSPACE to make any sense: if you counted the output as part of the space used, then even an algorithm such as "just output the input" wouldn't run in LOGSPACE. That's important because we often want to use LOGSPACE reductions between problems.

A simple example of a (nontrivial) FPSPACE algorithm that produces exponentially much output is a SAT solver that just tries every possible combination of values for the variables and outputs the combinations that satisfy the formula. This will produce exponentially long output for the class of inputs $X\_1\lor\dots\lor X\_n$.

Note that, for TIME-bounded complexity classes, we don't have this kind of problem since, on a Turing machine, writing $\ell$ symbols of output always takes at least $\ell$ time steps so, e.g., a polynomial *time* machine can only produce polynomially much output.

---
Tags: complexity-theory, space-complexity
---


# Question
Title: Are there any LTL to _non_ deterministic Rabin automaton translators?
I know of two translators LTL -\> deterministic Rabin automaton:

They produce *deterministic* automata, which can be much larger than their possible non-deterministic variants. Is there a translator LTL -\> *non* deterministic Rabin?

(my synthesis tool could handle *small non-det* Rabin automata but not large though det ones)

# Answer
> 0 votes
You can easily translate LTL to non-deterministic Buchi automata, which can be thought of as a simple fragment of Rabin automata (although they are equally expressive). I don't think any tool would actually output the acceptance condition described as a Rabin condition, but this is very easy to deduce from the Buchi states.

An example of an online tool to do this conversion is: http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/

But I'm sure there are many others, as the construction is relatively simple.

---
Tags: automata, reference-request, simulation, linear-temporal-logic
---


# Question
Title: Does a reduction from sorting imply an $\Omega(n \log n)$ time bound?
I have come across a proof where a certain function ("compute a straight skeleton") is shown to take $\Omega(n \log n)$ time by reducing the problem of sorting to it. The overhead for the reduction itself is linear, thus negligible.

*Now my question is: is this a valid argument?*

---

The original proof appears in: Huber - Computing Straight Skeletons and Motorcycle Graphs: Theory and Practice, page 19, last paragraph.

In summary:

Given a list of $n$ natural numbers, the author constructs a "Polygon with holes" $P$ of structural size $O(n)$ in linear time. The algorithm then computes a straight skeleton $S(P)$, which can be traversed to enumerate the original numbers in sorted order (with constant overhead per number). Thus, the problem of sorting is reduced to computing $S(P)$. The author claims that this implies computing $S(P)$ is in $\Omega(n \log n)$ due to the bound for sorting.

---

It is well know that comparison-based sorting algorithms have $\Omega(n \log n)$ worst-case bounds. However, there are $O(n)$ sorting algorithms such as radix sort or bucket sort which aren't based on comparisons and for which this restriction doesn't apply. As far as I can tell, these are all restricted to certain domains, such as fixed-length integers or strings.

I assume generalizing these algorithms to unrestricted domains would reveal hidden costs. If we consider arbitrary integers, some operations which are assumed to be constant cost would actually be logarithmic in the size of the integer. I don't know, however, if this necessarily has to be the case for all possible sorting algorithms.

I think the author's construction could be used for sorting real numbers (possibly requiring a variable-length encoding), if this strengthens the requirement on the sorting enough to rule out any $O(n)$ (or $o(n \log n)$) sorting algorithms.

Are there any information theoretic arguments showing that, for fully general inputs and all operations strictly accounted for, at least $\Omega(n \log n)$ basic units of work (whether they be comparison or something else) are always needed? If not, does that mean the argument of "by reduction from sorting" doesn't strictly prove a lower bound stronger than $\Omega(n)$?

# Answer
It's not a valid argument. What it *does* prove is that any *comparison-based* algorithm for Problem X must use at least $\Omega(n \log n)$ comparisons. (There *is* a known algorithm for integer sorting whose running time is $O(n \sqrt{\log \log n})$, in some models of computation, but it is not a purely comparison-based algorithm; see here.)
> 3 votes

---
Tags: complexity-theory, reductions, sorting
---


title: Summation with floor in upper bound

text:
# Question
Title: Summation with floor in upper bound
I'm learning about asymptotics and time complexity.
The algorithm I'm analyzing has a for loop that starts at $i = 1$ and ends at $\left \lfloor \sqrt n \right \rfloor$. The body is said to run in $n-i$ steps. I'm trying to do a summation from $i=1$ to $\left \lfloor \sqrt n \right \rfloor$ to come up with a Big Theta, but I am not sure how to deal with the upper bound of the summation. Thank you in advance.

# Answer
You want to estimate $$ S := \sum\_{i=1}^{\lfloor \sqrt{n} \rfloor} (n-i). $$ You can start with the formula $$ S(m) := \sum\_{i=1}^m (n-i) = m \left(n - \frac{m+1}{2}\right). $$ The formula for $S(m)$ is an increasing function for $m \leq n-1/2$ (as you can check by computing the derivative), and so $\sqrt{n} - 1 \< \lfloor \sqrt{n} \rfloor \leq \sqrt{n}$ implies (for $n \geq 2$) that $$ S(\sqrt{n}-1) \< S \leq S(\sqrt{n}+1). $$ Substituting, we get $$ n^{3/2} - \frac{3}{2}n + \frac{\sqrt{n}}{2} \< S \leq n^{3/2} - \frac{n}{2} - \frac{\sqrt{n}}{2}. $$ Therefore $S = n^{3/2} - O(n)$. In particular, $S = \Theta(n^{3/2})$.

We can also get an exact formula: $$ S := \lfloor \sqrt{n} \rfloor \left(n - \frac{\lfloor \sqrt{n} \rfloor + 1}{2}\right). $$
> 4 votes

---
Tags: time-complexity, asymptotics, runtime-analysis
---


title: Properties of a term rewrite rule

text:
# Question
Title: Properties of a term rewrite rule
While doing some bibliography on term-rewriting, I often found these two properties to define a term rewrite rule (see for example here and this one):

> A term rewrite rule is a pair $\langle l,r\rangle$ of terms, written $l \rightarrow r$, such that
>
> 1) $l$ is not a variable
>
> 2) all variables in $r$ occur also in $l$.

I fail to understand the reason of these properties, at least for the definition of a rule (I can see why they would matter for termination or confluence proofs). Why a term rewriting system could not contain a rule such as $x \rightarrow x + 1 - 1$ or $x \rightarrow x + y - y$ ? Just to provide some context, I'm trying to use TRS in the context of obfuscation, where such rewritings have meaning.

Can someone explain why rules composing a TRS would need these properties?

# Answer
> 3 votes
In general, there is no obstacle to *define* a rewrite system as above, and a few sources do indeed require rules 1. and 2. only as additional hypotheses.

However the hypotheses are almost always *necessary* (but not sufficient!) for both termination and confluence, which is indeed the main object of study of rewriting as a field.

Perhaps it's useful to remind why this is the case:

Termination:

1. If $x\rightarrow t$ is allowed as a rule, then *any* term $u$ rewrites to $t\[u/x\]$. In particular, the system is non-terminating.
2. If $l\rightarrow r$ and $r$ contains a fresh variable $y$ not in $l$, then for example, $l\rightarrow r\[l/y\]$, and so the system is non-terminating.

Confluence:

1. Take $x \rightarrow f(x)$ and $g(a)\rightarrow b$. Then $$ g(f(a))\leftarrow g(a)\rightarrow b$$ for instance, breaking confluence. In particular, you can "insert" an $f$ around any term you like, which makes confluence very hard to satisfy.
2. If there are constants $a$ and $b$, then given the rule $f(x)\rightarrow g(y)$, you get $$ g(a)\leftarrow f(x)\rightarrow g(b)$$ again, breaking confluence.

---

Now every theorem involving either termination or confluence *could* be prefaced with "assuming 1. and 2. holds, ..." but it makes sense to restrict your attention to systems where the theorems aren't trivially false. I don't think anyone would be shocked by a paper which lifts these restrictions though, at least condition 2. (condition 1. really creates anarchy). Condition 2. is mostly about non-determinism, for which rewriting is a nice framework in general.

There are *some* systems in which free variables can appear in the RHS, but usually not *any* fresh variable $y$ is allowed: there are additional *constraints* which need to be satisfied, e.g.

$$f(x) \rightarrow f(y)\ \mid\ 0\leq y \< x $$

where $x$ and $y$ are allowed to be integers. These types of systems are called **constraint rewriting systems** and are extensively studied.

---
Tags: term-rewriting
---


# Question
Title: "Huffman coding is unsuitable for text files"?
My lecturer for information theory says that "Huffman coding produces efficient codes but is unsuitable for text files where the letters are represented by a fixed length ASCII code".

I do not understand this statement. I understand that as you change the text file, you'll have to update the probabilities and thus the Huffman table/code itself but I don't think this is what is being referred to here.

Can someone explain?

Thank you so much for all your help

# Answer
> 5 votes
It's not unsuitable, it is just not optimal. That's because letters in human readable text are not independent, but quite strongly correlated. That correlation can be used to get huge savings. For example, the letters q and Q are almost always followed by u. Comma and period are almost always followed by a space character, and period space is almost always followed by an uppercase character. These correlations mean text can be compressed a lot more than by using Huffman coding. But Huffman coding *does* work and will you get some amount of compression.

---
Tags: coding-theory, huffman-coding
---


# Question
Title: Basic queries for Object Detection using deep learning
I have recently started working on the Object detection using deep learning.

I have understood the basic steps of object detection are:

Input Image -\> Object proposals -\> Feature Extraction -\> Training.

I have successfully implemented my own code up to the Object Proposal extraction. Now I want to use deep learning here from that point. For the input to deep learning I have fixed number of object proposals (i.e. 800 proposals from one image) and I need a labeled data. For example: I have a one class dataset. 1) Aircraft, Images number 1-90 are aircraft. and the above number of images have 800 aircraft.
Q: Here, I want to ask that how can I make the labels for the dataset with this configuration of class? According to the tutorials and the Matlab implemented examples I have seen, they used the images and the training labels as the input to the CNN. As I have training images I want to know how can i make training labels.

The input to the CNN network will be proposals (just a cropped regions) around 500 proposals. I want the output is to be if any of the proposals is matched as aircraft then it will appear a bounding box on the big image that this is a aircraft.

Input image.

# Answer
The input to your CNN is a small cropped image, and the output will be a prediction at the label (either "airplane" or "not-airplane"). The training set needs to contain example input-output pairs. So, you need your training set to contain many small images (of the size of a single crop), with a label indicating whether it should be classified as "airplane" or "not-airplane".

How do you do that? You take many large images where you know where the bounding box of the airplanes in each is. For each large image, you crop it around an airplane and add that to the training set, labelled as "airplane". You also crop it somewhere else (in a place not intersecting any of the airplane bounding boxes) and that to the training set, labelled as "not-airplane". You can do the letter step many times, taking many different crops. Repeat this for many large images. Use the resulting training set to train your neural network.
> 2 votes

---
Tags: neural-networks, image-processing, computer-vision
---


title: Knapsack variant

text:
# Question
Title: Knapsack variant
In my line of work, I have encountered the following variant of discrete knapsack and I was wondering if it has already been studied. E.g. We are given a set of 3 items (A,B,C). The goal is to maximize the value carried for a given weight constraint. The variant has the following additional constraints:

* Step 1: The first item choice is always A.

If the finite set with A's weights is $W\_A = \\{ 3.4 ,10, 12.5 \\}$, we pick e.g the value $w=12.5$ *once*.
* The choice $w$ of A's weight affects (deterministically) the weights and values of B and C. I.e. the weigt set $W\_B = f(w)$ and the value set $V\_B = g(w) $. Same for $W\_C, V\_C$.
* Step 2: We want to maximize the value (for a given total weight) by adding items B and C in the knapsack.

Has this been studied before? Is solving it equivalent to performing knapsack once per weight choice in set $W\_A$ ? (i.e. 3 times in the example above)

**UPDATED with more formal definition:**

Assume $n$ finite sets $A\_1,A\_2,...,A\_n$

Assume you are allowed a single choice $a\_i$ from each set, i.e. $a\_1 \in A\_1, ... , a\_n \in A\_n$

Assume the weight $w$ to be a function of all choices i.e. $w=f(a\_1,...,a\_n)$

Assume the value $v$ to be a function of all choices i.e. $v=g(a\_1,...,a\_n)$

Assume a maximum weight capacity $W\_c$

**Goal:**

Find choices $(a\_1,...,a\_n)$ that maximize value $v=g(a\_1,...,a\_n)$, while $w=f(a\_1,...,a\_n) \le W\_c$

# Answer
> 0 votes
This is a generic nonlinear optimization problem. Without further information about $f,g$, there's not much you can say about this. If you have absolutely no knowledge about $f,g$, the best strategy you can do is just exhaustively try all possible choices.

Of course in practice it's likely that $f,g$ will have some structure, and then there might be techniques or heuristics that have the potential to perform better -- but the techniques will depend on the kind of structure they have.

---
Tags: knapsack-problems
---


title: Resolution in First Order Logic

text:
# Question
Title: Resolution in First Order Logic
i have problem with resolution in first order logic

i have :

```
C1  :
¬ Loves(x,F(x) ) or Loves ( G(x) , x )

```

and

```
C2 :

¬ Animal ( X) or Loves ( jack , x )

```

can some one help me why the answer ( after Resolve C1,C2 ) is :

¬ Animal(F(jack) ) or Loves ( G(jack) , jack )

because my answer is :

x/ jack

then i will have :

```
C1 :
¬ Loves ( jack , F(jack ) ) or Loves ( G(jack),jack )

C2 :

¬ Animal ( jack ) or Loves ( jack,jack )

```

and i cant use resolution with Loves (jack,jack) and ¬ Loves (jack,F(jack))

thank you all !!

# Answer
> 1 votes
If you want to resolve C1 with C2, then the only option is for Loves(jack, x) (in C2) to match ¬Loves(x, F(x)) (in C1), and so as you state, you should substitute x=jack in C1 and x=F(jack) in C2. Upon making these substitutions, C1 and C2 become:

> C1\[x/jack\] = ¬Loves(jack, F(jack)) or Loves(G(jack), jack)
>
> C2\[x/F(jack)\] = ¬Animal(F(jack)) or Loves(jack, F(jack))

Resolving the two, we get:

> ¬Animal(F(jack)) or Loves(G(jack), jack)

---
Tags: logic, first-order-logic
---


# Question
Title: Pick matrices such that each partial sum is positive
There is a sequence of $n$ sets, each set contains a constant number of constant-size vectors, e.g:

* $\\{M\_{1,1},M\_{1,2},M\_{1,3},M\_{1,4}\\}$
* $\\{M\_{2,1},M\_{2,2},M\_{2,3},M\_{2,4}\\}$
* ...
* $\\{M\_{n,1},M\_{n,2},M\_{n,3},M\_{n,4}\\}$

The task is to pick, from each set, a single vector, such that the sum of vectors and all the partial sums have no negative elements, i.e, select $i1,i2,...,in$ such that the following vectors:

* $M\_{1,i1}$,
* $M\_{1,i1} + M\_{2,i2}$,
* $M\_{1,i1} + M\_{2,i2} + M\_{3,i3}$,
* ...

have only non-negative elements.

Is anything known about this problem?

# Answer
I'll represent you problem as:

> Let $S\_1, \dots, S\_n$ be sets of $p$ vectors of size $d$. Find a vector $v\_i$ in each $S\_i$ so that for every $k\le n$, $\displaystyle \sum\limits\_{0\le i \le k}v\_i$ has only non-negative coordinates.

**Prop**: This problem is in NP.

*Proof*: Once we have the set of indices / vectors, it's easy to check that they work in polynomial time.

---

**Prop**: For $d\ge 2$ constant and $p\ge 2$ constant, the problem (where $n$ is not bounded) is NP-hard.

*Proof*: We take an instance of the subset-sum problem, which is NP-hard. We have integers $i\_1, \dots, i\_n$. We define $M=|i\_1|+\dots + |i\_n|$.

We take $S\_0=\\{\[M,M\]\\}$. For $1\le k\le n$, $S\_k=\\{\[i\_k, -i\_k\],\[0, 0\]\\}$ and $S\_{n+1}=\\{\[-|M|, -|M|\]\\}$.

All the partial sums will clearly be $\ge 0$ except maybe the last one. The last one will be $\ge 0$ iff $\sum i\_k\ge 0$ and $\sum -i\_k\ge 0$, i.e. iff $\sum i\_k = 0$. So there is a solution iff the subset sum instance has one.

---

The following is a weaker result but it's written so I leave it here.

**Prop**: This problem with $2n$ sets of $p$ vectors of size $2d$ is at least as hard as $CNF-SAT$ on $n$ clauses with $p$ literals per clause and $d$ variables.

*Proof*: Take a set $C\_1,\dots, C\_n$ of clauses on $d$ variables, with $p$ literals per clause. $C\_i=l\_{i,1}\lor \dots \lor l\_{i,p}$.

We write $v\_k$ for the $k$th variable. To a positive literal $l\_{i,j}=v\_k$, we associate the vector $\phi(v\_k)$ of dimension $2d$ that has a $1$ at the $k$th position and $0$s everywhere else. To a negative literal $l\_{i,j}=\lnot v\_j$ we associate the vector $\phi(v\_k)$ of dimension $2d$ with a $1$ in $d+k$th position and zeros everywhere else.

Now, for $1\le k \le n$, we set $S\_i=\\{n\phi(v\_k),n\phi(\lnot v\_k)\\}$ (and we add some useless vectors with big negative values if you really want the set to have size $p$). For $1\le i\le n$, we set $S\_{n+k}=\\{-\phi(l\_{i,j}) / j\in\\{1,\dots,n\\}\\}$.

The idea is the following. In the first $n$ coordinates, we store how many times we can use each of the variable, and in the next $n$ coordinates, we store how many times we can use each of the negation of variables. Then, at the beginning, in the first $n$ sets, we pick for each variable if it's true or false (by adding $n$ to the number of times we can use the variable, or to the number of times we can use its negation). The last $n$ sets then use the variables / negations to make the clause true. To make a clause true, you need to make one literal true, and the true ltterals will be exactly those for which the corresponding coordinate is $\>0$ so that you can subtract $1$ while remaining $\ge 0$. If you chose $v\_k$ to be false, the corresponding coordinate will remain $0$ for the whole thing so if you try to use it, it will become $\<0$. And we add $n$ at the beginning because since there are $n$ clauses, we won't subtract more than $n$.

**Prop**: For $p\ge 3$, the problem (where $d$ and $n$ are not bounded) is $NP$-hard.

*Proof*: The reduction given above reduces $3-SAT$ to it in polynomial time. And $3-SAT$ is NP-hard.
> 2 votes

---
Tags: algorithms, matrices, searching
---


title: decision tree redundancy optimization

text:
# Question
Title: decision tree redundancy optimization
First question in the computer science section. I am currently working on a solution that optimizes decision tree redundancy.

the following is an example of optimization:

```
|  D1   |   D2   | Outcome |
| true  |  false |   Yes   |
| false |  false |   No    |
| true  |  true  |   Yes   |
| false |  true  |   No    |

when optimized gives:

|  D1   |   D2   | Outcome |
| true  |   -    |   Yes   |
| false |   -    |   No    |

```

I need to program this optimization. My decision tree will be different from the one that is shown here. I will have a string outcome, that is in no way a function of the input, and my input will contain 5 different possible inputs. `boolean, string, int, double` and `datetime` data types will also be present. Data in the input fields will be expressed using FEEL format.

**What I want to know** is if there already is a known algorithm for optimizing decision tables like these, or should can I expect to work this out by myself. I don't want to reinvent the wheel here, since this is quite a challenging project. An answer from the stackexchange forum suggested that I post here. He suggested that I start with the Quine–McCluskey algorithm. I looked into this, but it seems like that it's calibrated for boolen based decision tables.

Currently I am considering an approach like the flowing:

1. If there are no duplicate outcomes, stop process
2. Select rules with duplicate outcomes
3. See which decisions are redundant by grouping/merging them
4. etc

~~I am to write the code in C#~~

EDIT: Most inputs will be comparable to a degree. For instance, a string input will be one from a set of strings, and number values will fall in a certain range. But there is no guarantee they always will be.

# Answer
> 2 votes
The ID3 algorithm is one standard way to construct a decision tree. You can also look at successors like C4.5 and others. These aren't guaranteed to give the smallest possible decision tree (that is known to be NP-hard) but the decision tree it outputs is often fairly reasonable.

---
Tags: optimization, decision-problem
---


# Question
Title: How to choose the right input(s) to test my algorithm?
Suppose i want to trace an algorithm (think of it as a flowchart) to understand how it works, i need an input(s) for this algorithm, the question is: how can i determine the right input(s) that goes through all the cases ? Is there any "scientific" method to determine this input?

# Answer
> 1 votes
If you want to automatically explore the state space of a program, you could try a fuzzer like AFL. But usually programmers do this by running the program under a debugger and thinking a bit about how the input needs to look to take a particular path through the code.

# Answer
> 1 votes
To achieve 100% coverage of all the cases, you'll probably need many test cases.

You might want to do some reading on "test case generation". Typically, software developers think through the possibilities and manually write test cases that they think will exercise each code path. However, another option is to use automated tools, like symbolic execution or concolic execution. You can do some searching on those terms and you'll find lots of material on how they work.

---
Tags: algorithms, software-testing, testing
---


title: Generating Pairs of Random Numbers

text:
# Question
Title: Generating Pairs of Random Numbers
Please consider the following probability density function of two variables. \begin{eqnarray\*} f(x\_1,x\_2) &=& \begin{cases} 2(x\_1+x\_2) & \text{for} \\,\\, 0 \le x\_1 \le x\_2 \le 1\\ 0 &\text{ otherwise } \\ \end{cases} \end{eqnarray\*} I would like to generate two random values $X\_1$ and $X\_2$ such that there distribution is consistent with the above probability density function.

If the above probability density function was of just one variable, then I would solve the above problem with the following steps.
1) I would find the distribution function $F$ by integrating.
2) I would generate a random number $a$ on the interval $\[0,1\]$ using the uniform distribution.
3) I would find a number $X$, such that $F(X) = a$. Then $X$ would be the random number I seek.
I am wondering whether a similar method would work for a function of two variables.

# Answer
This is the problem of sampling from a multivariate distribution.

## Simple method

In your case, there is a fairly simple method that will probably suffice. First, randomly pick a value for $X\_1$ according to the *marginal* distribution on $X\_1$. In other words, we define

$$g(x\_1) = \int\_{x\_2=x\_1}^{x\_2=1} f(x\_1,x\_2) \\; dx\_2,$$

the probability density function for $x\_1$, and sample $X\_1$ according to $g$. Since this is a univariate distribution, you already know how to do that (using the methods you described). Here we have $g(x\_1) = 1 + 2x\_1 - 3 x\_1^2$.

Second, randomly pick a value for $X\_2$ according to the conditional distribution on $X\_2$ given the value of $X\_1$ picked earlier. This has probability density

$$h\_{x\_1}(x\_2) = f(x\_1,x\_2)/g(x\_1),$$

which is also a univariate distribution, so you already know how to sample from $X\_2$ (once $X\_1$ is fixed).

## More general method

Alternatively, you can apply any of the general methods for sampling from a multivariate distribution. They are probably shooting a fly with a cannon -- they're probably much more complex than what you need. But if you want a relatively simple one, you could take a look at slice sampling.
> 1 votes

---
Tags: randomness, numerical-algorithms, numerical-analysis, random-number-generator
---


title: ICP algorithm with misaligned point

text:
# Question
Title: ICP algorithm with misaligned point
I am currently working on a project that involves taking a single color frame, performing image segmentation and then visualization of the scene.

I am currently at the stage of performing alignment between two objects - one in my database and one segmented from picture.

Picture data is processed: for each pixel in the color frame, I have depth data, so from a color frame I am capable of generating a (x,y,z) point for each pixel. Therefore, given my segmentation I am capable of generating a Point Cloud for each object.

So given model in my database and a point cloud ( ***which might not represent full object - example: I might just see a corner of a table***, but I still need to align full table model), I would like to align object in my database with points in the cloud.

I have done some research and it seems that the method widely used is the Iterative Closest Point (ICP) algorithm. But I have also a different idea, and I would appreciate your evaluation, as I have some concerns regarding ICP.

**METHOD 1:ICP**

Given that my model and point cloud might not be aligned by default, I have decided to pick points that should be aligned in the result output (assigning corresponding points). So I pick for instance 4 points that should be aligned. However, the issue is obviously that my selection will not be precise and therefore *two points sets do not differ just by rotation and translation, but also by small point misalignment*.

I want to simplify calculations as much as possible to achieve some kind of convergence.

So I was wondering whether someone has any ideas on how to solve it, and whether you can actually use ICP given this misalignment..

**METHOD 2: NON-ICP**

Not use ICP, but rather use a simple one iteration calculation. Calculate centroid of selected points and pick one point from model and a corresponding point from the point cloud (obviously this is approximation, because I can't pick exact point), and create two vectors : "model centroid-to-point" vector and "point cloud centroid-to-point".

Then I could just calculate rotation and translation between these two vectors.

**QUESTIONS:**

1) Is there a way of solving the ICP issue?

2) Which method seems to be more sensible in terms of accuracy and possible errors?

# Answer
> 1 votes
I think you've misunderstood how to apply ICP. If you apply it correctly, ICP shouldn't have the problem you're worried about.

You're supposed to apply ICP to *all* the points. Don't just select 4 of the points and apply ICP to those points; apply it to the entire set of points. If you pick only 4 points, yes, ICP will have the problem you describe (it'll be sensitive to small errors in the point locations). That's why we don't do that. Instead, ICP applies least-squares regression to all the points. This eliminates the problem: any small errors in the point locations are averaged out, by the least-squares regression. So, try that. I suspect you'll be fine.

I don't expect your centroid method to work very well. It has several potential problems:

* It matches the "centroid of visible points" (from the picture) to "centroid of all points" (from the database). However, there's no reason to expect those two centroids to be in the same place. Consider an asymmetrical object with parts that are not visible; the two centroids might be at different positions, and if so, this will introduce a systematic and potentially large error into your results.
* Matching only one vector isn't enough to allow you to correct for both translation and rotation.
* It requires you to know, for the selected point from the picture, which the corresponding point in the database is. However the whole point of this problem is that we don't know the correspondence. You could try to select the closest point in the database, but this might be wrong, since the two point-clouds haven't been registered into the same coordinate system, so this might go horribly awry.

For these reasons I don't think your method sounds very promising.

Last remark: The problem you're trying to deal with is called point set registration. I recommend you read up on standard methods for that problem before trying to invent a scheme of your own.

---
Tags: algorithms
---


# Question
Title: Condition for infinitude of the language of a finite state automaton
There is a theorem which says that:

> Given a finite state automaton having $n$ states, if there exists a string $w$ whose length satisfies $n \leq |w| \leq 2n-1$ then the language accepted by the automaton is infinite.

I understand the constraint $|w| \geq n$, but I don't understand why the constraint $|w| \leq 2n-1$ is there.

# Answer
> 5 votes
In the worst-case scenario, your NFA could look like this:

The smallest $w$ for which it is guaranteed to loop (forcing it to accept an infinite language) has size $2n-1$.

# Answer
> 5 votes
The additional condition allows you write a straight-forward algorithm -- check all strings with lengths in this interval -- for deciding (in)finiteness of the accepted language. Thus, you get a proof that this property is decidable (which it isn't for most automata models with super-regular power).

# Answer
> 3 votes
The full theorem states an *equivalence* rather than an *implication*:

> The language accepted by an $n$-state NFA is infinite if and only if it contains a word $w$ whose size satisfies $n \leq |w| \leq 2n-1$.

The extra condition $|w| \leq 2n-1$ thus makes the theorem *stronger*.

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


# Question
Title: What is the difference between control flow and control logic?
I'm trying to learn about declarative programming, and while reading the wiki it said the following:

> In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the **logic** of a computation without describing its **control flow**.

What exactly does this mean? I am struggling to find a definition that effectively differentiates the two terms, especially in the context of declarative programming. Is it just describing a type of abstraction?

Thanks for your help.

P.S Would it help if i could tag this as declarative programming? I can't create the tag myself

# Answer
> 5 votes
Control flow is oriented around the idea of imperative statements. What is the computer *doing* at this given time? What will it do next? What actions should it perform?

Declarative programming abstracts this away (or at least tries to). You're program is now not a set of instructions for the computer to follow, but a sort of specification for the problem. In order to be powerful enough to be Turing complete, these specifications are usually recursive.

The main difference is that a declarative program makes no promises about how it will be run. You state the logic, and the compiler/interpreter makes a program that fulfills that logic.

One of the most important aspects of a declarative description is that it's (relatively) standalone. A procedure in an imperative language says "do this thing to the current state". A declarative program says often will not depend on its context, or will make its context more explicit.

In practice, you can usually infer the control flow of a declarative program pretty easily, especially in strict languages like ML, F# or Elm. There's a pretty close correspondence between recursive declarations and loops, and between declarative functions and imperative procedures.

Things get fuzzier in a language like Haskell, where evaluation is lazy (you don't decide what gets run when). Or in Prolog, where there's an implicit backtracking search that the runtime does for you. You're not coding these things manually, you're simply specifying what the result should look like, not how you will get that result.

---
Tags: terminology, programming-languages, logic-programming
---


# Question
Title: Is this padded version of the Halting Problem in NP?
I'm using the following definition of $NP$:

$$A \in NP \Longleftrightarrow A(x) = \exists w: B(x,w) $$ where $B \in P$ and $|w| = poly(|x|)$.

Now instead of the problem whether the program $\Pi$ halts on input $x$, I'll use the close cousin that asks whether $\Pi$ halts on $0$. Then I can write:

$$HaltsOnZero(\Pi) = \exists t: HaltsOnZeroInTime(\Pi, t) $$

where $HaltsOnZeroInTime$ is the decidable problem of checking whether $\Pi$ halts on input $0$ after $t$ steps. Comparing this with the definition of $NP$ $HaltsOnZeroInTime$ is already in $P$ as long as $t$ is encoded in unary. After all running $\Pi$ for $t$ steps *takes* only about $t$ steps, so this is a linear algorithm.
The only issue is that $t$ isn't in $poly(|\Pi|)$ because programs of size $|\Pi|$ when given $0$ as input run for $BusyBeaver(|\Pi|)$ time, which isn't even computable, much less polynomial. But now suppose we insist that $\Pi$ is padded until it reaches length $BusyBeaver(|\Pi|)$ and call that new input $\Pi'$. Then $t$ *would* be polynomial (in fact linear) in the size of $\Pi'$ and $HaltsOnZero(\Pi')$ would be in $NP$.
At this point there's of course a voice inside me shouting that this is all nonsense because $BusyBeaver$ isn't computable. Well I certainly haven't reduced the classical formulation of the Halting Problem to a problem in $NP$ because I had an uncomputable step in the reduction. But it seems to me like I've still defined a problem in $NP$ with the strange property that just writing down a problem instance requires uncomputable superpowers.
Is this really a bona fide $NP$-problem or am I making a subtle mistake somewhere?

# Answer
> 2 votes
Unless you're talking about promise problems, you are required to handle arbitrary inputs.

Given a string $x\in\left\\{0,1\right\\}^\*$, we have $x\in L$ iff $x=\langle M\rangle \cdot BB\left(|M|\right)$ and $M$ halts for some fixed input ($\cdot$ denotes concatenation).

This means that even before talking about the witness (which is indeed linear), you must verify that $x$ has this specific form (unlike in promise problems, where you only care about specific inputs), and this is undecidable.

Note that this only shows why your justification to why this problem is in NP does not work. However, this language is obviously undecidable, since otherwise you could compute $BB(x)$, and thus lies outside of NP.

---
Tags: np, halting-problem, busy-beaver
---


# Question
Title: Randomly partition an rectangle into N smaller rectangles
I'm looking for an algorithm that can partition a rectangle into N smaller rectangles, at random. N will be small (on the order of 5-10 in most cases). It need not be uniformly at random, but at the very least, I'd like to avoid algorithms which completely exclude interesting classes of partitions.

One algorithm I've come across a few times (including a question on Math.SE about the number of ways to do n partitions), is to randomly divide the rectangle in two by drawing an horizontal or vertical line across it, then do the same thing recursively to the resulting smaller rectangles until you get what you want.

The trick here is that although you can get a number of different partitions using this scheme:

There are some ways of dividing a rectangle into smaller rectangles that this method will never produce:

You can easily see that the divide-and-conquer partitioning will never generate the above, because there's no line that could possibly be the first cut, since no single straight line divides the entire square into two smaller rectangles.

So basically I'm looking for an algorithm to randomly divide a rectangle up into N smaller rectangles, where the results meet the following criteria:

* Partitioned into exactly N smaller rectangles
* Everything must actually be a rectangle (no L shapes, etc)
* No empty space left over

The algorithm as a whole should meet the following criteria:

* There is no valid partitioning that the algorithm is incapable of producing
* Can be biased towards certain types of configurations, though the less bias the better.
* Preferably works with integer indices.
* Does not operate by generating all possible partitions and then picking one at random.

I don't care about asymptotic complexity much, because I'll be working with small numbers.

# Answer
Here's a simple idea that I believe can generate all partitions. There are two types of subdivisions:

1. Given a rectangle, randomly generate a horizontal or vertical line to partition it into two subrectangles. (The usual "split in two" rule.)
2. Given a rectangle, randomly generate a rectangle that fits inside it. Consider the 4 corners of this inner contained rectangle: for each of them, flip a coin and draw a line from this corner outwards towards the outer containing rectangle, with the direction of the line (horizontal or vertical) being determined by what the coin says. **Regardless of the directions of the 4 lines, the result will always be 5 rectangles.** (Some partitions that can be generated by rule 1 can also be generated this way -- in fact, only 2 of the 16 possible configurations of lines will produce partitions that could not be produced by rule 1.)

At any point in time you will have a set of rectangles (initially, just the original one). Randomly choose one to subdivide (or you could, e.g., choose the biggest, etc.), flip a coin to decide which of the two rules to apply to it, and then apply that rule; keep doing this until you have $n$ rectangles.

Disclaimer: I have no idea how to even think about the set of all partitions, let alone whether the above procedure generates them all with equal probability... Probably not.
> 1 votes

# Answer
(Disclaimer : I have not thought about throughly nor tested this idea ) ... Why not keep track of the largest available area amongst all of the sections, pick the one with the maximum area and draw a random line segment (either vertical or horizontal) within that selected bounding area. This would create two new section and recurse.
> -3 votes

---
Tags: space-partitioning
---


# Question
Title: Is $\{u u^R u : u \in \Sigma^*\}$ context-free?
Given a finite alphabet $\Sigma$ with more than one symbol, **is $L = \\{u u^R u : u \in \Sigma^\*\\}$ context-free**? ($u^R$ is the reverse word of $u$)

I tried to show it wasn't context-free by using the pumping lemma but I'm out of ideas.

# Answer
> -2 votes
Based on : Pumping Lemma for Context-Free Languages for reversal language

By @lukas.coenig

{ww$^R$w| w $\in$ {a,b}\*} doesn't seem to be a context-free language over $\Sigma$ of length two.

Assuming this language isn't context free over an alphabet of size 2 to prove it also over size of 3.. and so on by induction might be interesting..(and if true by induction than there is probably a better way to prove it)

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


# Question
Title: What is the period of N xored identical random number generators, with differing seeds?
This question is a kinda spin off from Why do we not combine random number generators?

If for example we had N identical type random number generators, with N different seeds, what would the period be if their outputs were xored together? Would it be *period*, *N x period* or *period (power N)*?

So a numerical example would be:

2 linear feedback shift registers of 10 bits.

1 LFSR's period = 1023.

2 xored LFSRs' period = 1023, 2046 or 1046529?

(I have a sense that it's *period* but I can't overcome that fact that the state size is so much bigger.)

# Answer
> 2 votes
I will assume the N random generators have independent seeds and states. Suppose their periods are $t\_1,\dots,t\_N$. Then the period of their xor is a divisor of $\operatorname{lcm}(t\_1,\dots,t\_N)$. Typically, it will be exactly $\operatorname{lcm}(t\_1,\dots,t\_N)$, but I don't know whether that is guaranteed in all cases.

If all $N$ generators have the same period $t$, then the period of their xor is a divisor of $t$ (and thus cannot be any larger than $t$).

---
Tags: pseudo-random-generators
---


title: Complexity of vector comparison

text:
# Question
Title: Complexity of vector comparison
A question on SO about complexity of sorting vectors of vectors got me thinking about the complexity of comparing 2 vectors.

Let's consider vectors of average size 1) `N`.

The first formula we get for the comparison of 2 vectors is `O(N)`, but my intuition says it could be lower. Worst case scenario is `N comparisons` (vectors are equal), but best case scenario is `1 comparison` (vectors differ by first element). Obviously the range of values held is very important here. A vector of 64 bits integers (domain of `2^64 values`) is much much more likely it will end the comparison early on than say a vector of 1s and 0s (domain of `2 values`).

Let `M` be the size of the domain (number of values each element can hold; the size of the alphabet)

Now when we consider that `M` is fixed (which it is) we might be tempted to say that the complexity is still `O(N)`, no matter how large `M` is. It may have a very small factor `O(f*N)`, but it is still `O(N)`. Mathematically we consider the greatest power in the polynomial. Intuitively a large enough `N` will hide the factor (which is the probability of 2 elements being equal, or a product of probabilities, correct me if I am wrong).

But... in real life (computation real life) a vector doesn't have unbounded size. A 64 bits integers vector of size `2^64` (`N = M = 2^64`) would need about `10^8 terra` and even a 32 bits integers vector of size `2^32` (`N = M = 2^32`) would require `16 giga`. So I would say it is safe to assume 2) that `N < M`: the size of the vector is less, much more less than the size of the alphabet.

(for me, intuitively that means that the time complexity doesn't get the chance to "explode" because of the very small factor and because N doesn't get the chance to get sufficiently big - compared to M)

So considering `N < M` does this mean that for a large fixed alphabet (e.g. `2^32` or `2^64`) we can recompute the complexity of vector comparison to something lower than `O(N)`?

Or am I way off?

---

1) size of vector = number of elements (not size in bytes)

2) for vectors of large ints and for most real life uses (completely ignoring the rare applications that deal with very very large vectors)

extra) I think it goes without saying that element comparison is `O(1)`

# Answer
Normally, in asymptotic analysis, it's most typical to analyze the *worst-case* running time. It is correct to say that the worst-case running time of comparing two $N$-vectors is $\Theta(N)$; and not any less.

However there's nothing saying you have to focus on worst-case running time. For instance, perhaps you are interested in the average-case running time (also known as expected running time). In this case the answer will be $\Theta(1)$ if we assume that the vectors are uniformly distributed, as you predicted.

However average-case running time is tricky. The expected running time depends on the distribution of values, so you must specify a distribution before you can begin the analysis. If the distribution isn't uniform, then the expected running time might be very different.

Also the expected-running time doesn't add up like you might think. What happens if you run Quicksort on a list of vectors? Can we say that Quicksort does $\Theta(n \log n)$ comparisons on average, and each comparison takes $\Theta(1)$ expected time, so Quicksort on a list of vectors will take $\Theta(n \log n)$ time? No, that doesn't follow. Quicksort will tend to move similar vectors closer to each other, so as you get to later stages in the algorithm, it's possible that you might be mostly comparing vectors that are similar to each other. In particular, the two vectors you're comparing won't be uniformly distributed; they'll come from some joint distribution which tends to make similar vectors more likely. Of course similar vectors are (on average) slower to compare than independently uniformly-random vectors, so there's no longer any guarantee that every comparison takes $\Theta(1)$ time on average.

So, average-case running time analysis can be a lot trickier to get right than worst-case running time. Beware!
> 2 votes

---
Tags: complexity-theory, runtime-analysis
---


title: Hamiltonian path in grid graph

text:
# Question
Title: Hamiltonian path in grid graph
Here is my situation. I have a grid-type graph with obstacles. Every move (horizontally, vertically or diagonally with a range of 1) has a cost of exactly 1 (the graph is not weighted) provided that neither the source or the destination is an obstacle.

I need to, provided a starting node (a square), find any path that visits every single node that is reachable, without visiting any node twice. If there is no such path, then any path that would visit as many nodes as possible. In other words, I'm looking for an algorithm to find a Hamiltonian path in such a graph.

I am not looking for the shortest path.

The most important factor is the time the algorithm takes to complete (complexity).

I have searched Google and this site, and I only find variants of the travelling salesman, or algorithms for shortest path visiting all nodes, which won't work in my situation. My algorithm needs to find a path of any length visiting as many nodes as possible while never visiting a node twice. The path can end anywhere.

Does anyone have any tips? I've tried to do this with a variant of A\*, but I couldn't make it work. I've succesfully done it by brute-forcing, but as the graph can be rather large, I need something a faster than O(n!).

It would be even better if the algorithm was non-deterministic, which means that if there are multiple possible solutions, we wouldn't always get the same one with the same graph and starting location. I have no idea how to do this without slowing it down though, and speed is more important.

# Answer
> 2 votes
Since an exact algorithm is most likely off the table, I'll propose the following heuristic: Start at any vertex (though a vertex with no vertices above it would be best), and always move to the first neighbour in the following list that exists and has not yet been visited: UPLEFT, LEFT, DOWNLEFT, DOWN, DOWNRIGHT, RIGHT, UPRIGHT, UP. This should cause you to quickly travel to the top-left part of the graph, and thereafter alternatingly "snake" down and then up adjacent columns, "bending" around any obstacles but always hugging as close to the left border of the graph as possible, and thus gradually covering the graph from left to right.

There are probably many ways for this algorithm to get stuck -- that is, to make a move that leads to the subgraph induced by the unvisited vertices becoming disconnected, meaning that at most one of the resulting components can be visited. One way to ameliorate this somewhat is to first test whether the next valid move will lead to such a disconnection by checking whether there is a path through unvisited vertices from the vertex we would get to at the move *after that* to the *next* valid move from current vertex -- this can be done with BFS (or DFS, but BFS will terminate faster in the common case where a short path does exist). If no such path would then exist, and if a heuristic estimating the length of the path reachable from the first move is small (for example: the size of the connected component of unvisited vertices you would find yourself in), try the next move.

# Answer
> 3 votes
There isn't going to be a fast algorithm for this problem.

The class of graphs you're dealing with is, in some of the literature, called grid graphs. That is, they're finite induced subgraphs of the infinite graph with vertices $\mathbb{Z}\times\mathbb{Z}$ with an edge from $(x,y)$ to $(x',y')$ if, and only if, $|x-x'|+|y-y'|=1$.

Itai, Papadimitriou and Szwarcfiter (*Hamiltonian Paths in Grid Graphs*, *SIAM Journal on Computing*, 11(4):676–686, 1982) showed that it's **NP**-complete to determine whether a grid graph has a Hamiltonian path. Your problem is **NP**-hard (under Cook reductions, and possibly also under the more usual Karp reductions): if you can determine the length of the longest path from a vertex, just do that for each vertex in turn and see if any of the longest paths is Hamiltonian.

---
Tags: algorithms, graphs, optimization, hamiltonian-path
---


# Question
Title: Terms and definitions for regular language and NFA
let's say L is a regular language,what term does L should uphold so that there is an NFA without epsilon moves,in which for every accepting state δ(q,σ)=Ø?I can think of some terms like that the last letters can't hold a power,but I was wandering if there is a formal definition?

# Answer
> 2 votes
Let $L$ be a regular language. There exists a NFA for $L$ in which $\delta(q,\sigma)=\varnothing$ (for every final state $q$ and every symbol $\sigma$) if $\lambda\notin L$.

We can make this into a characterization: iff $\lambda\notin L$ or $L = \\{ \lambda\\}$.

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


# Question
Title: Why is ARP needed in a host - router system if the router already has list of addresses it assigned using dhcp?
The hosts are assigned IP address by the router using dhcp. So, the router has a list (mac addresses) of all the hosts that are directly connected to it as well their ip addresses. Now if a packet comes from outside, the router must be able to find the destination mac address from its logs. Then what is the need to use ARP in such a case (hosts connected to router)?

The only time I see an use of ARP is when router has to find new routers. Using ARP allows it to find new routers as well as to force a more rigid use of longest matching address method if needed. However what is the use of ARP during "router to host" packet transfer?

# Answer
> 3 votes
The fact that the router has the list does not help when computer A wants to talk to computer B, because neither of the two has the list.

---
Tags: computer-networks
---


# Question
Title: how can i know if a First order logic sentences is valid or unsatisfiable or neither?
i have trouble with understand this type of questions ,

i know how i can determine if the sentences is valid or unsatisfiable in Propositional logic , but in FOL i can't

for example , i have the following sentences in FOL :

```
1 = 2

```

the professor said this is neither valid nor unsatisfiable

but , i think it is always unsatisfiable , because 1 != 2 !!!

can someone explain to me how can i answer this type of question

thank you all

# Answer
A formula is *valid* if **all** of the possible truth-assignments to its variables evaluate to true.

A formula is *satisfiable* if **at least one** of the truth-assignments to its variables evaluates to true.

The formula you gave is :

> $1 = 2$

Since this contains no variables, under any truth-assignment, the expression is $1 = 2$, which is false.

Neither of the above conditions have been met.

Therefore the formula is neither ***valid*** nor ***satisfiable***. Since it is not satisfiable, we can say that it is ***unsatisfiable***.
> 2 votes

---
Tags: artificial-intelligence, first-order-logic
---


# Question
Title: Does Bellman–Ford algorithm can handle zero-weight cycles?
According to my understanding, the Bellman–Ford algorithm can handle cyclic graphs with negative weights. but it cannot have negative cycles. But can it handle zero weight cycles?

# Answer
Yes. Bellman-Ford can handle graphs with zero-weight cycles; they aren't a problem.

Intuitively, negative-weight cycles are problematic because they can make the notion of "shortest path" ill-defined: there *is* no shortest path. For instance, suppose we have a cycle from A to A with weight -5, and an edge from A to B with weight 10. Then there is no shortest path from A to B. There's a path with length 10 (go straight there), a path with length 5 (traverse the cycle once, then go there), a path with length 0 (traverse the cycle twice, then go there), a path with length -5, a path with length -10, and so on.

Zero-weight cycles don't cause this problem.
> 3 votes

---
Tags: algorithms, graphs
---


# Question
Title: How does an image classifier select relevant features?
I am trying to understand cascade classifiers for computer vision. I use OpenCV Traincascade for now and successfully trained some cascades.

However I am trying to grasp the whole process. One thing I do not understand about the cascade training is how the features are selected on each stage.

How does an image classifier select only relevant features?

# Answer
> 1 votes
There is no single answer. A cascade is a very simple idea: it basically represents a bunch of classifiers, applied sequentially.

You are free to decide how each individual cascade will work. You could design the cascade so that every classifier uses the same set of features. Or, you could design the cascade so that each classifier has a different subset of features. They're both considered cascades.

In the standard cascades I've seen used in computer vision, there is one set of features. Each stage in the cascade is a single classifier which is trained on the entire feature vector. Part of the training involves selecting a subset of the features (perhaps only a few features) to use at that stage of the cascade. The training process is responsible for that, and there are many different algorithms for training out there. One example is ADAboost, with decision stumps as the weak classifier; you could take a look at that to see how it works.

---
Tags: image-processing, computer-vision, classification, features
---


# Question
Title: Are Pervasive Computing and Pervasive Sensing the same.concept?
Pervasive Sensing focuses on sensors and Pervasive Computing talks about using sensors for example. Are they both the same thing but different names?

# Answer
> 2 votes
First off, keep in mind that these are just labels. They don't have a formal definition.

That said, I would say that they tend to imply different things. Pervasive computing is about embedding sensors and computational systems throughout everyday life -- that includes sensors, computing, actuation, integration with the rest of the world, etc. To me, pervasive sensing would refer just to the sensing part, without much emphasis on how the sensor data is used. Thus, I would think of pervasive sensing as a subset of pervasive computing.

But don't take this as authoritative or a formal definition. These labels are loose, and reflect social shared values as much as anything else.

---
Tags: terminology
---


# Question
Title: Minimum hamming distance of multiple binary words
Our task is to compute the **minimum hamming distance** for the following 16-bit words:

```
0000000000000000
0011001100110011
0101010101010101
0000111111110000
0011111111000000
1100110000000000
1111111111111111

```

This minimum distance is defined as the minimum of all distances between every combination of two of these bitstrings, so the first approach would be to calculate all of these individual distances. I'm pretty sure this is not the right way to do it, since there are `21` possible combinations.

Then I came across this answer on StackOverflow which says that:

> We have a theorem that d\_min=weight(sum(all codes)); weight is the number of non zeros in the result string . In your example modulo add all string codes like first column of all and second....... then we get code as \[ 0 0 1 1 0 \], weight of this is 2 ( no. of non zeros), i.e the minimum distance of hamming code

but is that really true? If we for example take the three bitstrings

```
0000
1000
1110

```

the minimum hamming distance is obviously `1` but the calculation based on that answer would result in `0110` and would suggest that the minimum distance is `2`. Am I right about this and is that answer wrong? Or did I miss something really simple that I'm just not noticing?

I also read this answer which - if I understood it correctly - states that there is no *simple* way of finding the result.

# Answer
You are correct.

Here's what's going on. There are two subtly different questions here. The Stack Overflow question is asking: "given a set of bitvectors *that form a Hamming code*, how do I find the minimum distance?". In contrast, it sounds like you might be asking "given an *arbitrary* set of bitvectors, how do I find the minimum distance?". Those aren't the same question. Unsurprisingly, they have two different answers.

The answer on Stack Overflow you're referring to isn't 100% clear, but I suspect it is making the following claim: *if* you have a set of bitvectors that form a Hamming code, *then* the minimum distance can be obtained by computing the Hamming weight of the xor of all the bitvectors. I don't know whether that claim is true, but let's suppose it is. That still doesn't help you with (what I think is) your question, because in your problem you have an arbitrary set of bitvectors -- they might not form a Hamming code.

It is easy to find counterexamples to demonstrate that the claim doesn't hold in general, for an arbitrary set of bitvectors. For instance, your example is a perfectly good disproof of that.

There *are* techniques for finding the minimum distance of a set of arbitrary bitvectors (at least, there are heuristics), but hopefully this is enough to answer the question you asked.
> 2 votes

---
Tags: algorithms, hamming-code
---


# Question
Title: Example of unrestricted grammar which produces non-context-sensitive language
I'm talking about Type-0 (Chomsky hierarchy) *unrestricted grammar*, where production rules of grammar are of the form $\alpha\rightarrow\beta$, where $\alpha,\beta\in N\cup\Sigma$.

I can not find any example of real **unrestricted grammar** which produces a **non-context-sensitive language** (***of words***). While there are examples of non-context-sensitive languages like here or here, there are not examples with proper grammars for them. Could somebody provide such example?

(Ideally if you would provide links to corresponding papers where such example(s) are described).

**Note**: I've tried to build unrestricted grammar for known universal Turing machines, as it was suggested in commentaries above. I've used JFLAP tool for this purposes. But obtained grammars appear to be extremely huge, incomprehensible and complex. If you would use same approach and give clear explanation of result, this would partially suit me. Thanks.

# Answer
> 12 votes
For posterity.

Start with undecidable Post Correspondence Problem, or PCP:

> Given two lists of words $(u\_1,\dots,u\_n)$ and $(v\_1,\dots,v\_n)$ does there exist a sequence of indices such that $u\_{i\_1}\dots u\_{i\_k} = v\_{i\_1}\dots v\_{i\_k}$?

The language will consist of PCP over $\\{a,b\\}$ that have a solution, coded as string $(u\_1;v\_1) \dots (u\_n;v\_n) $ with $u\_i,v\_i \in \\{a,b\\}^\*$.

The grammar will generate a PCP instance, and non-deterministically an attempt for a solution. Then equality of the two strings is tested by deleting matching letters.

The equality check is more easily done when one of the strings is stored in reverse, so we will generate $u^R\_{i\_k} \dots u^R\_{i\_1} X v\_{i\_1}\dots v\_{i\_k}$.

Generate an instance of PCP.

* $ I \to (W;W) I \mid (W;W) $ (add a pair of words)
* $ W \to a W \mid b W \mid \varepsilon $ (generate a word)

Copy one of the pairs of PCP and move it to the pair of words around $X$ that should be equal.

* $ D \tau \to \tau D$ for $\tau = a,b,(,),;$
* $ D ( \to ( L $ (pair selected)
* $ L ; \to ; R $
* $ R ) \to ) $
* $ L \sigma \to \sigma L\_\sigma L $ for $\sigma = a,b$ (make a copy)
* $ R \sigma \to \sigma R\_\sigma R $ for $\sigma = a,b$
* $ L\_\sigma \tau = \tau L\_\sigma $ for $\sigma = a,b$ and $\tau = a,b,(,),;$ (move right)
* $ R\_\sigma \tau = \tau R\_\sigma $ for $\sigma = a,b$ and $\tau = a,b,(,),;$
* $ L\_\sigma X \to \sigma X$ (drop copy to the left of $X$, it will reverse)
* $ R\_\sigma X \to X \sigma$ (drop copy to the right of $X$)

Check equality

* $ X \to Z $
* $ \sigma Z \sigma \to Z$ for $\sigma = a,b$

Start. The $\\#$ marks the end of the string, or rather the end of the solution that is generated. The last rule will delete it and at the same time test whether the solution has been completely removed by the earlier rules checking equality.

* $ S \to C I X \\#$
* $ C \to C D \mid D $ for generating the solution, copy several word pairs

Done

* $ ) Z \\# \to )$

PS. Most constructions for a non-context-sensitive language use diagonalization on context-sensitive grammars to get a language that is still recursive. This one is not recursive, but recursively enumerable.

Indeed many rules are context-sensitive (or rather monotonic/non-contracting). But especially note the rules like $aZa\to Z$: they shorten the string. These are definitely type-0 and not monotonic, and they are essential. After the computation they delete the proposed solution of PCP. Like a scratch tape used by a Turing machine.

PS2. Although the intuitive meaning of each of the productions is explained above, it is not very simple to *formally* prove the grammar is correct. This is mostly due to the parallellism. There are many nonterminals moving around in the grammar at the same time independently (for instance, when a copy of a PCP pair $(u\_i,v\_i)$ is made all these letters move in a row to the right; also we can start looking for the next pair to copy even before the last one was finished). This makes it hard to formulate invariants. It takes some time to check that all nonterminals keep in a proper order, for instance. Fortunately none of the moving nonterminals can overtake one another.

For this reason analysing Turing Machines sometimes is less complicated. Only the reading/writing head is moving around.

**Example** (*added by Andremoniy*)

Consider simplest case: $(a;a)$. For this string derivation sequence will be:

$S\Rightarrow CIX\Rightarrow D(W;W)X\Rightarrow C(a;a)X\Rightarrow D(a;a)X\Rightarrow (La;a)X\Rightarrow (aL\_aL;a)X\Rightarrow (aL\_a;Ra)X\Rightarrow (a;L\_aRa)X\Rightarrow (a;L\_a aR\_aR)X\Rightarrow (a;aL\_aR\_aR)X\Rightarrow (a;aL\_aR\_a)X\Rightarrow (a;aL\_a)R\_aX\Rightarrow (a;a)L\_aR\_aX\Rightarrow (a;a)L\_aXa\Rightarrow (a;a)aXa\Rightarrow (a;a)aZa\Rightarrow (a;a)Z\Rightarrow (a;a)$

---
Tags: formal-languages, turing-machines, formal-grammars
---


title: Dominator Tree for DAG

text:
# Question
Title: Dominator Tree for DAG
Is there a fast algorithm to compute dominator tree for acyclic graphs?

The Lengauer-Tarjan Algorithm is a fast algorithm for general flowgraphs. But if a graph is acyclic, do we have a faster algorithm?

# Answer
> 6 votes
Recall the definition of dominators:

$$\hbox{Dom}(n\_o) = \\{ n\_o \\}$$ $$\hbox{Dom}(n) = \\{ n \\} \cup \bigcap\_{p \in \hbox{preds}(n)} \hbox{Dom}(p)$$

This can be done in a single pass over all nodes, if you can guarantee that you visit all predecessors of a node before you visit that node. So perform a topological sort, and you're done.

It may be possible to calculate dominator trees directly (i.e. without first computing dominators) if the graph is a DAG, but I'm not certain how you would do this.

# Answer
> 1 votes
In a directed acyclic graph $D = (V,E)$, the *dominator tree* $T(s) = (V(s),E(s))$ with respect to source vertex $s \in V$ is such that $V(s) \subseteq V$ is the subset of vertices reachable from $s$ and $$E(s) = \\{(\text{idom}(u,s),u) \mid u \in V(s) - \\{s\\}\\}$$ where $\text{idom}(u,s)$ denotes the *immediate dominator* of $u$ regarding $s$ (closest vertex to $u$ present in all paths from $s$ to $u$). Hence, $\text{idom}(u,s)$ is defined only if $u \in V(s)$. Also, we define $\text{idom}(s,s) = s$, despite $(\text{idom}(s,s),s) \notin E(s)$.

Now, let's fix $s$ and write $\text{idom}(u) = \text{idom}(u,s)$. Also, let's write as $\text{deg}^-(u)$ the indegree of $u \in V(s)$, excluding external edges (any edge $(v,u)$ such that $v \notin V(s)$ is not considered).

Follows by induction that $$\text{idom}(u) = \text{lca} \\{v \mid v \in V(s) \wedge (v,u) \in E\\}$$ where $\text{lca}(W)$ denotes the *lowest common ancestor* of all vertices in $W$, if $W$ is a subset of vertices of a *tree*. In this case, the dominator tree.

Algorithm:

1. Initialize $\text{idom}(u) \gets u$ for all $u \in V(s)$.
2. Run a depth-first search from $s$ to compute $\deg^-(u)$ for all $u \in V(s)$.
3. Run a recursive "DFS-like-but-not-depth-first" search starting from $s$. For each edge $(u,v)$ discovered in this search:

3.1. If $\text{idom}(v) = v$, then $\text{idom}(v) \gets u$, else $\text{idom}(v) \gets \text{lca}\\{\text{idom}(v),u\\}$.

3.2. Decrease $\deg^-(v)$ by one. Enter $v$ recursively *only if* $\deg^-(v)$ becomes zero!

The algorithm is correct because, since $D$ is a DAG, Step 3.2 ensures topological order. Hence, the LCA query of Step 3.1 always runs correctly, as the dominator tree edges for all vertices $x \in V(s)$ that reach $u$ are already built (this is induction).

Steps 1 and 2 cost $O(|V|+|E|)$ time and $O(|V|)$ space.

LCA preprocessing for Step 3 costs $O(|E| + |V| \lg |V|)$ time and $O(|V| \lg |V|)$ space. Each LCA query costs $O(\lg |V|)$ time, so Step 3 costs $O(|V| + |E| \lg |V|)$ time.

The overall costs are $O((|V|+|E|) \lg |V|)$ time and $O(|V| \lg |V|)$ space.

LCA preprocessing can actually be made on the fly with the help of *dynamic programming* and *memoization*! The time cost will be the same, but amortized.

I saw this algorithm here. The dominator tree was built over the Dijkstra's shortest paths DAG.

Here is my C++ 14 implementation.

---
Tags: algorithms, graphs, reference-request
---


# Question
Title: transmission delay in store and forward, what is L/W and how to compute tw
I don't understand some things in Store and Forward equation:

* D -\> Number of channels and switches pairs.
* tr -\> Routing time.
* tw -\> Transfer time in a channel.

What is the **L/W**?

And normally exercises provide me **tw** (time transfer in a link), but now I am doing an exercise in which tw is not provided. I think I should compute with the **speed** of the links and the data **size** transferred. But I don't know what should be the size for the data.

Thanks.

# Answer
> 1 votes
You ask us what $L$ and $W$ are. But we can't tell you. Only you know where the formula came from (you haven't told us). And only you have access to that book. If the book is any good, it will have defined what $L$ and $W$ represent before using them, so look through the book. If the book uses variables $L$ and $W$ without defining them, then I recommend you look for a better book.

---
Tags: computer-networks
---


# Question
Title: How to classify simple priority queue algorithm
I have a simple priority queue algorithm that I implemented, and I doubt it's new but I haven't been able to classify it. Wondering if I could get some help with classifying it! Once I classify it I can read more about how to implement it properly, etc.

Assuming the implementation is sound, I am also trying to figure out how to prove certain aspects of the queue, namely to determine if the maximum amount of time (or steps) for an item to come off the queue is deterministic. Ideally we could figure out how long that would be as a function of some variables and initial state, or what not.

Here is the basic algorithm:

**Setup/background/assumptions:**

* We have a FIFO queue, and each item in the queue has a priority of 1, 2, or 3 (generically, we could make it 1 -X where those are all integers). By FIFO we mean that, in general, items that are enqueued first get dequeued first, but with a priority queue that is not exactly the case (that should be pretty obvious).
* 3 is highest priority, 1 is lowest priority, the higher the number the higher the priority.
* Let's assume a single server for simplicity, but the concept should be similar enough for multiple servers.
* Assume we only take one item off the queue at a time, but this same algo should work if we pop off multiple items.

**Algorithm:**

(Note that the only question at hand is: What item do we pop off the queue next? That is what the algorithm is trying to solve).

*Step 1:* For all your priority levels, determine a number of cycles for each level. Higher priority levels should have more cycles - so let's say priority 3 has 10 cycles, priority 2 has 6 cycles and priority 1 has 2 cycles.

*Step 2:* Instead of looking at the whole queue, look at only the first Y items, for example the first 20 items. This makes things faster (O(20) instead of O(n)), and easier to prove that the implementation is working as expected. Most importantly, setting this cap should prevent starvation for the lower priority levels. Because eventually the 20 items will be filled with lower priority items, and then they will start seeing some attention.

*Step 3:* Every time you dequeue an item, increment an integer. Then mod this integer against the total number of cycles (10 + 6 + 2) = 18. This will determine which priority cycle you are in, for any given dequeue event.

*Step 4:* Take the value from the mod operation, determine what cycle you are in by comparing the value to an accumulated cycle value, e.g.:

```
Priority     Cycles      Accumulated

3            10           10

2            6            16

1            2            18

```

In that way if the mod result of our incremented integer is in the range 0 - 10 we are in priority 3 mode, if the mod result is in the range 11-16 we are in priority 2 land and if the mod result is in the range 17-18 we are in priority 1 realm.

*Step 5:* Sort the first 20 items in the head of the queue, first by priority level, then by age, oldest to the front. Given the priority level found from step 4, look through the sorted list find the first one that is at the priority level or below. So if we are at priority 3 we will look at all items. If we are at priority 2, we look at items with priority 2 and below, etc etc.

*Step 6:* If no items can be found with priorty Z and below, then cycle to the highest priority again, in this case 3, which will always yield something off the queue.

**Done.**

The basic idea is that our priority system is is based off of the number of cycles given to each priority, where more cycles are given to higher priority items. This should make things more deterministic.

But like I said, I am most interested in (a) proving this actually works somehow and (b) determining some value for maximum time (or steps) for an item to come off the queue.

# Answer
You asked about starvation. Starvation is impossible in your scheme: every item will eventually come off the queue, after finitely many dequeue operations.

Consider an arbitrary priority-1 item, call it T. I'll prove that T will eventually be removed from the queue. Let $M$ denote the number of items that are older than T (i.e., were enqueued before T). This number must be finite. Let's call the first-20 items of the queue the *endzone*, so we have a concise name for it.

**Lemma 1.** T will reach the endzone after at most $M-19$ dequeue operations.

*Proof:* If T isn't among the endzone, then a dequeue operation will move it one position closer to the endzone. As long as T isn't among the endzone, no enqueue operation can jump a younger item ahead of T. There are initially $M$ items ahead of T, and as long as T stays out of the endzone this number decreases by one for each dequeue operation, so after $M-19$ operations, there are only 19 items ahead of T, i.e., T is in the endzone.

**Lemma 2.** Once T reaches the endzone, it will stay in the endzone until it is dequeued.

*Proof:* Follows by inspection of the algorithm. The only way for an item to be removed from the endzone is if it is selected to be returned by the dequeue operation.

**Lemma 3.** Let $N$ denote the number of priority-1 items that are ahead of T when it first enters the endzone. Then T will be dequeued after at most $18 \lfloor N/2 \rfloor + 18$ dequeue operations.

*Proof:* Consider the set of priority-1 items that are ahead of T, starting from the time when T first enters the endzone. Once T enters the endzone, this set can only shrink -- no new priority-1 item can jump ahead of T. (Any other priority-1 item will be tied with T for priority, and will be younger, so the sorting operation won't jump it ahead of T.) Moreover, after every 18 dequeue operations, we'll have dequeued at least 2 priority-1 items, so this set will shrink by at least 2. This can happen at most $\lfloor N/2 \rfloor$ times before this set has size at most 1. When the set has size at most 1, T will be removed after at most 18 more dequeue operations. Thus, T will be removed after a total of at most $18 \lfloor N/2 \rfloor + 18$ dequeue operations.

**Theorem.** T will be dequeued after at most $M+161$ dequeue operations.

*Proof:* By Lemma 1, T will enter the endzone after at most $M-19$ dequeue operations. Then we will have $N \le 19$ (since there can be at most 19 items ahead of T, when it is the endzone). By Lemmas 2 and 3, T will be dequeued after at most $18 \times \lfloor 19/2 \rfloor + 18 = 180$ more dequeue operations. Consequently, after at most $M-19 + 180 = M+161$ dequeue operations, T will have been removed.

It follows that every priority-1 item will be removed after at most finitely many dequeue operations; indeed, the latency (compared to a priority-less FIFO queue) is at most 161 extra dequeue operations. A similar argument can be applied to priority-2 items (adjusting Lemma 3 so $N$ counts the number of priority-1-or-2 items ahead of T) and to priority-3 items (adjusting Lemma 3 so $N$ counts the number of items ahead of T). We deduce that every item will be dequeued after at most finitely many dequeue operations, i.e., starvation is impossible.
> 2 votes

# Answer
You can't prove an algorithm is correct without a specification what correctness means.

This algorithm isn't a priority queue. A priority queue has two properties: pop always removes the highest-priority item; and it resolves ties (in priority) in a FIFO fashion. Your algorithm doesn't do that; if the first 20 items in the last are all low priority, but there's a high-priority item elsewhere, a priority queue would return the high-priority item, but your algorithm returns a low-priority item.

A true priority queue is easy to implement if you only have three priority levels: you just have three ordinary queues, one for each priority level. When pushing an item, push it onto the corresponding queue. When popping an item, first look at the level-3 queue and pop off of it if it is non-empty; otherwise check the level-2 queue and pop from it if it is non-empty; otherwise pop from the level-1 queue if the other two queues are empty. This achieves $O(1)$ time for all priority queue operations.

Possibly you are looking for information on process schedulers; this is studied in the operating systems area.
> 3 votes

---
Tags: priority-queues, queueing-theory
---


# Question
Title: Understanding A Recursive Definition of CL-Terms in Combinatory Logic
From page 26 of *Lambda-Calculus and Combinators*:

> **Definition 2.18 (Abstraction)** For every CL-term $M$ and every variable $x$, a CL-term called $\[x\].M$ is defined by induction on $M$, thus:
>
> (a) $\[x\].M \equiv \mathbf{K}M$ if $x \notin FV(M)$;
>
> (b) $\[x\].x \equiv \mathbf{I}$;
>
> (c) $\[x\]Ux \equiv U$ if $x \notin FV(U)$
>
> (f) $\[x\]UV \equiv \mathbf{S}(\[x\]U)(\[x\].V)$ if neither (a) nor (c) applies.

Here $\mathbf{I}$ is meant to denote the identity operator, $\mathbf{K}$ the constant operator, and $\mathbf{S}$ the "stronger composition operator" where in mathematical notation:

$$ \mathbf{S}(f,g))(x) = f(x, g(x)) \text{ for functions $f$, $g$} $$

**Question:** It seems that (f) of this definition *just comes out of nowhere*. I have no idea what is motivating it behind the scenes. Does anybody have any insight on where this definition comes from?

# Answer
Here are some considerations that could have been used to *sort of* "derive" the (f) rule:

* it is natural to define our type of conversion recursively;
* the *general* case when the body of "$\lambda$" is an application $(UV)$ needs to be addressed;
* we certainly would like to get $\[x\].(\[y\].(\[z\].xz(yz)))$ converted into its corresponding combinator $\mathsf{S}$.

Using the above we get an intermediate version of the (f) rule:

$$\[x\].UV \equiv A(\[x\].U)(\[x\].V),$$ where some closed CL-term $A$ is to be determined. The position of $A$ is chosen so that the subsequent "calls" of the (c) rule would be possible, or all three positions could be tried in turn.

$$\begin{array} (\[x\].(\[y\].(\[z\].xz(yz)))) &\equiv \[x\].(\[y\].A(\[z\].xz)(\[z\].yz)) &\text{rule (f)}\\ &\equiv \[x\].(\[y\].(A x) y) &2 \times \text{rule (c)}\\ &\equiv \[x\].Ax &\text{rule (c)}\\ &\equiv A &\text{rule (c)}, \end{array}$$ hence $A = \mathsf{S}$ and the final version of the (f) rule $$\[x\].UV \equiv \mathbf{S}(\[x\].U)(\[x\].V).$$

Note that the above is not a "real derivation", it's just some informal speculations, which I hope can help you to build up some intuition about that conversion.
> 3 votes

---
Tags: lambda-calculus, combinatory-logic
---


# Question
Title: Prove L = L(R) based on a regular expression
I'm given the following language:

`L = {w∈{0,1}* | w ends in 010 and contains 011}`

The task is to find a regular expression R that describes this language and prove L = L(R).

I have found the regular expression : `^([011])[01]*010$`.

But have no idea how to prove L=L(R)?

# Answer
In the expression you propose it seems you require the string to start with `011` rather than have it as an arbitrary substring.

So in my dialect of RegEx the expression would be `(0+1)*011(0+1)*010`. By definition that would specify all strings of the form $u 011 v 010$ where $u,v$ are arbitrary. This means all those strings have `011` as subword and end in `010`.

We also have to explain the converse. That every string with that subword and suffix is covered by the expression. For that it suffices to note that `011` and `010` cannot overlap. So, `010` must come before `011`. Which means it is of the form $u 011 v 010$.
> 1 votes

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


# Question
Title: Time complexity for count-change procedure in SICP
In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem statement suggests drawing the tree for `(cc 11 5)` \- which looks like this):

```
 ; count change
 (define (count-change amount)
   (define (cc amount kinds-of-coins)
     (cond ((= amount 0) 1)
           ((or (< amount 0) (= kinds-of-coins 0)) 0)
           (else (+ (cc (- amount
                           (first-denomination kinds-of-coins))
                        kinds-of-coins)
                    (cc amount
                        (- kinds-of-coins 1))))))
   (define (first-denomination kinds-of-coins)
     (cond ((= kinds-of-coins 1) 1)
           ((= kinds-of-coins 2) 5)
           ((= kinds-of-coins 3) 10)
           ((= kinds-of-coins 4) 25)
           ((= kinds-of-coins 5) 50)))
   (cc amount 5))

```

Now... there are sites with solutions to the SICP problems, but I couldn't find any easy to understand proof for the *time* complexity of the algorithm - there is a mention somewhere that it's polynomial `O(n^5)`

# Answer
Probably this was not the right place for this question, but anyway, I found the answer in the meantime, in the form of a mostly "digestible" proof at http://wayback.archive.org/web/20141122124458/http://wqzhang.wordpress.com/2009/06/09/sicp-exercise-1-14/.
> 2 votes

# Answer
Order of growth of number of steps: $\theta (n^5)$

We can prove that, in general, the order of growth of number of steps is $\theta (n^m)$, where $m$ is the number of types of coin available. Here is my (very) crude reasoning using induction:

1. When there is only one type of coin, the number of steps is obviously proportional to n.
2. Suppose it would take `(cc n m)` steps to change an amount of $n$ with $m$ types of coin. Now let's consider `(cc n m+1)`: ($A$ is the denomination of the $m$th kind of coin.)

> (cc $n$ $m+1$)
> = (cc $n$ $m$) + (cc $n-A$ $m+1$)
> = (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m+1$)
> = (cc $n$ $m$) + (cc $n-A$ $m$) + (cc $n-2A$ $m$) + (cc $n-3A$ $m+1$)
> = ......

It would eventually computes to

```
(cc n m) + (cc n-A m) + ... + (cc <something-negative> m+1)

```

There are approximately $n/A$ items. So the total number of steps would be proportional to $n/A\*n^m$, which is proportional to $n^{m+1}$. Thus, the order of growth for number of steps of `(cc n m)` is $\theta (n^m)$.

Let $m$ be 5, and the order of growth of number of steps is $\theta (n^5)$.
> 6 votes

---
Tags: algorithms, time-complexity, space-complexity
---


# Question
Title: How to generate all $n$-bit numbers with certain bits fixed?
Consider the example where $n = 4$, bit 0 is fixed at 1, and bit 2 is fixed at 0. I would like to generate all $n$-bit numbers with those bits fixed. Essentially, everything I generate would have the form:

$$1\*0\*$$

where $\*$ represents a bit that can vary. The fixed bits can be in arbitrary positions, and there can be arbitrarily-many of them (anywhere from 1 bit fixed to $n-1$ bits fixed). Ideally, I would prefer these to be generated in lex order; what I'm looking to generate for the example case would be:

$$1000, 1001, 1100, 1101$$

I've only found solutions for doing something like this when specific bits are set to 1 - my question is more general, as it allows bits to be set to 0 or 1. What is a good algorithm (in terms of simplicity and efficiency) to do this for arbitrary $n$?

# Answer
> 1 votes
Practically speaking, here is one thing you could try:

1. Make a list $A\[1\],\ldots,A\[m\]$ of powers of two corresponding to free bits.
2. Generate a list of all XORs of elements from $A\[i\]$ (in the correct order), XORed to a mask consisting of the fixed bits.

If you don't care about the order, then an efficient way to generate the list is using a Gray code. Otherwise, you could use a recursive procedure.

# Answer
> 0 votes
In python:

```
n = 4
or_mask =  0b1000
and_mask = 0b1101
answer_set = set()
for i in range(2**n):
    answer_set.add((i | or_mask) & and_mask)
return sorted(answer_set)

```

---
Tags: algorithms, enumeration
---


title: Prove $\log(n^2 + 1)$ is $Θ(\log n)$

text:
# Question
Title: Prove $\log(n^2 + 1)$ is $Θ(\log n)$
This is a homework problem and I'm not sure if I am doing it correctly.

> Show that $\log(n^2+1)\in \Theta(\log n)$.

I got:

$$ \log (n^2) \leq \log(n^2+1) \leq \log (n^2+n^2) $$ $$ 2\log n \leq \log(n^2+1) \leq \log(2\cdot n^2) $$ $$ 2\log n \leq \log (n^2+1) \leq \log 2 + \log(n^2)$$ $$ 2\log n \leq \log(n^2+1) \leq 1 + 2\cdot\log n$$

I'm not sure if I have proved it according to the definition that a function $f(x)$ is in $Θ(g(x))$ if there exist positive constants $a,b$, and $n\_0$ such that $a\cdot g(x) ≤ f(x) ≤ b\cdot g(x)$ for all $n \> n\_0$.

I feel like I did something wrong here.

# Answer
> 4 votes
In order to prove that $\log(n^2+1) \in \Theta(\log n)$ according to your definition, you have to produce $a,b,n\_0$ such that $a \log n \leq \log(n^2+1) \leq b\log n$ for all $n \geq n\_0$. This is not what you did. What you have shown is some other inequality.

To help you in future such questions, here is a complete proof. We choose $a = 2$, $b = 3$, and $n\_0 = 2$. So we have to show that for $n \geq 2$, $$ 2\log n \leq \log(n^2+1) \leq 3\log n. $$

The first inequality follows from $$ \log(n^2+1) \geq \log(n^2) = 2\log n. $$ You did that part correctly.

The second inequality follows from $$ \log(n^2+1) \leq \log(n^2+n^2) = \log(2n^2) \leq \log(n^3) = 3\log n. $$ This is the part you did incorrectly.

# Answer
> 0 votes
Remember that Θ doesn't care about constant factors, and $log (x^k) = k·log (x)$, so replacing $x$ with $x^k$ doesn't change Θ. Θ also only cares about large n.

If n ≥ 2 then $n^2 + 1 ≤ n^3$, so $log (n^2 + 1) ≤ log (n^3) ≤ 3 log (n)$, therefore $log (n^2 + 1) = Θ (3 log n)$.

---
Tags: asymptotics
---


# Question
Title: Language of TMs that accept some x in less than 50 steps. Is it in co-RE?
L = {M | M is a TM and there exists an input that the TM M accepts in less than 50 steps}

I need to find a minimal class it belongs to between R/ RE/ co-RE/ not in RE∪co-RE. I managed to show that it is in RE with a TM. I think its not in co-RE, because it has to check every input to know wheter a TM M belongs to L. and there are an infinite amount of inputs. I tried to use mapping recursion with ATM, but that failed. Would appreciate any advice, thanks.

# Answer
Maybe that will help ?

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6\_045JS11\_lec09.pdf

Page 42 Credits : Nancy Lynch MIT

Applications of Rice’s Theorem

• Example 3: Another property that isn’t a language property and is decidable

**{ M |M is a TM that runs for at most 37 steps on input 01 }**

– Not a language property, not a property of a machine’s structure.

– Rice doesn’t apply.

– Obviously decidable, since, given the TM description, we can just simulate it for 37 steps.
> 3 votes

# Answer
Your problem is decidable, since a Turing machine accepts some input in $t$ steps iff it accepts some input *of length at most $t$* in $t$ steps, and the latter property can be easily checked.

---

Repeating my comment, if you aimed at proving a negative answer, one avenue would be to prove that the language is not recursive; since you already know that the language is recursively enumerable, it would follow that it is not co-recursively enumerable.

Stated succinctly, an r.e. language is recursive iff it is co-r.e.
> 2 votes

# Answer
This is my solution:

reduction from ATM to L

On input M,w: return a machine M', that on input x: runs w on M, and if M accepts, M' accepts(in a single step) if M decline or loops, decline

if M accepts w, L(M')=Sigma\* and therefore is y in Sigma\* that M' accepts in a single step(in fact it's true for all y in Sigma\*)-that's less 50. if M loops or declines, L(M')=emptyset and therefore there is no word the M' accepts in less than 50 steps, because M' rejects all words.

good luck on your hw!
> -1 votes

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


# Question
Title: Proof that language is not context-free with Parikh's theorem
I want to prove that the language $L = \\{ a^{n}(ab)^{{n}^{2}}b^{n} \mid n \geq 0 \\}$ is not context-free by using Parikh's theorem.

My first assumption is that the $(ab)^{{n}^{2}}$ part cannot be written as a subset of linear vectors. From this it follows that $\psi(L)$ is not semi-linear.

My problem is to show that by a formal proof.

# Answer
> 0 votes
If $L$ were context-free then, applying the homomorphism mapping both letters to $a$, also the following language would be context-free: $$ L' = \\{ a^{2n^2+2n} : n \geq 0 \\}. $$ According to Parikh's theorem, a unary language is context-free iff the corresponding subset of $\mathbb{N}$ is eventually periodic. Yet the sequence $2n^2+2n$ has arbitrarily long gaps, since $2(n+1)^2+2(n+1)-2n^2-2n = 4n+4$. Therefore the set $\\{2n^2+2n : n \geq 0\\}$ is not eventually periodic, and so $L'$ is not regular or context-free.

---
Tags: formal-languages, context-free, proof-techniques
---


# Question
Title: Associativity Question , Computer organization
an access sequence of cache block address of length N and contaons n unique addresses. The no. of unique block address between 2 consecutive accesses to the same block address is bound above by k. What is miss ratio if access sequence is passed through a cache of associativity A \>= k exercising LRU replacement policy? Ans is n/N but how?

Problem : I m not understanding what is meant by an access sequence of cache block address of length N ? Describe it and give answer of whole question .

# Answer
> 0 votes
An *access sequence* is a sequence of accesses. The length of the sequence is the number of accesses it contains. In this case, each access is an access to an address. So that should help you decode what is meant by "an access sequence of cache block address".

As far as solving the problem, it's your exercise so I'll let you have the joy of solving it. I suggest that you try working through some examples with small values of $N$ and $k$. For instance, try $k=1$ and $N=10$ and try to work out some examples of access sequences, and for each compute what the miss ratio is (by hand). See if you spot a pattern.

A tip on how to parse the language: They are talking about an access sequence of length N, where each element in the sequence is a cache block address. Don't read it as "cache block addresses of length N": I don't know what that would mean either, and it's probably not what they intended.

---
Tags: computer-architecture
---


# Question
Title: What are applications of Coin Change problem?
I've read so many about the **Coin Change problem**, debates about wheather it is solvable using *Greedy*, *Dynamic Programming* and so on.

Nevertheless I cannot find an application of this problem.

What are applications of Coin Change problem?

# Answer
> 11 votes
This is going to sound very silly but, I once had to implement the coin change solution for the purpose of... distributing change!

The application was a soda pop vending machine that could accept bills and coins and dispense coins.

The spec required the use of a least coin pay, plus an alternative algorithm should one of the coin tubes be empty and thus unable to dispense coins of that denomination.

The classic example was buying a 60 cent soda pop with a dollar (I know, pop was cheap back then ;-). This leaves 40 cents change, or in the US, 1 quarter, 1 dime, and 1 nickel for least coin pay. If the nickel tube were empty though, the machine would dispense 4 dimes.

I know to is not quite the lofty heights of academia, but it was an actual application of the problem's solution. On a further note, more modern coin changer mechanisms implement their own coin management so for those more capable peripherals, we would just let the coin mech figure out if change could be made.

If not, the customer would get the dreaded NO CHANGE error message and the money would be returned.

# Answer
> 2 votes
Coin change problem is actually a very good example to illustrate the difference between greedy strategy and dynamic programming. For example, this problem with certain inputs can be solved using greedy algorithm and with certain inputs cannot be solved (optimally) using the greedy algorithm. However, dynamic programming version can solve all cases.

A simple example can be as follows. Let's say that you have N tons stuff, to be delivered from one place to another place. You can use airplane (capacity 100 tons), big truck (capacity 15 tons), medium truck (capacity 10 tons), etc. How do you manage to send your N tons of stuff with the minimum number of facilities? There are an infinite number of applications that you can find.

---
Tags: algorithms, applications, coin-change
---


# Question
Title: Language is non-empty is recursively enumerable (intuitive way)
$M$ is some Turing machine, $\left\<M\right\>$ is the code of the Turing machine.

$L =\\{\left\<T\right\> | L(T) \ne \emptyset\\}$

How to see **intuitively** that $L$ is partially decidable?

We can try running a given $M$ on all strings and accept if $M$ accepts. *However, what if the simulated $M$ gets into an infinite loop?*

# Answer
> 1 votes
A language $L$ is partially computable if there is a machine $M$ that on input $x$:

1. If $x \in L$ then $M$ halts.
2. If $x \notin L$ then $M$ doesn't halt.

This is equivalent to the other definitions.

To answer your question, what we do is to run the input machine $M$ on all inputs *in parallel*. If it never accepts on any input, then we never halt, but that's ok.

In order to run $M$ on all inputs in parallel, we use the technique of *dovetailing*:

* We run $M$ for one step on the first input.
* We run $M$ for one step on the first two inputs.
* We run $M$ for one step on the first three inputs.
* And so on.

---
Tags: computability, turing-machines
---