# Question
Title: Store and sort a large number of 64-bit integers
I have about $500000000$, $64$-bit integers, so these numbers are very large. I want to sort them as quickly as possible. I have couple of questions:

1. What data structure do you suggest for storing this data?
2. What algorithm do you suggest for sorting these numbers?

I'm concerned about speed.

# Answer
You're not going to get much in the way of programming tips here, this is a site for computer science, not programming.

For the sorting algorithm, you probably want to use Radix Sort, which will run in time $O(k n)$, for you $k = 64$ and $n = 500 000 000$.

For the storing of these numbers, you might want to look into compressed data structures. However, these are necessarily going to bring some overhead. You're looking at approximately 4GB of memory, which is reasonable on many modern machines. As you will learn in computer science, there is often a tradeoff between time and space. Here, you must choose between a fast data structure and a space-efficient data structure.

EDIT: I change the time complexity to $O(kn)$, I'd mistyped and originally written $O(k\log n)$. Sadly, it's impossible to sort a list without actually looking at the entire contents of the list.
> 5 votes

# Answer
Parallel processing is your solution, and GPU would do that. Since you have a large chunk of data (4GB) to be sorted, GPU would definitely outperform CPU's execution time.

See http://www.nvidia.com/docs/IO/67073/nvr-2008-001.pdf for details of an efficient parallel GPU sort.
> 1 votes

# Answer
With some work on your part, you might be able to use an *O(n)* method. That's where you have a big hash table, and the hash function is one that preserves order, such as just grabbing the first *k* bits.

If the distribution of numbers is highly non-uniform, it could be important to first get a rough empirical distribution, by sampling a subset of numbers from the set and sorting them. Then you use an interpolated inverse of the distribution function to assign each number to a cell.

Then you sort the contents of each cell, which should not take too long if there are enough cells that each one does not contain too many numbers.

Finally you just read it all out sequentially.

Complicated? Yes. Fast? Yes.
> 1 votes

---
Tags: algorithms, algorithm-analysis, data-structures, time-complexity, sorting
---


title: Visualize Graph Clusters

text:
# Question
Title: Visualize Graph Clusters
I am working on my thesis which involves using ant based techniques for graph clustering. I am testing the algorithm currently and I was wondering if there is a way that I can visualize the clusters of a given graph.

In this case, I have the graph as a file and another file corresponding to the clustering where each node is given its cluster. Is there a software using which I can visualize this graph where nodes belonging to the same cluster have like the same color or something?

The graph is represented as an edge list, or in the ".net" format or Graph Modelling Language ".gml" format. I know there are a lot of programs out there for networks such as gephi, graphviz, networkx, pajek etc but I don't know how to do this. Any help/ideas would be greatly appreciated!

Thanks!

# Answer
> 4 votes
You could use `graphviz`. Its input format allows you to specify the color for each vertex. You could write a simple script to take the specification of the graph and the clustering, and output a `.dot` file that lists the vertices and edges and specifies an appropriate color for each vertex (based upon your clustering).

# Answer
> 0 votes
I have implemented clustered circular graph layout algorithm for Graph drawing purpose. For this i have used boost graph library(specially subgraph concept). Boost subgraph is a best solution for anyone to go for graph lay outing problem, it has provided very efficient results to me. Only problem is to study boost library which has very less documentation or may be its very difficult to understand and given in very abstract way. You can try reading following paper for start with layout algorithm as http://ijettcs.org/Volume3Issue2/IJETTCS-2014-04-20-099.pdf

---
Tags: graphs, cluster
---


# Question
Title: Why is it necessary to use binary numbers in logspace?
I have noticed that a lot of problems that are in L and NL use binary numbers. I don't understand why this is the case. Does a TM use less space by storing a binary number, than a "normal" one. In my head, it uses less space to store the number 0, than the binary ecquivalent number 0000. Hope someone can help me understand :)

# Answer
The "usual" encoding of numbers is binary. Binary can mean two things:

1. Encoding a number in the range $0,\ldots,2^n - 1$ using $n$ bits.
2. Encoding an arbitrary natural number.

In the latter case, the "width" or "length" of the number is not known in advance, and so some special encoding has to be used. An especially simple one encodes a number $b\_0 \ldots b\_{n-1}$ as $$ 1b\_0 1b\_1 \ldots 1b\_{n-1} 0. $$ This is known as a *self-delimiting* encoding. If you allow the input alphabet to be larger, then you can use a non-binary character as a separator instead, which is a popular convention.

We are more used to decimal numbers rather than binary numbers. In terms of encoding length, the two differ by a multiplicative constant, so binary encoding and decimal encoding are equivalent for most purposes. Binary encoding is used since sometimes we imagine the input encoded as a string over $\\{0,1\\}$ (this is the case when we talk about circuits, for example).

The other option is *unary encoding*, in which the number $n$ is encoded by $1^n 0$ (that is, $n$ times the bit 1 followed by the bit 0).

Encoding $n$ takes $n+1$ bits in unary, but only $\Theta(\log n)$ bits in binary. This can make a huge difference in complexity theory, since the running time is measured in the size of the input. For many problems, however, the number parameters pale in length compared to other inputs (say an input graph), and so the exact encoding used is not important.

Here is an example in which encoding is important. Many cryptographic algorithms include a subroutine that accepts $n$ and outputs a key of length $n$. If the input is encoded in binary then its length is $\Theta(\log n)$, and so the subroutine must run in exponential time (since the output is of length $n$). If the input is encoded in unary then there is no such restriction. This is why in such algorithms, $n$ must be encoded in unary.

In other cases, encoding an input parameter in unary might make the problem too easy, and so it is important to encode it succinctly. Unfortunately, I can't think of any such problem right now, since as stated before, usually the number parameters are dwarfed in length by other inputs.
> 3 votes

---
Tags: space-complexity
---


# Question
Title: Decomposing a bipartite graph of maximal degree d to d matchings
I have tried for the last few days to prove that any bipartite graph of maximal degree d may be broken into (at most) d matchings.

My main approach is to prove this inductively over the maximal degree d. This would require me to show that there must exist a matching which contains an edge for every one of the maximal degree nodes. (Such that the removal of this matching will leave me with a bipartite graph of maximal degree d, for which my inductive claim holds)

What I do know is to find a maximum matching (Via either some max-flow algorithm, or using the augmenting paths method, and arriving to the Gallai-Edmonds decomposition of the graph), but can't augment it to a maximum matching in which all maximal degree nodes are necessarily matched.

I was not able to prove it nor find a counter example for this subclaim, and would appreciate help. Thanks

# Answer
> 3 votes
Possible approach: If a bipartite graph is $d$-regular then it can be decomposed into $d$ perfect matchings by Hall's theorem. Any bipartite graph of maximal degree $d$ can be completed to a $d$-regular bipartite graph (possibly by adding vertices).

---
Tags: bipartite-matching
---


title: Steiner tree four points example

text:
# Question
Title: Steiner tree four points example
I have been looking at the wikipedia page for steiner trees, and I don't quite understand their 4-point solution. If the four vertices are arranged in a rectangle shape wouldn't there be only one steiner vertex required in the middle to create the shortest length graph? The solution shows two vertices S1 and S2, but it seems that it would be shorter if there was only one vertex S instead, in between S1 and S2 and all of the vertices A, B, C, and D connect to S.

# Answer
You are asking the question for Euclidean Steiner Trees. For Euclidean Steiner Tree problem one can show that "points added to the graph (Steiner points) must have a degree of three, and the three edges incident to such a point must form three 120 degree angles". That's why you need two steiner vertices instead of just one for 4 point solution. If you take just one extra point the degree will be 4 and angles also will not remain 120 degree.

To prove the property of Euclidean Steiner Trees take help of your favorite search engine. A good reference. See section 3.
> 2 votes

# Answer
Honestly, a ruler should be enough to convince you for this one case, though the difference may be quite small.

For the general 4-corners-of-a-tall-rectangle case, I suggest formulating an expression that computes the total distance of a 2-point Steiner tree in which the 4 points are the corners of a w by h rectangle, with w \< h, and the two Steiner points are located x units either side of the vertical centre (and, of course, at the horizontal centre). Plug in x = 0 (your single-point solution -- i.e. a single point is the same as 2 overlapping points), and plug in x = h/2 - sqrt(1/3)\*w/2 (the displacement for the optimal 2-point solution), and compare them. Even better, differentiate w.r.t. x and verify that the curve is 0 for the latter point.
> 2 votes

# Answer
It seemed that using one steiner point at the center would be shorter because of the triangle property but the mistake I was making was double-counting the middle segment S1S2 in calculating the length of the graph which led me to believe that it was longer than it actually was. This was my (faulty) logic:

> suppose P was the center point of the rectangle ABCD. Consider the triangle formed by A, P, and S1, the length of AP is shorter than AS1 \+ S1P by the triangle property. I can make the same argument for each of the 4 corners to show that (AP + PD + BP + PC) \< (AS1 + BS1 + S1S2 \+ S2C + S2D). In other words, using one steiner point P is shorter than using two different points S1 and S2.

Although it's true that AP is shorter than AS1 + S1P, using this argument on all 4 corners, I implicitly counted the middle segment more than once.
> 1 votes

---
Tags: algorithms
---


title: CNF H is in the class P

text:
# Question
Title: CNF H is in the class P
```
CNF H = {<ø>|ø is a satisfiable cnf-formula where each clause contains any number of
literals, but at most one negated literal}

```

I want to show that CNF H is in P, but I'm having some trouble finding an algorithm. My first idea was to check for each clause c in P if that clause contained at most one negated literal. If no clause contains more than one negated literal, accept, if not, reject.

The problem with this idea is if there is a clause with only one literal, and this literal is negated. Than the clause would be false, and therefore ø is false. How do I write an algorithm that also covers this case?

# Answer
I have come up with a polynomial-time algorithm for this language that I think is in P.

Possible algorithm (-x means not x).

```
M = "on input <ø> where ø is a boolean formula in CNF:
1. Repeat until there are no (-x) unit clauses:
   For a unit clause (-x), remove all the clauses containing -x from ø
     and remove all occurrences of x from the clauses in ø
2. If there is an empty clause in ø, reject.
3. Let all literals x in ø be 1, -x 0, and accept.

```
> 1 votes

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


# Question
Title: Given a graph, finding if a node has three adjacents from a node subset $N$
Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \\{n\_1, n\_2 ...\\} \subset V$ and $P = \\{p\_1, p\_2, ...\\} \subset V$ such that $N \bigcup P \neq V$.

I want to find if there exists an edge subset such that $\\{\<n\_i,p\_l\>, \<n\_j,p\_l\>, \<n\_k, p\_l\>\\}$ i.e. three nodes from $N$ and one node frpm $P$.

Should I first list the triplets of $N$ and search if they have a common adjacent in $P$ or for each $p \in P$, check if $p$ has three adjacents in $N$?

Which method would be more efficient? Or does it depend on the sizes of the sets?

**Edit:** What if I want to list all the edge subsets for all $p\_l$?

