# Question
Title: Is repetition the origin of countability?
The original question was "Do all non-regular languages have an uncountable number of strings?".

How can someone prove that..? I am squeezing my head but I can't figure it out.

And the other side of the coin: is a language always regular, if it has a countably infinite number of strings?

A bit more generally: is repetition (DFAs) the origin of countability (and/or vice versa?) and if so, why?

Thank you in advance for your help.

# Answer
I assume by countability, you mean a set being countably infinite, like $\mathbb{N}$.

All languages over a finite alphabet are countably infinite, whether they are regular or not.

It's easy enough to show that we can encode any string in $\mathbb{N}$: just take map its letters onto $\\{1,2,\ldots\\}$ and interpret the string as a base-$(n+1)$ number for an alphabet with $n$ letters. (Starting at $1$ avoids the problems with multiple $0$s on the left side of a number). You can also use Gödel numbering, which is simpler but less efficient.

It's important to distinguish languages themselves from the set of languages:

* Any language over a finite alphabet is countably infinite (or finite)
* There are an uncountably infinite number of languages over any finite alphabet
* Any class of languages we describe with a finite representation (including DFAs, CFGs, Turing Machines, or even logic statements) is countably infinite. So there are more languages than we will ever have ways to talk about or describe.

So no, repetition is not the origin of countability. Even undecidable languages are countably infinite.
> 3 votes

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


# Question
Title: Show that PTIME and PSPACE is closed under Klenee star
How to show that PSPACE and PTIME are closed under Kleene star ? I can only show that NP is closed, but it is easy because we can use non-determinism to guess partition of word. In these two cases I don't have idea how to attack it.

# Answer
Suppose you are given a language $L$ in one of these complexity classes, and you want to decide $L^\*$ in the same complexity class. On input $x\_1 \ldots x\_n$ (where the $x\_i$ are *bits*), use dynamic programming to find out which substrings $x\_i x\_{i+1} \ldots x\_j$ belong to $L^\*$. Since there are only $O(n^2)$ such substrings, this will only cause a polynomial blow-up in the resources used.
> 1 votes

---
Tags: complexity-theory, computability, closure-properties
---


# Question
Title: 3✕n chessboard with holes - maximum number of knights not attacking each other
I'm trying to to create an algorithm (working in polynomial time) to solve the following problem:

What maximum number of knights that any two of them don't attack each other can be placed on a 3✕n chessboard with holes (knight can't be placed on a hole). Width of the chessboard (n) and positions of holes are given. Besides the maximum number of knights that can be placed, the algorithm should return their positions.

I think some dynamic programming techniques can be used here but I have no idea how to get a solution for bigger chessboard having a solution for a smaller one. What I make out about the problem so far is:

* the chessboard is a bipartite graph, where nodes are the normal (not holes) fields and edges are legal knight moves (white fields in the "left" set and the black ones in the "right" set)
* the maximum degree of a node is 4 (knight can move to maximum 4 fields because the width of chessboard equals 3).

# Answer
> 2 votes
Use dynamic programming to calculate the maximum number of non-attacking knights on the left $3\times m$ part of your board with holes, given the placement of knights in the last two columns of this part of the board.

---
Tags: graphs, dynamic-programming, bipartite-matching
---


# Question
Title: How an I prove if this language is decidable or not
In the context of computability and turing machines

Let $L\_1$ be an undecidable language and $L\_2 = \\{n \in \mathbb{N} | \exists x \in L\_1 |x| \geq n\\}$

How can I prove if $L\_2$ is decidable or not?

I guess $L\_2$ is not decidable in general and it depends on $L\_1$ but still nothing proved. \

# Answer
> 1 votes
Consider two cases:

* $L\_1$ is finite, and so there is a word of maximal length.
* $L\_1$ is infinite, and so there are words of arbitrarily large length.

Try to see if you can decide $L\_2$ in these two cases.

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


# Question
Title: Is the set of all possible finite alphabets uncountable?
In my opinion it is uncountable since we can think every natural number as a member of one alphabet like $\quad0\in\sum\_0 ,1\in \sum\_1, ... \quad$ And there are also other symbols than natural numbers in alphabets. So there is no possible 1:1 and onto mapping from set of all alphabets to natural numbers. Thus they cannot be enumerated which means they are uncountable. Is there anything wrong with my approach?

# Answer
Your approach can essentially be summarized as:

1. I define an injection between $\mathbb{N}$ and my set $S$.
2. This injection is not a bijection because some elements of the codomain are left unmapped.
3. Therefore there exists no bijection between $\mathbb{N}$ and $S$.

Stated like this, it is perhaps clear that the last statement does not follow from the others. An example of where this reasoning would fail is if we let $S = \mathbb{Z}$ and let the injection be the identity function (mapping naturals to themselves). This leaves all the negative integers in the codomain unmapped, but we know that $\mathbb{Z}$ is countable.
> 1 votes

---
Tags: formal-languages
---


title: Computing tree alignment distance

text:
# Question
Title: Computing tree alignment distance
I am implementing the dynamic programming algorithm for computing tree alignment distance as described in "Alignment of trees — an alternative to tree edit". But I got stuck in lemma 3 on page 141 (page 5 of pdf). The notations are given at the beginning of section 2. The last case in lemma 3 says

However, there is no recurrence formula given to compute . How did we obtain this?

I don't think the following holds either: ?

# Answer
If I understand the paper correctly (and I might not), the solution seems to be described in Section 2.2 of the paper. It says "we have to compute $D(F\_1\[i\],F\_2\[j\_s,j\_t\])$..." and then it goes on to describe a strategy for doing so (namely, the Procedure 1, as described in Figure 2).
> 0 votes

---
Tags: algorithms, trees, dynamic-programming
---


# Question
Title: Formally proving properties of fold function
Recall the fold function for lists:

$fold(f,z,\[x,xs\]) = fold(f,f(z,x),xs)$

$fold(f,z,\[\]) = z$

I want to formally proof that if $f$ is associative, commutative and idempotent (meaning $f(x,y) = f(x,f(x,y))$ and we have to lists $l\_1$ and $l\_2$ such that their contents are equal then $fold(f,z,l\_1) = fold(f,z,l\_2)$.

**What I've tried**

1. I've tried double induction on the sizes of the list but this doesn't clarify much the problem.
2. I've figured out a procedure that would leave me with a list of non-repeating elements. I take each element of the $f(f(f(\cdots)))$ list and take it to the outside thanks to associative and commutative property. En each step I make sure that if I find two equal elements I remove them using idempotence. The basic rules are as follows:

$f(f(z,x),y) \text{ push x out, push y in} = f(y,f(z,x)) = f((y,z),x) = f(f(z,y),x)$

$f(f(z,x),x) = f(z,x)$

The actual transformation to the list would look like this:

```
     def transform[A](l: List[A]) := l match {
        case Nil() => Nil()
        case x :: Nil() => x :: Nil()
        case x :: x :: xs => transform(x :: xs)
        case x :: y :: xs  => y :: transform(x :: xs)
     }

```

My first problem is how to write the predicate to say that this algorithm gives a list with non-repeating elements. I do it like this:

$\forall x,y. x \in l \land y \in l \land x = y \implies index(x) = index(y)$

But I don't how to proof that my algorithm guarantees that this property holds.

3. The idea is that if I can proof that this transformation does not leave repeating elements then it would be easy to show that the lists end up with equal lengths and for each first element of one list I could transform the second list to get the very first element and I could apply induction to show that the statement holds.

So in short, if you think my approach is efficient and correct do you know how to solve the problems I got? And if you think you have better ideas can you give me any hints?

**Edit**

Just realized that my function only eliminates one repeating sequence. So adapt the argument...

# Answer
"contents are equal" implies that their lengths are equal, so you don't need double induction. Instead, try single induction. A straightforward induction argument on the length of the list should suffice.

I wouldn't suggest trying to remove repeated elements. That is not necessary, and it is an unnecessary complication that turns a simple induction into something really complicated and messy (as you have discovered).
> 2 votes

---
Tags: functional-programming, first-order-logic, software-verification
---


title: parsing left linear CF grammars

text:
# Question
Title: parsing left linear CF grammars
In **Introduction to Formal Languages** by *György E. Révész* a polynomial time algorithm that can convert a left linear grammar to a right linear one is presented.

Trying to understand when it is useful I read that *left linear grammars* are generally harder to parse than *right linear grammars*.

Is this statement true?

I'm asking because I would say that there is no difference between recognizing the two in terms of hardness, but I found arguments about a difference between them.

In particular in these slides on page 8, the author argues that "left linear grammar are evil" and provides the following example:

Grammar

A → Babc

B → Cb | D

...

with $w = abbabc $.

The motivation seems to be that after checking for abb**abc** it is necessary to check the first part **abb**abc if can be derived from B that has 2 rules associated: Cb and D, while it could be done easily with a right linear grammar.

# Answer
> 2 votes
Left- and right-linear grammars define regular languages, and it is straight-forward to convert the grammar into a form appropriate to build an NFA which can recognise the language.

That doesn't say anything about the ease of *parsing* the grammar, in the sense that parsing transforms a string into a parse tree which relates the various syntactic parts of the string. While we can prove that the regular language can be recognised in linear time and constant space, we cannot say much about the parse tree because there is no guarantee that the parse tree for a given string is unique. In other words, left- and right-linear grammars can be, and often are, ambiguous.

What we can say is that the transformation from left- to right-linear form does not preserve the parse tree; if the intention was to build a particular parse of each string, then the transformation will not help us.

Left-linear grammars cannot be parsed with an LL(k) parser, because no left-recursive grammar can be. However, there is no guarantee that the transformed right-linear grammar will be amenable to LL(k) parsing.

Either a left- or a right-linear grammar might be LR(1), although there are no guarantees. (But every LL(k) grammar is LR(k) so a grammar which is not LR(1) is also not LL(1).) If the intention is to parse, and not just recognise, it seems reasonable to use a grammar which actually reflects the intended syntactic structure, to the extent possible given the constraints of different parsing algorithms.

While it is evident that there are people who feel that their failure to understand the LR parsing algorithm somehow makes it less valuable (or even "evil"), that is not borne out by any objective metric: LR(k) parsers run in linear time and space, just like LL(k) parsers, and can be constructed in polynomial time if the grammar is LR(k). There are readily available tools which will compute the necessary tables for an LR(1) parser, and the parsing algorithm itself, given the tables, is just a few lines of simple code.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: $\text{MOD}_{2017}(x_1, \ldots, x_k)$ computable by bounded depth polynomial size circuit in basis $\{\neg, \text{MAJ}\}$?
Now, I have the following conjecture.

> $\text{MOD}\_{2017}(x\_1, \ldots, x\_k)$ is computable by a bounded depth polynomial size circuit in the basis $\\{\neg, \text{MAJ}\\}$.

However, I am at a loss at how to realize/see this. Could anybody help me out?

# Answer
Consider what happens when you feed into a majority gate the the inputs $x\_1,\ldots,x\_k$ and $k-1$ zeroes. You get an $\mathsf{AND}$ gate. If you feed into it $k-3$ zeroes, you get a gate corresponding to $x\_1+\cdots+x\_k \geq k-1$. Using similar ideas, you can construct a constant-depth circuit over the basis $\\{\lnot,\mathsf{MAJ}\\}$ that computes $x\_1+\cdots+x\_k = \ell$ and so $\mathsf{MOD}\_{2017}$.

If you're not allowed to use constants but there is a tie-breaking rule for $\mathsf{MAJ}$, then you can implement constants using $\mathsf{MAJ}(x\_1,\lnot x\_1)$, whose constant value will depend on the tie-breaking rule.

If you're not allowed to use constants and every majority gate needs to have an odd number of inputs, then it is generally not possible to construct such a circuit. Indeed, suppose that you plug $x\_i = x\_1$ for all $i\>1$, and that $k$ is chosen so that the output is constant whatever the value of $x\_1$ is (this depends on your definition of $\mathsf{MOD}$, which you haven't supplied). On the other hand, you can prove by induction that every gate computes either $x\_1$ or $\lnot x\_1$, and in particular not a constant function
> 2 votes

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


