# Question
Title: HandyAR finger tip detection and tracking
I am reading this paper Handy AR.

As suggested I am adding certain quotes from paper to get basic idea of what is it about :

1. Intro
> In this paper, we present and evaluate a method to use a user’s bare outstretched hand in the same way a cardboard AR marker would be used, enabling spontaneous tangible user interfaces in mobile settings

Steps:

1. Adaptive Hand Segmentation

> Given a captured frame, every pixel is categorized to be either a skin-color pixel or a non-skin-color pixel. An adaptive skin color-based method 17 is used to segment the hand region. According to the generalized statistical skin color model 14, each pixel is determined to be in the hand region if the skin color likelihood is larger than a constant threshold.
> In order to adapt the skin color model to the illumination change, a color histogram of the hand region is learned for each frame and accumulated with the ones from the previous n frames (n = 5 works well in practice). Then the probability of skin color is computed by combining the general skin color model and the adaptively learned histogram.
2. Accurate Fingertip detection

> Fingertips are detected from the contour of a hand using a curvature-based algorithm similar to the one described in \[2\]. We then fit the curvature points to ellipses in order to increase the accuracy. The curvature of a contour point is measured on multiple scale levels in order to detect fingertips with various sizes as follows: The points with higher curvature values than a threshold (on any scale level) are selected as candidates for fingertips.
> Since the detection algorithm may produce false positives of fingertips for initial detection, we choose the most frequently detected points above the center of the hand for a certain number of consecutive frames as our final fingertips. Thus, for initial detection, the hand has to be held fingers up, which is the most convenient and by far the most common pose anyway. After fingertips have been detected, we eliminate false positives by tracking a successful configuration over time.
3. FingerTip Tracking

> Once fingertips are detected, we track them based on matching the newly detected fingertips to the previously tracked fingertips. Similar to 21, we track the fingertip trajectory by a matching algorithm that minimizes the displacement of pairs of fingertips over two frames. In addition, we use our knowledge about the centroid of the hand blob to effectively handle large movements of the hand as follows: The matching cost is minimized as the formula I mentioned below.

---

I have a couple of doubts in this :
1. In the 2nd paragraph of the 2nd points of steps:

> After fingertips have been detected, we eliminate false positives by tracking a successful configuration over time.

What does 'successful configuration over time' mean? If we already are tracking a successful configuration , then why are there false positives.

2.In the next section, Fingertrip tracking has been explained. From what I understood , it has two parts

* Using a matching algorithm
* Using centroid to effectively handle large movenments.

My doubt is in the second part, I am not able to understand properly how does it handle large movenments and also the correctness proof of that statement.

Formula for `fi+1`

where `fi` `fi+1` are the sets of N fingertips at the `ith` and `i + 1th` frame and
`Ci` , `Ci+1` are centroids at `ith` and `i + th` frame.

Citation -

I got this from  paper published by Taehee Lee, Tobias Hollerer in 2007 11th IEEE International Symposium on Wearable Computers

---

1. Handy AR

# Answer
> -1 votes
1. What does 'successful configuration over time' mean?... why are there false positives.
2. I am not able to understand properly how does it handle large movements

they are repeatedly scanning a similar form, the "hand blob", so any outliers from the usual successful input will hopefully be ignored. (maybe if someone nearby passes you something and it thinks their hand is yours for a few frames)

the paper says they register the "hand blob" or centroid of skin color as an easier tracking target for large movements. the "one time calibration" is probably about where your hand is, and it's predominant shade, in relation to the device. then it makes sure the fingers are there and orientates using the thumb. there is no difference to the formula for large movements except where Ci+1 actually is compared to Ci.

I really am looking forward to real time interaction with augmented reality. are there many more papers you know of like this? id love to read them too.

Edit: hello again raphael. this is someone of my lvl of understanding and the attempt has been made to fill all of the exceedingly strict criteria for a simple question. this guy is interested, like many are, but has been told off and deleted by you lot before. i can tell.

---
Tags: image-processing, computer-vision, research
---


# Question
Title: Literature about a naive approach to graph isomorphism by inspecting polynomials of adjacency matrices
I describe an approach to graph isomorphism which probably has false positives, and I am curious whether there is literature indicating that it does not work.

Given two adjacency matrices $G, H$, an admittedly naive method of checking for isomorphism is to check whether for each row $u$ of $G$, there is a row $v$ of $G$ which is a permutation of row $u$, denoted by $G\[u\] \sim H\[v\]$. Slightly more strict is the question, is there a "local isomorphism" $\pi$ for which $G\[u\] \sim H\[\pi(u)\]$ for all rows. Producing a local isomorphism can be done in polynomial time by building an $n\times n$ matrix $A$ with $A\[u,v\] = (G\[u\]\sim H\[v\])$; then $G$ and $H$ are locally isomorphic iff $A$ has a cycle cover, and every cycle cover is a local isomorphism.

All regular graphs fool this method, obviously, so a slightly less naive approach is to compute powers $G^2, H^2, G^3, H^3,\ldots$ of the matrices and checking them for local isomorphism, exploiting the fact that you have multiple matrices by setting $A\[u,v\] = 0$ when you find *any* power such that $G^k\[u\]\not\sim H^k\[v\]$, and checking for cycle cover only at the end. An even less naive approach is to find a set of polynomials, indeed a set of arithmetic circuits, and setting $A\[u,v\]=0$ when we find *any* polynomial $p$ with $p(G)\[u\]\not\sim p(H)\[v\]$.

This looks to me like an incredibly naive approach to graph isomorphism, so I am sure somebody has already investigated it and proved a theorem such as

**Thm** For infinitely many $n$ there are nonisomorphic $n\times n$ matrices $G, H$ and a permutation $\pi$ such that for every polynomial $p$, $p(G)$ and $p(H)$ are locally isomorphic by that permutation: $p(G)\overset{\pi}{\sim}p(H)$.

**Question:** Is there such a theorem? I have looked in the literature and cannot find it.

If there is a bound on the degree $k$ that is polynomial in $n$ such that for every two nonisomorphic matrices, local isomorphism is refuted by computing $G^1, H^1, \ldots, G^{poly(n)}, H^{poly(n)}$, or if there is an easily computable family of polynomials $p\_1, \ldots ,p\_k$, each having polynomially-bounded length but possibly exponential degree, then we have a **P** algorithm for graph isomorphism. If such polynomials (or arithmetic circuits) are easy to guess, then we have a **coRP** algorithm. If there always exists a (family of) arithmetic circuits to witness non local isomorphism, then this gives a **coNP** algorithm.

Note that we can avoid the problem that the entries of high-power matrices grow too large by computing the polynomials over small fields, e.g. by computing them modulo small primes. In a **coNP** algorithm, the prover can provide these primes.

# Answer
Yes, there is such a theorem, more or less. It basically states that the k-dimensional Weisfeiler-Lehman procedure subsumes (i.e. dominates) all known combinatorial approaches to graph isomorphism testing. (Your concrete proposal should be subsumed by the 2-dimensional Weisfeiler-Lehman procedure, if I am not mistaken.) For each fixed k, there is a class of counterexamples to the k-dimensional Weisfeiler-Lehman procedure known as the Cai-Fürer-Immmerman construction.

I first learned the basics of the Weisfeiler-Lehman procedure and the Cai-Fürer-Immmerman construction from

> http://users.cecs.anu.edu.au/~pascal/docs/thesis\_pascal\_schweitzer.pdf

There is much more to learn about the Weisfeiler-Lehman procedure than described there, but at least the treatment of the Cai-Fürer-Immmerman construction is complete and sufficient for your purpose. "The Weisfeiler-Lehman Procedure", by Vikraman Arvind is a recent brief essay meant as an invitation to the topic.

Perhaps the crucial point to take away from my answer is that if you would find a purely combinatorial isomorphism testing method (like the one describe in your question), which is not subsumed (i.e. dominated) by the k-dimensional Weisfeiler-Lehman procedure, then this would be a breakthrough by itself, independent of whether the method would be actually useful.
> 12 votes

---
Tags: reference-request, graph-isomorphism
---


# Question
Title: why nominal unification is a first-order unification?
In my understanding, if a unification solves equations of terms that are not higher-order terms, then it is a first-order unification.

If a unification solves equations of terms that are higher-order terms, then it is a higher-order unification. Therefore a unification solves equations of $\lambda$-terms should be a higher-order Unification.

That is what I thought.

Read about unification

the paper nominal unification said that nominal unification is a first order unification, but it is solving equations of $\lambda$-terms.

Why nominal unification is a first-order unification while clearly solving equations of higher-order terms?

Also, that paper shows an example of unification

$$ \lambda a.\lambda b.(b \\, M\_6) =?= \lambda a.\lambda a.(a \\, M\_7) $$

on the right side $\lambda a.\lambda a.(a \\, M\_7)$, what is that? Why two abstractions have same bound variable $a$ ?

I am confused, could anyone clearify it to me, thanks!

# Answer
> 8 votes
Most experience people have with unification (if any) is usually unification modulo syntactic equality: two terms unify if there is a substitution for unification variables that makes the terms *syntactically* identical. However, you can consider other base equivalence relations that are coarser than syntactic equality. For example, there's associative, commutative equality that let's you unify two bags (aka multisets) of terms, e.g. the term $\\{\\!\\!\\{\mathtt{x},\mathtt{y}\\}\\!\\!\\} = \\{\\!\\!\\{\mathtt{y},\mathtt{x}\\}\\!\\!\\}$ where I'm using $\\{\\!\\!\\{ \ldots \\}\\!\\!\\}$ to represent a bag. Unification with a base equivalence like this, coarser than syntactic equality, come up, for example, in checking record types. You can imagine you have a bag of record labels and you want to record types to be the same regardless of how you wrote down the labels.