# Answer
> 2 votes
To find such triples of edges, partition the adjacency list $L\_i$ of each node $p\_i$ in $P$ into three sets: $P\_i$, the set of neighbors in $P$, $N\_i$, the set of neighbors in $N$, and $Q\_i$, the set of neighbors in $V \setminus (N \cup P)$. If each vertex is labeled with which set it belongs to, then the partitioning can be accomplished in linear time. Then, for each $p\_i$, check if $P\_i$ contains at least 3 vertices. If so, then you have an edge subset that meets your requirements.

If you want to generate all possible edge subsets of the outgoing edges in each node, you would be generating the *powerset* of the neighbors of $p\_i$. If a vertex has $n$ neighbors, the size of the powerset will be $2^n$. This strategy is impractical for all but the smallest input graphs.

If you only want to list the edge subsets from each $p\_i$ that meet your requirements, the number of subsets for a vertex with $n$ neighbors in $V$ will be ${n \choose 3}$, but the algorithm to enumerate them should not be complicated.

# Answer
> 0 votes
If you can find a single node in $V$ of degree $3$, you know that there exists the $N$ and $P$ for the edge subset you are looking for.

Finding every possible combination of triplets is slower than $O(n)$.

However checking the degree of each node in $V$ is $O(n)$.

So which is more efficient?

---
Tags: algorithms, graphs, search-problem
---


# Question
Title: Does spectral graph theory say anything about graph isomorphism
Is there research or are there results that discuss graph isomorphism in the context of spectral graph theory?

Two known theorems of spectral graph theory are:

1. Two graphs are called isospectral or cospectral if the adjacency matrices of the graphs have equal multisets of eigenvalues.
2. Almost all trees are cospectral.
3. The eigenvalues of a graph's adjacency matrix are invariant under relabeling (but this is not a necessary and sufficient condition).

Furthermore, is graph isomorphism "easy" to solve?

# Answer
> 10 votes
Graph isomorphism has been mentioned along with primality testing as early as 1971 in Cook's famous paper on NP-completeness. Cook mentions that he was unable to prove the NP-completeness of both problems. Nowadays we known that primality testing is in P, but the status of graph isomorphism is still unknown. Most experts conjecture that it is "NP-intermediate", that is, not in P but not NP-complete. Some conjecture that it should be solvable in quasipolynomial time (algorithms running in time $2^{\log^{O(1)} n}$). The best currently known algorithm, due to Luks, has running time $2^{O(\sqrt{n\log n})}$. It uses the so-called group theory method.

The two most common approaches are individualization/refinement and the group theory method. The former approach tries to match vertices of one graph to vertices of the other. Given a vertex of degree $d$ belonging to the first graph, it can only be matches to a vertex of degree $d$ in the other graph, but this offers no saving if both graphs are $d$-regular. Individualization/refinement is a framework for generating more detailed "types" of vertices.

It is possible that a similar approach can enhance the spectral method (which as stated fails for cospectral graphs), but I am not aware of any work along these lines (though it might exist; I'm not an expert in this area).

The group theory method reduces graph isomorphism to the problem of finding generators for the automorphism groups of graphs. Given two graphs $G\_1,G\_2$, the idea is to compute generators for $\operatorname{Aut}(G\_1 \cup G\_2)$, and check whether any of them switches a vertex of $G\_1$ with a vertex of $G\_2$. For more details, see for example lecture notes of Arvind.

For a recent overview of the state of the art, consult a paper by Babai; Babai is one of the principle researchers in the area.

*Practical* graph isomorphism is a completely different issue. A recent overview can be found in a paper of McKay, author of the popular package `nauty`.

---
Tags: graphs, linear-algebra
---


title: How to prove that problem is not in P

text:
# Question
Title: How to prove that problem is not in P
Given some abstract problem how can I prove that this problem is not in `P`. I mean, what is the method for proving such thesis?

# Answer
> 15 votes
The most common technique is to prove that the problem is hard for some class. For example, consider the problem HALT in which we are given a Turing machine $T$ and a number $n$ (encoded in binary, i.e., in the usual way), and the task is to decide whether $T$ halts within $n$ steps. HALT is EXPTIME-hard. If HALT were in P then P=EXPTIME (using the EXPTIME-hardness of HALT), which contradicts the time hierarchy theorem. We conclude that HALT is not in P.

Consider now a different problem, REGEXP-INT, in which given a list of regular expressions, we have to decide whether their intersection is empty. This problem is coPSPACE-hard, and so if it were in P, then P=PSPACE. While we don't know for sure that P is different from PSPACE, this is widely conjectured (and follows from P$\neq$NP), and assuming that, we conclude that REGEXP-INT is not in P. We call this a *conditional result*. Similarly, SAT is NP-hard, and so unless P=NP, SAT is not in P.

The unconditional results invariably use one of the hierarchy theorems, and so eventually, diagonalization. This technique itself cannot separate P from NP, due to the so-called "relativization" barrier (though non-black-box diagonalization still stands a chance).

# Answer
> 5 votes
Showing a lower bound on a problem is much harder than showing an upper bound. For an *upper bound* you simply must show an example algorithm of that complexity (a *witness*). Conversely, for the lower bound you have show that *for all* solutions each takes at least $\Omega(f(N))$ steps where $f(N)$ is some super-polynomial function. One simple case is where the output is exponential in the input.

* The Towers of Hanoi is an example problem where one can prove a lower bound (of exponential time) in any solution. The gist of the proof is to show that *any algorithm* must generate each of the $\Omega(2^N)$ positions.

Another example (but one in $P$).

# Answer
> 5 votes
The generally easiest solution for this kind of thing is to assume that you can do it, and show that it contradicts a well-established result.

The easiest case will be when you can show that the problem is undecidable -- not in P, not in NP, not guaranteed to halt, ever. Those solutions typically read like:

> "Suppose, for contradiction, that there exists an algorithm for the Foo problem. I will show you that if I was able to solve the Foo problem at all, then I would be able to decide if any arbitrary program halted, since I can somehow reduce the question of "Does algorithm Bar halt on input $s$?" to an instance of the Foo problem. The halting problem is undecidable, a contradiction. Hence no such algorithm exists, in particular, no algorithm in P."

Your next best bet would be to show that it would give you a polynomial time solution to something in EXPTIME, and P $\subsetneq$ EXPTIME. That would look like this:

> "Suppose, for contradiction, that there exists an $O(n^c)$-time algorithm for the Foo problem, where $c$ is a constant. I will show you that, in no more than polynomial time, I can reduce some existing problem known to be in EXPTIME but not in P to an instance of the Foo problem, a contradiction. Hence no such algorithm exists."

Anything other than that is hard. We haven't proved very many results about the limits of P.

# Answer
> 1 votes
of course the big open question is P=?NP as commenters have noticed but you dont specifically mention NP. what neophytes not realize is that there are many problems proven outside of P, its just than none are NP-complete. it is possible to prove a problem takes more than P time ie is "not in P" if it takes eg ExpTime. the simplest way to prove a problem requires ExpTime is to prove it requires ExpSpace. this has been done with a sophisticated problem involving regular languages:

the proof involves showing that any TM that computes a language using Expspace can be computed by the above problem/formulation. so proving that any problem reduces to this ExpSpace complete problem in the above paper is sufficient.

---
Tags: complexity-theory, proof-techniques, polynomial-time
---


# Question
Title: What is the simplest way to understand Turing machines and the busy beaver problem?
The Wikipedia description has way too much math.

# Answer
From quora.com:

> A Turing machine is a computer (PC, Mac, iPhone or Conway's Game of Life - pick whichever is most familiar) with unlimited storage (memory, hard disk, doesn't matter). Assume you can program the computer in some programming language, and that you're interested in what it can and cannot compute. "Compute" means "read some input, do stuff, write some output".
>
> This is not the usual description of a Turing machine, of course, but for the study of computability - which is mostly what Turing machines are good for - it's completely equivalent.
>
> The Busy Beaver problem is this: suppose I challenge you to write a computer program (again, pick your favorite programming language) whose sole purpose in life is to print a long string of dots and then stop. If the length of your program is limited to k characters, how long of a string can you make?
>
> It should be clear that this question has an answer, for any choice of programming language and any given limit k. After all, there are only finitely many possible computer programs of length, say, 10,000 characters in, say, C++; some of them print finite strings of dots, and of all the ones that do, we can pick the one (or ones) that print the absolutely longest string.
>
> If you happen to know something about programming, it should also be clear that as soon as k becomes reasonably large to accommodate some non-trivial programs, the answer will be incredibly humungous. It's quite easy, for example, to write a computer program that prints 100^{100} dots and then stops, and in most reasonable programming languages this shouldn't take up more than a few hundred characters to implement. With some cleverness you can get much higher numbers.
>
> The Busy Beaver function is a table that lists, for any given k, the answer to this problem - the length of the longest string of dots you can achieve with a program of length k that prints such a string and stops. This function, or table, is pretty wild: it can be shown that it grows faster than any computable function. Therefore it is itself non-computable. It's unknowable in a pretty strong sense.
>
> If you don't know what "programming language" means or what programming languages can do, you can just imagine that you're giving a friend a notebook with very precise instructions such that, if your friend follows those instructions, she will end up writing a great number of dots on a very large piece of paper. You needn't assume the friend is a math genius, but you may assume she's immortal, very patient and capable of following simple instructions like "write the number 6 on the yellow sticky note" or "read the number on the orange sticky note, erase it and replace it with the next counting number". It's fine if she can't count beyond a billion herself: with enough sticky notes we can help her overcome that.
> 3 votes

---
Tags: turing-machines, busy-beaver
---


title: Understanding Tiernan's Algorithm

text:
# Question
Title: Understanding Tiernan's Algorithm
I am currently working through Tiernan's paper, "An efficient search algorithm to find the elementary circuits of a graph" (published 1970), and I am stuck on point 3 of the following excerpt:

> The algorithm is named EC for "elementary circuit." The function blocks of EC are denoted EC1, EC2, etc. EC requires that there be assigned to the vertices, in any order, the integer designators 1, 2, .-., N. The algorithm utilizes two principal arrays in addition to that describing the graph. The first is a one-dimensional array, P, containing the vertices of an elementary path. The second is a two-dimensional array, H, and is initially zeroed. Elementary path building in P is the basic process of EC. The first path is started as vertex 1. A path is extended from its end, one arc at a time, with three conditions checked before a tentative extension is performed:
>
> 1. The extension vertex cannot be in P.
> 2. The extension vertex value must be larger than that of the first vertex of P.
> 3. The extension vertex cannot be closed to the last vertex in P. H contains the list of vertices closed to each vertex.

What does Tiernan mean by point 3? I've tried googling the term "closed to \[some vertex\]", but the results were not entirely helpful.

# Answer
> 4 votes
I think I have managed to figure it out from the paper, and would like to leave my explanation for the next person who struggles with this concept.

From my understanding, Tiernan means nothing of a mathematical nature when he says "$u$ is closed to $v$". He's actually trying to say "$u$ is closed off to $v$", i.e. no longer accessible.

By following along with Tiernan's paper and his example, his algorithm manages to discover a cycle with the following vertices:

> $v\_1, v\_2, v\_4, v\_3, v\_5$

Now that he has discovered a cycle, he removes the last vertex $v\_5$ to see whether another vertex, say $v\_x$, can be added to the remaining nodes, e.g. $v\_1,v\_2,v\_4,v\_3,v\_x$, in the hopes of finding another cycle.

However, to avoid rediscovering the same cycle (such that $v\_x \ne v\_5$), the vertex $v\_5$ is now closed to $v\_3$ and $v\_3$ cannot extend an arc to it again. In the matrix $H$, we now have $H\[3,1\] = v\_5$ (or simply $5$ since Tiernan requires unique integer labels for each vertex). If $v\_3$ would become closed to another vertex before $v\_3$ was removed from $P$ (to backtrace and attempt to discover cycles using $v\_1, v\_2, v\_4, v\_x$), then that vertex would be placed in $H\[3,2\]$.

In a nutshell, "closed to" should actually be "closed off to/inaccesible" due to the fact that the node was already used as the last node in either a cycle, or a "non-cyclic dead end". This prevents the algorithm from rediscovering the same cycles over and over.

# Answer
> 1 votes
This is not standard terminology. Rather, as the text says, $H$ contains the list of vertices closed to each vertex. So a vertex $u$ is closed to a vertex $v$ iff $H\[v\]$ contains $u$ (for the exact form of the condition, consult the algorithm). I suggest you continue reading the article and try to understand the algorithm. You can then come up with what being closed means *semantically* in the context of the algorithm.

---
Tags: algorithms, graphs
---


# Question
Title: How many algorithms solve the same problem?
Its kind of a weird question to ask but I have been asking myself this: Is there a limit to number of ways to find a solution to a particular problem.

Take the simplest problem: sorting a sequence of numbers.

Now there are a lot of algorithms to sort. Is there a limit to such algorithms? Technically, you can always flip a bit and back again, so there are infinite number of ways.

But still, simple problem as sorting, surely there must be finite number of ways to solve it.

In computer science we have computability theory which tells us whether a problem is solvable, complexity theory which tells us time and space to solve the problem. Similarly, is there something which can tell us the number of ways we can solve a particular problem?

Motivation for this question is that I'm amazed how many sorting algorithms we have. Such a simple problem and there are so many solutions!

Note: I asked this on stackoverflow. It seems that we need to precisely define how we would differentiate between two algorithms. Let's say we do it by somehow recognizing steps that are useless. That way we can say if two algorithms are doing the same thing. What after that? Lets take the example of sorting. All you can do is move one number from one index to other. With just this operation, surely there must be finite number of algorithms to solve the sorting problem

# Answer
As far as I can see, there are always infinitely many ways of doing something, even if you try to define and disallow redundant steps. Let's take the example of sorting. Even if you restrict to the operations of comparing and swapping numbers, there are infinitely many ways of sorting a list: quicksort the list; swap the first two numbers and then quicksort; swap the first two numbers twice and then quicksort; ...; swap the first two numbers $n$ times, then quicksort; ...

OK, so you try to disallow that as "wasting time". But then there are still infinitely many ways: quicksort; mergesort if the list has length two, otherwise quicksort; mergesort if the list has length three, otherwise quicksort; ...

OK, so you try to disallow *that* on grounds that quicksort and mergesort will always produce the same answer so the test on the length of the list is redundant. But this is too coarse a notion of equivalence, since now there's exactly one algorithm for every problem – every correct sorting algorithm produces the same answer by definition.
> 3 votes

---
Tags: algorithms
---


title: k-ordered array problem

text:
# Question
Title: k-ordered array problem
> An array $A\[1...n\]$ is said to be k-ordered if
>
> $$A\[i - k\] \leq A\[i\] \leq A\[i + k\]$$
>
> for all $i$ such that $k \< i \leq n - k$.
>
> For example, the array $A = \[1, 4, 2, 6, 3, 7, 5, 8\]$ is 2 ordered.
>
> Q1. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

```
a) 2n-1                b) 2
c) n/2                 d) 1                 e) n

```

> Q2. In an array of 2n elements, which is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

```
a) 2n-1                b) 2
c) n/2                 d) 1                 e) n

```

I can understand how the example array is two ordered, but I am having trouble understanding what the questions 1 and 2 are trying to say.

Can someone please explain to me the meaning of the questions in simple terms?

Thanks!

P.S. First time questioner here. Sorry if I missed anything.

# Answer
> 9 votes
Take your example $$ A = \[1,4,2,6,3,7,5,8\]. $$ An array is 1-ordered if it is ordered, and the 1-ordered array corresponding to $A$ is $1,2,3,4,5,6,7,8$. Let's write both arrays together: $$ 1,4,2,6,3,7,5,8 \\ 1,2,3,4,5,6,7,8 $$ You can see that matching digits are at distance at most 2.

An array is 2-ordered if its even elements are 1-ordered and its odd elements are 1-ordered. This could be helpful in question 1. A similar property is true for 3-ordered arrays. How do these two properties combine? I suggest you try writing out a few 2- and 3-ordered arrays to see what the possibilities are.

# Answer
> -1 votes
2.) Suppose A=\[1,2,3,4,5,6,7,8,9,10\] index from 1-10. k=3 from condition 3 \< i \<=10-3 for i=4,5,6,7