title: About the spaces between bits

text:
# Question
Title: About the spaces between bits
Let's say I have three functions and each gives true/false answers. The first one gives 2 booleans, the second 6 and third 4. Are they written like this: 01 110010 1000? Do they get spaces between the functions? If so, do the spaces count as data? What I wanna know is, if you send an encryption key using RSA, how does RSA recognize the length of your key with the spaces? Another way to put it is if a symmetric key has 256 functions of one bit each (0 1 1 0 0 1 0, etc.) would it end up being 512 bits long because of the spaces?

I'm new in computer science and I'm learning for fun by myself. I apologize if my question is the smh type.

# Answer
> 2 votes
First of all, encoding is up to you — you get to decide the answer to the question you state.

Let's consider a more generic situation, in which you want to serialize (convert to bits) a sequence of values $x\_1,\ldots,x\_k$. If you know ahead of time what the length of $x\_i$ is, then the most efficient encoding would be to put together all the bits of all values (no spaces!). (In practice, we also need to pack them into bytes, since data is passed around in byte chunks.)

If you don't know the length in advance, then there are several option. One option is to use some self-terminating encoding. For example, you could preface each bit by 0, and end the stream by a 1. A 2-bit string $b\_0b\_1$ would be encoded by $0b\_00b\_11$. Such an encoding is not very common. Another option is to store the length somewhere — this is quite common. For example, JPEG files store the dimension of the picture in a header. A third option is that the length, while not predetermined, is one of very few options. In that case it suffices to store just the index of the option in some header. This is probably what happens in cryptographic protocols.

Finally, there seems to be a basic misunderstanding in your question. Information is passed around in bytes. When you have a stream of bits, you pack them into chunks of 8 bits and send them in that way. There are only two options for bits — they can be either 0 or 1. What beginners sometimes do is send the bitstream as an ASCII or Unicode string, which does accept 0s, 1s, and spaces (as well as many other letters). However, this is very wasteful, spending at least 8 bits per one input bit.

---
Tags: computability
---


# Question
Title: Precise definition of oracle classes $A^B$
I was reading in Papadimitriou's "*Computational Complexity*" book Chapter 14, about Oracle Machines. Papadimitriou defines, in definition 14.3, page 339-340, Oracle Turing Machines with oracle a *language* $A \subseteq \Sigma^\*$:

> The computation of $M^{?}$ with oracle access $A$ in input $x$ is denoted $M^A(x)$.

So far so good.

In the next paragraph, he writes:

> If $\mathcal{C}$ is any deterministic or non-deterministic *complexity class*, we can define $\mathcal{C}^A$ to be the class of all languages decided by machines of the same sort and time bound as $\mathcal{C}$, that have oracle access to $A$.

My question is:

> Given any complexity class $B$ and $C$, can we *always* define $B^C$?

This is motivated by a question I posted (and deleted) at TCS.stackexchange where , using Papadimitriou's notation, I defined $B^C$ for a complexity class $B$ and $C$ but I received criticism (besides the context of the question) that *I am not allowed to do that because oracle is not an operation defined on languages* and hence complexity classes. Does this contradict the extract from Papadimitriou's book (where he explicitly defines $B^C$ for a \_complexity class $B$)?

My understanding is that

> We can define $B^C$ for a complexity class (i.e., a set of languages) $B$ if $B$ can be defined by a Turing Machine model.

If yes, why it is not explicit in Papadimitriou's book?

# Answer
The simplest case is when $C$ has complete problems with respect to $\mathsf{F}B$ reductions (the function class corresponding to $B$). In that case, you can define $B^C$ as $B^L$ for some $C$-complete problem $L$, and everybody will be (mostly) happy, at least if $B$ is not a very weak class. This allows us to define $\mathsf{P}^{\mathsf{NP}}$, for example.

When $C$ doesn't have complete problems, sometimes the following definition is used: $B^C = \bigcup\_{L \in C} B^L$, or perhaps $B^C = \bigcup\_m \bigcup\_{L\_1,\ldots,L\_m \in C} B^{L\_1,\ldots,L\_m}$. However, this definition doesn't necessarily have the right properties.

Another option is if you can enumerate all languages in $C$ (for example, $\mathsf{BPP}$ can be enumerated using probabilistic Turing machines with an explicit time bound), say they are $(L\_n)\_{n \in \mathbb{N}}$. In that case you can define $B^C = B^{L\_1,L\_2,\ldots}$, where the oracle for $L\_1,L\_2,\ldots$ accepts an index $i$ and a word $x$, and outputs whether $x \in L\_i$. One drawback is that this definition depends on the enumeration; it's best to use a "natural" enumeration. Otherwise, you can "cheat" by putting information into the enumeration. A way out it to define $B^C$ as the intersection of $B^{L\_1,L\_2,\ldots}$ for *all* possible enumerations.

Things become even more complicated when $B$ is weak. For some of the issues involved, see Aehlig, Cook, and Nguyen, Relativizing Small Complexity Classes and their Theories. These issues are orthogonal to what we have described above: they cause problems even when trying to define $B^L$ for a *language* $L$.
> 3 votes

---
Tags: complexity-theory, computability, computation-models, complexity-classes, oracle-machines
---


# Question
Title: Does a PDA follow a transition if the top stack symbol doesn't match?
Does a PDA only move states when both the input symbol matches and the symbol on the top of the stack matches?

In other words, is it possible to have two different transitions that both take the same input character but pop different stack symbols?

For example if we have a state `Q0` with the two following transitions:

`a, a -> b
 a, b -> a`

I know that a PDA will transition in regards to the input symbol but how does it handle the stack symbol that it is trying to pop?

For some reason I can not find the answer to this simple question for the life of me. I have searched and searched in my textbook and online.

# Answer
TL;DR: No, it does not.

I would guess that your notation `a, a -> b` means the syntax in a PDA transition such that **if** we read a character `a` from the input **and** we pop a character `a` from the stack, then we **put** a character `b` on top of the stack.

The notation of that transition that I'm used of is written as $$q\xrightarrow{\text{e,d;u}}r,$$

where the left side of the semicolon is what we read, i.e. character `e` from the input and character (or symbol) `d` from the stack. Right side of the semicolon is what we put onto the stack: `u`.

In order for your PDA to follow a transition, it has to match **both** of the conditions on the **left side** of the above notation. So, your PDA won't follow that particular transition if the stack symbol doesn't match.

What comes to your second question about having two different transitions with same input but different stack symbol, yes, that is possible based on **nondeterminism**, but your PDA still has to meet both conditions in the left side of the notation in order to move anywhere.

Hope this had any help!
> 3 votes

# Answer
No to the title, Yes to the question in the description. The domain of the transition function $\delta$ of the PDA is given by $$Q\times (\Sigma\cup\\{\epsilon\\})\times(\Gamma\cup\\{\epsilon\\})$$

The input of the PDA is thus a 3-tuple $(q,a,b)$, where $q\in Q, a\in\Sigma\cup\\{\epsilon\\}, b\in\Gamma\cup\\{\epsilon\\}$.

If the character at the top of the stack is different, the input to the transition function is different, and it can give different outputs in each case. You can have, as per your example, something like

$$\delta(q\_0,a,a)=(q,b)$$ $$\delta(q\_0,a,b)=(q,a)$$

where $q\_0,q\in Q$ and $a,b \in \Sigma$ and $a,b\in \Gamma$.

Such examples are often found in the transition functions, such as in this example.

The transition is not with regards to just the input symbol, it depends on all the three values, the state, the input symbol, and the symbol on the top of the stack, which form the input.
> 2 votes

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


# Question
Title: recognize strings of 1's and 0's which are multiples of 3
Construct a minimized Deterministic Finite Automaton that recognizes strings of 1's and 0's that are multiples of 3.

This was one of the questions asked in my cycle test.

What would be a correct interpretation to this question?

1. Strings having a number of 0's and 1's that are multiple of 3, e.g.`000111`, `011010`
2. Strings of 0's and 1's which in binary notation is a multiple of 3, e.g. `11`, `110`
3. Or any other radix notation, taking 0's and 1's, and checking if they are multiples of 3

# Answer
If the question intends anything other than your option 2 (binary representations of natural numbers that are divisible by 3), then it is a badly written question.

If the qeustion meant strings in which the number of 0s and the number of 1s are both divisible by 3, it would have said that. It would be bizarre to have numbers whose digits are all 0s and 1s and intend some base other than binary without mentioning that.
> 1 votes

# Answer
To answer your question, I would go for option 2. But:

I think that's a badly written question without a clear interpretation.

I had a similar type of task in a course related to this, the task was about constructing a DFA for a language that accepts strings of a's and b's, where the amount of a's is divisible by 2 but not by 3.

In the case where the alphabet consists of characters the interpretation is clear in my opinion (in this particular task setting), but talking about "strings of 0's and 1's" is confusing.
> 0 votes

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


# Question
Title: Constructing a PDA for the language $\{ 0^n 1^m | n ≠ m \}$
Could anybody help me design a PDA for the language $\\{ 0^n 1^m | n ≠ m \\}$?

Here is what I currently have:

# Answer
Hint : try to construct two PDA's for languages given below $$ \\{0^n1^m : n \> m\\}, \quad \\{0^n1^m : n \< m\\}. $$ Now combine the two PDA's for the language $$ \\{0^n1^m : n \ne m\\} $$
> 1 votes