So, in this context, higher-order unification is unification modulo $\alpha\beta\eta$-equivalence. The base equivalence is what makes it higher-order-unification, *not* the terms it operates on. I can apply normal, syntactic, first-order unification to lambda terms too. Unification modulo $\alpha\beta\eta$-equivalence means being able to unify expressions like $E(3) = (3,3)$ via a substitution such as $\[E \mapsto \lambda x.(x,x)\]$ as these are $\beta$-equivalent. (Following Prolog, I'll use capital letters to indicate unification variables. Also, note $\[E\mapsto\lambda x.(3,3)\]$ is another *non-equivalent* substitution which is why higher-order unification produces extra non-determinism.) Nominal unification does not unify these terms. $(\lambda x.(x,x))(3)$ is not $\alpha$-equivalent to $(3,3)$. An application will never be $\alpha$-equivalent to a pair constructor. (However, if the notation was implicitly in curried-style, i.e. $(3,3)$ meant $((,)(3))(3)$, these would *syntactically* unify. Generally, though, multi-ary application is never $\alpha$-equivalent to unary application.)

Nominal unification is unification modulo $\alpha$-equivalence. At a raw syntax level $\lambda x.x$ is syntactically different from $\lambda y.y$ because $x$ is different syntax than $y$. This is undesirable as we want to treat these terms as completely identical. We don't want the choice of variable name to matter to, e.g., type checking. This problem is clearly solvable because we could use deBruijn notation and the only term corresponding to the two above lambda terms would be something like $\lambda\mathbf{1}$. The power of deBruijn notation is that syntactic equality is $\alpha$-equality. Nevertheless, it would be nice not to use deBruijn notation.

So one way to implement nominal unification would be to simply convert each term to deBruijn notation and unify. This would be fine if all we needed to do was answer "yay" or "nay", but we also need to produce a substitution. If we convert $\lambda x.x$ and $\lambda y.E$ to $\lambda\mathbf{1}$ and $\lambda E$ respectively, then unify them, we get $\[E \mapsto \mathbf{1}\]$. But obviously $\lambda x.x \neq (\lambda y.E)\[E\mapsto x\]$. Basically, we need to keep track of what variable corresponds to $\mathbf{1}$ on each side of the equation. This gives us two bijections (for any particular unification variable, i.e. locally) that maps variables to deBruijn indices, here $\[x \mapsto \mathbf{1}\]$ and $\[y\mapsto\mathbf{1}\]$. We can compose these bijections to get a bijection (i.e. permutation) between variables on each side. This leads to $\[E \mapsto (x\ y)\bullet x\]$, in their notation, which simplifies to $\[E\mapsto y\]$, the desired substitution. There are some extra concerns about capturing variables that additionally complicates the picture.

Summarizing, higher-order unification means unification modulo $\alpha\beta\eta$-equivalence. Nominal unification means unification modulo only $\alpha$-equivalence. This can be reduced to syntactic unification of deBruijn terms, but if we want to produce substitutions on non-deBruijn terms we need to keep track of some extra information. Doing a similar reduction for higher-order unification would involve reducing to terms in $\beta\eta$-normal form, which thus requires such normal forms to exist hence the focus on the typed case, and leads to creating terms out of nowhere which themselves require unification.

---
Tags: lambda-calculus, unification
---


# Question
Title: Understanding Cache Mapping and Access (Computer Architecture)
Consider a 512-KByte cache with 64-word cachelines (a cacheline is also known as a cache block, each word is 4-Bytes). This cache uses write-back scheme, and the address is 32 bits wide.

Answer the next questions for Direct Mapped cache, Fully Associative and Way Set Associative

What is the size in bits of the cacheline offset, cachline index and tag?

What I know:

Direct mapped caching allows any given main memory block to be mapped into exactly one unique cache location.

Set-associative mapped cache allows any given main memory block to be mapped into two or more cache locations.

Fully-associative mapped caching allows any given main memory block to be mapped into any cache location.

I don't know how that would make a difference in computing byte offset, index and cache

$Byte offset=log\_2(\text{bytes in one cache block})$ $Index=log\_2(\text{Number of cache blocks in the cache})$
tag: The rest of bits in the address

Attempt at a solution

I would do the mapped cache part by using the previous expressions. I don't want the answer, but I would like orientation.

Thanks!!

# Answer
> 4 votes
Any physical address consists of two parts : one part is the block offset and the other part is the block number.

```
Physical Address { Block number, Block Offset}

```

Block Number has further 2 parts : the index part and the tag.

The memory is assumed to be logically divided into many blocks. A block may contain more than one words in it ( which is indicated by the block size ). To reach to a specific word block offset is used.
Block offset is the number of bits required to address each word in the memory.

For instance, in a byte addressable system ( 1 word = 1 byte ) if the block size = 1 KB then
Block Offset = 10 bits. (Byteoffset=log2(bytes in one cache block)
The block offset remains same in each type of mapping as the number of words in each block do not change.

The implementation of block number is different in different mappings.

In case of Direct mapping the block number has two parts:

```
block no { tag, line number}

```

Since each block is mapped to one line in the cache, the "line number" part of block number contains number of bits required to identify each line in the cache.
In this case since cache size = 512 KB and block size = (64 * 4)B = 256 B
The Number of lines in the cache = 512 KB / 256 B = 2 K = 2 ^ 11
Therefore, the number of bits in line number part will be 11.
The remaining bits are tag bits.

Fully Associative Mapping the tag number is same as the block number .
In Fully Associative Mapping any memory block can be mapped to any of the cache lines. So to check which line of the cache a particular block is mapped to every line number is "tagged".

And in Set Associative Mapping the block number is divided into two parts:

```
block no { tag, set number}

```

Here, the cache is divided into many sets, so the "set number" part consists of the number of bits required to identify each set uniquely.
Depending on the number of lines in each set ( a K-way set associative mapping will contain K lines in each set), the number of sets can be found out.

Hope this will help you.

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


# Question
Title: Turing machine for which it is impossible to decide if it halts?
Assuming someone tries to approximate a function which decides if a turing machine halts or not. It uses only a finite amount of time. The function returns $0$ (=the turing machine halts), $1$ (=the turing machine never halts) or $2$ (=the algorithm could not decide if the turing machine ever halts). If it returns $0$ or $1$ the answer must be correct.

Of course there are (countable) infinite many calculatable functions which could be used for this. All those functions could be called $f\_n(t\_i)$ where $t\_i$ is a turing machine.

For every $f\_n$ there must be some $t\_i$ for which the function is not able to decide if the turing machine halts or not. \begin{align} \forall n\in\mathbb{N}:\exists i\in\mathbb{N}:f\_n(t\_i)=2 \end{align}

One could then define a new $f\_m$ which tries all previous defined $f\_n$ and if one of the previous $f\_n$ was able to decide if a turing machine halts it has the final answer. But of course this also does not work perfect, beause there are still some turing machines for which it is not possible to decide if they halt (otherwise the halting problem would be solved).

Then it is possible to say that a turing machine (or infinite many...) $t\_i$ must exist for which all halting problem solver approximations $f\_n$ must return $2$.

In words: A turing machine must exist for which it is not possible to decide if it ever halts or not. Is such a turing machine known? If not: why not? Or isn't it possible to find such a turing machine?

Thank you very much

# Answer
> 2 votes
> A turing machine must exist for which it is not possible to decide if it ever halts or not.

This is an incorrect conclusion. For some ordering of $f$ and $t$, it could be that $f\_n$ correctly solves all $t\_i$ for $i \< n$, i.e. every $t\_m$ is solved by $f\_{m+1}$. This would still not give a complete solution to the halting problem, as long as the function $n \mapsto f\_n$ is not computable.

---
Tags: computability, turing-machines, undecidability, halting-problem
---


# Question
Title: what is definition of algorithm in computer science?
I have problems in writing algorithms before writing code for a particular program.

An algorithm is just like a recipe.

But when it comes to programming complex structures (like nested conditional statements and loops) in my code, I am not able to write one, and often get confused easily. How can I get over this thing?

# Answer
> 1 votes
An algorithm is, alas, an informal concept, which can not have a precise mathematical definition. One can still attempt at an informal definition, and argue that it conveys the right (informal) intuition.

Because of its informal nature, sometimes it's also easy to argue against a given definition, attacking the definition wording. For instance, I've read more than once that an algorithm is a "sequence of steps" which makes my eyebrows raise, since it suggests that any algorithm will always halt within those number of steps, no matter how large the input is. Once, I had a conversation with a physicist where I couldn't follow their argument, and it turned out they identified "halting algorithm" with "constant-time algorithm" since they believed the number of steps were fixed by the algorithm (hence independent from the input).

If I had to define an algorithm, very informally, I would say that it is an informal but unambiguous description that, to each input, it associates a finite sequence of elementary computation steps which can be used to obtain the desired output.

This is far from being perfect. For instance, what is a "elementary computation step"? Further, it does not express that the mapping form input to the sequence of steps must be effective -- otherwise we could associate to all halting TM encodings the steps `print 1`, and `print 0` otherwise.

To fix these issues, I believe that we also need to convey the notion of computability in some way, which is however too much for that definition. One could refer to a specific formalism or programming language, but I'd want that definition to be computation-model-agnostic.

Indeed, one could say that an algorithm is an informal description of, say, a Java program, which is not as detailed as real code, yet is enough detailed that it could be turned into actual Java without needing to do further research, but only doing "coding". I would regard such a definition as quite inelegant, though.

---
Tags: algorithms, terminology
---


# Question
Title: Is there a metric for the similarity of two image filters?
## Definitions

An image filter is a matrix $m \in \mathbb{R}^{k\_1 \times k\_2 \times k\_3}$ which gets applied to an image $I \in \mathbb{R}^{l\_1 \times l\_2 \times l\_3}$ as a discrete convolution

$$I'(n\_1, n\_2, n\_3) = \sum\_{i=0}^{k\_1} \sum\_{j=0}^{k\_2} \sum\_{k=0}^{k\_3} I\[n\_1-i - \lfloor \frac{k\_1}{2} \rfloor, n\_2 - j - \lfloor \frac{k\_2}{2} \rfloor, n\_3 - k - \lfloor \frac{k\_3}{2} \rfloor\] \cdot m\[i, j, k\]$$

There are some well-known filters like Laplace filters, Prewitt filters, ... (see my interactive example)

For example, for an RGB image $k\_3 = 3$ and $k\_1, k\_2$ are width and height.

## Question

Is there a metric to compare the similarity of image filters?

## Context

Convolutional Neural Networks (CNNs) learn image filters. As they are randomly initialized, the filters they learn are different each time you train them. I am interested in quantifying those differences.

I could, of course, use any metric for elements of $\mathbb{R}^{k\_1 \times k\_2 \times k\_3}$. However, consider the filters

$$ \begin{align} m\_1 &= \begin{pmatrix}-1&0&1\\\-1&0&1\\\-1&0&1\end{pmatrix}\\ m\_2 &= \begin{pmatrix}1&0&-1\\1&0&-1\\1&0&-1\end{pmatrix}\\ m\_3 &= \begin{pmatrix}-0.9&0.1&1\\\-0.9&0.1&1\\\-0.9&0.1&1\end{pmatrix}\\ \end{align} $$

For the image

$m\_1$ produces

and $m\_2$ produces

You can see a difference, but much less than for the result of $m\_3$:

This is probably not captured by most metrics. Another idea was to apply the metrics to the processed images on a given dataset, but this would make the results depend on the dataset and be computationally very intensive.

(In case you want to try image filters yourself with Python: https://gist.github.com/MartinThoma/f51a1044c4abc6c7b81915ef96b7cfbd)

# Answer
> 3 votes
The ‘k-translation correlation’ is probably a good candidate for what you are looking for. It measures the maximum correlation between a pair of two filters $\mathbf{W\_i}$ and $\mathbf{W\_j}$ achieved by translating one filter up to k steps along any spatial dimension and then selecting the maximum thereof:

$$\rho\_k(\mathbf{W\_i,W\_j})=\max\_{(x,y)\in \\{-k,...,k\\}^2\setminus(0,0)} \frac{\langle\mathbf{W\_i}, T(\mathbf{W\_j}, x,y)\rangle\_f}{\left \\| \mathbf{W\_i}\right \\|\_2 \left \\| \mathbf{W\_j}\right \\|\_2}\\,,$$

where $T(\cdot, x,y)$ refers to the translation of its first operand by $(x,y)$ and $\langle\cdot,\cdot\rangle\_f$ denotes the flattened inner product of the two filters (the second of which is translated). Note that both filters are reshaped to column vectors to perform the inner product. For more details refer to Doubly Convolutional Networks (Zhai, Cheng, Lu, Zhang, in *Proceedings of 30th Conference on Neural Information Processing Systems (NIPS 2016)*).

# Answer
> 1 votes
One plausible approach is to compare the outputs of the two filters on each image in a training set, and take the average of those values.

In particular, given an image $I$ and two filters $m\_1,m\_2$, you can compute the results of applying each filter to $I$, namely, $m\_1 \otimes I$ and $m\_2 \otimes I$. Then, you can compare the similarity of those two results, say, by computing the correlation between them (say, Pearson correlation coefficient). Denote this by $c(m\_1 \otimes I, m\_2 \otimes I)$.

Now given a training set $\mathcal{I}=\\{I\_1,\dots,I\_n\\}$ of images, you can compute the average value of the correlation coefficient across all images in the training set, and use that as your distance metric:

$$d(m\_1,m\_2) = \frac{1}{n} \sum\_{I \in \mathcal{I}} c(m\_1 \otimes I, m\_2 \otimes I).$$

If the composition of the training set matches the set of images you intend to use the filter on, this should give you a reasonable measure of the similarity of two filters.

You rejected this approach out of the concern that it would make the results dependent on the dataset, but I think that's addressed by choosing a training set that matches the distribution of images you intend to use the filter on. In other words, if you intend to use the filter on images produced by some statistical process, then choose the images in the training set by the same procedure. If you do that, then that concern should evaporate. In particular, thanks to the central limit theorem, if the training set is large enough, $d(m\_1,m\_2)$ converges to a single "true" value as $n \to \infty$ (as the size of the training set increases).

---
Tags: machine-learning, computer-vision, comparison
---


title: Reinforcement Learning - Agent training

text:
# Question
Title: Reinforcement Learning - Agent training
In RL, in a game situation, usually the agent is trained by playing against itself.

When we should not depend on this self-training, and switch to train the agent with a real or different player agent other than the agent it self?

I mean is there any characteristics of the environment that would make self-play worse choice than playing against an existing player?

# Answer
Ideally when training an agent you would reach an equilibrium between both player strategies strategies (hopefully a Nash equilibrium). When using only self-play this equilibrium might be different to the one you would reach when competing against a specific player, in particular, taking into consideration that the other player might not be very efficient, may have a different reward structure, etc.

Now, answering your specific question about the environment.. I would say that the critical aspect is the game being played. You should check if you are dealing with a zero-sum game, cooperative vs non-cooperative, etc.
> 1 votes

---
Tags: reinforcement-learning
---


# Question
Title: Allocating flows in a network while avoiding a particular node
I am considering a network with the max flow problem in a particular situation. I have a set of flows which should pass a certain node **A** and and another set of flows which should avoid **A** and pass through another node **B**. The flows can cross each other at any other arbitrary node.

Under what category of network flow problems should this be considered?

# Answer
Flows with more than one "thing" flowing are known as "multicommodity flows".

The basic definitions assume that every thing can flow through every vertex and edge. However, the standard way of solving these problems is linear programming and you could easily modify the normal multicommodity flow program to deal with your situation, just by substituting zero for the appropriate variables.
> 7 votes

---
Tags: graphs, network-flow
---


title: Doubts abouts join implementation

text:
# Question
Title: Doubts abouts join implementation
I'm studying advanced database and I can not understand some concepts related to the join. I hope I'm in the right place to post my doubts, otherwise I'm sorry.

I realized that to make the equijoin there are several families. In particular, the family that is based on the Cartesian product includes three main methods: nested loops, nested blocks and nested scans.

The **nested loop method** iterates on the outer relation *R* (tipically the smaller one) and for each tuple of *R*, it scans the internal relation *S* and applies the join condition. Then it just use the join definition: Cartesian product + selection. The cost of this process is:

`C = |R| + |R| * |S|`

You can get an improvement if instead of considering the tuples, consider the pages. In this case the cost is:

`C = P_R + |R| * P_S`

Why? I do not understand.

From what I remember of Operating Systems, the logical memory is divided into pages and the physical memory in frames, where the pages are of the same size of the frames. This is done to permit the non-contiguous allocation of files.

A tuple instead of what corresponds? I guess as a record (one line) of a table, but in this context what is it?

The **nested blocks method** is a further improvement because in main memory maintains a block of tuples of *R*. The improvement is obtained by scanning *S* only once for each group of tuples of *R*. A version of this charging algorithm in the tuples of *R* memory, then proceeds to *S* and examines the memory to find the *S* tuples that match any tuple of *R*. This reduces the number of necessary *S* scans. In this case the cost is:

`C = P_R + P_R * P_S`

I must admit that I did not understand very well this algorithm. Someone could explain it better?

Thus a block is a set of tuples? And a set of tuples form one page? I'm very confused.

Maybe some sketch could help me, I have not found that showed the tuples.

Thank you all

---

If I understand correctly, this is how I imagine the logical memory, physical memory, pages and frames:

**Nested loops (tuple)**

Again, as I understand it:

I apologize but I have not yet understood the nested loop (pages) and nested block :(

What do you mean with "*We can achieve some improvement checking the tuples stored on one page of relation S for each record in relation R*"?

And with "*In Block nested approach each block in the inner relation S is read once for each block in the relation R which gives you the desired cost*"?

I feel a bit stupid, sorry.

# Answer
First, let's establish some variables: we'll have $n\_r$ tuples of relation $r$ and these tuples will be grouped into $b\_r$ blocks; similarly the relation $s$ will have $n\_s$ tuples, grouped into $b\_s$ blocks. We'll assume that a single disk access can retrieve one block.

**Nested-loop join**. In this implementation we work on a per-tuple basis. The algorithm looks like this:

```
for each tuple t_r of r
   for each tuple t_s of s
      test the pair (t_r, t_s) to see if it meets the join condition
      if it does, include the joined pair in the result

```

To get the tuples $t\_r$ in the outer loop, we get a block of tuples in one disk access, so the outer loop will require $b\_r$ disk accesses to eventually get all the tuples of $r$. For each of the $n\_r$ iterations of the outer loop, we need to compare a $t\_r$ with all the $t\_s$ tuples in $s$, so each iteration of the inner loop will take $b\_s$ disk accesses. We have $n\_r$ iterations of the inner loop for a total of $n\_r\cdot b\_s$ more disk accesses, so this algorithm will require $\mathbf{b\_r+n\_r\cdot b\_s}$ disk accesses.

In your example, $n\_r=5, b\_r=b\_s=2$, so we'd need $2+5\cdot 2= 12$ accesses.

**Block nested-loop join**. Here we do the same comparisons as before, only on a per-block basis, like this:

```
for each block B_r of r
   for each block B_s of s
      for each tuple t_r in block B_r
         for each tuple t_s in block B_s
            test the pair (t_r, t_s) to see if it meets the join condition
            if it does, include the joined pair in the result

```

Now the outer loops will require $b\_r$ disk accesses, as before, and for the next loop we'll require $b\_s$ accesses for each of the outer $b\_r$ blocks, for a total of $b\_r\cdot b\_s$ accesses, giving us a total of $\mathbf{b\_r+b\_r\cdot b\_s}$ accesses. Note that the two innermost loops will require no accesses, since all their actions can be done in memory.

With $n\_r=5, b\_r=b\_s=2$, we'd need just $2+2\cdot 2= 6$ accesses.

---

It's worth mentioning that these are worst-case values, assuming that only one block of each relation can fit in the disk-to-memory buffer. Of course, if we had enough memory to store all of $r$ and $s$, then we'd only need $b\_r+b\_s$ disk accessses, to read both $r$ and $s$ into memory.
> 0 votes

# Answer
First of all let us talk about the cost measure . The cost C is calculated actually in terms of the number of disk access made in order to compute the join.

A block is defined as the smallest unit of memory which is transferred from disk to main memory during a disk access.

A page is a contiguous block of memory. (set of blocks)

Anther term associated is the blocking factor. which is the number of records which can be present on a single block of memory.

Suppose we need to compute the join of relation RxS The first method we first bring the relation R in the main memory which take n(R) disk accesses (n(R)= number of records in the relation R). Note that records and tuples mean the same thing. For each record in relation R we make another disk access to bring a single record of relation S to check the join condition this gives another n(r)\*n(S) disk accesses. the total being n(r)+n(R)\*n(S)

We can achieve some improvement checking the tuples stored on one page of relation S for each record in relation R.

In Block nested approach each block in the inner relation S is read once for each block in the relation R which gives you the desired cost
> 1 votes

---
Tags: database-theory
---


# Question
Title: Modelling a dependency of multiple transitions on data in one place
We are modeling our process using a colored Petri net. One of the limitations we have is that when multiple transitions depend on one place, only one of those transitions will fire because then the token and data is consumed.

How can we model our process, or what type of Petri net property can we use, to facilitate the fact that multiple transitions can depend on one place and *all* have to be able to consume the same token?

# Answer
> 2 votes
I do not know if there is a variant of Petri nets that captures your intent exactly -- there *probably* is, there are so many -- but the feature can be expressed with regular Petri nets.

Just add a transition that creates tokens in multiple places, one per original transitions. Then, all three follow-up transitions can fire after the preceding one is done.

Introduce whatever syntax you want to express this neatly, and implement it using multiple places in the backend.

# Answer
> 1 votes
Another way to model your situation with Petri Nets would be to use an arc with weight as shown below.

However in the "traditional way" of interpreting a Petri Net, only one enabled transition will be chosen for firing at a time. Thus you must include in your model the method of interpreting your Petri Net when there is more than one enabled transition. In this case if each of the transition fires "at the same time" using a different processor then you must also consider the problem of updating the place by three different processor. In Raphael's Petri Net this is not a problem.

---
Tags: modelling, petri-nets
---


# Question
Title: What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?
Everybody knows the Chomsky-hierarchy for describing formal languages and big-O notation for describing time and space complexity of a function.

We know, that each class in the Chomsky-hierarchy corresponds to an atomata, that can recognize any language in the corresponding class.

The question is: What is the worst-case time and space complexity of these automatas given any language of the above class?

What I found out already:

**Chomksy-3 class**, the regular languages can be recognized by an FSM of n-states where n is a finite number. IMO this makes it require O(n) space and O(l) time, where l is the length of the input.

**Chomsky-2 class**, the context free languages can be recognised by a Non-deterministic pushdown automaton. CYK algorithm run $n^3 * G$ where n is the length of the input and G is the number of rules in the grammar in Chomsky Normal form.

But how much space needed? Do we have better bounds?

**Chomsky-1 class**, the context sensitive languages can be recognised by a Linear-bounded non-deterministic Turing machine.

This class seem to depend on the length of the context to be recognised. Maybe in exponential time.

**Chomksy-0 class**, the recursively enumerable languages can be recognised by Turing machine.

Can anything stated for this class? If not, why? Maybe the $P \stackrel{?}{=} NP$ problem is related.

Are the above statements true?

Please give citations to your answer!

# Answer
> 3 votes
Regular languages can be accepted in linear time and constant space.

Valiant's algorithm parses arbitrary context-free languages in time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant. Deterministic context-free languages (which are those used in practice) can be parsed in linear time.

Context-sensitive languages are identical to the class $\mathsf{NSPACE}(n)$. I'm not aware of any non-trivial time upper bound.

Recursively enumerable languages cannot be parsed in general, since $\mathsf{R} \neq \mathsf{RE}$.

The $\mathsf{P}\stackrel?=\mathsf{NP}$ question is completely unrelated. Unfortunately, the undergraduate curriculum usually spends much more time on the old-fashioned Chomsky hierarchy compared to more modern hierarchies afforded by computational complexity theory.

---
Tags: complexity-theory, time-complexity, space-complexity, chomsky-hierarchy
---


# Question
Title: Understanding the bandwidth problem on graphs
I'm trying to understand the bandwidth problem on graphs. Consider the following tree given as an adjacency list:

```
1 => 4
2 => 6
3 => 5, 6
4 => 7
5 => 3
6 => 2, 3, 7
7 => 4, 6

```

It is claimed an optimal ordering of the vertices is `1 4 5 7 3 6 2`, but I don't see how.

When I draw the graph, 5 is 4 edges away from 4, and 3 edges away from 7... yet we jump back to 7 anyways? I don't understand how this problem works.

Wouldn't the ordering be `1, 4, 7, 6, 2, 3, 5` because everything is one node apart, with a maximum bandwidth of 2, because 2 is 2 edges away from 3? With 1 edge separating everything else.

Bandwidth problem explained in homework assignment:

> The bandwidth problem takes as input a graph G, with n vertices and m edges (ie. pairs of vertices). The goal is to find a permutation of the vertices on the line which minimizes the maximum length of any edge. This is better understood through an example. Suppose G consists of 5 vertices and the edges (v1, v2), (v1, v3), (v1, v4), and (v1, v5). We must map each vertex to a distinct number between 1 and n. Under the mapping vi → i, the last edge spans a distance of four (ie. 5-1). However, the permutation {2, 3, 1, 4, 5} is better, for none of the edges spans a distance of more than two. In fact, it is a permutation which minimizes the maximum length of the edges in G, as is any permutation where 1 is in the center

# Answer
I think you got the definition of bandwidth wrong. Here is your definition of the bandwidth of an ordering of the vertices:

> The bandwidth is the maximum distance *in the graph* between adjacent nodes *in the ordering*.

The correct definition is:

> The bandwidth is the maximum distance *in the ordering* between adjacent nodes *in the graph*.

Your problem is equivalent to the usual one – just take the inverse of the ordering permutation to get from one to the other.
> 3 votes

---
Tags: graphs, optimization, ordering
---


# Question
Title: How to Define an Efficient, Optimal or Suboptimal Parallel Algorithm?
I am going through the book of Parallel Programming and a parallel algorithm is often classified as *Efficient*, *Optimal* or *Suboptimal*. I googled these terms but I didn't found a clear definition for them.

Define $T(n)$ as the running time of the sequential algorithm, $t(n)$ as the running time of the parallel one, $p(n)$ as the number of processing units. Hence work $w(n)=p(n)t(n)$, speedup factor $S(p)=\frac{T(n)}{t(n)}$, efficiency $E=\frac{T(n)}{p(n)t(n)}\times 100\\%$.

The parallel algorithm is *efficient* if:

1. $t(n)=O(\log^c n)$ for some constant $c\>0$; and
2. work $w(n)=T(n)O(\log^c n)$

The parallel algorithm is *optimal* if:

1. $t(n)=O(\log^c n)$ for some constant $c\>0$; and
2. work $w(n)=O(T(n))$

Are the definitions of *efficient* and *optimal* correct? And what about *suboptimal*?

I am literally a noob to parallel programming and I googled a lot without a clue. Any help would be greatly appreciated. Thanks in advance.

# Answer
> 1 votes
The word "correct" is misplaced, what you should be asking is whether those definitions are meaningful / express the notion of "efficient" that you (or the author) had in mind.

The notion of efficient might vary depending on the context, so there is no "correct" definition. For example, in sequential computing, polynomial time is usually considered efficient. One of the reasons to use polynomial time is because polynomials have nice properties that cause our definition to well-behave, e.g. an efficient algorithm which uses another efficient algorithm as a subroutine is still efficient (this is because polynomials are closed under composition).

With this in mind, I'll try to give a few reasons as to why these definitions might be useful or reflect what you imagine that an efficient parallel algorithm will be.

First, it obviously holds that $w(n)=\Omega(T(n))$, since a sequential algorithm can simulate the parallel one by doing the work of all processors one by one, which takes $p(n)t(n)=w(n)$ time. Here I assumed that $T(n)$ is a lower bound on the time required for a sequencial algorithm to preform the given task. This explains your notion of optimallity, one cannot do better then $w(n)=O(T(n))$.

As for efficient, requiring the running time for each processor to be $O(\log^c n)$ results in exponential speedup over a sequencial algorithm, since $T(n)=\Omega(n)$ (the sequencial algorithm must at least read the entire input), and thus $T(n)=\Omega\left(2^{\[t(n)\]^{\frac{1}{c}}}\right)$.

The additional requirement of $w(n)=T(n)O(\log^c n)$ means that the overall number of operation does not increase too much (you pay in processing power for better computation time). So in this case, the overall number of operations for the sequencial/parallel algorithm is equivalent up to polylogarithmic factors.

---
Tags: asymptotics, parallel-computing
---


# Question
Title: The Taylor series and time complexity analysis
I was just wondering, if an algorithm $A$ has a time complexity O$(2^n)$, since $2^n$ can be represented using a Taylor series, which is a polynomial, does this mean that $A$ has polynomial time complexity? Generalising even further, does this mean that any algorithm which has a time complexity O($f(n)$) where $f(n)$ has a corresponding Taylor series representation is also a polynomial time algorithm?

Thanks very much in advance.

# Answer
$2^n$ can be represented as a Taylor series, which is an *infinite sum* of polynomials. Notably, there is no single polynomial which is equal to $2^n$.

In general, since big-O lets us get rid of lower-degree terms in the polynomial, we can say that something has polynomial time (or space or whatever you're measuring) when it is $O(n^k)$ *for some fixed $k$*.

Since there's no *single* $k$ where $\forall n \ldotp O(2^n) = O(n^k)$, we say that $2^n$ is not polynomial.
> 6 votes

# Answer
Your mistake is that you are confusing *Taylor series* and *Taylor polynomial*. $2^n$ can be represented as a *Taylor series*, which is an infinite series of polynomials (that is the limit of an infinite sequence of polynomials). When you cut off a *Taylor series* at some fixed degree, you get a *Taylor polynomial*, which is a polynomial. However, $2^n$ cannot be reasonably approximated by any polynomial, including a *Taylor polynomial*.
> 4 votes

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


# Question
Title: Find number of nodes that seperate graph to two or more subgrahps when removed individually - Find articulation points on a non-directed graph
Suppose that we have an undirected graph, and that for any two nodes there is a path from one to another. In such a graph, there might be some nodes that, if removed from the graph individually, leave behind the starting graph as two or more subgraphs - that is, removing one of the said nodes no longer makes possible to find a path between any two nodes.

What I want is a good algorithm to find how many these nodes are - nodes that if removed individually tear the graph connectivity apart.

What I have thought so far involves removing a node at the time and trying to reach all nodes from a starting node - failing to reach every node would mean the node removed is of the kind I am looking for. Some optimizations may apply, but that's the main idea.

Can you propose any better algorithm for this, e.g. taking advantage of say the degree of the nodes?

EDIT: After having found the answer, my question is equal to asking to find the number of articulation points in an undirected graph, so the title has changed accordingly.

# Answer
> 3 votes
After some searching, I came across exactly what I wanted - seems like knowledge of terms is important. Source from Wikipedia - Biconnected components.

> **Linear time depth first search**
>
> The classic sequential algorithm for computing biconnected components in a connected undirected graph is due to John Hopcroft and Robert Tarjan (1973).\[1\] It runs in linear time, and is based on depth-first search. This algorithm is also outlined as Problem 22-2 of Introduction to Algorithms (both 2nd and 3rd editions).
>
> The idea is to run a depth-first search while maintaining the following information:
>
> the depth of each vertex in the depth-first-search tree (once it gets visited), and for each vertex v, the lowest depth of neighbors of all descendants of v in the depth-first-search tree, called the lowpoint.
>
> The depth is standard to maintain during a depth-first search. The lowpoint of v can be computed after visiting all descendants of v (i.e., just before v gets popped off the depth-first-search stack) as the minimum of the depth of v, the depth of all neighbors of v (other than the parent of v in the depth-first-search tree) and the lowpoint of all children of v in the depth-first-search tree.
>
> The key fact is that a nonroot vertex v is a cut vertex (or articulation point) separating two biconnected components if and only if there is a child y of v such that lowpoint(y) ≥ depth(v). This property can be tested once the depth-first search returned from every child of v (i.e., just before v gets popped off the depth-first-search stack), and if true, v separates the graph into different biconnected components. This can be represented by computing one biconnected component out of every such y (a component which contains y will contain the subtree of y, plus v), and then erasing the subtree of y from the tree.
>
> The root vertex must be handled separately: it is a cut vertex if and only if it has at least two INDEPENDENT (non-connectible) children. However, since we hold the child count of each visited node, and the count only increments if the adjacent node being checked is not already visited, the root having \>=2 children count would surely mean that at least two of the root's children are independent. If there were no 2 independent children of the root, all of the children of the root apart from the first checked would be marked as visited BEFORE the DFS search returned to root and continued the search to the second child, therefore the root's children count would be stuck at 1.

The code below prints the said articulation points, but with minimal changes it can also just print out the count of the said points.

**Pseudocode**

```
GetArticulationPoints(i, d)
      visited[i] = true
      depth[i] = d
      low[i] = d
      childCount = 0
      isArticulation = false
      for each ni in adj[i]
          if not visited[ni]
              parent[ni] = i
              GetArticulationPoints(ni, d + 1)
              childCount = childCount + 1
              if low[ni] >= depth[i]
                  isArticulation = true
              low[i] = Min(low[i], low[ni])
          else if ni <> parent[i]
              low[i] = Min(low[i], depth[ni])
      if (parent[i] <> null and isArticulation) or (parent[i] == null and childCount > 1)
          Output i as articulation point

```

---
Tags: algorithms, graphs, counting
---


# Question
Title: Does transforming a CFG to Chomsky normal form make it unambiguous?
Does transforming a CFG to Chomsky normal form make it unambiguous? And if not, is there a technique to convert a CFG G to an equivalent CFG G', so that G' is both unambiguous and LL(1)?

# Answer
There are inherently ambiguous context-free languages, and like all context-free languages they have grammars in Chomsky normal form, so transforming a CFG to Chomsky normal form doesn't necessarily make it unambiguous. For the same reason there is no technique to convert an arbitrary context-free grammar to one which in unambiguous.

Deciding whether a given context-free grammar is ambiguous, or whether a given context-free grammar generates an inherently ambiguous language, is undecidable. This doesn't necessarily mean that there is no procedure that converts any context-free grammar into an unambiguous one given that the language isn't inherently unambiguous, but it does make the existence of such an algorithm somewhat doubtful.
> 10 votes

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


# Question
Title: Can I notate time complexity depending on the result of an algorithm?
I have a program that calculates the first year some two events happen on the same day. I have not calculated any upper limit for the year. The time complexity of the program would be equivalent to **O(Years)**, where Years is the result of the algorithm.

Is such a notation possible?

If yes, can I call the algorithm "linear"?

If not, what would be the correct way of notating the complexity?

# Answer
> 0 votes
You can use whatever notation you want, as long as you explain what it means.

A linear time algorithm usually means an algorithm running in time $O(n)$, where $n$ is the length of the inputs in bits or in machine words (depending on the computation model). The only exception is algorithm which produce a large amount of output. In that case you can say that the algorithm runs in time linear in the output length.

# Answer
> 1 votes
You can express algorithms costs in whichever parameters you desire, so long as you define them. The parameters don't even have to be known given the input; that gives your bound limited use, but well.

*Warning:* Landau bounds are *asymptotic*, that is they only hold meaning when you let the parameter(s) go towards infinity. That is you can not *really* use parameters that can not be arbitrarily large.

*Warning:* It's unlikely that your cost is independent of the input, which is what your bounds seems to suggest. You probably made a mistake.

---
Tags: algorithm-analysis, landau-notation, notation
---


title: Why are progress bars so inaccurate?

text:
# Question
Title: Why are progress bars so inaccurate?
Computers and programming languages tend to be deterministic and predictable. Yet progress bars seem the opposite, especially if the operation is complex. Even for world class professional products, some progress bars do little to reflect the real progress of an operation. I've seen them go from 10% to 90% in one leap after doing nothing for 4 hours. I've even seen some take steps backwards, suggesting extra unexpected processing has been discovered.

Granted that there may be database operations, network processing and parallel operations but it seems that this could be quantified in some manner and a percentage estimated. After all, there must be a finite amount of instructions executed to complete an operation. Is this simply poor coding, or is there some fundamental reason representing progress is difficult?

# Answer
To add to the more general answers so far I can give a few examples from my field where progress bars don't work and why;

Computer aided design programs - programs that perform thermal analysis or fluid mechanics can be generally terrible with progress bars. They jump forward, backwards, take inconsistence steps and there is almost no use in watching them. This is due to the iterative nature of these types of simulations and the need to find convergence. This is best viewed not by a progress bar but by a iteration v convergence plot.

Complex simulations - I wrote a program that simulates a complex environment with many cross related factors. It was for a fixed timeline so you'd this the progress bar could just be the time right? In my case the simulation too longer with each new time step thereby meaning the progress bar gets slower and slower - not great. I found another metric for how long the average simulation takes based on the number of items in the simulation which was closer to accurate - but not ideal since sometimes the process bar never filled (simulation stopped before) or reach 100% to early (simulation ran longer than expected).

In either case a pure progress complete bar would either be impossible to calculate the maximum for beforehand (case 1) or none linear and hence not much use (case 2)
> 2 votes

# Answer
Both. Sometimes it's just difficult to estimate how much time an operation will take, because you don't know ahead how much work needs to be done. Sometimes its simplistic and inaccurate estimates.

Example: I'm downloading four files simultaneously. Someone knows how big each file is, how much has been downloaded, and how many megabytes per second were downloaded for each file. Seem easy to predict how long it will take. However, I know that after one file is downloaded, the others will download faster. Even more after 3 files are downloaded; the last one will download four times faster. Have never seen any progress bar taking this into account.

Example: You are copying a big folder. The progress bar assumes that you copy X megabytes per second, knows how many megabytes there are, and your average speed so far. Problem is, "megabytes per second" is very inaccurate - in practice, it takes x milliseconds per file, plus y milliseconds per megabyte. So lots of small files take much longer than the progress bar anticipates.

The problem is that software developers might care, but their managers don't as long as your computer doesn't crash.
> 3 votes

# Answer
I think the overarching answer is that it is often too complex (or impossible) to calculate the amount of time it will take.

Sometimes it would just be a matter of crunching more computing time to better estimate the amount of work required (for instance, taking a better analysis of the files to be copied, or applying a more complex calculation to better estimate the number of steps needed to complete a simulation).

Other times it's rather quite indeterminate. When your system is installing a new program, it often has many dependencies to check are installed. And generally it doesn't have an idea of how long each one will take, and what dependencies those may in turn need. You may have all the dependencies installed already and it could take 30 seconds, or you may be lacking dozens and it takes hours. Hard to give a fair ballpark on that, especially when each situation will be unique.

Additionally, other drains on the system may change over time (due to what the user does... or background/scheduled processes).

Sometimes the estimate could be improved if the programmer would put a little more work into them. But then it's another reality that this probably isn't most developers' top concern, compared to furthering the actual productive tasks the application can accomplish.

In the end, right now, I believe it's quite often just a linear estimate -- a look at how many of the required basic tasks has the program completed. So it indeed tends to be a very rough estimate, and you should generally consider it as such going in.

---

A good analogy might be when you're reading a book.
And you decide you'd like an idea of how long it will take to finish the book...
You could check the page count and get a quick estimate based upon the pace so far.
It might be a bad estimate if you just started reading, because your speed might not be typical yet. But often it'd be a fair rough guess.
Or you could also skim the book, get a rough idea of how many pictures there are and the text spacing. And then have a better idea of what you face.
But it still may be a poor estimate if, for example, the text readability decreases, perhaps transitioning from simple to complex prose. Or the estimate may wind up way wrong because you failed to anticipate another task that will divert your attention.
You could get a great estimate by applying a big chunk of time to carefully analyze what remains in the book page by page, and could likewise improve it by checking your calendar and keeping a list of long-term past reading paces for various books.
But in the end, is the time it takes to do so worth the delay on just getting the book read?

---

We'd all love better indicators. But as is, we're probably going to have to make due with rough estimates, at least until computers as a whole start getting improved standardized algorithms, and being adept at "intelligently" weighing and anticipating dynamic factors (such as your ways)!

And the progress bar on that is maybe stuck at 5% right now. We'll just have to see how that goes 8-)
> 3 votes

# Answer
I'd add to the answer of @gnasher729 that this is another hidden consequence of the undecidability of the halting problem.

Setting aside the inherent unpredictability of interactive computations, even those that can be isolated may have an execution time (and "rythm"), whose predictability cannot be approached by a general method.

Sadly, a progress bar is quite often a useless metaphor. What would be the alternatives, you might ask. If the user is aware of what is going on "under the hood", adding some semantic information to the interface can be an option, transitioning to a trace mode-like execution. If not, creating a calm atmosphere that reduces expectations.

Educating the user to understand our limitations is a - long term - third option.
> 1 votes

# Answer
Progress bars are drawn based on the number of subtasks completed rather than on the time elapsed/required for completion.

For example, suppose an operation X has four different sub steps, at the end of each step you increase the progress bar by 25%. If one step take longer to execute, you would likely see the behaviour you described - 1 to 90% in one go and hours for the rest.

The logic behind using number of subtasks as a unit rather than time is that the latter is unpredictable. Even in the case of downloading a file, the connection may drop, hence time cannot be used as a unit. You would rather use the amount of bytes downloaded and not the time required as a progress unit.
> 1 votes

---
Tags: computation-models
---


# Question
Title: Deriving epsilon with a context free grammar with epsilon rules
The below problem is from my Formal Languages class. The professor suggested drawing derivation trees for the language until we reach epsilon in all the leaves, and that it should begin to look like a geometric series. But I'm still having trouble getting started.

The way it was explained: if a context free grammar G contains epsilon rules and can reach epsilon, then show that it does so in N replacements, where N is \<= the sum of a geometric series. What's the proof for showing an implication like this?

# Answer
> 0 votes
Here's an example to get you started. Suppose our grammar had productions $$ S\rightarrow TT\qquad T\rightarrow UU\qquad U\rightarrow \epsilon $$ so $l=2, m=3$.

Then, how fast can you get from $S$ to $\epsilon$? Clearly, it'll take 7 steps: $$ S\Rightarrow TT\Rightarrow UUT\Rightarrow UUUU\Rightarrow UUU\Rightarrow UU\Rightarrow U\Rightarrow \epsilon $$ Notice that $(l^m-1)/(l-1)=(2^3-1)/(2-1)=7$.

What does the parse tree for this derivation look like? In particular, how many leaves will it have?

Now generalize this construction.

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


# Question
Title: What is the time complexity of binary sum (recursion)
Currently, I'm reading Data Structures and Algorithms in Java, 6 edition by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser link, particularly a chapter about recursions.

There is an example of algorithm which uses a recursion to calculate sum of all elements of the array:

```
public static int binarySum(int[ ] data, int low, int high) {
  if (low > high)  // zero elements in subarray
    return 0;
  else if (low == high) // one element in subarray
    return data[low];
  else {
    int mid = (low + high) / 2;
    return binarySum(data, low, mid) + binarySum(data, mid+1, high);
  }
}

```

It further says:

> the running time of binarySum is O(n), as there are 2n−1 method calls, each requiring constant time.

I don't understand why it is that the time complexity is O(n) and not O(logn). What am I missing here?

# Answer
> 3 votes
First of all, calculating the sum can't be better than $O(n)$ in the general case because you have to inspect all elements in order to determine the sum.

The function also does not halve the problem size every step: instead of choosing one subarray, as in binary search, we sum *both* subarrays. This does not save work at all.

We can determine the running time using the recurrence relation:

$$T(0) = T(1) = 1$$ $$T(n) = 2 \times T(n/2) + 1$$

Setting $k = log\_2(n)$ we can write this this as:

$$T'(0) = 1$$ $$T'(k) = 2 \times T'(k-1) + 1$$

Now we can use:

$$T'(n) = \sum\_{i = 1}^{k} 2^i \times 1$$ $$= 2^{k + 1} - 1 = 2 \times 2^{k} - 1$$ $$= 2 \times n - 1$$

---
Tags: algorithm-analysis, runtime-analysis, recursion
---


title: Meaning / proof of these regex

text:
# Question
Title: Meaning / proof of these regex
I came across following excerpts while reading about regular expressions identities:

> The regex associative laws are: $$(L+M)+N=L+(M+N)$$ $$(LM)N=L(MN)$$ Some important implications out of associative laws are: $$r(sr)^\*=(rs)^\*r$$ $$(rs+r)^\*r=r(sr+r)^\*$$ $$s(rs+s)^\*r=(sr+s)^\*sr$$ $$(LM)^\*N\*\neq L\*(MN)\*$$

The issue is that

* I don't find the implications much intuitive as the identities themselves are. How can I understand the implications intuitively? I can always form a strings belonging to left hand side regex and check whether it can be accepted by other regex. The first implication is very simple to test this way. However how can I make them more intuitive??
* Are these implications simply made up expressions which are tested rigorously to hold true and they don't have any specific expression as we can form many such expressions?
* I am unable to get the point behind stating these implications. I dont think of any problem in which I can use these regexes straight / immediately. It may be because I am not able to get intuition behind these implications so that it may strike in my head immediately when to use these implications.

# Answer
For all three of your statements, the answer is that, generally speaking, the implications simply aren't as intuitive as, say, the associative laws. Look at the analogous problem with algebraic expressions: we have associative laws for addition and multiplication and we also have a distributive law that states that for any expressions $p,q,r$ we have $$ p\cdot(q+r)=(p\cdot q)+(p\cdot r) $$ Eventually, these rules should be intuitively obvious. However, one implication of these rules, that $$ (p+q)^3=p^3+3p^2q+3pq^2+q^3 $$ is probably not as intuitively obvious as the rules used to derive that identity. The utility of the result above is that it can be used as a tool to simplify other more complicated problems.

It's the same for regular expressions: the fact that, say, $r(sr)^\*=(rs)^\*r$, is correct can be proven rigorously, but having done that you can use it as a tool to show that $$ aa+(aab)^\*aa=aa+aa(baa)^\*=aa(\epsilon+(baa)^\*) $$ should you ever need to. For example, there is a handy technique, involving what's known as *Arden's lemma* that can be used to produce a regular expression describing the language accepted by a finite automaton. Depending on how it's applied, this can produce several regular expressions from the same FA, so it might fall to you to show that the expressions are indeed equivalent, in which case the "implications" you listed might be handy.

The upshot (here's the **tl;dr** part), is that the implications you mentioned are simply tools you can use when needed: they've beed proven to hold, but there's no reason why they should be intuitively obvious.
> 4 votes

---
Tags: regular-expressions
---


# Question
Title: Language of a Turing Machine that runs its input on two other Turing Machines
Given two Turing Machines M1 and M2, we build a new machine M that does the following on input x:

1. Run M1 on x. If M1 accepts x, then go to an accept state.
2. Run M2 on x. If m2 accepts x, then go to an accept state.

What would be the language of such a Turing Machine? My first intuition was that $L(M)=L(M1) \cup L(M2)$ , but this can't be the case since if $x \notin L(M1)$ and $x \in L(M2)$, then there is the possibility that M1 runs forever, so M2 will never get the chance to recognize x and go to an accept state.

Unless we assume that M1 never runs forever, how is it possible to express $L(M)$? Thanks!

# Answer
You're right: it might happen that $M\_1$ might run forever on input $x$, so you'd never get to the "run $M\_2$ on $x$" part. This problem goes away if $M\_1$ and $M\_2$ were *deciders*, i.e., if they are guaranteed to halt on any input in either an accept state or a reject state. In that case we would have $L(M)=L(M\_1)\cup L(M\_2)$ and would have proven that decidable (aka recursive) languages are closed under union.

All is not lost, though, to show that this holds for more general languages. Suppose that we know that we have languages $L\_1,L\_2$ such that there are TMs $M\_1, M\_2$ with $L\_1=L(M\_1)$ and $L\_2=L(M\_2)$. Then we can make a TM $M$ such that $L(M) = L\_1\cup L\_2$ by a very useful technique known as *dovetailing*, like this

```
M(x) =
   repeat
      run M_1(x) for one move (beyond any that have been made already)
      if M_1 accepts
         return accept
      run M_2(x) for one move (ditto)
      if M_2 accepts
         return accept
   // end repeat

```

If either $M\_1$ or $M\_2$ accepts $x$ then it will do so in some finite number of moves, and that's all we need for $M$ to accept $x$. So for this machine, we'll have $L(M)=L(M\_1)\cup L(M\_2)$, exactly as needed.
> 1 votes

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


# Question
Title: If NP is the class of problems that cannot be solved in polynomial time, what is co-NP?
In my super non-rigorous class on optimization, the prof defined NP as the class of decision problems that cannot be solved in polynomial time. By definition, P is the class of decision problems that can be solved in polynomial time.

Then what is so called co-NP? Does co-NP = P in the sense of 'complement' of a set as used in set point topology?

Is there an intuitive way of explaining the meaning of co-NP in terms of problem that can be solved in \_________ time? And the intersection between NP and co-NP?

# Answer
> 12 votes
Your prof was absolutely not rigorous (i.e. completely wrong), that's why the distinction between NP and co-NP doesn't make sense with his definition. Better definition:

Def.: A decision problem (that is a problem where the result is either YES or NO and nothing else) is in NP if for every instance where the result is YES there exists a hint such that we can prove that the result is YES in polynomial time in the size of the problem by using the hint. (You will notice that there need not be a hint to prove the answer is NO, if the answer is indeed NO).

An example (not NP complete): If your decision problem is whether a number is composite (YES) or prime (NO), then for every composite number I can give you as a hint one non-trivial factor f. Then you can prove that the answer is YES by checking that the number is divisible by f.

Interestingly, when the number is prime, there isn't such a trivial hint that let's you prove the answer is NO. (There *are* hints, but nowhere near as simple).

And co-NP is defined almost the same, except there must be a hint if the answer is **NO**. For every problem X in NP, you can pose the problem Y: "Is the answer to problem X NO", and that problem Y would be in co-NP by definition.

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


# Question
Title: How is a Transition System in Operational Semantics defined?
I'm describing the semantics of a new optimization for Java using Operational Semantics but I'm not sure how to define the transition system.

I found this link :http://www.irisa.fr/celtique/teaching/PAS/opsem-2016.pdf where in slide 20 the transition system is defined but I don't get it.

# Answer
Operational semantics utilizes the tools of logic, so as a prerequisite we must understand judgements and inference rules.

A *judgement* is like a proposition, but more general. It asserts a relation between two entities of our language. For example, in programming, we often employ the judgement $e: \tau$, asserting that expression $e$ has type $\tau$.

*Inference rules* are used to define judgements. They have the general form

$$ \frac{J\_1 \dots J\_n}{J} $$

which reads: if we know judgements $J\_1$ through $J\_n$, we can infer judgement $J$. For example, we may have the following self-explanatory inference rule for the previously defined typing judgement:

$$ \frac{n: \text{int} \quad m: \text{int}}{n+m: \text{int}}. $$

A structural operational semantics is defined using a transition system between states. In a programing language, the states are all closed expression in the language, and the final states are values. Formally, we make use of two judgements:

1. $e\_1 \to e\_2$, stating that expression $e\_1$ transitions to state $e\_2$ in one step
2. $e \space \text{final}$, stating that expression $e$ is a final state of the system.

Here are some example inference rules in a language with arithmetic and function abstraction:

$$ \frac{}{n \text{ final}} $$ $$ \frac{}{n+0 \to n} $$ $$ \frac{n + m \to k}{s(n) + m \to s(k)} $$ $$ \frac{}{\lambda x. e \ \text{final}} $$ $$ \frac{(\lambda x. e\_1)e\_2}{\[e\_2/x\]e\_1} $$

Most languages do not have a formal definition, including Java (as far as I know). There are also other methods for defining the semantics of a language, but for describing an optimization, I believe structural dynamics is a wise choice, as it has a natural notion of time complexity (the number of transitions).
> 3 votes

---
Tags: formal-languages, operational-semantics
---


# Question
Title: Accounting method amortized analysis of a sequence of operations (CLRS 17.2-2)
I'm working through CLRS, Chapter 17 on Amortized Analysis. One of the problems I attempted to solve is 17.2-2 (described below), but my answer differs from the one in the instructor's manual, so I thought I'd solicit your feedback. I appreciate any help with this.

**Problem.** We have a data structure supporting some number of operations. Given a sequence of n such operations, we're to determine the amortized cost of each operation using the Accounting Method \[CLRS, 17.2\]. The actual cost of $i^{th}$ operation is defined as follows:

$$ cost(i) = \begin{cases} i & \text{if $i$ is an exact power of 2} \\\\[2ex\] 1 & \text{otherwise} \end{cases} $$

Assume that *exact powers* of 2 form the sequence: $1, 2, 4, 8, \ldots$.

**Solution.** (*My attempt*) For the sake of concreteness, consider a sequence of 10 operations:

$$ \begin{array}{c|ccc} i & cost(i) & notes\\ \hline 1 & 1 & 1 = 2^0\\ 2 & 2 & 2 = 2^1\\ 3 & 1 &\\ 4 & 4 & 4 = 2^2\\ 5 & 1 &\\ 6 & 1 &\\ 7 & 1 &\\ 8 & 8 & 8 = 2^3\\ 9 & 1 &\\ 10 & 1 &\\ \end{array} $$

The approach is predicated on the observation, based on this data, that between consecutive power of 2 operations (say, 1 and 2 or 2 and 4 or 4 and 8, etc.) there are exactly $i-1$ unit-cost operations. For example, if $i=1$, then between operations 1 and 2 there should be $1-1 = 0$ unit-cost operations and indeed there are none. Another example, consider $i=4$. We again verify that between 4 and 8 there are $4-1 = 3$ unit-time operations.

Based on that hypothesis, we assign the following "charges" ($\widehat{cost}$) to each of the operations:

$$ \widehat{cost}(i) = \begin{cases} i + (i - 1) & \text{if $i$ is an exact power of 2} \\\\[2ex\] \tag{$\alpha$} 0 & \text{otherwise} \end{cases} $$

The idea is that each power of 2 operation pays for itself (that's the $i$ summand) and leaves credit just enough to cover the $cost$ of the next $(i-1)$ unit-cost operations. Visually:

$$ \begin{array}{c|ccc} i & cost(i) & \widehat{cost(i)} & \text{"remaining credit"}\\ \hline 1 & 1 & 1 & 0\\ 2 & 2 & 3 & 1\\ 3 & 1 & 0 & 0\\ 4 & 4 & 7 & 3\\ 5 & 1 & 0 & 2\\ 6 & 1 & 0 & 1\\ 7 & 1 & 0 & 0\\ 8 & 8 & 15 & 7\\ 9 & 1 & 0 & 6\\ 10 & 1 & 0 & 5\\ \end{array} $$

At the end of the sequence, we're left with 5 units of credit, which will pay the price of the next 5 unit-cost operations ($i = 11, \ldots, 15$).

The amortized cost of a given operation is $i + (i - 1)$, which is bounded by $2n$. The book has a $3n$ in the analysis, so I'm wondering where I'm messing up.

# Answer
> 1 votes
An amortized cost is just the average cost of a sequence of $n$ operations (in the worst cases). If I remember correctly, its definition is defined as

$$ \hat c(n) \sim \frac{\sum\limits\_kc(k)}{n} $$

Now, $$ \hat c(n) = \begin{cases} 2n - 1 & \text{if $n$ is a power of 2} \\ 0 & \text{otherwise} \end{cases} $$ obviously fits that description. In the same vein, so does $$ \hat c(n)\_{\text{alt}} = \begin{cases} n & \text{if $n$ is a power of 2} \\ 1 & \text{otherwise} \end{cases} $$ which is just our original cost function ;)

In fact, many such cost functions exist. However, none of them clearly spells out a tight bound on the cost of any arbitrary instruction.

For example, to say that $\hat c(n) \sim 2n$ is to say that the total cost of $n$ operations is approximately $\sum\_k^n 2k = 1 \times n^2$. On the other hand, the true total cost of $n$ operations is \begin{align\*} \sum\_k c(k) &= n + (2^0 - 1) + (2^1 - 1) + \dots + (2^{\lfloor\log\_2(n)\rfloor} - 1) \\ &= n + 2^{\lfloor \log\_2(n) \rfloor + 1} - 1 - (\lfloor\log\_2(n)\rfloor + 1) \\ &\le n + 2n - \log\_2(n) - 2 \\ &\le 3n \end{align\*}

This means that a good "amortization" technique here would give an amortized cost of $\hat c(n) = 3$ *for any arbitrary $n$*.

Now, why is $\hat c(n) = 3$ more "elucidating" than $\hat c(n) = \text{n is a power of 2} ~?~ 2n - 1 ~:~ 0$? Well, because it gives a uniform amortized value **for every $n$**. This then forms the (unspoken) cardinal rule of amortized runtime analysis:

> Good amortized cost functions are *not* piecewise.

Why? If $\hat c(n) = \square$ uniformly, then we can easily say that each and every operation is bounded by the same $\square$.

Now, I can definitely hear some readers protest: "but I see case analyses in CLRS itself!" Do you? Well, for algorithms with multiple operations (say PUSH, POP, and MULTIPOP), then we need to give a cost function for each individual operation. However, the amortized cost function given for each operation is "continuous"!

Fret not, this is a pretty common problem. I haven't gone through CLRS myself, but I've stumbled upon these confusions as well when I first went through this technique.

We've already seen that $\hat c(n) = 3$ provides a valid bound, but it doesn't really give us any intuition about the problem (beyond pushing around some inequalities). Why 3? How do we get to that answer without working with (or around) arithmetic and geometric series?

There are good news and bad news. Bad news first: the most general framework you have here is the vague phrase that you already know; just figure out how much you have to pay upfront so you can cover the up to the next "big shock." While this might not seem like very much to work with, it does give us some general intuitions: the important aspect of the problem is not only the magnitude of these shocks (heh), but also their **location**.

In our case, we know that the location of these shocks are logarithmically distributed, which means that most of the time, you just incur a cost of one. However, these shocks are also pretty big, so you'll need to pay enough up-front to cover for them. In particular, after $2^k$ operations, you'll have to pay at least $2^k - 1$ operations and a further $2^k$ operations. This immediately suggests that $2^{k} + 2^{k} - 1 \le \hat c(2^k)$. Following a similar argument, we also have $\hat c(2^k) \le 2^{k} - k + k \times 2^k$. This refines our bound to $2n -1 \le \hat c(n) \le \lfloor \log\_2 n + 1\rfloor n - \lfloor \log\_2 n\rfloor$. After this, you can keep refining this bound until you get something as tight as possible. Unfortunately, there's really no way to do this unless you stumble onto the geometric series and realize that $\sum\_k^n 2^k = 2^{n+1} - 1$, but at least this should give you a way to make gradual progress in your analysis.

Good luck!

---
Tags: algorithms, amortized-analysis
---


title: Application of a directed almost tree

text:
# Question
Title: Application of a directed almost tree
Is there anything interesting to say about an "almost BST" with directed edges? Is there a domain where this structure naturally arises? I'm imagining a tree like the one below, but it would of course be more interesting if the tree were deeper with just a few of these strange edges.

I found this article on circuit rank which uses the term "almost tree", but it talks about circuits in undirected and directed graphs. What I'm describing is not a cycle.

# Answer
> 4 votes
What you are looking for are directed acyclic graphs (DAGs). If you want your DAG to have a unique "root", then you can ask for a DAG with a single *source*. DAGs are very useful in many branches of computer science.

---
Tags: graphs, terminology, binary-trees
---


# Question
Title: Is my implementation of genetic algorithm correct?
In genetic algorithms, we have a function called "mutation". Before we call this function, we choose parents.
In my version of the algorithm, when i mutate the child, i don't change the bits which are the same as the given input.
By that, I mean : Imagine we want to reach the string "ABCDE".
The algorithm first generates 5 strings randomly :
"ADDDE", "ABDIO", "MSDKO" , "POIUU" , "QWERT"
The fitness function says that the first two strings, have better quality to survive. So, we select them.
So we have "ADDDE","ABDIO" as parents.
Then we choose a random number between 0 & 4. Assume that 1 is chosen.
We take "AD" from the first string and "DIO" from the second one.
The child we made is : "ADDIO"

Now, The part which makes me confused :
When i mutate this child, I say "A" is in the same place of "ADDIO" as "ABCDE". So, I don't change "A". I mutate the other characters . For example i make "AQWERT","ARTYUI" , ...

Is this correct? Any idea? Any improvement ?

# Answer
No, that does not make sense.

What you have there is a toy example. In any application, the algorithm will *not* know the goal -- otherwise you wouldn't need it! That is, you don't have any way of known whether a mutation is benefitial before executing it.

What's more, mutating *away* from the optimum is an essential part of the algorithm, and can be shown to be necessary for it to work well (otherwise you get stuck in local optima more easily).
> 1 votes

---
Tags: algorithms, optimization, genetic-algorithms
---


# Question
Title: Algorithmic Complexity of Statistical Estimators
This might be very basic but I am interested in evaluating the algorithmic complexity of an estimator of the form:

$$\hat{\theta} = \text{argmin}\_{\theta} \\;\\; Q\_n (\theta)$$

where $Q\_n(\theta)$ denotes some objective function of interest (e.g. - log likelihood) computed on a sample of length $n$. $\hat{\theta}$ is assumed to be obtain through some numerical optimization methods (typically a stepwise procedure). Under this setting, how could I compute the algorithmic complexity of $\hat{\theta}$?

I am really not sure if this makes sense but here is how I approach this problem:

* Suppose that the numerical procedure used to compute $\hat{\theta}$ requires $S$ steps to converge.
* Assume that there exist a deterministic function, say $f(p)$, where $p$ denotes the dimension of $\theta$ such that $S \leq f(p)$ and that $f(p) \< \infty$ for $p \< \infty$.
* Assume that $\mathcal{O} (Q\_n(\theta)) = g(n)$ for all $\theta$.
* Then $\mathcal{O}(\hat{\theta})$ is simply given by

$$\mathcal{O}(\hat{\theta}) = \mathcal{O}(Q\_n(\theta) S) = g(n),$$

since $p$ is assume to be fixed (and bounded). This seems really too simple... Any comments would be more than welcome. Thank you very much.

# Answer
> 1 votes
The bound $O(Q\_n(θ) \cdot S(p))$ represents only the cost of evaluating $Q\_n$ once per step in the "numerical optimization method"; you ignore all other cost that incurs.

Without looking at the whole algorithm, little more can be done.

*Note:* I very deliberately replaced $S$ with $S(p)$. That is because there is no reason, per se, to believe that $S$ is a constant. You need to be more careful about setting up your cost functions; our reference question may be helpful.

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


# Question
Title: Intersection of functions given asymptotic relationship
If $f(n) = O(g(n))$ and $g(n) \neq O(f(n))$ than can we say that $f(n)$ and $g(n)$ will never intersect?

# Answer
The asymptotic behavior of a function only depends on its value on "large" inputs. More formally, let $f$ be an arbitrary function, and let $f'$ be obtained by changing finitely many values of $f'$. Then for every function $g$, $f = O(g)$ iff $f' = O(g)$.

I believe that you can now answer your own question.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Given a Turing Machine M and a string $x$ how do we tell whether a the Turing Machine M loops on the string $x$
Let us say there is a Turing Machine $M$ and a string $x$. So now I want to know if $M$ accepts or rejects the string or loops on it. So, I feed the string to $M$. So, if $M$ is accept or reject the string it would halt after a finite time and I would get my answer. But how do I know if the machine loops on the string or not.

One possible way is to see if a configuration repeats itself. However, the machine has no way of knowing if the configuration has occurred before because it cannot store them . So, we would never get an answer. So, how will I be able to tell whether or not $x$ is accpted or rejected or looped upon by $M$.

# Answer
> 3 votes
Halting problem is generally unsolvable. The states don't have to repeat. But if you know that they will, see cycle detection.

---
Tags: computability, turing-machines, halting-problem
---


title: Types as first class Citizen

text:
# Question
Title: Types as first class Citizen
Coming from a C++ background I don't understand why one needs types / type expressions as first class citizen? The only language I know that supports this feature is Aldor.

Does anybody have some literature about types as first class citizen or know some reasons why it's useful?

# Answer
> 11 votes
First class types enable something called *dependent typing*. These allow the programmer to use values of types at type level. For example, the type of all pairs of integers is a regular type, while the pair of all integers with the left number smaller than the right number is a dependent type. The standard introductory example of this is length encoded lists (typically called `Vector` in Haskell/Idris). The following pseudo-code is a mixture of Idris and Haskell.

```
-- a natural number
data Nat = Zero | Successor Nat

data Vector length typ where
  Empty : Vector Zero typ
  (::)   : typ -> Vector length typ -> Vector (Successor length) typ

```

This piece of code tells us two things:

* The empty list has length zero.
* `cons`ing an element onto a list creates a list of length `n + 1`

This looks very similar to another concept with 0 and `n + 1`, doesn't it? I'll come back to that.

What do we gain from this? We can now determine additional properties of the functions we use. For example: An important property of `append` is that the length of the resulting list is the sum of the lengths of the two argument lists:

```
plus : Nat -> Nat -> Nat
plus          Zero n = n
plus (Successor m) n = Successor (plus m n)

append : Vector n a -> Vector m a -> Vector (plus n m) a
append Empty  ys = ys
append (x::xs) ys = x :: append xs ys

```

But all in all this technique does not seem all to useful in everyday programming. How does this relate to sockets, `POST`/`GET` requests and so on?

Well it doesn't (at least not without considerable effort). But it can help us in other ways:

Dependent types allow us to formulate invariants in code - rules as how a function must behave. Using these we get additional safety about the code's behaviour, similar to Eiffel's pre- and postconditions. This is extremely useful for automated theorem proving, which is one of the possible uses for Idris.

Coming back to the example above, the definition of length-encoded lists resembles the mathematical concept of *induction*. In Idris, you can actually formulate the concept of induction on such a list as follows:

```
              -- If you can supply the following:
list_induction : (Property : Vector len typ -> Type) -> -- a property to show
                  (Property Empty) -> -- the base case
                  ((w : a) -> (v : Vector n a) ->
                      Property v -> Property (w :: v)) -> -- the inductive step
                  (u : Vector m b) -> -- an arbitrary vector
                  Property u -- the property holds for all vectors

```

This technique is limited to constructive proofs, but is nonetheless very powerful. You can try to write `append` inductively as an exercise.

Of course, dependent types are just one use of first class types, but it's arguably one of the most common ones. Additional uses include, for example, returning a specific type from a function based on its arguments.

```
type_func : Vector n a -> Type
type_func Empty = Nat
type_func v     = Vector (Successor Zero) Nat

f : (v : Vector n a) -> type_func v
f Empty = 0
f vs    = length vs :: Empty

```

This is a nonsensical example, but it demonstrates something you cannot emulate without first class types.

---
Tags: programming-languages, language-design, types
---


# Question
Title: Is a language of some deciders decidable?
Is

$$L = \\{ \langle M \rangle \mid M = (\\{Q\_1, Q\_2, . . . , Q\_{100}\\}, \\{0, 1\\}, \\{0, 1, \\\_\\}, δ, Q\_1, Q\_2, Q\_3) \text{ is a decider}\\}$$

decidable?

I know

$$HALT\_{TM}= \\{ \langle M \rangle \mid M \text{ is a decider}\\}$$

is not decidable, but in the case we are given a specific Turing Machine that has 100 states, alphabet $\\{0,1\\}$, tape alphabet $\\{0, 1, \\\_\\}$ (where _ is space), a transition function $\delta$, a start state $Q\_1$, an accept state $Q\_2$ and a reject state $Q\_3$.

Checking that M is in the correct format is easy but is it possible to build a Turing Machine that decides $L$? I assume I can use the fact that $HALT\_{TM}$ is undecidable to show that $L$ also is, but I am not sure how to proceed.

And I don't see how I could reduce $L$ to $A\_{TM}$ to prove by contradiction that it is not decidable?

How should I proceed?

# Answer
> 3 votes
I don't fully understand the details of your question (especially the notation that you've used).

However, the language you're asking about appears to be finite (something like the language of descriptions of all Turing machines that halt for all inputs and have at most 100 states), and every finite language is decidable. You could, in principle, produce a list of all the strings in your language, and then just design a Turing machine that accepts exactly that list of strings.

Note also that reducing $L$ *to* the halting problem wouldn't prove that $L$ is undecidable, since every recursively enumerable language reduces to the halting problem. You'd just be showing "If I could solve the halting problem, I could solve $L$, too." That's a bit like saying, "If I was the world's strongest man, I could lift an apple." Maybe you don't need to be so strong to do such a simple thing? If you want to prove that $L$ is undecidable by reductions, you need to reduce an undecidable language *to* $L$: then, you're saying, "If I could decide $L$, I'd be able to decide this undecidable language, and I know I can't do that."

---
Tags: formal-languages, turing-machines, reductions, undecidability, halting-problem
---


# Question
Title: Interesting problems that can be solved with algorithms
I need to write a blog post on a problem that can be solved algorithmically. I need to do two things:

1) I need to decide what the naive brute force method would be and touch on it's time and Space complexities.

2) I need to come up with a more elegant/ideal method to solve the problem, then discuss tradeoffs with the ideal method's time and space big O

Does anyone have ideas for an interesting topic I can cover? I'm not looking for the answers, just the topic to cover

Here is an example of something I could write about: https://medium.com/@hannahsquier/two-algorithms-for-solving-vigneres-cipher-in-ruby-77bf0b37507a#.go43z5vas

# Answer
Depending on the level of sophistication of your intended audience, a simple canonical example is testing whether an input number $n$ is prime.

A brute force approach is to test, for all $d$ in the range $2,\dotsc n-1$ whether $d$ divides $n$. If you find a $d$ that divides $n$ you can stop and assert that $n$ isn't prime; if you don't find any such $d$, you can assert that $n$ is prime. That'll take about $n$ divisions if $n$ is prime.

An improvement is to try just those $d\le\sqrt{n}$ (rounding up), since it's easy to see that if $n$ has any divisors, there must be one in that range. This is a big improvement, since it reduces the number of divisions from $n$ to $\sqrt{n}$, more or less.

If you want to expand this, there are even faster ways to test for primality and if your audience is sophisticated enough, you might want to try one or more of them.
> 1 votes

---
Tags: algorithm-analysis
---