Applying condition: A\[i-k\]\<=A\[i\]\<=A\[i+k\] i= 4 A\[1\]\<=A\[4\]\<=A\[7\], i=5 A\[2\]\<=A\[5\]\<=A\[8\], i= 6 A\[3\]\<=A\[6\]\<=A\[9\], i=7 A\[4\]\<=A\[7\]\<=A\[10\]

3-ordered A=\[1,4,7,2,5,8,3,6,9,10\]

k=2 from condition 2 \< i \<=10-2 for i=3,4,5,6,7,8

Applying condition: A\[i-k\]\<=A\[i\]\<=A\[i+k\] i= 3 A\[1\]\<=A\[3\]\<=A\[5\], i=4 A\[2\]\<=A\[4\]\<=A\[6\], i= 5 A\[3\]\<=A\[5\]\<=A\[7\], i=6 A\[4\]\<=A\[6\]\<=A\[8\], i= 7 A\[5\]\<=A\[7\]\<=A\[9\], i=8 A\[6\]\<=A\[8\]\<=A\[10\]

2-ordered A=\[1,4,2,5,3,6,8,7,9,10\] similarly 1-ordered A=\[1,2,3,4,5,6,7,8,9,10\]

so maximum position of the element is N/2 (see from 2-ordered A\[8\]=7 and from 3-ordered A\[3\]=7 so position = 8-3=5 but total number of element N=10 hence 10/2=5)

Now lets A=\[1,2,3,4,5,6,7,8\] index from 1-8. k=3 from condition 3 \< i \<=8-3 for i=4,5

Applying condition: A\[i-k\]\<=A\[i\]\<=A\[i+k\] i= 4 A\[1\]\<=A\[4\]\<=A\[7\], i=5 A\[2\]\<=A\[5\]\<=A\[8\],

3-ordered A=\[1,4,7,2,5,8,3,6\]

k=2 from condition 2

Applying condition: A\[i-k\]\<=A\[i\]\<=A\[i+k\] i= 3 A\[1\]\<=A\[3\]\<=A\[5\], i=4 A\[2\]\<=A\[4\]\<=A\[6\], i= 5 A\[3\]\<=A\[5\]\<=A\[7\], i=6 A\[4\]\<=A\[6\]\<=A\[8\]

2-ordered A=\[1,4,2,5,3,6,7,8\] similarly 1-ordered A=\[1,2,3,4,5,6,7,8\]

so maximum position of the element is N/2 (see from 2-ordered A\[7\]=7 and from 3-ordered A\[3\]=7 so position = 7-3=4 but total number of element N=8 hence 8/2=4)

Hence (C) N/2

1.) similarly , A=\[1,2,3,4,5,6,7,8,9,10\] index 1-10 2-ordered A=\[1,4,2,5,3,6,8,7,9,10\] 1-ordered A=\[1,2,3,4,5,6,7,8,9,10\]

so maximum position of the element is 2 (2-ordered A\[2\]=4, 1-ordered A\[4\]=4 hence position = 4-2=2 or 2-ordered A\[5\]=3, 1-ordered A\[3\]=3 hence position = 5-3=2)

Lets A= \[1,2,3,4,5,6,7,8\] 2-ordered A=\[1,4,2,5,3,6,7,8\] 1-ordered A=\[1,2,3,4,5,6,7,8\]

so maximum position of the element is 2 (2-ordered A\[2\]=4, 1-ordered A\[4\]=4 hence position = 4-2=2 or 2-ordered A\[5\]=3, 1-ordered A\[3\]=3 hence position = 5-3=2)

Hence (b) 2

---
Tags: data-structures, arrays
---


title: RSA encryption why does ed=1?

text:
# Question
Title: RSA encryption why does ed=1?
So I fully understand the how the RSA algorithm works, but now I am trying to reason with the formula. I want to know:

> why the public key e and the private key d in the RSA encryption have to satisfy the equation ed = 1 mod (p − 1)(q − 1)?

Is it because of the standard modular arithmetic rule where 1 mod anything is 1, or is there a more to this answer?

# Answer
> 5 votes
The relation of $e$ and $d$ is set so that encryption and decryption are inverses of each other, that is, if you encrypt a message then the ciphertext decrypts to the original message. Encryption and decryption are $$ c = m^e \pmod{n}, \quad p = c^d \pmod{n}, $$ where $n = pq$ is part of the public key, $m$ is the message, $c$ the ciphertext, and $p$ the decrypted plaintext. We want $p = m$, i.e., $$ m = m^{ed} \pmod{n}. $$ This equation holds for all $m$ iff $ed \equiv 1 \pmod{\lambda(n)}$, where $\lambda(n)$ is Carmichael's function. For $n = pq$, $\lambda(n) = \mathrm{lcm}(p-1,q-1)$. In practice, $\lambda(n)$ is replaced by Euler's function $\varphi(n) = (p-1)(q-1)$.

---
Tags: algorithms, complexity-theory, cryptography
---


title: Confusion in Reducibility

text:
# Question
Title: Confusion in Reducibility
In Sipser's Theory of Computation book, it is stated while reducing ATM to REGULARTM

> We let R be a TM that decides REGULARTM and construct TM S to decide ATM. Then S works in the following manner.

S = “On input , where M is a TM and w is a string:

1. Construct the following TM M2.

M2 = “On input x:

1. If x has the form 0n1n, accept .
    2. If x does not have this form, run M on input w and accept if M accepts w.”