# Answer
I quickly constructed and tested a PDA for this. It consists of three states:

* $q\_0:$ This is the initial state of the PDA. We stay here as long as we read 0's from the input. Every time we see a 0, we also put a 0 onto the stack. **If** the input starts with a 1, we make a transition straight to $q2$, and stay there as long as we read 1's. In this case the string will be accepted since there were no zeros; the amount of 1's can be anything (else than $\epsilon$). **ALSO** if we reach the end of the input and there is a 0 in the stack we can also move straight to $q\_2$: this is the case where there are only 0's in the input; will be accepted.
* $q\_1:$ We move to this state with a transition from $q\_1$ if we read a 1 and there is a 0 in the stack: this means that the input has both 0's and 1's. We stay in this state as long as we read 1's. **The decision** for accepting the string is based on the stack. **If** we reached the end of input (i.e. read an $\epsilon$) **AND** the stack is **empty**, then the string will be rejected, because this means that the amount of 1's and 0's were the same, which was not to be accepted. In the other case, where we reach the end but there is a 0 in the stack, we can move to the state $q\_2$ because we know that now the amount of 1's is less than that of 0's. In addition, if the stack is empty and we still read a 1, we can also move to the state $q\_2$: this indicates that there are more 1's than 0's; can be accepted.
* $q\_2:$ This is the final state of the PDA. We will read 1's and stay in this state as long as there is input left: we already know that the string will be accepted; the amount of 0's is either $\epsilon$ or less or more than that of 1's.

This PDA is of course nondeterministic but solves the problem nonetheless. Hope this helps you build the PDA!
> 0 votes

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


# Question
Title: Is there a language for which any string (that works) can be shown to not be pumped using the Pumping Lemma?
Of course, whenever the Pumping Lemma for Regular Languages (or CFLs) is applied to a language $L$, only a single string $w \in L$ and $|w| \ge p$ needs to be picked (to eventually show that $w$, when pumped, leaves the language).

Is there a non-regular (or non-context-free) language $L$ for which *every* string $w \in L$ having $|w| \ge p$ can be used to derive a contradiction?

# Answer
> 4 votes
I'd say the language $L = $ { $0^n1^n | n \> 0$ } fits the bill for the Pumping Lemma for Regular Languages. Any substring to be pumped would consist either of all the same symbol, in which case pumping up produces a string with an unequal number of $0$'s and $1$'s, or it contains instances of both symbols, in which case pumping up produces a string with a $1$ followed by a $0$; in neither case is the pumped-up string in $L$.

# Answer
> 0 votes
I'm not sure if I quite understood the question properly, but:

If a language $L$ is non-regular, then it might be context-free and in this case a contradiction can be provided as you explained for regular languages.

If a language is known to be non-CFL, then I would say there's no point of proving anymore that that language is not context-free. But if you want to do it again for any string $w$ in that language, at least the string must be able to be presented in the form $$w = uvwxy,$$ such that

* $|vwx| \leq l$, or the middle part of the string between $u$ and $y$ isn't very long
* $vx \neq \epsilon$, or at least another of the parts to be pumped $v$ and $x$ is not empty
* $uv^kwx^ky ∈ L$ for every $k ∈ \mathbb{N}$, or we can pump them in balance for an arbitrary amount $k$ and still belong in the language $L$.

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


# Question
Title: Generating uniform random connected graphs: doubt about Wilson's algorithm
I want to generate a random connected simple labeled graph with $n$ vertices and $m$ edges, selected uniformly over all connected graphs with such $n$ and $m$. I found this approach. It says: build a random spanning tree using a loop-erased random walk (also called Wilson's algorithm); then add remaining $m-n+1$ edges between random pairs of vertices.

I implemented and investigated this algorithm and have several doubts.

First, what do they denote with *random spanning tree* in the first part? A random spanning tree of $K\_n$? If so, there are $n^{n-2}$ of them, so we may directly restore the tree by its (random) Prüfer sequence. Why do we need the loop-erased random walk here? As far as I experimented it gives the same distribution as the Prüfer-based generation.

Second. If I'm right at the first part and each tree is equiprobable, then different graphs may have different probabilities. For example, if $n=4$ and $m=4$, we have two graphs (I skipped the labels as they are irrelevant here):

```
o--o    o---o
|  |    |\ /
o--o    o o

```

The first one can be produced from some spanning tree in 4 distinct ways, while the second one only in 3 ways. If all trees are equiprobable, this obviously introduces bias in graphs.

Where is my mistake? I don't understand Wilson's algo and the distribution on trees is not uniform, or I don't understand the latter part, or this algorithm is in fact incorrect?

Finally, if it is incorrect, how does one generate a random connected graph? The approach of generating a random graph and checking its connectivity fails if $m = \Theta(n)$.

P.S. When saying about randomness, I assume that I have an oracle which returns me a uniform random number in range $\[0, n)$ for a reasonable $n$.

# Answer
> 4 votes
Here are two alternative algorithms. There are probably better ones.

**Large $m$** When $m \gg \frac{1}{2} n\log n$, it is very likely that a $G(n,m)$ random graph will be connected. Generate $G(n,m)$ graphs until one of them is connected.

**Small $m$** When $m$ is small, you can try the following algorithm, which however might be a bit slow (or perhaps very slow). Generate a random graph according to the stackoverflow procedure, calculate the number of $T$ spanning trees it has, and accept with probability $1/T$. You can check that this produces a uniform sample, though the expected running time is $n^{n-2}\binom{(n-1)(n-2)/2}{m-n+1}/G\_{n,m}$, where $G\_{n,m}$ is the number of connected graphs on $n$ vertices and $m$ edges.

You can speed up the algorithm by sacrificing the accuracy of the sample. Find a number $M$ such that "most" graphs generated by the stackoverflow algorithm have at least $M$ spanning trees, and accept with probability $\min(M/T,1)$. You can estimate $M$ by sampling.

---
Tags: graphs, pseudo-random-generators, random-walks
---


# Question
Title: What is the best algorithm to match a student's schedule with a tutor's schedule?
I am building an application (RoR framework) that can help to match a tutor and a student based on their subjects, budgets, locations and freetime. I have done the first three parts(subjects, budgets, locations). Now, I am getting stuck at the most difficult one which is freetime matching.

**The student's sample freetime**:

```
Monday: 7AM-8:30AM
Wednesday: 6AM-8AM
Friday: 9AM-10:30AM

```

Now I want to match this student with a list of tutors who have the freetime that can match with the student's freetime. In addition, each session between a student and a tutor must be 90 minutes.

For example, the following is **the tutor's freetime**:

```
Monday: 6AM-9AM => matches because both the student and tutor can start their session at 7AM, and when the session ends at 8:30AM, it is still in the range of the student's freetime and tutor's freetime.
Tuesday: 7AM-10AM => doesn't match, of course.
Wednesday: 7AM-9AM => doesn't match because both of them can start their session at 7AM, but when the session ends 8:30AM, the student's time is already over.
Friday: 10AM-11:30AM => matches, like the case in Monday.
=> Conclusion: this tutor doesn't match with the student since he just matches 2 out of 3 days with the student (Monday and Friday)

```

I tried to use Hash data structure to solve the problem.

```
student_freetime = { monday: { start_time: 7, end_time: 8.5 }, wednesday: { start_time: 6, end_time: 8 }, friday: { start_time: 9, end_time: 10.5 } }

tutor_freetime = { monday: { start_time: 6, end_time: 9 }, tuesday: { start_time: 7, end_time: 10 }, wednesday: { start_time: 7, end_time: 9 }, friday: { start_time: 10, end_time: 11.5 } }

```

However, I think this is a bad solution since I need to use loop and if many times.

Therefore, I have been searching for the best solution for this problem, and found some suggestions on using the Hopcroft–Karp algorithm on stackoverflow. However, I've never implemented graph related algorithm before, so I am not sure the Hopcroft–Karp algorithm is the best choice in my case. As I understand, to implement Hopcroft–Karp algorithm first I need to create to have 2 sets of data. In this case, I think the first set would be the student's freetime in a particular day, and the second set would be the tutor's freetime in the same day. But at this step, I am wondering how can I match their time by using Hopcroft–Karp algorithm as I pointed out above, their freetime can be different and still match as long as it satisfies the session's limit time (90 minutes). I would be appreciated if anybody could give me some suggestions here or point me to the right resources/similar problems.

# Answer
This sounds like an instance of the assignment problem (see also our tag). You can also view it as a bipartite matching problem. There are standard algorithms for these problems; I suggest you use one of them. Hopcroft-Karp is one of those standard algorithms. I suggest that you either look for an existing implementation of one of those algorithms, or study them and implement themselves.

Expressing this as a network flow algorithm or as an instance of linear programming might provide extra flexibility to deal with additional constraints.

The specifics of how to express your problem as an instance of these problems will depend on the specific constraints you want to impose (e.g., is there a limit on the number of students you want to assign each tutor to? is it ok to limit things to a set of non-overlapping 90-minute time slots?), which you haven't specified in the question, so it's hard for us to say much more.

I suggest you try applying one of those approaches to your specific problem, study one of the standard algorithms, and if you get stuck understanding some specific aspect of the problem, ask a new question where you ask about that specific difficulty.
> 2 votes

---
Tags: algorithms, graphs, bipartite-matching
---


title: Construct a DAG using Tarjan

text:
# Question
Title: Construct a DAG using Tarjan
This is a question related to a homework assignment so I guess I'm asking for hints, if that's ok? Basically, I'm wondering if there is some way to use Tarjan to compress the nodes in every SCC found into one single node, essentially producing a DAG. The problem I'm faced with is that every SCC is obtained as a set but I can't seem to find a way to preserve the edges leading out of the SCC.

# Answer
Construct a new graph whose vertex set is the strongly connected components. Now go over all edge in the original graph, and if they connect two different strongly connected components, add the corresponding edge to the new graph if it's not already there.
> 2 votes

---
Tags: graphs, dag
---


# Question
Title: What machine learning techniques work on ASTs?
I am interested in experimenting with machine learning on the ASTs of programming langauges (e.g. some Java code). I would like to develop an algorithm that determines if a given AST satisfies some predicate. I have a training set of programs that do and do not satify the predicate.

The machine learning techniques that I am aware of operate on vectors or matricies. Are there techniques that operate on trees?

# Answer
> 1 votes
Your problem can be solved by existing machine learning methods. So, instead of searching for new technique you should choose from existing techniques. The main part of your problem which separates it from general machine learning problems is AST data which will act as input to your algorithm.

There are a lot of feature extraction techniques available which will help you convert AST data into usable format. I would suggest doing tree traversals to generate a feature vector from your AST and then applying machine learning techniques on it.

# Answer
> 0 votes
Probably due to recent popularity (and relative accessibility) of certain algorithms, like neural networks, we often think of "machine learning" as being about heavy statistical/numerical algorithms. The Machine Learning Wikipedia page mentions that machine learning is often conflated with data mining. As that page demonstrates, there are other facets to it. In particular, there's the "programming-by-example" community with one of the tools being inductive logic programming (ILP) or inductive programming in general.

You should browse the Machine Learning Wikipedia page for other algorithms, and I'm not suggesting that you couldn't apply a more numerical algorithm like neural networks to this problem, but at least some forms of ILP seem like they would be a good fit. Essentially the goal there is to learn a logic program that correctly classifies examples given positive and negative examples. A logic program is just a collection of predicates.

---
Tags: machine-learning
---


# Question
Title: Generating a random path in a grid without deadlock
I want to write an algorithm that takes an $n \times n$ grid and a number $L$, generate a random walk of length $L$ on the grid that doesn't visit the same cell twice.

One simple solution would be keep randomly choosing a neighbour of the last cell to add to the path. I found that for small density (i.e. $L \< 0.625n^2$), I can repeat this algorithm a large amount (at least $1000$) times and can almost find some complete path without deadlock, i.e. without a a state where the path is incomplete but there is no more move available (i.e. all neighbours of the current cell is already filled). A DFS can lead to a deadlock state, and from my experiments, most of the end states are deadlocks, hence it is very hard to get to a complete state with DFS. But for larger density, it is nearly impossible to avoid deadlock no matter how many times I repeat.

My second attempt is to backtrack one step if the current $i^{th}$ step results in a deadlock (i.e. delete the last action from the list of possible actions at $(i-1)^{th}$ step and randomly choose a remaining action to retry). However it apparently took forever to finish the path (it kept going forward and backward when $i$ reaches $0.625n^2$).

Is there any suggestion for a fast algorithm that have fairly high probability of avoiding deadlocks? I'm fine with pseudo-randomness.

# Answer
You have a solid grid graph, and want to generate a random Hamiltonian path in it. The following paper describes a polynomial-time algorithm to generate such a path, randomly (from a distribution that is close to uniform):

Self-testing algorithms for self-avoiding walks. Dana Randall, Alistair Sinclair. Journal of Mathematical Physics, vol 41 no 3, pp. 1570–1584, 2000.

Be warned that the algorithm is fairly complex.

Here is a more recent paper that also proposes an algorithm to solve this problem:

Secondary Structures in Long Compact Polymers. Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen, Jane' Kondev. arxiv.org:cond-mat/0508094

On cursory inspection, it looks like it might be easier to implement.

---

Other related work that might possibly be of interest:

The following paper proposes an algorithm to *count* the number of such Hamiltonian paths:

A matrix method for counting hamiltonian cycles on grid graphs. Y. H. Harris Kwong, D. G. Rogers. European Journal of Combinatorics, vol 15 no 3, pp.277-283, 1994.

I found a reference that claims that the following paper describes

Enumeration of tours in Hamiltonian rectangular lattice graphs. Basil R. Myers. Mathematics Magazine, vol 54, no 1, Jan 1981.

Often, if you can count the number of objects of a particular type, you can sample uniformly at random from the set of such objects. So, that would be a good starting point to look, if you don't like either of the two papers mentioned above.

The following paper describes how to find *a* Hamiltonian path of such a solid grid graph (but with no guarantees of any particular random distribution on the output):

Hamiltonian Cycles in Solid Grid Graphs. Christopher Umans, William Lenhart. FOCS 1997.

See also https://mathoverflow.net/q/1592/37212, https://stackoverflow.com/q/7371227/781723, Hamiltonian path in grid graph.
> 1 votes

---
Tags: algorithms, graphs, search-algorithms, randomized-algorithms, random-walks
---


# Question
Title: Is it possible to submit every March Madness bracket?
A few years ago Warren Buffett started offering $1 billion to anyone who could correctly predict the winner of every game in the NCAA men's basketball tournament. A 64 team (we won't count the first four play-in games) single-elimination tournament bracket like "March Madness" has 2^63 possible bracket combination, putting the odds of correctly predicting a perfect bracket around 1 in 92 quadrillion.