2. Run R on input \< M2\>
3. If R accepts, accept ; if R rejects, reject .”\`

My question is, shouldn't M2 reject x of the form 0n1n?

# Answer
Here, M2 hasn't been designed to accept Regular Languages. It has been designed to be used as argument of R. As per assumption that R can decide REGULARTM, R is free to reject M2 if the case arises. Remember, decidability includes both acceptance and rejection.

**Update:**
As per definition, R will accept only if argument TM accepts regular language. And, it will reject if argument TM accepts non-regular language. The setup of M2 harnesses this rejection property of R. If R hasn't rejected (as it can decide, it'll accept), it means point 2 of M2 was in action (which makes M accept w creating contradiction).
> 1 votes

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


# Question
Title: Is $L_p$ decidable when p is a trivial property?
If

$\qquad\displaystyle L\_p = \\{ \langle M \rangle : p \in P(L(M)) \text{ s.t. } p \text{ is a specific trivial property} \\}$,

where a trivial property is a property that is shared by *all* recursively enumerable languages or is *not* a property of *any* recursively enumerable language, is it implied that $L$ is decidable?

# Answer
> 4 votes
If $p$ is a trivial property of r.e. languages, it either applies to all r.e. languages or applies to no r.e. language. That means that either

1. $L\_p$ is the set of all TM descriptions or
2. $L\_p=\emptyset$.

In the first case, a decider for $L\_p$ ignore the input $\langle M\rangle$ and immediately accept and in the second case, a decider would similarly reject. In either case, $L\_p$ is clearly decidable. While we don't necessarily know which decider is the right one to use, that doesn't matter, since the *existence* of a decider is all that we need.

# Answer
> 0 votes
Not sure if I understood your question correctly, but if $P$ is a trivial property, i.e., shared by all languages in $RE$, then $HALT$ language also has that property. So, $L$ in your definition could just as easily be $HALT$; it fits your definition. But, $HALT$ is not decidable. Hence, the answer is no.

# Answer
> 0 votes
In Rice's theorem, a 'trivial property' is a property that holds for all *subprograms* (partially computable functions) within a specific *language*.

If this is what you intended, then the answer to your question is: no, the presence of a trivial property does not mean a specific language is decidable. However, such a property would necessarily be invariant - such as memory safety, purity, or deadlock freedom. Naturally, a program with a non-terminating expansion cannot have any trivial inductive properties that are functions of said expansion.

If you truly mean a trivial property as one possessed by all *recursively enumerable languages*, then I hypothesize that the only such properties are those directly implied by being *recursively enumerable languages*, and that also does not imply decidability.

---
Tags: computability
---


# Question
Title: Ideas for CS-related challenge for teams of high school students?
I am helping design a CS-related activity for a Let's Talk Science competition, which promotes STEM amongst high school students. In the competition, teams of six students will move from station to station, trying to complete each as quickly as possible.

One station might give the team a metre stick, then ask them to measure the height of a building. (This can be solved by using similar triangles to estimate the building's height.) Time penalties are added to the team's completion time depending on how close their answer was.

My constraints are thus:

* Most students won't have CS/programming knowledge
* Challenge should not require a computer
* Idea should challenge teams of six students for 15-20 minutes
* Challenge must have clear answer that can be objectively scored (not judged)

One reasonably good challenge presents a sentence encoded with a Caesar cipher, then asks the students to decode it. The person running the station give a short explanation of what a Caesar cipher is, then leave the teams to decode the text. Time penalties are awarded based on correctness -- each incorrect character adds a 30-second penalty.

The Caesar cipher idea has been used often in the past, however, and I'm trying to develop something novel. I have been through the various activities on CS Unplugged, but none appealed to me -- the exercises I saw were generally aimed at illustration and not suitable for competition, were too simple, or required too much explanation of background knowledge.

Do you have any ideas on what would make a fun CS-related challenge for teams of six high school students?

Thanks!

# Answer
> 6 votes
One activity that I really liked is the following: devise a way to communicate a short text message across a long soccer field, without using electronics and without shouting. You can use any large field or open area that is large enough that they won't be able to hear each other by shouting, yet provides line of sight.

The idea is that the team will get together in advance to devise a communication method. Then, half of the team stands at one end of the field, and the other half at the other end. The first half is given a message, and they have to communicate it to the other end. They are scored based upon the accuracy of the received message and how long it takes them.

This is a very cool exercise. It gives them a lot of opportunity for ingenuity. You can give them a few materials and they can select a signaling scheme -- maybe use flags, or mirrors, or large objects, or you name it.

They'll have to devise an efficient method of encoding text into something they can signal, and a good signalling algorithm. It's their interests to trade off efficiency for robustness (redundancy to deal with errors in receiving the data). They might choose to use a forward error correcting code (e.g., add some redundancy), or they might choose to use an acknowledgement/retry mechanism (where the recipient can signal "didn't get that, please try again").

Another thing that is nice about this exercise is that it provides an opportunity for teamwork and brainstorming and cooperation within their team. It's always more fun to do this stuff together with a few others than to do it on your own.

If you like, you can point out the rich history of signalling schemes that have been used in the past: semaphore, Morse code, the signal fires used by Alexander the Great, etc.

---

If you don't like that one:

CS Unplugged is one of the best resources. If they don't have anything you like, this might be pretty tough.

---

By the way, please keep in mind that competition has mixed effects, some good and some bad. Competition is good for motivating for some students but at the same time, some students find competition demotivating. Also, there is a gender gap here; competitions are more likely to turn off women than men, which might not be desirable in an activity for high school kids, given that there are already enough barriers keeping women out of computer science.

---
Tags: education
---


# Question
Title: How to modify Bellman-Ford algorithm for this specific Minimum Cost Flow problem?
I'm trying to design an algorithm for the following optimization problem. Suppose that $G=(V, E)$ is a digraph where $V$ and $E$ are sets of vertices and edges of $G$, respectively. $|V| = n$ and $|E| = m$. $c$ is the cost vector; $c\_{ij}$ is the cost of edge $(i,j)$. Costs **can** be negative and $G$ **may** have cycles (negative or positive). **The target** is a minimum cost flow from source vertex $1$ to sink vertex $n$ which must satisfy some constraints. So let $x$ be the solution vector; if $x\_{ij}=1$ then the edge $(i,j)$ is a part of minimum cost flow. Here is my optimization problem:

$$min \sum\_{(i,j)\in E}c\_{ij}x\_{ij}$$

Subject to these constraints:

$$\begin{array}{ll} \sum\_{i\in V}x\_{ij}&=&\sum\_{i\in V}x\_{ji}~~~~~~\forall j\in V (j\neq1,n)\\ \sum\_{j\in V}x\_{1j}&=&1\\ \sum\_{i\in V}x\_{in}&=&1\\ x\_{ij}&\in&\\{0,1\\}~~~~~~\forall i,j\in V\end{array}$$

**First constraint** makes us sure that in the final solution vector, total number of edges outgoing from vertex $i$ and total number of edges incoming to that vertex are equal.

Only one edge can go out from vertex $1$, based on **second constraint** and only one edge can come to vertex $n$, based on **third constraint**.

Finally, **last constraint** tells us that the maximum flow allowed for each edge is $1$.

This is the problem of sending **a flow of value one** from vertex $1$ to vertex $n$ subject to the constraints with a capacity limit of $1$ on each edge and the vector $b$ set to $0$.

**I asked this question because** I think a flow in this case can be viewed as a path, in which we can goes around it's cycles (if any cycle exists on the path) only once and it can't meet vertices $1$ and $n$ more than once. So, can we solve this problem using a modified version of Bellman-Ford or any other dynamic programming algorithm? Time order isn't the matter to me. I just don't want to use algorithms designed for the general form of minimum cost flow problem.

# Answer
> 2 votes
## Minimum cost path

If you're looking for a minimum cost path, you can find that directly with Bellman-Ford. Just let the weight on each edge $(i,j)$ be the cost $c\_{ij}$, and ask Bellman-Ford to find for you the shortest path from the source to the sink; this will be exactly the minimum cost path (assuming there are no negative cycles in the graph).

## Minimum cost flow

If you're looking for a minimum cost flow, one natural approach is to try using the Ford-Fulkerson method. In each iteration of Ford-Fulkerson, you must find an augmenting path in the residual network. In your particular case, you might try computing a minimum-cost augmenting path from the source to the sink. Now what algorithm do you know that can compute a minimum-cost augmenting path in a digraph (potentially with cycles and potentially with negative-weight edges)? That should be enough of a hint to give you something you can try. Since it's your exercise problem, I'll let you work out the details and see if you can prove whether it works or not.

Alternatively, if conceptual simplicity is the goal, linear programming (LP) is one approach that is conceptually very simple and might apply to your porblem, and it has a polynomial running time. LP immediately gives a solution to your problem (though possibly not with integer $x\_{ij}$'s), and it's a well-known theorem that you can solve LP in polynomial time. Of course, LP might be a "bigger hammer" than you want to throw at this. Also, I don't know if LP will give you an integral flow, which you seem to want. There's a standard theorem that says that, for the linear program associated with a maximum flow problem, there is always an integral solution to the LP that is optimal (you can't do better with non-integral flows). I don't know if that carries over to the minimum-cost flow setting as well.

---
Tags: graphs, optimization, dynamic-programming
---


title: Infinite Language vs. finite language

text:
# Question
Title: Infinite Language vs. finite language
I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory.

I think the root of the trouble is that a language like $L=\\{ab\\}^\*$ is **infinite** in the sense that it can generate an infinite (but countable) number of strings. Yet, it can still be recognized by a **finite** state automaton.

It also doesn't help that the Sipser book doesn't really make this distinction (at least as far as I can tell). A question about infinite/finite languages and their relationship to regular languages came up in a sample exam.

# Answer
> 33 votes
Oh my. This seems like a confusion caused by the (old school) terminology of "finite-state language" as a synonym for what is known today as "regular language".

Anyways, the standard definitions for finite/infinite accepted these days regard only the size of the language:

1. a **finite** language is any set $L$ of strings, of finite cardinality, $|L|\<\infty$.
2. an **infinite** language is any set $L$ of strings, of infinite ($\aleph\_0$) cardinality $|L|=\infty$.

A finite $L$ is always regular.

An infinite $L$ can be regular (sometimes called "finite-state"), decidable (sometimes called "recursive"), non-regular (non-finite-state), non-decidable, etc.,

# Answer
> 6 votes
A language is a set of strings. It is finite if it has a finite number of strings in it.

# Answer
> 4 votes
> I'm unclear about the use of the phrases "infinite" language or "finite" language in computer theory.
>
> I think the root of the trouble is that a language like $L=\\{ab\\}^∗$ is infinite in the sense that it can generate an infinite (but countable) number of strings. Yet, it can still be recognized by a finite state automaton.

Another issue is that formal language theory is rather peculiar in how it uses the term "language".

To everybody in this world except people in formal language theory, a language is a system of utterances used to communicate, so each utterance has a form (its *syntax*) and some sort of meaning (its *semantics*). Formal language theory, at least the part that is used in computer science, is devoted to the problem of how best to define, formally, the *syntax* of languages. It is all about the relationship between the syntax of languages (what the utterances look like) and formalisms (languages!) such as regular expressions that are used to define the syntax of languages.

Hence, in formal language theory, 'a language' is defined simply as 'a set of strings'. It does not typically assign meanings to the strings in the language.

At the same time, the formalisms used to describe languages, such as regular expressions, also form languages in this sense: for instance, every regular expression is a string, and hence, the set of regular expressions is a language. However, for these formalisms, the strings in the language *do* have a meaning: for instance, the meaning of every regular expression is the language it denotes.

For instance, $ab$ is a string; hence, $\\{ab\\}$ is a language, namely, the language consisting of the string $ab$. However, $ab$ is not only a string, but also a regular expression: a member of the set of valid regular expressions (which is a language). Like every regular expression, it has a meaning: it denotes a language, in this case, the language $\\{ab\\}$.

Now let's get on to your example: $\\{ab\\}^\*$. The operator ${}^\*$ denotes a function that maps languages to languages: it maps each language $L$ to the language consisting of all strings that consist of a string in $L$ zero or more times repeated. If $L$ is the empty language, the result is $L$; in all other cases, the result is an infinite language. For instance, $\\{ab\\}^\*$ is the language $\\{ \epsilon, ab, abab, ababab, abababab, \ldots \\}$. It is infinite, but using the operator ${}^\*$, we can describe it in a finite way, as $\\{ab\\}^\*$.

Furthermore, we can use a regular expression to describe this language, namely $(ab)^\*$. Like all regular expressions, this is a finite string, but like most regular expressions that contain the ${}^\*$ operator, it describes an infinite language.

Whenever a text on formal languages uses an expression such as $(ab)^\*$ that denotes a language, ask yourself whether it is discussing the regular expression itself (e.g. how it is constructed, which language it denotes, etc.) or whether it merely uses the regular expression to refer to the language being denoted.

---
Tags: formal-languages, terminology, regular-languages
---


# Question
Title: Do all decidable problems lie in the class NP?
All decision problems (i.e.language membership problems), which are verifiable in polynomial time by a deterministic Turing machine are called NP problems. Further, these problems can be solved by a non-deterministic Turing machine in a polynomial time and in exponential time by a deterministic Turing machine.

Do we have a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable?

# Answer
> 5 votes
No to the question in your title; yes to the question in the body of your post.

By the non-deterministic time hierarchy theorem, every decidable NEXP-hard decision problem is "a decision problem that is not verifiable by a deterministic Turing machine in polynomial time but decidable".

# Answer
> 0 votes
A concrete counterexample could be Quantifed Boolean Formula, which is only verifiable in polynomial time if PSPACE=P. There's a whole myriad of other examples. You might also want to look at coNP-complete problems. For these a polynomial TM can only verify counterexamples (unless coNP=NP). The language of all tautologies is a prominent example for that class.

---
Tags: undecidability, np
---


title: Number of Different AVL Tree

text:
# Question
Title: Number of Different AVL Tree
I studying the related question.

https://stackoverflow.com/questions/13500560/number-of-ways-to-create-an-avl-tree-with-n-nodes-and-l-leaf-node

but it's not so general.

In-fact, We want to know with N keys, how many different AVL Tree, we can make?

we know with N=1 key is 1 AVL Tree. with N=2 key we have 2 different AVL Tree, but in general we can make any recurrence formula? for example for N=4, N=5 and so on.

# Answer
Let $a\_{n,h}$ denote the number of AVL trees with $n$ nodes and height $h$. It is straightforward to get a recurrence for $a\_{n,h}$:

$$a\_{n,h} = \sum\_{k=1}^n \bigl(a\_{k-1,h-1}a\_{n-k,h-1} + a\_{k-1,h-1}a\_{n-k,h-2} + a\_{k-1,h-2}a\_{n-k,h-1}\bigr),~ n\geq h \> 1,$$

with the initial conditions $a\_{n,h} = 0$, if $h\>n$ or $h\in\\{0,1\\}, n\neq h$, and $a\_{0,0} = a\_{1,1} = 1$.

The numbers you are looking for then are $a\_n = \sum\_h a\_{n,h}$.

Unfortunately there apparently is no known closed form for this sequence. The OEIS has a list of the first 1000 terms and maple + mathematica code to compute further ones (via the recursion).
> 7 votes

---
Tags: algorithms, graphs, data-structures, trees, binary-trees
---


title: Three phase commit : study case

text:
# Question
Title: Three phase commit : study case
Consider a group of five processors implementing three-phase commit protocol. During the execution of the protocol, the coordinator and one other process crash. Two of the remaining processes are waiting in "READY" state for the coordinator while the third process is in "PREPARE COMMIT" state. Can they continue and complete the protocol without waiting for recovery of the crashed processes? Do they COMMIT or ABORT? Which state can the crashed process be in?

In my opinion, the crashed processor maybe was in the "ABORT" state, so how can the other processors know the "global decision"?

# Answer
I found the answer consulting the book "**Distributed System : Principles and Paradigms**" (Andrew S. Tanenbaum - Maarten Van Steen). First of all it is possible to continue just because 3PC is non-blocking protocol by definition. A processor can reach the state “PRE-COMMIT” only if the coordinator was in state “PRE-COMMIT” (thus each processor sent a COMMIT request), so the crashed processor could not be for sure in state “INIT” nor in "ABORT", but at least in the state “READY”. Anyway, all the “alive” processors, after seeing the “PRE-COMMIT”, will go in “COMMIT” state.
> 1 votes

---
Tags: distributed-systems, communication-protocols, fault-tolerance
---


# Question
Title: Shortest even path that goes through a vertex
Given an undirected and connected graph $G=(V,E)$ and two vertices $s,t$ and a vertex $d \in V- \\{s,t\\}$, we would like to define a legal path as a path from $s$ to $t$, passes through $d$ (at least once) and is of even length (regarding number of edges).

We need to find such a path that is the **shortest** in $O(V+E)$ time.

I thought about BFS from $s$ to find a shortest path to $d$, and BFS from $d$ to find shortest path to $t$, but then it wouldn't necessarily be of even length. Plus, such a path we're looking for is not necessarily simple.

Any hints?

# Answer
Your remark is true: there might be no simple even path from $s$ to $t$, an even path perhaps includes a cycle of odd length.

The shortest path from $s$ to $t$ via $d$ is the shortest path from $s$ to $d$ plus the shortest path from there to $t$.

To compute even length paths you might consider turning the graph into a bipartite graph using two copies of itself. Double $V$ by adding a copy $V'$. Now duplicate every edge $(x,y)$ into $(x,y')$ and $(x',y)$, where the primes indicate copies in $V'$. Now the shortest path from $s$ to $t$ will be of even length. (And all paths of even length in the original graph are 'represented' in the new graph.)

Problem: the intermediate node $d$ might be $d'$, its copy in $V'$. Your turn to connect the two requirements 'via $d$' and 'even length'.
> 5 votes

---
Tags: algorithms, graphs
---


# Question
Title: Space complexity problem, relation between $DSPACE(log^kn)$ and $DSPACE(log^{k+1}n)$
I need help with the following:
Let $k\in \mathbb{N}$, define:
$L^k=DSPACE(O(log^k(n)))$
$NL^k=NSPACE(O(log^k(n)))$
and:
$PolyL=\bigcup\_{k=1}^{\infty}L^k$
$PolyNL=\bigcup\_{k=1}^{\infty}NL^k$

I need to prove, disprove or to determine if it is an open question:
1. For every $k\in \mathbb{N}$ it holds that $NL^k\subseteq L^{2k}$
2. There exist $k\in \mathbb{N}$ s.t. $L^k=L^{k+1}$

The first one is easy, since it is almost immediately the result of Savitch's theorem.
The second one I'm not sure... I'd love to get some lead there.

# Answer
> 2 votes
Use the space hierarchy theorem, which is a finite form of the undecidability of the halting problem.

---
Tags: space-complexity
---


title: Functional Dependencies in Relations

text:
# Question
Title: Functional Dependencies in Relations
I'm currently reading about functional dependencies.
I've read Armstrong's axioms about:

Relexivity: $if$ $B\subseteq A$ $then$ $A\to B$
Augmentation: $if A\to B$ $then$ $AC\to BC$
Transitivity: $if A\to B$ $and$ $B\to C$ $then$ $A\to C$

and also about:

Union Rule: $if A\to B$ $and$ $A\to C$ $then$ $A\to BC$
Decomposition Rule: $if A\to BC$ $then$ $A\to B$ $and$ $A\to C$

I also know that for a relation R(A, B, C, D, E) that:
$if A\to B$ $then$ $ACDE\to B$.
In fact, the left side could be any superset of A.
Is there a name for this rule?
I've looked at various books but while they use it in examples, they never mention a name.

# Answer
> 1 votes
While I'm unaware that your suggested rule has a name and couldn't find it in any texts on my shelf, it's a consequence of reflexivity and transitivity, as you probably know already. Here's how: $$ \begin{align} ACDE &\rightarrow A &\text{(reflexivity)}\\ A &\rightarrow B &\text{(hypothesis)} \\ ACDE&\rightarrow B &\text{(transitivity)} \end{align}$$

---
Tags: database-theory
---


# Question
Title: Using the Pumping Lemma to show that the language $a^n b a^n$ is not regular
I've seen a lot couple of questions regarding the pumping lemma that are pretty similar to each other and this one is unfortunately not the exception. Most likely will be this question marked as a duplicate. But I guess there's no harm in asking.

I was trying to show using the pumping lemma that this language is not regular:

$$ { L = \\{a^n b a^n \mid n \in{\mathbb N}\\} } $$

I've tried the following, although I'm not sure of what I'm doing:

I've tried also to follow the example in this question

$$ w = xyz $$ $$ xyz = a^p b^p a^p $$ $$ |w| = 3p $$ $$ 3p \> p $$

$$ |xy| \leq{p} $$

$$ |y| \geq{p} $$

but here is as far as I come. A thing that I don't understand is $b$ doesn't have an $n$ exponent like in $a$. **Is it ok what I did by placing a $p$ exponent on $b$?**

I would appreciate any help in this matter.

# Answer
According to your question, you can't put a $p$ as exponent on $b$ (at least $p = 1$ like @Guildenstern said) because that string wouldn't be in your language $L$. Putting $p = 1$ wouldn't be correct too because you should never give values to the pumping lenght.

**You must always choose a string in** $L$, for example $a^pba^p$ if you pump correctly you will have less $a$'s in one side than the other side.

(A very different matter is the number $k$ which is used to pump in $y^k$, maybe you are confusing the $p$ over $b$ with that)
> 2 votes

# Answer
The given language is $$ { L = \\{a^n b a^n \mid n \in{\mathbb N}\\} } $$

This is how you prove that it's not regular language:

1. You assume that it is regular language, which means it can be pumped.
2. **You pick a string from the language** which has a length atleast p.
3. You show that this string can't be pumped, meaning our assumption was incorrect.

Now, tell me how on the Earth do you think the string $a^pb^pc^p$ belongs to the language $L$? Certainly, you can't pick this string to prove $L$ is not regular. Pick a string from $L$.

**Proof:**
Pick $a^pbc^p$ where p is pumping length. The length of this string is 2p+1,so it's a valid candidate.

Now, you need to divide the string in $xyz$ satisfying all three condition of pumping lemma. As $|xy| \le p$ and $|y| \ge 1$, the $y$ must contain $a$.

Now, pump with $xyyz$ or $xyyyz$. The resulting string won't be in $L$ (if $y$ contains only $a$, pumped string would have more $a$ than $c$. if $y$ contains other characters too, the pumped string won't contain $abc$ in order distinctly).
> 2 votes

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


# Question
Title: Is the following problem decidable in polynomial time?
We are given an initial set of tuples $S\_0=\\{(x\_i,y\_i)|i\in \[n\], \forall i:x\_i,y\_i\in \mathbb{N}\\}$ and a number $B\in \mathbb{N}$.

At time $t$ we are allowed to remove ($S\_t := S\_{t-1} \setminus \\{(x\_i,y\_i)\\}$)

a pair $(x\_i,y\_i)\in S\_{t-1}$: if $$x\_i + \Sigma\_{j:(x\_j,y\_j)\in S\_{t-1}, j\neq i} y\_j \geq B$$.

(That is if the sum of $x\_i$ and the rest of the $y\_j$'s is at least $B$ we're allowed to remove tuple $i$).

The problem is finding a sequence of tuples which can be legally removed, and leave a minimal cardinality set (i.e. remove as many tuples as possible).

**Is this problem in $P$ as it is?**

**What if we know that $\forall i:y\_i\leq x\_i$?**

---

Example: Assume $S\_0 = \\{(5,3),(5,5),(1,1),(6,0),(2,2)\\}, B=10$ then $(\<1,1\>,\<6,0\>,\<2,2\>,\<5,3\>)$ is an example of a maximal output sequence.

# Answer
> 1 votes
This is a nice exercise, such as one might find in an undergrad-level algorithms class. (Congratulate your professor on selecting such a nice exercise.) Since it's *your* exercise, I'm going to let you solve it, but I'll give you a series of hints.

Important: Spend at least an hour exploring each hint, before moving on to the next hint.

---

Hint #1:

> When given an algorithms problem, it is often very helpful to look at some small examples and work out what's going on by hand.
>
> So, pick a sample problem instance with 3 items (generate the $x\_i,y\_i$'s arbitrarily); map out all possible timelines (all possible sequences of item removals); and see what you see. Do another example with 3 items. Try one with 4 items. Do a few such examples, and see if you can build some intuition. I suspect you'll spot what is going on, and then from that you might be able to figure out how to solve the problem.

---

Hint #2:

> What chapter of the textbook are you currently in? This is often a good heuristic to help you select a type of algorithm to try.

---

Hint #3:

> A natural algorithmic approach is to use a greedy algorithm: if multiple items are currently eligible for removal, select the item whose $y\_i$ value is `_____`. (You fill in the blank.) So, see if you can determine whether you can find any way to fill in the blank that provides a correct algorithm for your problem. This gives you a few candidate algorithms; for each candidate, see if you can prove or disprove its correctness. To do that, try some small examples. See if you can find a proof of correctness or a counterexample demonstrating it is incorrect. Once you've worked out whether there is any algorithm of this form that is correct, you should be able to answer your question.

---

Hint #4:

> If you've tried all of the above diligently, show us your work and where you got stuck and I'll give you one more hint.

---
Tags: algorithms
---


# Question
Title: Having trouble with turing machine over language $L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$
I am having trouble giving the description of a Turing machine that goes for $L = \\{0^n 1^m 0^n 1^m \mid m,n \geq 0\\}$. What I have so far is:

If we start with a blank, the string is empty and it should accept, if not, start reading $0$s and I thought marking the $0$s with $X$ and the $1$s with $Y$ would be OK. After we reach a $1$, start marking $0$. Now comes the part I'm worried about, what do I do when the 2nd round of $0$s comes? How will I check if there are equal amounts of $0$s and $1$s?

Thanks in advance

# Answer
What I tend to do when it comes to counting with a tape is to go back and forth on the tape, marking the relevant portions of the tape as I'm reading new input.

**Example**
To recognize the language $0^n1^n$ with a Turing machine (not that you'd need the power of a Turing machine, but for illustrative purposes), you can read the first $n$ $0$s, and then when you read the first $1$, mark that $1$ (write $1'$ in that cell), then go back all the way to the first $0$ and mark that, too (writing $0'$). Then go back to the next $1$ (the one to the right of the cell with the $1'$) and write $1'$, go back to the next $0$ that is not marked, and mark that. When you run out of $1$s to read/mark, you have to go back and make sure that all $0$s have been marked. If this is the case, accept the language. If not, or if any other deviation has occurred during the operation of the machine (e.g. encountered some input symbol other than a $0$ or a $1$, read and marked a $1$ but there were no $0$s left to mark; these are treated like undefined transitions), you must reject the language.

Say you are given the string $0000111$ as input.
After counting two $1$s:

> $0' 0' 0 \\,0 \\,1' 1' 1\\,$

After counting three $1$s:

> $0' 0' 0'0 \\,1' 1' 1'$

Now there is one $0$ left that is not marked; reject the language.

For your language, it is simple (but, like the above, pretty tedious) to use this strategy to recognize the language. The variation comes in keeping track of what parts of the previous input to mark, and how to get back to the next input cell to read.

**Aside**: This can be generalized to multiplication, for example to recognizing the language $0^n1^m0^{n \cdot m}$.
> 2 votes

# Answer
Turning Machine compares such numbers by zig-zaging across the tape. It can mark first 0 from first $0^n$ and go to all the way across 1s to mark first 0 from second $0^n$, then return back to first $0 ^n$ to mark second 0 and so on.

And yes, you don't need extra tape alphabet Y. X can do fine for 1s too without conflicting with 0s.

The transition functions defining zig-zaging aren't that complex. They're like loops with loop break rules.
> 0 votes

---
Tags: turing-machines
---


title: Running algorithms in parallel

text:
# Question
Title: Running algorithms in parallel
I'm doing a course in Computational Number Theory and am currently looking at algorithms such as Euclid's algorithm, Square-roots modulo a prime, LLL reduction algorithm, McKee's method, Pollard's $p-1$ method, the elliptic curve method and a couple of others.

In an assignment, I'm asked the following question: Which of the algorithms can be run easily using several computers in parallel?

Here are my questions which I hope can shed some light on my above question:

1. What is the alternative to running computers in parallel (if such an alternative exists)? What are the differences?
2. What criterion determines whether running computers in parallel is an advantage?

# Answer
I'll start by giving an example which can be easily run in parallel: the elliptic curve method (ECM). In this method, we choose a random elliptic curve $E$, and run Pollard's $p-1$ method on this curve up to a certain point. The idea is that with probability $\alpha$, Pollard's $p-1$ method terminates within $T$ iterations. We optimize over $T/\alpha$, the end result being that $\alpha$ is quite small.

Here is how you would run ECM in parallel. Each processor (or core) runs the algorithm just described, until one of them succeeds in factoring the integer. Having $N \ll 1/\alpha$ processors (or cores) cuts the running time by a factor of $N$. An algorithm where a similar approach is possible is called *embarrassingly parallel*.

A slightly different example is the quadratic sieve. In this algorithm, we need to find a certain number of smooth integers and factor them. If we aim at finding $n$ such integers and there are $N$ processors available, we can assign each of them to find $n/N$ integers. A more complicated approach would be to have one central processor assign "jobs" (integers) to processors: each time a processor finishes factoring a smooth integer, it receives a new one. (In practice, since the algorithm sieve for smooth integers, each processor will get a range of potential smooth integers.) This scheme is also *embarrassingly parallel*.

In contrast, consider the simple Pollard's $p-1$ method. The algorithm is iterative in nature and there doesn't seem to be a simple way to run it in parallel; we can perhaps run the FFTs associated with modular exponentiation using a sophisticated parallel scheme, but this is no longer embarrassingly parallel.

At this point you should be able to answer the question on your own. The question is asking you to determine which of the algorithms are embarrassingly parallel.
> 4 votes

---
Tags: parallel-computing
---


# Question
Title: Demonstration that every finite set is computable
What is the best demonstration that show that "Every finite set is computable"?

thanks

# Answer
Given any finite set, it's trivial to write a program that accepts exactly the members of the set: just compare the input against each element of the set in turn.
> 4 votes

---
Tags: complexity-theory, computability
---


# Question
Title: Using induction to prove a big O notation
I'm trying to prove that the following recurrence relation has a runtime of `O(n)`:

```
 fac(0)   = 1
 fac(n+1) = (n + 1) * fac(n)