But what if I don't want to leave this up to chance or skill? If I wanted to submit all 2^63 possible brackets to ensure that I submitted a winner, how improbable is this? I see two limiting factors - computational time and storage space, although I might argue that this is possible.

My question is two-fold:

1. Given current computing limitations, how long would it take to compute all possible brackets? Particularly, how long would it take to compute one bracket, and how quickly could the fastest computer compute them all?
2. How much space would storing these brackets take, and is it a feasible amount of storage?

For 2, my guess is that it's a lot of data, but it's feasible. A bracket can be represented by 63 bits, each bit representing a game in the tournament and the 1 or 0 signifying whether the high or low seed won. Thus we have 2^63 brackets, each at 7.875 bytes each, for a total of roughly 72.6 exabytes of data. Given that Google is estimated to have between 10-15 exabytes of data, this is an absurd amount of data but not out of the realm of storage possibility.

# Answer
> 6 votes
The rate-limiting factor is the cost of *submitting* each of those $2^{63}$ combinations. Since submitting a combination probably requires (at minimum) opening a network connection and sending the combination to a remote server, you can generate combinations a lot faster than you can submit them. Similarly, the cost of storing the submissions is probably negligible compared to the time it takes to submit them all.

In particular, if it takes one second to submit a proposed combination, it will take you $2^{63}$ seconds to submit all $2^{63}$ of them. That's about 21 times the age of the universe. If it takes you one millisecond to submit a single combination, it will take you $2^{63}/1000$ seconds to submit them all -- that's about 300 million years. Obviously, not possible within your lifetime.

Also, note that the contest rules specified a maximum of one entry per person, as well as a maximum of 15 million submissions (not 15 million per person; 15 million total -- once there have been 15 million combinations submitted, the contest closes). Consequently, your proposed strategy simply wasn't possible. The creators weren't dumb: presumably, they thought of that and made sure it wouldn't happen.

---
Tags: program-optimization
---


title: Why are there only 2^i configurations?

text:
# Question
Title: Why are there only 2^i configurations?
In the proof of TQBF-complete, it says if the input size is i, then the TM for the input has at most 2^i numbers of configuration. Can someone explain why? The proof is from: http://zoo.cs.yale.edu/classes/cs468/fall12/TQBF-complete.pdf

# Answer
> 1 votes
Let $s(n)$ be the space used by Turing machine, $\Sigma $ is a input alphabet, $Γ$ is tape alphabet ( $Σ ⊆ Γ$ ) and $Q$ is a finite set of states. Then maximum number of different configuration bounded by $|Q| \times| Γ|^{s(n)}\times s(n)$. You have $s(n)$ many places and in each place you have choices and then you can derive the expression very easily.

# Answer
> 1 votes
I don't know which proof you're referring to, but i'd expect it's because the input is assumed to be binary. I.E. a binary string of length 1 can have two values, 0 or 1. A binary string of length 2 can have 4 values, 00,01,10,11, and a binary string of length 3 can have 8 values, and so on.

# Answer
> 0 votes
That's not what the proof says. Nowhere does the proof claim there are only $2^i$ configurations, where $i$ is the length of the input. In particular, in the proof you link to, $i$ is not the length of the input.

Rather, the proof says that every configuration can be encoded as a bitstring of length $c \cdot s(n)$, and consequently there are at most $2^{c \cdot s(n)}$ possible configurations. Then it goes on to consider a value of $i$ that is $c \cdot s(n)$.

---
Tags: turing-machines
---


# Question
Title: What does "Outstanding" mean in the context of architecture?
I'm taking an Advanced Computer Architecture course and I've come across the term "outstanding" a few times and I've searched online about what it means in the context of computer science/architecture but I can't find anything relevant. For example, on my notes there are some references such as:

> "IBM Power5 allows 8 outstanding cache line misses"
>
> "Each thread can perform 8 outstanding memory accesses"

# Answer
> 12 votes
Outstanding means, it hasn't been resolved. In the case of cache misses, that means the data request has not been serviced yet. When a cache miss happens, it has to fetch the data from the next level cache/memory, until this data arrives, you need to hold this request somewhere. You've got two options in this situation. Either block the entire cache, until data from the next level arrives. This is the easiest to implement, but quite bad in terms of performance. On the other hand, you could save the information about this data request somewhere, and carry on servicing others. This is is much better in terms of performance. Now, coming to this "place" where you are going to store information about the pending cache miss, this is a hardware structure. So you can only have finite number of "outstanding" misses. Number of entries in this buffer, is what is being provided as the number of outstanding cache misses.

---
Tags: computer-architecture
---


# Question
Title: Do we need to read the input completely in Turing machine?
This question is motivated from the question $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$. I am wondering, how is it possible to decide a language without reading the entire input. I have seen the similar situation in space complexity ( L and NL ,where we define new model of computation).

My model of computation is Turing machine (for e.g. see lecture note on Turing machine)

**My question :** Do we need to read the input completely in Turing machine ?

# Answer
> 3 votes
There is no such requirement. A Turing machine which decides a language can do whatever it wants as long as it always halts; the language it decides is the set of words which it accepts.

There are many languages which don't require reading the entire input:

* The empty language.
* The complete language.
* The language of all words starting with 0.
* The language of words of length 2.

Here is a more non-trivial example:

* Given a language $L$, define the language $$ X(L) = \\{ 0^\ell 1 w x : |w|=\ell \text{ and } w \in L \\}. $$ The language $X(L)$ can be decided by a Turing machine which doesn't always read the entire input. Moreover, generally speaking $L$ and $X(L)$ have roughly the same complexity (though $X(L)$ requires the ability to count).

---
Tags: turing-machines
---


# Question
Title: Djikstra's shortest path vs Brandes algorithm for betweeness centrality
I have a couple of Python scripts that calculate various network measures.

Given a graph (G), the first script calculates the average shortest path from each node to all other nodes and stores this in an Nx1 matrix (L). An implemntation of Djikstra's algorithm from the NetworkX Python library is used for this:

```
for i in range(num_nodes):
    for j in range(num_nodes):
        dj_path_matrix[i,j] = nx.dijkstra_path_length(G, i, j)

L = np.sum(dj_path_matrix, axis=0)/(num_nodes - 1)

```

Given the same graph (G), the second script uses an implementation of Brande's algorithm in the NetworkX library to calculate betweenness centrality and stores this in an Nx1 matrix (BC):

```
BC = nx.betweenness_centrality(G, normalized=True)

```

My question is: why does it take so much longer to calculate L compared to BC?

The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph. And surely then, BC should take at least as long as L? Using my scripts, given the same graph, it will take a couple of seconds to calculate BC, but up to half an hour to calculate L.

# Answer
> The way I understand it, BC of a node is a measure of how often a shortest path travels through that node. As such, to calculate BC, surely you would need to calculate all possible shortest paths in the graph.

This isn't necessarily true. Perhaps there is a different algorithm that is faster than what you outline. One possible explanation for the discrepancy in running times is that the NetworkX library uses a smarter algorithm. However, it's hard to know because you haven't told us how the function `betweenness_centrality` is implemented in NetworkX. It is also possible that it uses an algorithm along similar lines, but employs some optimizations that don't affect the asymptotic running time (big O) but does save a large constant factor.
> 1 votes

---
Tags: graphs, graph-traversal
---


title: Proof that a language is not regular

text:
# Question
Title: Proof that a language is not regular
as part of my homework assignment I have to proof that the following language is not regular using the pumping lemma:

$L = \\{w\in \\{a,b,c\\}^\* \\; | \enspace z(a,w) = z(b,w) + z(c,w)\\}$

The function $z(x,w)$ denotes the number of symbols $x$ in word $w$.

I started my proof by assuming that the language is regular. That means that there must exist an integer $m\>1$ so that $|w| \geq m$ is fulfilled. I have then chosen the following word which is part of L.

$w = a^{2m}b^mc^m$

After that I split my word in three parts ($x$, $y$ and $z$). Because $|xy| \leq m$ and $|y| \> 0$ must be true, at least one character $a$ has to be in $y$.

I have read that I have to choose an $i$ such that the word $w\_1 = xy^iz$ is not part of my language any more. I am not quite sure how I can proceed from above to finish my proof.

Could somebody please give some advice on this?

# Answer
> 1 votes
After taking $w=a^{2m}b^mc^m$, you now need to show that *irrespective of how you split $w$ into $x,y,z$*, at least one of $|xy|\le m$, $|y|\gt0$ and $\forall i, xy^iz\in L$ is false.

To do this, you try to split it such that all three do hold, and show that you cannot do so.

For any split in which $|xy|\gt m$ or $|y| = 0$, one of the three is already false, and we are done. Now, suppose that both of these are true. Then, as the first $2m\gt m$ characters of your strings are $a$s, and $|xy|\le m$, you can conclude that $x$ and $y$ must contain entirely of $a$s, if they have non-zero length. As $|y|\gt 0$, $y$ contains at least one $a$.

Suppose $y$ consists of $k$ $a$s. Then, take $i=2$, which gives $xy^2z\in L$. The new string will be thus $a^{2m+k}b^mc^m$. But this cannot lie in $L$, and we have a contradiction. How ever you try to split $w$, you will always fail to satisfy at least one of the conditions. Then, you can conclude that $L$ is not regular.

Note that you *cannot* choose how you want $x,y,z$ to be. The pumping lemma only assures the existence of $x,y,z$ satisfying the conditions. Your inability to find one combination does not prove that it doesn't exist; you need to show it explicitly.

# Answer
> 1 votes
You've almost solved it already. You need to define which part of your word x, y, and z represent, and the obvious partition works well here. You know, by the pumping lemma, that you can repeat y any number of times, and the new word will still be in the language.
In this case, repeat y twice. Is the resulting word still a member of the language?

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


# Question
Title: Longest possible path from root to a leaf of a red black tree
For the worst case of a red-black tree, what would a tree with 10 nodes look like?Since there can not be 2 consecutive red nodes and there is rotation is it safe to say that it balances out the trees leveling it I tried this attempt at creating a tree with 10 nodes:

# Answer
> -1 votes
As you can read as **"Properties"** in the "Wiki Red-Black Tree", "*the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.*".

For a Red-Black Tree having **'N'** nodes, the mean length path is **'ln(N + 1) + 1'** (for 'N=10' 'Lmean = 2.397 + 1 \>\> 4').

Note: *\`ln(X) = neperian logarithm'*.

So the Longest balanced-path from root to leaf is shorter than the double of the mean length **'\< 2 * ln(N + 1) + 1'**. (for 'N= 10' longest \< 8).

---
Tags: trees
---


# Question
Title: Using Induction to prove that $n^3log^4n=O(n^4)$
I need to prove the following asymptotic relation for the purpose of cacluating a recurrence relation: $$n^3log^4n=O(n^4)$$ I tried and failed to do it with induction, which, if possible using basic Calculus 1 level math, I would like you to help me with. I am not required to do it with induciton or anything, I just wondered if I can do it.

I was able to prove it though, in a differet manner: $$f \in o(g) \Rightarrow f \in O(g)$$ $$lim\_{n\to \infty} \frac{n^3log^4n}{n^4}=0$$ Using L'Hôpital's rule 4 times, which proves that: $$n^3log^4n=o(n^4)$$ By the definitino of $o$.

Therefore it also follows that $$n^3log^4n=O(n^4)$$

For the basis of the induction let $n=1$ and with $c=1$: $$f(1) = 1^3log^4(1) = 0 \leq 1=1^4 \cdot 1=c \cdot g(1)$$ From here I think that it would be enough to show that: $$log^4(n) \leq n$$ Although I am not sure how to continue from here.

# Answer
You showed that f (n) = o (g (n)). That's it. There is nothing else to prove.

If you look at the definition of o (f (n)) and O (f (n)), they are almost identical except one says "for every eps \> 0" and the other says "there is one c \> 0". You can take every single eps of the little-o definition and use it as the c in the big-O definition.
> 1 votes

# Answer
You already have your induction basis: $$f(1) = 1^3log^4(1) = 0 \leq 1=1^4 \cdot 1=c \cdot g(1)$$

Now you need to apply the induction step. Suppose $$n^3log^4n\leq c \cdot n^4$$

Then prove: $$(n+1)^3log^4(n+1)\leq c \cdot (n+1)^4$$

and your proof by induction will be completed.
> 1 votes

---
Tags: asymptotics, recurrence-relation, induction
---


title: Encoding a tree

text:
# Question
Title: Encoding a tree
> Let $A$ be an $m \times n$ matrix. Let $F(A,S(t),t)$ be a program function, where $t$ is an integer counter beginning at $0$ and stopping at some $k \leq m,$ and such that $S(0)$ is empty. The function first iterates $t=1$ and then operates on $A$ in such a way that indices for a subset of columns of $A$ are stored in $S(1).$ For each index $k \in S(1),$ the program recursively calls itself and collects another subset of columns of $A$ that depend on which $k \in S(1)$ is under examination. How should $S$ be constructed to record the indices of each branch $k$ of $S(1)$ so that the indices in further recursive calls remain connected and in order with their respective parent indices?

I have not programmed in years, so I apologize if the question is poorly worded, and would welcome any editing or correction if clarification is needed.

In short, I need to set up some kind of data structure $S$ for indices of $A$ that can be described as a set of trees; the pseudocode I have written intends to traverse branches of these trees, operating on the columns corresponding to the stored indices.

My problem is that I do not know what data structure to use to store the indices properly. I thought of creating an array for each branch that follows each possible line of recursive calls of my program, but it becomes hard to think of even how to label these arrays, as I do not know beforehand how many I need nor how many recursive calls my program will make prior to termination. My only other thought was to use a language like MATLAB that could create an adjacency matrix for each tree belonging to each index $k$ collected in the first function call, but I am not quite sure how I could program this.

Any help would be appreciated!

EDIT: Here is the pseudocode for the function:

The function receives a matrix $A$ and a vector $b.$ The matrix is assumed to have more columns than rows, so that solutions will be underdetermined (and therefore infinite over real and complex fields, and likely large for finite fields), assuming the system has a solution to begin with.

My job is to find *all minimal support solutions,* or solutions to the system that have the most 0's as entries.

Of course (as part of my dissertation shows, oddly for the first time in published literature over every finite field, though it has been shown for binary and for real/complex already) the problem is NP-Hard, making the program my advisor and I devised hopelessly exponential - but it is what it is; my advisor wanted me to sort of start something that might continue in the spirit of the SAT solvers out there, I guess, since algorithms that seek minimal support solutions over finite fields are (at the time of this post) comparatively few.

===================

FUNCTION $MinSup(\[A|b\],r)$

Matrix $A$, vector $b$ (as an augmented system), "depth" $r$

initialize $A=A\_0,$ $b=b\_0,$ $r=1$

ASSUPTION: Ax=b has at least one solution, $m=numrows(A) \< n=numcolumns(A)$, and A is row-independent.

RETURNS: Support for the set of minimal support vectors $X$ to the system $Ax=b.$

PSEUDOCODE (sorry, SE is forcing weird formatting I cannot fix)

1. Form augmented system $\[A|b\].$ (EDIT: No longer needed as the program receives an augmented system from the start)
2. Use row operations on $\[A|b\]$ until column b has a 1 on top and 0's on the bottom (doing row exchanges to get a nonzero top if necessary).
3. Look for any columns that *have all zeros* from rows $r$ through m (and a nonzero top). Record these indices in $S.$

4. If S is not empty, then for each $k \in S,$ if $r=1$ RETURN the set $x\_k=(a\_k)^{-1}e\_k$ and $x\_j=0$ otherwise (solutions are weight one). If $r \neq 1,$ for each $k \in S$ BACKSOLVE column $k$ and RETURN each smallest resulting minimal support solution (the matrices $A$ sent to the function when $r\>1$ will have $r-1$ columns of the identity matrix already).

Else

5. For all columns that have a nonzero top row entry, record the indices of each column in $S.$ Iterate $r=r+1.$ If $r=m$ then RETURN all $n$ choose $m$ solutions as your minimal support set.
6. ELSE For each index $k \in S,$ BACKSOLVE column $k$ (we need to use row $r-1$ at this point to pivot for each of these, and of course store the augmented system somewhere in case we need to return to this level). There should be a copy of (a multiple of) column $k$ as the "new $b.$" Send this updated augmented system and index $A', b',r$ to another call of $MinSup(\[A|b\],r).$

========

There will probably be a small parent program that can cull through multiple responses for the MinSup calls. Essentially, I keep calling until I "hit the jackpot," or the deepest iteration $r$ for which my row-exchanged update to $b$ on that particular call identifies a perfect multiple for rows $r$ and below (has all zeros from row $r+1$ to $m$).

As anyone can see, this is obviously a combinatorial nightmare, but it is what it is and I have to program it - and given that my advisor is now one year past retirement, and knows nothing but Mathematica, I'll have to program it on that somehow. It is ugly, but it is what it is.

# Answer
It might be that I'm misunderstanding, but in your case a Node data structure should be all you need. I'll use a C++ example:

```
class NodeData{
  Matrix a;
  Vect b;
  int column;
  ...
};