```

I think that I can use induction in the following manner:

**Base case**

If `n=0` then `fac(n) = fac(0) = 1`

**Inductive case**

Assume that `fac(n)` has a runtime of `O(n)`

```
fac(n+1) = (n + 1) * fac(n)

```

Therefore `fac(n+1)` has a runtime of `O(n+1)`

However, I have a suspicion that my inductive case doesn't really prove much. Maybe this is because the my assumption for the inductive case is wrong?

Can you point me in the right direction to prove this runtime?

# Answer
> 2 votes
In essence, your proof is correct. A more general solution that you can use for recursive algorithms is this.

The way to solve this is to create a function T(n) that measures the runtime of the function and figure out the big O notation for it.

To solve a problem of size n, I must solve a problem of size n - 1. Then I must perform constant time arithmetic to get the answer. Thus :

```
T(n) = T(n - 1) + O(1)

```

Prove T(n) is O(n) ie by definition

```
T(n) <= cn for all n >= n0

```

Assume:

```
T(n - 1) <= c(n - 1)

```

then

```
T(n) = T(n - 1) + O(1)
T(n) <= c(n - 1) + d
T(n) <= cn + d - c
T(n) <= cn for c >= d

```

use T(1) as a base case to complete the proof, giving you n0 = 1

# Answer
> 1 votes
Here is a similar example. Consider the recurrence $$F\_n = \begin{cases} n & n \leq 1, \\ F\_{n-1} + F\_{n-2} & n \> 1. \end{cases}$$ Let's prove by induction that the runtime to calculate $F\_n$ using the recurrence is $O(n)$. When $n \leq 1$, this is clear. Assume that $F\_{n-1},F\_n$ are calculated in $O(n)$. Then $F\_{n+1}$ is calculated in runtime $O(n) + O(n) + O(1) = O(n+1)$.

There is something wrong about this proof — to start with, the result is wrong: calculating the Fibonacci sequence recursively takes exponential time. The problem is that every big O carries with it a hidden constant, and this constant grows in our example.

In order to do things properly, we fall back to the definition of $O(n)$: a function $f(n)$ is $O(n)$ if for some $K,N$ and all $n \geq N$, $f(n) \leq Kn$. In your case you can take $N = 1$. Find an appropriate $K$ and prove by induction that the runtime of your recurrence is at most $Kn$ for $n \geq 1$.

---
Tags: complexity-theory, asymptotics
---


# Question
Title: writing a Context free grammar for a language
Hi I have two question about this language: **L = {a^i b^j c^k | i = 2\*j OR j=2\*k }**

1)Finding a CFG

2)If in condition part we put **AND** instead of **OR** , is this language remains **CONTEXT FREE** or not ??

thanks.

# Answer
1. $L\_{i=2j ~\text{OR} ~ j=2k} = L\_{i=2j} \cup L\_{j=2k}$. I'll assume you can do the languages with only one condition.
2. If OR turns into AND, then $L = \\{a^ib^{2i}c^{4i}\\}$. Use pumping lemma to show that $L$ is not context free.
> 1 votes

---
Tags: context-free, automata, pushdown-automata
---


# Question
Title: requirement for pumping lemma in regular language
I am a bit confused on the theory of the pumping lemma. As I know is used to decide if a language is regular or not.

This is what I have understood so far though For a regular language $L$, there exists a $p \> 0$ such that for all $w ∈ L$ where $|w| ≥ p$, there exists some split $w = vxu$, for which the following holds:

$|vx| ≤ p$

$|x| \> 0$

$vx^iu ∈ L$ for all $i ≥ 0$

but what is the rationale behind the requirement of $|vx| ≤ p$ what happens if we drop that requirement??

thanks ahead

# Answer
> 3 votes
$|vx| \< p$ mean that $x$ is short and it is at the beginning of $w$. If you were to remove that constraint, all regular languages would still satisfy the lemma, but more irregular ones would too. For example $L = \\{a^n \mid n ~\text {is not prime}\\}$, when $n = m \cdot k $ can be pumped by taking $x = a^k$.

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


# Question
Title: How to use different size features in SVM?
I want to train a support vector machine with some features. The problem is, one of the features is 1-dimensional (only an angle) and the other is an LBP Histogram, an 58-dimensional vector.

Therefore if I concatenate them, like this (in MATLAB) :

```
f = [lbp_histogram; angle];