class Node{
  NodeData data;
  vector<Node*> children;
};

```

Your tree is represented by a single Node which is the root. You iterate the children vector to iterate node's children.
> 1 votes

---
Tags: data-structures, dynamic-programming
---


title: Error in simple mode finding algorithm?

text:
# Question
Title: Error in simple mode finding algorithm?
I'm working through a few chapters on algorithms from the Discrete Math text by Rosen.

In the solutions manual there is an algorithm (specified in pseudocode) for finding the mode within a list of non-decreasing integers.

Here is the algorithm:

```
procedure find a mode(a_1, a_2, ... , a_n : non-decreasing integers)
modecount = 0
i = 1
while i <= n
    value = a_i
    count = 1
    while i <= n and a_i == value
        count = count + 1
        i = i + 1
    if count > modcount then
        modecount = count
        mode = value
return mode

```

Now, I immediately see a problem with this algorithm. For instance, take the list $\<1,2,2,2,4,4,4\>$ we see that the following steps are followed, counting the element $1$ twice when it only appears in our list once.

Steps below begin upon first entry of the body of the while loop:

Step 1. Assign $a\_1=1$ to $value$.

Step 2. Assign $1$ to $count$

Step 3. Check that $i=1 \leq 7$ and that $a\_1=1$ equals $1=value$.

Step 4. Increase the value of $count$ by $1$ so that $count := 2$.

But we only have $1$ appearing once in our list and we have counted it twice.

Is my interpretation of this algorithm incorrect? To me $count$ should first be set to $0$.

# Answer
Yes, you are right. The pseudocode is clumsy, poorly constructed, and confusing. At the end of the outer loop, `modecount` holds the number of times that `value` appears in the array, plus one. That's weird and not what you'd expect from the variable name: from the variable name, we'd expect it to hold the number of times `value` appears (without the plus one).

That said, the algorithm still returns the correct answer: it does indeed return a mode, as claimed. For example, with your example input, it correctly returns `2`.

(Why? Because the exact value of `modecount` isn't returned. It's one too high for every value, so the mode will indeed have the largest value of `modecount`.)

So while the pseudocode is confusing and poorly constructed, it happens to return the right answer -- i.e., it happens to be a correct algorithm for the "find a mode" problem. But it's still ugly. Yuck. I agree with you that they should have initialized the count to 0, not 1; then the algorithm would be both correct *and* easier to understand.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Rotation matrix between two objects - alignment
I am trying to align two objects based on the notion of points and their correspondence, but struggling to find a solution.

I have two objects A and B. However, they are rotated in a different direction, and therefore I would like them to align. I have a notion of some correspondence between the points in object A and in object B.

The initial idea that I had looks as follows. Pick two points( let's call them center and end point) in A, and then pick the corresponding points in B. Then measure the angle between them.

I believe that I could get an angle between them, but I am not sure how would that translate to the rotation matrix. I was also wondering whether it is not better to split it into different axes , and then perform multiplication. However, I am not sure how would I proceed with that.

Could anybody give me advice whether my approach is ok, or possibly provide a way of obtaining a rotation matrix for the whole object based on those vectors?

My idea:

Let's say that I have object A, and two points:

***A0 = \[2,4,6\]***

***A1 = \[3,5,7\]***

Then I calculate a vector

**A0A1 = \[1,1,1\]**

Then I find a corresponding two points in object B:

***B0 = \[4,8,12\]***

***B1 = \[2,7,5\]***

Then **B0B1 = \[-2,-1,-7\]**

Now I would calculate the angle

# Answer
You probably want to find a homography that maps object A to object B. I suggest reading about image rectification/alignment/registration. A homography is a linear function of the form

$$q = Ap+b,$$

where $A$ is a matrix, $b$ is a translation vector, $p$ is a point from object $A$, and $q$ is the corresponding point from object $B$.

If you have four points from object A and the corresponding four points in B, you can solve uniquely for a homography that maps each of those A-points to the corresponding B-point (using linear algebra). There are standard methods for finding that homography in the computer vision literature, based on solving a system of linear equations. For instance, OpenCV has a method that will do that for you.

More generally, if your points have some small amount of error in them, it can be more effective to take more than four points and then find the best-fit homography. For instance, you could take five points, or six points, or 10 points, and find the best-fit homography that maps those 10 points from object A (as close as possible) to the corresponding 10 points from object B. This becomes a least-squares fit problem, where you want to minimize the sum of the squared distances between (homography applied to point from object A) and (location of corresponding point in object B). There are ways to find that best-fit homography using a least-squares fit.

There's lots more one can say about the subject -- it has been studied extensively in the image processing and computer vision literature. See https://en.wikipedia.org/wiki/Point\_set\_registration for a starting point.
> 1 votes

---
Tags: graphics
---


title: Maximum One Third Cut

text:
# Question
Title: Maximum One Third Cut
I want to solve the following problem (This is a homework problem. Not looking for definite or complete answers):
**Maximum One Third Cut:**

* **Input:** An undirected graph *G=(V,E)* where *V={1,2,...,n}*, such that *|V|* is divisible by 3, and a positive integral weight function *w:E to N* (on edges).
* **Goal:** Fin a subset of vertices *U* subset of *V* such that *|U|=|V|/3*.
* **Objective:** Maximize the total weight of the edges between U and its complement.

Of course, you can do that using a full search of all the possiblities. I want a more efficient algorithm though.
I'm thinking about some sort of **Local Search** algorithm, like Steepest Ascent Hill Climbing (**SAHC**), or a variation thereof (Simulated Annealing, Random Restart etc.).

* **States:**
Could be a binary vector, where the *i*-th element represents whether the vertex i is in U or not (0: not in U, 1: in U), where the number *1*-s is |V|/3.
* **Successors:**
Turn one bit off, turn another on.
* **Heuristic Function:**
Sum of all weights of edges between U and V\U. Could be computed when generating a successor, you only need to check the vertex removed and added. Perhaps states can contain a list of edges that are relevant.
* **Other Parameters:**
Like Temprature or amount of restarts allowed could be set by testing the algorithm on graphs of varying in size, weight function and edges, and choosing the best values.

I was also thinking about **Evolutionary Search**.
Am I on the right track here? Are there better options perhaps? Any suggestions would be much appreciated.
Thanks!

# Answer
> 2 votes
Great project! There are many possibilities. I suggest reviewing the approaches listed in Dealing with intractability: NP-complete problems and trying as many of them as possible to see which tends to work best on the kinds of graphs you have to handle in your class. It will be a fun learning experience, where you get to learn about multiple techniques and get some experience with them.

At minimum, I'd recommend trying some form of local search, such as hill climbing and/or simulated annealing. I have rarely seen situations where genetic algorithms outperform other forms of local search. I'd also recommend trying integer linear programming (ILP) or possibly MaxSAT.

---
Tags: algorithms, graphs, weighted-graphs, max-cut
---


title: Classifying objects by set proximity

text:
# Question
Title: Classifying objects by set proximity
The project I'm working on has a number of objects arranged in overlapping sets. I need to classify them by whether they have a trait or not, using pre-classified objects that they are connected to (through shared set membership). I.e., the objects within the same set are likely to share whether they have that trait. The training data only consists of whether some objects have the trait or not.

To illustrate by example:

* Green and red circles represent pre-classified objects (with having and not having the trait respectively). White circles are unclassified.
* Objects A, C, D and E are likely to have the trait, and thus should have a positive score, because they are in common sets with other objects which are known to.
* A should have a better score than C because there is more certainty (C's unclassified neighbor might or might not have the trait).
* Similarly, D should have a higher score than A.
* E is likely to have the trait because all of its neighbors are.
* F and G should have a neutral score, because we don't know anything about F, and G has equally conflicting information.

I'm looking to sort all unclassified objects by score (likelihood to have the trait), which in this example would roughly be D, A, E, C, F, G, B, or at least get the top N objects with the highest score.

My set size is about 50 million objects across 10 million sets. The training size set (number of pre-classified objects) can vary from 1 to a few thousand. The objects are pretty well connected - the biggest "connected subgraph" contains 90% of all objects.

# Answer
One powerful and general approach is to write a probabilistic model that describes how colors are chosen, then apply maximum-likelihood estimation. The probabilistic model provides an expression for $p(x)$, where $x=(x\_1,\dots,x\_n)$ and $x\_i$ is a random variable that describes the color of the $i$th object. You are given an observation for some of the $x\_i$'s, namely, the color of the pre-classified objects, and want to infer the color of the rest. This can be done by finding a vector $x$ that maximizes the value of $p(x)$, subject to the requirement that it be consistent with the observed colors. You then apply some mathematical optimization routine to find $x$ that maximizes $p(x)$, subject to the constraint that $x$ is consistent with the observations.

This requires that you supply a model for how colors are generated. Only you can provide that, since that depends on the specifics of your application domain and the random process underlying your observations.

One possible approach is to model this as a Markov random field. Build an undirected graph where the vertices are the objects; add an edge $(u,v)$ between two objects $u$ and $v$ if $u,v$ are in the same cluster. Then the Markov random field assumption says that $p(x)$ is proportional to

$$\prod\_{(u,v) \in E} q(x\_u,x\_v),$$

where $q(\cdot,\cdot)$ is some function $q:\\{\text{red},\text{green}\\}^2 \to \[0,1\]$. For instance, you might take $q(c,d) = 0.99$ if $c=d$ and $q(c,d)=0.01$ if $c\ne d$. That defines a Markov random field. There are algorithms for maximum-likelihood inference for Markov random fields. (In particular, as a starting optimization, you can decompose the graph into connected components and solve the problem separately for each connected component.)

Another possible model would be a hierarchical model, where we first pick a color at random for each cluster, then randomly pick a color for each object based on the color(s) of the cluster(s) it is contained in. Suppose there are $m$ clusters, and let $w=(w\_1,\dots,w\_n)$ where $w\_i$ is a random variable describing the color of the $i$th cluster. We might imagine that the $w\_i$ are independently uniformly distributed. Then, we might imagine that we pick a color $x\_j$ for object $j$ based on the values of $w\_i$ for each cluster $i$ that contains object $j$. In particular, we might imagine that the conditional probability distribution $p(x|w)$ is proportional to

$$\prod\_{j=1}^n \prod\_{i \text{ s.t. } j \in i} p(x\_j|w\_i),$$

where we define $p(x\_j|w\_i) = 0.99$ for $x\_j=w\_i$ and $p(x\_j|w\_i)=0.01$ if $x\_j \ne w\_i$ (say). Using the fact that $p(x,w)=p(x|w) \cdot p(w)$ and that $w$ is iid uniform, we obtain that $p(x,w)$ is proportional to

$$2^{-m} \prod\_{j=1}^n \prod\_{i \text{ s.t. } j \in i} p(x\_j|w\_i).$$

We can then try to find $x,w$ that maximizes $p(x,w)$, subject to the constraint that $x$ be compatible with the observations (the pre-classified objects). This could be done by mathematical optimization. Again, as an optimization, you can decompose the problem into independent subproblems through a connected component decomposition (consider two objects in the same component if they are members of the same cluster).

It is also possible to obtain confidence scores through "marginalization": if you can compute $p(x\_i|y)$ where $y$ denotes the observed colors of the pre-classified objects, then this serves as a confidence score for the inferred color of object $i$.

There are other models that might be appropriate. We can't tell you which one is most suitable for your application domain, but once you choose one, you can work out how to apply the maximum-likelihood maximization principle to it.
> 1 votes

---
Tags: machine-learning, classification
---


# Question
Title: Algorithm Selection for Classification problem
I've been working on a developing a product selection network for my workplace. I work with lots of chemicals and the clients don't always know what they want/need so most of the time I have to ask a bunch of question, collect useful/ignore useless information, then make a selection from there. Discussions take place over the phone.

Ideal situation In terms of information collection/flow: 1. I ask a probing question which specifies which feature I am referring to 2. Client answering question and speech recogniser converts voice to text filling in feature input. 3. Text summariser searches the feature and reduces down to specific key words. \- For example: Me: "what kind of application are you looking to perform?" Client: "I'm wanting to adhere two pieces of wood together" Feature summarised to: adhere, wood 4. Once feature vector has enough information the network recommends the most suitable product.

Problems: 1. Clients tend to waffle and give useless information therefore network will need lots of training data. 2. Once a question is asked - client may not directly answer that question and may incidentally answer another feature question.

I would think the logical place to start would be a speech recognition RNN - I have written a weak tensorflow one however I think I'll just look to tap into Google's cloud speech recognition API here. This is where I get stuck - should I just use a simple forward/back propagation network from here and treat it as a classification problem or is there another way to do it?

Any direction pointers would be greatly appreciated.

Kind Regards, Andy

# Answer
I don't think existing state-of-the-art technology will be adequate to solve this task effectively. The current state of knowledge in NLP and AI probably isn't good enough to build something that will work well in practice. Instead, I think you'll need to use humans. Perhaps you can hire someone and train them -- that will probably be both cheaper and more effective than anything feasible with AI today.

(It seems impractical to obtain the large training sets typically needed for deep learning. Also, your task requires deep understanding of spoken text at a semantic level, which is currently hard. Finally, your task requires domain knowledge about the kinds of application tasks that clients are likely to ask about.)
> 1 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: What cannot be proven at compile-time about a computer program?
Is there a Turing-Complete-ish programming language without runtime errors? Like segmentation faults, memory leaks, race conditions, deadlock/livelock/starvation, etc.? With strongly typed languages, the compiler can detect null pointer exceptions and refuse to compile code. How much can we statically check? Everything, or are there some things impossible to check?

Are there any language projects that are trying to do this (especially with concurrent and networked applications)?

---

EDIT:

I guess there are two sorts of behavior that I'm looking to avoid: unwanted erroneous behavior (deadlocks, etc), and runtime exceptions (divide-by-zero, etc).

Taking the example of divide-by-zero, can we create some computation `x/y` so that, whenever such a computation is done, we require `y` to be of the type `T nonzero` where `T` is integer, floating-point, or whatever for that overloaded operator?

With deadlocks, and other concurrent scheduling hazards, is there a set of control structures which cannot create those hazards, or better yet, can detect those hazards at compile time (better because I think it might be more expressive)?

# Answer
In the theory of programming languages there are the so-called **safety theorems** which tell us that programs "do not do bad things". A typical safety theorem says:

> **Safety theorem**: If a program $P$ has a type $T$, then it either runs forever or it terminates and yields a value of type $T$.

Not every language satisfies such a theorem, and in fact, it usually takes a bit of work to make sure that a language *is* safe. Once we have the theorem, the compiler can make a strong guarantee by checking that the program has a type.

The safety theorem guarantees that:

1. A program which has a type will never get *stuck*, i.e., it will not encounter an undefined state.
2. A program which has a type will not suddenly switch to doing something completely diffrerent, for instance, it will not return a `string` if its type is `int`.

What exactly this means in practice depends a lot on what sort of information is expressed by the types of the language. For example, since a well-typed program will not get *stuck*, we can be sure that it will not segfault, and it will not perform an invalid pointer dereference. This is quite useful to know. Many modern programming languages strive to provide this sort of guarantee, or actually have it in cases of programming languages that have formal definitions (SML).

There are other kinds of errors which we might try to prevent, for example division by zero. Since it is non-computable whether a particular operation will happen at runtime, we cannot expect that the compiler will simply figure out whether division by zero is possible. In order to recover the safety theorem in presence of division by zero we can introduce *exceptions* into the language and make sure that division by zero raises an exception (rather than encounters an undefined state). The safety theorem then says:

> **Safety theorem (with expcetions)**: If a program $P$ has type $T$, then it runs forever or terminates by either returning a value of type $T$ or raising an exception.

This sounds like cheating but is the best we can do with this sort of language. It is also a very common solution, also because exceptions are a generally useful programming concept (they are *not* errors, but rather a *flow control mechanism*). We can do slightly better if we allow the types to contain information about exceptions. Java does this with the `throws` declaration. Note however, that types cannot describe runtime exceptions *exactly* because that would make type checking non-computable.

Another way to deal with division by zero is to design the language in such a way that it is impossible to divide by zero. This could be accomplished by having a construct

```
x / y orelse z

```

which divides `x` by `y` if `y` is not zero, or returns `z` otherwise. Most programmers would find this kind of solution impractical.

Deadlock and race conditions are problematic in the same way as division by zero. In the general case it is non-computable whether a deadlock, or a race condition will happen. There are two lines of attack (just as with division by zero):

1. We can have more expressive types which guarantee that deadlock does not happen. The danger is that the types will be so fancy that type checking becomes undecidable, or that programmers will find the types too complex to understand.
2. We can design the language so that deadlock is impossible. The danger is that we will impoverish the language by doing so.

Regarding the second point above: programmers and designers of programming languages both like to use loss of expressivity as an excuse for a non-safe design. A case in point is the `null` pointer/object/value, where it is often falsely claimed that not having `null` is impractical and results in slower code. Good design goes a long way, and sometimes requires change of habits, but brings many many advantages. (It used to be the case that "real programmers" disliked garbage collection, and never admitted to themsleves that their programs leaked memory because humans could not allocate and deallocate memory by hand correctly).

In general, by making types even fancier, we can make sure that the safety theorem precludes other kinds of bad behavior by specifying *good* behavior. For example, in a dependently typed langauge such as Idris you can specify that your program sorts lists, in which case it can't cause division by zero, nor can it run forever. (But now the compiler may possibly need a lot of help from the programmer in order to establish that the program really has the stated type.)

You might expect also that a compiler shold be able to guarantee that a well-typed program must terminate. However, this is non-computable (Halting Oracle), not to mention that there are many useful possibly non-terminating programs (such as the browser you're using right now, and the operating system). If you need termination guarantees, then instead of referring to a safety theorem, you can design the language so that it cannot express a non-terminating computation. An example of such a language is Agda, which is also dependently typed and it doubles as a proof assistant. Note however that there is an important theorem stating that a language with computable syntax in which all programs terminate is not Turing complete.
> 6 votes

# Answer
Yes, there is a programming language without runtime errors. For instance, my programming language only lets you compute sums of numbers: valid programs include `2+2` and `3+17+42+19` but not anything more complicated (you can only have constants and the addition operator, but nothing more); all operations are done with big integers, so no runtime errors are possible.

However, as you can see, this language is extremely limited in what it can express.

The answer depends on what you mean by "runtime error", and on what kinds of operations you want the programming language to be able to support.

Let's start with what we mean by "runtime error". Here is my understanding. My impression is that deadlock, livelock, starvation, and infinite loops generally aren't considered runtime errors. Anything that causes the program to run forever without making useful progress is a failure of availability, but not of safety -- not a runtime error, as I understand the term. In contrast, segmentation faults, null pointer dereferences, etc. generally *are* considered runtime errors. They can cause the program to crash, go wrong, or return incorrect answers.

With that understanding, it *is* possible to make a language that is free of runtime errors, if you're willing to make enough compromises about what constructs are allowed in the language. We can define all the operations supported by language so that no runtime error is ever possible, and then we could have a language where you can guarantee absence of runtime errors. However, this might or might not be what you were actually hoping for. For instance, normally we define the division operator so that `x/y` is a runtime error if `y` is zero. That won't work. We could alternatively define a programming language where the result of `x/y` is defined to be something specific (zero; NaN) if `y` is zero. Thus `/` doesn't represent the usual division operator; it represents something slightly different. We could continue to do the same for every operation that might cause a runtime error.

In this way, you could obtain a language with no runtime errors. However, you'll have to decide whether you like the result or not -- it has a somewhat different flavor from many imperative languages you might be used to. For instance, imagine a language like Python, except surrounded by a giant try-catch block that ensures if any runtime error occurs at runtime, the program terminates and returns 0 -- that would be fully defined and have no runtime errors, but only by virtue of "re-defining" the meaning of runtime error to mean that we don't count it as a runtime error (even though it's probably still a bad thing if a program tries to divide by zero).

Suppose you don't like that outcome, and you really want a language where you can determine that a program will never cause any runtime error, including never attempt to divide by zero. Unfortunately, I have bad news. It is not possible to have a programming language with that property, and that is also fully expressive. In particular, if it is Turing-complete programming language, and if it supports the division operator, it can't be guaranteed free of runtime errors, because determining whether a divide-by-zero error can occur at runtime is as hard as the halting problem and thus undecidable. The same occurs for every other operator that could potentially trigger a runtime error.

As a result, if you are imagining a language that looks like typical imperative programming languages, the pragmatic answer to your question is going to be "no: you can't have a language with that property (if you want it to be Turing-complete and to feel familiar), because deciding whether or not a program will cause a runtime error is undecidable".
> 4 votes

---
Tags: programming-languages, type-theory
---


# Question
Title: How to avoid loops/cycles in iterative deepening with linear space?
Breadth first graph search adds states that have already been visited to an explored set to avoid getting stuck in loops and cycles. This is fine since breadth first search needs exponential space to keep all the nodes in memory.

One of the main reasons for using iterative deepening depth first search is to avoid the exponential space requirements. To ensure linear space you can't simply add every visited state to the explored set. How then do you avoid loops in iterative deepening graph search?

My intuition is that you could remove states from the explored set at some point? Or backtrack to the root but that seems more expensive.

# Answer
> 4 votes
The main point of Iterative Deepening is to completely search a potentially infinite (or just really huge) tree with depth first search with storage linear in the maximum you search. To detect cycles, the information that a node has been visited before must be stored somewhere. This requires exponential storage, so there is no non-exponential ID algorithm that prevents searching in cycles.

However, this may not be too bad in practice if the graph is already stored somewhere. The easiest method to do this then is simply to label the 'depth' of every node as encountered by the search, so you can detect when a cycle has been found. (This is essentially the same as depth limited breadth first search, apart from the order.)

But in general, cycle detection requires more storage, or a different algorithm that uses a bit more time. In fact, you can see a very clear time-space trade-off in many cycle detection algorithms.

---
Tags: algorithms, graphs, search-algorithms, space-complexity
---


# Question
Title: I need to prove Prove that the language L = {w | number of 11s in w is more than the number of 010s} is context free
How would you go about proving that this Language is Context free. I'm having issues with drawing the PDA for this.

I need to prove Prove that the language L = {w | number of 11s in w is more than the number of 010s} is context free.

I so far assume that when a string of 11s occur add x to the stack and when 010s add y to the stack, but I'm having issues drawing that part out the part were you check to see if the number of x's in the stack is greater then the number of y's.

Update based on GoodDeeds answer, just need to clearify something Basic PDA Input, Pop -\> Push

"Whenever a 11 is encountered, and the top of the stack is not a y, push an x. Else, pop a y."

So in this case whenever a 11 is encountered do I draw out the transition like example A or B?

# Answer
Sketch of an answer:

As you suggested, use the states of the PDA to check when a $11$ or a $010$ has been found. Then, instead of keeping track of the number of $11$s and $010$s separately, keep track of the difference in their numbers.

You could have some symbol in the stack initially, say, $\\$$, to mark that the stack is empty. Then, use a symbol $x$ to denote $+1$ in the difference, and $y$ to denote $-1$ in the difference.

Whenever a $11$ is encountered, and the top of the stack is not a $y$, push an $x$. Else, pop a $y$.

When a $010$ is encountered, if the top of the stack is not an $x$, push a $y$. Else, pop an $x$.

Thus, at any given point, the stack consists entirely of $x$s or entirely of $y$s, or only the $\\$$. The number of $x$s denotes how many more $11$s have been encountered as compared to the number of $010$s, and vice-versa.

At the end of the input, accept if the top symbol is an $x$, as this would mean that the number of $11$s were more than the number of $010$s.
> 1 votes

---
Tags: pushdown-automata
---


# Question
Title: Proof of decidability of determining whether a DFA accepts a string
I want to ask the acceptance problem: Whether a particular deterministic finite automaton accepts a given string can be expressed as a language, $A\_{DFA}$. Show $A\_{DFA}$ is decidable. The proof in the textbook (Siper page 195) uses two steps:

$M$ = “On input $\langle B,w\rangle$, where $B$ is a DFA and $w$ is a string:

1. Simulate $B$ on input $w$.
2. If the simulation ends in an accept state, accept. If it ends in a nonaccepting state, reject .”

What exactly is the meaning of "simulating $B$" in the first step? In my understanding, if $M$ wants simulates multiple DFA $B$, the parameters of $M$ (transition function or acceptance state) need to be changed according to the different input DFA $B$ and input string $w$, since different DFAs may have different structure. In other words, can a TM simulate infinite DFAs? And how it can be done? I know this question may be trivial, but it really bugs me. Any clarification will be appreciated.

# Answer
> 4 votes
I've often found that, with problems like these, it's easiest to reason by analogy to software, since anything you can do with a computer you can do with a TM and vice versa (with a giant asterisk). The problem $A\_{DFA}$ essentially is the following: given a DFA $D$ and a string $w$, determine whether $D$ accepts $w$. In software, you could imagine that you'd want to write a method

```
bool accepts(DFA D, string w)