```

I got a 59x1 vector, I can train SVM with these vectors, however, in this case the "weight" or "importance" of angle feature is 1/59, whereas lbp has 58/59 weight. What if I want to give them equal weights? Or better, I want to adjust the weights for best performance. How can I change the weight?

The only 2 options I have in mind is :

Scale the angle feature with the weight like this :

1. `angle = angle * w_angle`
2. `angle = angle ^ w_angle`

Do you reccomend one of these, or any other way that I can make `angle` as important as `lbp_histogram`?

I hope I stated my problem clearly, Thanks for any help.

# Answer
> 4 votes
I think you have a misconception. SVM does not necessarily give the latter 58 features a weight of 58/59. Rather, SVM learns what weights to use for each feature, based upon what helps it build the best classifier.

So, just use those features and train with them. Don't try to find a way to manually provide different weights for the features; SVM training automatically takes care of that for you.

---
Tags: machine-learning, linear-algebra, matrices, cluster
---


title: What type of HMM-GMM I need

text:
# Question
Title: What type of HMM-GMM I need
**Context:** I have 100 speech sentences that I asked my friend to speak. The vocabulary in the sentences are same but only the order of words are changed. My friend says that he spoke exactly what was asked for each sentence. But I don't know whether he spoke exactly that sentence or something else. What I have here is those 100 reference sentences against which I need to match his speech samples. As I want to do it by computer and not by listening manually therefore I am seeking your guidance.

**Data:** I have been able to segment the words in each speech sample of my friend. So I have 100 sentences each segmented into individual words with sequence of each word preserved for each sentence. I have extracted required features from each word (MFCC + Delta and Delta Delta).

**What I am looking for:** I need your guidance and help in informing how can I recognize these words with over 95% accuracy. As I read many papers and articles, GMM + HMM is the reasonably good way to do this. But I have a confusion, when I have already segmented every sentence, why should I try to match the entire speech sentence by transitioning state to state using HMM? I can simply match each word and see if the sequence is same with respect to the reference sentence word sequence. Is GMM + HMM the way to go for this? Can I use DTW or Neural Network or SVM to classify (matching or not matching) each word and get high accuracy?

# Answer
Normally in speech-to-text we don't already have a perfect segmentation into words, which is why we often use the HMM to match the entire speech sentence. Also, this way the HMM can take into account probabilistic information on the distribution of word bigrams (and even trigrams). If you already have a segmentation and you are sure it is correct, then you can use the HMM to match just the word, if you like. But getting a reliably correct segmentation is tricky, given how people speak in practice, so you might want to check how accurate your segmentation is before relying upon it.

Either GMM + HMM or DTW would be a reasonable approach.

A very simple approach would be to download an existing speech-to-text tool and use it on those sentences, instead of trying to build something yourself.
> 1 votes

---
Tags: hidden-markov-models, speech-recognition
---


# Question
Title: Is an Event Counter essentially an integer version of Barrier?
Just like there exists binary and integer Semaphores, does the **Event Counter** play an integer version of a **Barrier**?

Event Counters are described in the paper

> Reed, DP; Kanodia, RK: Synchronization with eventcounts and sequencers. *Commun. ACM* 22(2):115-123, 1979, http://doi.acm.org/10.1145/359060.359076

There is an online versions of the paper here.

# Answer
> 0 votes
An event counter can function like a barrier when a set of threads all use the same value to await. For example, 3 threads can perform an await operation on the Event-Counter EC, using the same value. Then await(EC, common\_val), and then threads each will block until the EC is advanced to the common value to synchronize with one another.

However, Event Counter along with Sequencers can be used in many other ways as well, while barrier primitives have only this one type of behavior, used only to allow a set of threads to move through multiple steps. Event Counter along with a Sequencer can also make up a semaphore.

---
Tags: terminology, operating-systems
---


title: TCP repeated acknowledgement

text:
# Question
Title: TCP repeated acknowledgement
My professor has asked this (exam) question and it actually makes no sense to me:

> TCP offers a reliable, bidirectional byte stream over the best effort packet delivery in IP. For reliability, a sender in a TCP connection re-transmits a possibly lost packet. One of the methods with which TCP guesses the loss of a packet is by duplicated (repeated) acknowledgements. Illustrate clearly and succinctly this method, with a reason why it is a reasonable way to guess a packet loss.

Surely a packet is only acknowledged when it is received? If so, how can repeated acknowledgement detect a lost packet if that packet is lost and has not been acknowledged. Unless of corse he means a lost acknowledgement packet? Where that is duplicated several times to signify that it has not be received and the packet has not been acknowledged? Or is there more to this?

# Answer
One assumption in TCP design is that packets arrive in the same order as they are sent.

And TCP performs cumulative ACK, "where the receiver sends an acknowledgment signifying that the receiver has received all data preceding the acknowledged sequence number." (Wikipedia). And receiver sends back exact one ACK for every one packet it receives.

These facts make sender assume a packet is lost if it receives duplicated ACKs. To avoid false negative guess (because of out of order delivery), TCP sender usually assumes a packet is lost when three duplicated ACKs are received.
> 1 votes

---
Tags: distributed-systems, computer-networks
---


# Question
Title: (AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees?
Question: If an AVL tree has height h (assume h ≥ 2), what is the maximum possible diﬀerence between the number of nodes in its two subtrees? Prove your answer. Your answer should not use big-Oh or big-Theta.

I drew six trees and drew the max number of nodes I could on one tree and the min number of nodes on the other subtree while keeping it an AVL tree. Here is table with the information for number of minimum nodes in left subtree, max number of nodes in right subtree and difference between the number of nodes between the two trees:

But I simply cannot figure out a pattern for the maximum possible difference between the number of nodes in the two subtrees. My current guess is that the max possible difference between the two number of nodes is 2h-1 - (h-2).

Here is a picture of the diagrams I drew to come up with the numbers in the table above:

I drew as little nodes as possible on the left subtree and drew as many nodes as I could on the right subtree.

# Answer
**I assume that we start labeling heights from $0$.**

Actually your approach is right. You must consider the left-side (or right-side) sub-tree with the least possible amount of nodes and the right-side (or left-side) sub-tree with the most possible amount of nodes, and both sub-trees must be AVL trees too. For this purpose, we fix the height of left-side sub-tree to $h-2$ (doing so, the bottommost node of this sub-tree would be at height $h-1$ of the main tree) and we fix the height of right-side sub-tree to $h-1$. Now, we should answer following questions:

1. What is the minimum number of nodes in an AVL tree of height $h-2$?
2. What is the maximum number of nodes in an AVL tree of height $h-1$?

**Answer to question 1:** By recursions and assuming that $n(h)$ is the minimum number of nodes of an AVL tree of height $h$ we can easily get: $$ \begin{array}{rl} n(h) &=& n(h-1)+n(h-2)+1\\ n(1)&=&2\\ n(0)&=&1 \end{array} $$

**Answer to question 2:** In this case, we're dealing with a perfect tree (which is an AVL tree too) and we must find the number of nodes in a perfect tree of height $h-1$.

So, the answer to your question would be: $$ 2^h - 1 - n(h-2) $$

As an example, if $h=2$, this formula returns $2$, which is not the value you have got, and I think that's because you start labeling heights from $1$.
> 6 votes

---
Tags: data-structures, search-trees
---


# Question
Title: In memory paging, how does the S.O. know where the page is in secondary Memory?
So every process has its own Page Table, the page table references the frame where the page is in physical memory and also has a valid-invalid bit that tells whether it is in physical memory or in secondary memory.

But how does the S.O. knows exactly where the page is saved when the valid-invalid bit it's off? Is there another table I'm missing? Or it just does a linear search through the whole SWAP space?

# Answer
The first thing is that when the page-table entry is invalid you are allowed to use all the other bits in the page-table entry for whatever you want. So, for example, you could use it to store an offset into the swap space, or a disk block number.

But that's actually not the whole story. Each process on most operating systems has some kind of segment map that describes for each valid range of *logical* addresses what's in that range. Ranges that contain read-only data (such as the code segment, usually) don't need to be swapped. Instead they can just be reread from the executable that contains them if they are needed again.
> 3 votes

---
Tags: memory-management, virtual-memory
---


# Question
Title: Proving DPATH is NP-complete by a reduction from HAMPATH
I have a language DPATH that I'm trying to complete is NP-complete.

```
DPATH = {<G, a1,...,an>|G is a digraph with a directed path that covers the sequence
a1,...,an}