```

that takes as input a DFA $D$ and a string $w$, then returns the answer. Notice that we're given the DFA as a parameter, since if we don't have it, then there's no way that we can answer the question. It would be like someone saying "I'm hiding a DFA behind my back - can you guess whether it accepts a given string?"

The pseudocode for this function might look something like this:

```
bool accepts(DFA D, string w) {
    currState = D.startState;
    for (char ch: w) {
        currState = D.transitionTable[currState][ch];
    }
    return D.isAcceptingState(currState);
}

```

Since this is something that we can do with a computer, it's certainly something that we can do with a TM.

Given this code, it's probably clearer what the TM you described above would do. It doesn't take in infinitely many DFAs or strings - it just takes in a single DFA and a single string at a time. There are infinitely many possible choices for what that DFA could look like or what that string could be, but at any one point in time the TM works on just a single string and a single DFA. The fact that the TM (or this code) correctly works on *every possible DFA* and *every possible string* is why $A\_{DFA}$ is decidable: there's a TM that, given an arbitrary string, decides whether it's in the language.

---
Tags: turing-machines, computability, finite-automata
---


# Question
Title: Order-of-growth of selection sort is quadratic, it takes 2secs to sort 100 elements, what will be the expected completion time to sort 200 elements?
The above is an *MCQ* from an online quiz given by my *Algorithm* lecturer. The available options are **6secs**, **4secs**, **12secs** and **20secs**.

The answer I selected was **12secs** and it was rejected. The lecturer said the answer should be **4secs** and then I started to prove that the answer is **greater than or equal to 8secs** in the following ways.

---

### 1. Using *Proportions*

**T = kN2**, *where k is an arbitrary constant*

2 = k x (1002) **-------------(1)**

x = k x (2002) **-------------(2)**

***(2)/(1)*** *implies,* x/2 = 2002/1002 = 22 = 4,

*i.e.* x/2 = 4 but **x** = 2 x 4 = **8secs**

---

### 2. Using *'doubling hypothesis'*

***NOTE:*** *This is almost identical to the first proof.*

Running Time = aNb, *where b = 2*

2 = 1002a, and a = 2/1002

Then again, **Time** = aN2 = (2/1002)N2 =(2/1002) x 2002 = 2 x 4 = **8secs**

---

### 3. Using a slide from a reliable source

As you can see the ratio **T(2N)/T(N) = 4** for *Selection Sort*

Suppose the answer is **4secs**,

**T(2N)/T(N)** = 4/2 = **2** and the order-of-growth becomes *linear* and this proves the answer 4sec is wrong.

Whereas when you substitute the answer **8secs**,

**T(2N)/T(N)** = 8/2 = **4** and proves that the order-of-growth is *quadratic* according to this slide.

---

### 4. By ploting the curve on a graph

Both the points **(100,2)** and **(200,8)** satisfies *Y=mX2* and *m = 2 x 10-2*, and I proved it through equations as well to show that the curve is quadratic and not cubic or else. Also plotted the straight line for the points **(100,2)** and **(200,4)**.

---

Finally, the lecturer agrees that the answer should be **8secs** but since that option is missing I should select the closest approximation which is **6secs**.

But my point is the running time should be greater than or equal to **8secs** and at the same time closest to **8secs** because there are other basic operations involved as well like *variable declaration, initiation, comparison, swap function* and for small inputs the time taken for those aren't negligible. So the answer **12secs** is my answer in the given context.

***Although we can't tell the exact running time, what do you think is the possible range for running time? and, is my argument valid or not?***

I thank you in advance!

# Answer
First off, that's a less than wonderful question.

Second: If the running time is indeed quadratic (with no linear term), the best answer is **8 seconds**, not 4 seconds. Suppose the running time is $T(n) = c \cdot n^2$ for some constant $c$. Then we know $T(100) = $ 2 seconds. One can show that

$$T(200) = c \cdot 200^2 = c \cdot 4 \cdot 100^2 = 4 \times T(100),$$

so it follows that $T(200) =$ 8 seconds.

That said, I still don't like the question very much. Usually when we say that an algorithm has quadratic running time, we mean that its running time is in $\Theta(n^2)$. That means the running time could be something like $T(n) = c\_1 \cdot n^2 + c\_2 \cdot n$. If the running time looks like that, then we don't have enough information to conclude what the running time will be for $n=200$.
> 3 votes

# Answer
Both answers **4secs** and **6secs** given by the lecturer are correct since those are the only possibilities.

*My friend derived to this conclusion based on the following calculation*,

**T(N) = a(N2) + bN + c = 2**, where ***'bN+ c'*** is **not neglegible** for small input size like 200 elements.

> **T(2N) = 4a(N2) + 2bN + c \< 4a(N2) + 4bN +4c**
>
> **T(2N) \< 4\[a(N2) + bN + c \]**
>
> **\< 4T(N)**
>
> **\< 4 x 2**
>
> **T(2N) \< 8secs**

At the same time ,

> **T(2N) \> T(N)**
>
> **T(2N) \> 2secs**

This gives the range for T(2N) as below,

> ***2secs \< T(2N) \< 8secs***

Since both of those answers are within this range, this proves my argument is **invalid**.
> 0 votes

---
Tags: algorithms, runtime-analysis, sorting
---


# Question
Title: Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$
Find $f\colon \Bbb{N}\to\Bbb{N}$ such that $f = n^{o(1)}$ and for every $c\in\Bbb{N}$, $f(n)=\omega(\log^c n)$.

It looks like I need to find a very small growing function $g$ that will satisfy $$\lim\_{n\to{\infty}} \frac{1}{g} = 0 $$ and also $$\lim\_{n\to{\infty}} \frac{\log^cn}{n^{\frac{1}{g}}} = 0 $$

My first attempt was $g(n) = \log n$ but according to wolfram alpha, the second limit was not satisfied, I then tried $g(n) = \log\log n$ which according to wolfram does the trick.

But I'm not sure how to prove that $$\lim\_{n\to{\infty}} \frac{\log^cn}{n^{\frac{1}{\log\log n}}} = 0 $$

Im looking for a way to prove this, or find a simpler solution than $f=n^{1/\log\log n}$.

# Answer
Take the log of your ratio to get $$ c\log\log n - \frac{\log n}{\log\log n} = \frac{c\log^2 m - m}{\log m}, \quad \text{where } m = \log n. $$ It is not hard to show that this tends to $-\infty$ as $m\to\infty$, and so as $n\to\infty$, which means that your ratio tends to zero as $n\to\infty$.

Indeed, since $c\log^2 m = o(m)$, for large enough $m$ we have $c \log^2 m - m \leq -m/2$. Since $2\log m = o(m)$, it follows that $\frac{m}{2\log m} \to \infty$ and so $\frac{-m}{2\log m} \to -\infty$.
> 4 votes

---
Tags: asymptotics
---