```

All of the nodes in the sequence has to be visited exactly one time, but it doesn't matter in which order they are visited.

I am trying to show a reduction from HAMPATH to DPATH but I'm having some difficulties. When given input `<G, s, t>` I have to create a computable function f, that outputs `<G, a1,...,an>.` Can i say that a1 = s, and an = t, and that each node that the hamiltonian path goes through is labeled with a node from the sequence? My problem with this, is that what if the HAMPATH graph has more nodes than the sequence? Do I have to take this into account when creating the reduction?

# Answer
> 4 votes
Remember that given the HAMPATH instance, you are constructing the DPATH instance. As long as

* it's a valid instance of DPATH,
* it's a Yes-instance if and only if the HAMPATH instance is, and
* it's computable in polynomial time,

you can do whatever you want. So in particular, you get to pick how long the sequence is, you can pick any $a\_{i}$ to be $s$ or $t$ (though in this case you may want to think carefully how you ensure that these are the first and last vertices in the path - otherwise it might be hard to argue for the Hamiltonian path), you don't even have to have the graph $G$ in the HAMPATH instance be the graph $G'$ in the DPATH instance (I suggest that you look at something very close to it though).

In the spoiler below are some additional hints, but don't use them unless you're really stuck - you learn a lot less if you don't put in the effort and time.

> One thing you have to do is take the HAMPATH graph and make it directed. There is a very simple way to turn undirected graphs into directed graphs, and it can work here. Another is ensuring that $s$ is the start of the sequence and $t$ is the end. I suggest adding new vertices to be $a\_{1}$ and $a\_{n}$ such that you can only get out of $a\_{1}$ and only get into $a\_{n}$, but you still have to work out how to connect them into the graph - remember that you don't know whether $G$ has a Hamiltonian path, or where it is even if it does, so you have to take care of all possibilities.

---
Tags: complexity-theory, np-complete, reductions, hamiltonian-path
---


# Question
Title: Why is the throughput (performance) of the Aloha protocol ≈ 0.18?
I've read in a few places (like here that the throughput - that is, the amount of good useful messages relative to capacity - of the ALOHA protocol for networks is roughly 0.18%.

But its not clear how we arrived at that number.

Can someone explain it?

# Answer
This number is reached first by assuming that messages will be produced and sent according to a Poisson process.

$$P\[(N(t + \tau) - N(t)) = x\] = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^x }}{{x!}}$$

This means, that the probability of $x$ messages arriving for the given interval $\[t, t+\tau\]$ where $\lambda$ messages are expected to arrive, is equal to right side of the equation. In other words, if we are expecting 10 messages to arrive per hour, the chances of 6 messages arriving in an hour is roughly 6.3%.

Now, **messages sent by ALOHA need to be alone in order to make it to all other the nodes undisturbed**. In other words, no other nodes can be sending messages at the moment we want our message to be sent and must stay silent until our message is completely sent.

This means we want to find: $$P(exactly\space1\space\space message\space arriving) * P(exactly\space0\space\space messages\space arriving\space in\space next\space t)$$

The odds of exactly one message arriving is

$$P\[(N(t + 1) - N(t)) = 1\] = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 1 }}{{1!}} = \lambda\tau e^{ - \lambda\tau} = \lambda e^{ - \lambda}$$

The odds of 0 messages arriving for $t$ is:

$$P\[(N(t + 1) - N(t)) = 0\] = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 0 }}{{0!}} = e^{ - \lambda\tau} = e^{ - \lambda}$$

and together they make

$$\lambda e^{ - \lambda} \times e^{ - \lambda} = \lambda e^{ -2 \lambda}$$.

This function tells us the throughput of the Aloha for all values of $\lambda$. So which $\lambda$ offers the highest throughput? To find out, we take the derivative of $\lambda e^{ -2 \lambda}$ and get:

$$ e^{ -2 \lambda} - 2\lambda e^{ -2 \lambda}$$ set to 0 and solve for $\lambda$ and we get

$$\lambda = \frac{1}{2}$$

This means that in order to have the highest throughput (i.e. be most efficient) we should have an expected rate of incoming messages to be $\frac{1}{2}$ per timeslot.

And after all that, what is the maximum throughput that we get when we have an expected rate of $\frac{1}{2}$? Simply, plug it into our equation $\lambda e^{ -2 \lambda}$ and we get:

$$\frac{1}{2} e^{ -1} = 0.18393.... $$
> 5 votes

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


# Question
Title: Why is this language over {a,b,c} regular?
The language of all words over the alphabet {a,b,c} such that

* the number of as in the word
* minus the number of cs in the word

is divisible by three.

How is this language regular? Lecturer notes says that it is, and then provides no explanation at all. I tried drawing a DFA for it, but it just seems that the longer the word, the more states there will be and there could be an infinite amount, which is not allowed? Please help, thanks.

# Answer
> 6 votes
All you need to keep track of is the value "number of $a$s seen minus number of $c$s seen", modulo 3 – call that $X$. There are only three different values that $X$ can take. When you see the next character of the input, it's either $a$, $b$ or $c$. Think about how each one affects $X$ and you should be very close to a 3-state automaton that accepts the language you're interested in.

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


# Question
Title: Are cache contents specific to a process?
Suppose the L1 cache is filled up with data from some process. Now CPU loads another process. Does the new process share cache contents? Or the cache has to be invalidated completely in each context switch?

# Answer
> 7 votes
It depends, there are several kinds of caches.

Some caches, known as PIPT (physically indexed, physically tagged) operate entirely on the physical address. The cache subsystem is independent of virtual memory, so it doesn't matter which process is accessing the cache: all processes share all cache entries.

Some caches, known as VIVT (virtually indexed, virtually tagged) operate entirely on the virtual address. In this system, a cache entry is only valid for a given process. There are several ways to ensure that a cache entry will not be used in the wrong process:

* The operating system may flush the cache at each context switch. This requires no hardware support but is obviously inefficient unless context switches are rare.
* The operating system may assign disjoint sets of addresses to distinct processes. This again requires no hardware support, but is a heavy burden on the operating system (it means that the MMU is effectively as a mere MPU (memory protection unit)).
* The MMU and cache may contain an extra label which is set by the operating system to an identifier for the process that owns each page or cache entry. ARM and Intel call this label ASID (address space ID). Each cache entry is only valid for a virtual address with the matching label.
* There are also VIPT caches (virtually indexed, physically tagged). The physical tagging ensures that the cache entry will only be served to a request for the correct chunk of memory. The virtual index means that if a page is shared at different addresses in different processes, the cache entries will not be shared.

See the “Address translation” section in the Wikipedia article for more information on these kinds of caches.

Cache types typically vary between processor families within the same processor architecture. Even on a given processor, data and instructions caches may have different types, as can L1 vs L2 (and more) caches.

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


# Question
Title: Is the length of the shortest quine in a programming language computable?
The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of possible outputs.

This is a classical result and is easily proven; a proof outline appears in the Wikipedia article on Kolmogorov complexity.

My question is about a related complexity metric operating on programming languages rather than program outputs. A **quine** is a program that outputs its own source code (and nothing else). Every Turing-complete programming language is capable of formulating quines (by Kleene's recursion theorem). We can therefore define the **quine complexity** of a programming language as the length of the shortest quine possible in that language.

**Is the quine complexity a computable function on the set of programming languages?**

My gut tells me that it is not, but the standard approach used to prove the uncomputability of the Kolmogorov complexity metric does not seem to work here.

# Answer
> 2 votes
You need to formally define the computational problem. It appears that the input is "a programming language" and the output is the length of the shortest quine in that language. But how is the programming language specified? The only way I can think of is to specify it by giving the encoding of a Turing machine that interprets the language. So, then, our input is $\langle M\rangle$ and our output is $\min\\,\\{|x|\mid M(x)=x\\}$. This is uncomputable: it's uncomputable even whether $M(0)=0$

---
Tags: computability, optimization, kolmogorov-complexity
---


# Question
Title: Is there a problem that cannot be represented using graph?
It is obvious that the representational power of graphs are huge.
Is there a problem that cannot be represented using graph?

I have recently asked this question to my students and no answers came up. I could not answer this either.

For instance:
**Problem:** Finding the shortest path between two given cities in a country.
**Graph type:** Directed, weighted.
**Vertices:** Cities.
**Edges:** An edge $(i,j)$ indicates there is a way from city $i$ to city $j$ and weight of $(i,j)$ indicates the distance between cities $i$ and $j$.

**Problem:** Expressing your feelings using crayons.
**Graph type:** Directed, weighted.
**Vertices:** Neurons in the brain.
**Edges:** Values of electronic signals being transmitted among neurons.
**Output:** Interpretation of the signals by the brain.
(Just kidding)

**Edit:** *Problem* in this post means, **a problem that can be solved using computers**.

# Answer
It's trivial to encode natural numbers as graphs (represent $n$ by a path of length $n$, or by $K\_n$) so anything that can be represented as numbers can be represented as graphs.
> 4 votes

---
Tags: computability, graphs, computation-models
---


title: Sorting numbers in $O(1)$

text:
# Question
Title: Sorting numbers in $O(1)$
Here is an experiment I came up with (I don't have sufficient material to make it):

Say that, you have a list of $n$ numbers $L = \\{l\_1, l\_2, ..., l\_n\\}$.
And you have bars representing those numbers like so:

Say that, width of every bar is $w$.
Imagine a line, thatis made up of $n$ line segments, each of them are $w$ long, and they are enough to cover all the bars.
When any of the lines touches a bar, it sends a signal, declaring its ID.
ID of each bar correspods to its position.

If we are able to build a system as described above, we can release the whole line and store the signals respectively in an array, therefore have the real poisitons of each number we want to sort.

Therotically, when does it take more time and energy to sort $n$ numbers with this method than sorting $n$ numbers using a supercomputer?

# Answer
This is similar to what is known as counting sort. Whether your method is more efficient than other methods depends on the model of computation, which you haven't specified. For example, what if the dynamic range of the numbers is really large, say they are integers from $0$ to $2^{100}$? You could use some adaptive approach ("scanning" from top to bottom, stopping each time a number is reached), but it really depends on what your computer is allowed to do, and in practice you probably won't be able to pull it off. Counting sort is a conventional algorithm which uses a very similar idea in situations in which the dynamic range is small, in which case the algorithm is highly effective.
> 6 votes

---
Tags: algorithms, algorithm-analysis, time-complexity, sorting
---


title: Are Boolean functions Turing complete

text:
# Question
Title: Are Boolean functions Turing complete
A Boolean function is a function $f:\\{0,1\\}^n\rightarrow\\{0,1\\}$.

The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\\{0,1\\}$ to be flipped or to be left unchanged. The same can be said of $\mathrm{XOR}$ gates.

In this sense we can start with an initial machine configuration $\textbf{b}=(b\_1,\ldots,b\_n)$ such that $b\_i\in\\{0,1\\}$ and $\mathrm{XOR}$ it with successive values $\textbf{v}\_i$:

$ \textbf{b}\oplus\textbf{v}\_1\oplus\textbf{v}\_2\oplus\textbf{v}\_3\ldots $

Each state $\textbf{v}\_i$ would represent a permutation of some element in $\textbf{b}$. This process effectively mimics a Turing machine and assumes that there is some generator for the values $\textbf{v}\_i$.

So can we say that Boolean functions Turing complete?

# Answer
Informally, a (programming) language is Turing complete if every computable function has a representation. A general computable function accepts an input of arbitrary size. Boolean functions, on the other hand, accept an input of a fixed size. Hence Boolean functions don't even *qualify* as potentially Turing-complete.

The relevant notion of completeness here is a complete basis of connectives. A set of connectives ($k$-ary functions on Boolean values for arbitrary $k$) is *complete* if every Boolean function on $x\_1,\ldots,x\_n$ (for arbitrary $n \geq 1$) can be represented using the connectives. The following sets are complete: the de Morgan basis $\\{\lnot,\lor,\land\\}$ and the basis $\\{\lnot,\Rightarrow\\}$. In contrast, $\\{\lnot,\oplus\\}$ is not complete: it can only express linear functions.
> 9 votes

# Answer
strictly speaking as YF has answered, finite circuits cannot be Turing complete.

however its worth mentioning a lead in response to this question (and maybe what youre looking for) a closely related concept used quite widely in theory where circuits are used to compute functions in a way that is *stronger* than Turing complete.

namely, circuit families. a family of circuits can compute infinite languages. each input of size $n$ has an associated circuit/function $C\_n$ built via some method, not necessarily built via a TM! the circuit-languages computable by decidable TMs are known as *uniform* circuits and circuits not constructable within this class are known as *nonuniform*.
> 5 votes

---
Tags: turing-machines, turing-completeness, boolean-algebra
---