# Question
Title: How to get the expected running time of an algorithm
I have an algorithm which, basically given an array of $n$ numbers, checks if there is any repeated numbers in the array, and returns true if there is and false otherwise.

It uses a direct access table (hashing function $h(x)=x$), which makes the running time linear. So it creates a new array, initializes all values to false, then iterates through the given array, and since each value is an index to the hash table, it accesses that array location and changes it to $1$. If it is already a $1$, then you know that it is a repeated number.

But when getting the expected running time, you need to first define a probability space. This is the part I am confused about. How can you define a probability of a number being repeated in A, if you are just given an array with arbitrary numbers?

# Answer
> 1 votes
Usually you assume uniform distribution on inputs which share a certain parameter. You could assume uniform distribution on e.g.

1. All inputs of length $n$, e.g. if your input looks like $w\_1\\#\dots\\#w\_k$, where $w\_i\in\\{0,1\\}^\*$, $n=k-1+\sum\_{i=1}^k|w\_i|$.
2. All multisets (bags) of $n$ integers up to $k$
3. All $n$-tuples of integers integers up to $k$ (different,since e.g. $\\{1,2\\}\_b$ corresponds to $(1,2)$ and $(2,1)$ and $\\{1,1\\}\_b$ only to $(1,1)$)

You can combine this with an assumption about the distribution of the parameter, say the size $n\sim \mathrm{Geo}(0.5)$. However, this is unusual, most would consider the limit of probabilities as your parameter $n\rightarrow\infty$ instead.

---

If you choose 3, the probability of no repeated numbers can be calculated this way: There are different $\binom{k}{n}$ sets of size $n$ and each set corresponds to $n!$ $n$-tuples. There is a total number of $k^n$ $n$-tuples, so $$P(\text{no repeated number})=\frac{\binom{k}{n}\cdot n!}{k^n}$$

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


title: Formal Language Syntax

text:
# Question
Title: Formal Language Syntax
Here is the question:

Show that $L = \\{0^m1^n : m \> 1, n \> 1, n \< m \\}$ is not regular.

I am not sure what superscripts mean in this situation? Does it mean something like this:

$0^5 = 00000$ or $1^7 = 1111111$.

# Answer
> 5 votes
Yes, `0^n` or $0^n$ denotes the string obtained by concatenating $n$ copies of the symbol $0$.

# Answer
> 2 votes
Yes, superscripts mean exactly what you think they do. For your other question (how to use superscripts in SO), there are two ways: use html tags like sup, or use $...$ math.

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


# Question
Title: Is $\{\Theta(f)|f:\mathbb{N}\rightarrow\mathbb{N}\}$ Dedekind-complete?
Let $\Theta$ and $o$ be defined as usual (Landau-notation). For two equivalence classes defined by $\Theta$ we define $$\Theta(f) \<\_o \Theta(g) :\Leftrightarrow f \in o(g)\qquad.$$ Let $$\mathbb{F}:= \\{\Theta(f)\mid f:\mathbb{N}\rightarrow\mathbb{N}\\}$$

**My question**: Is $\langle \mathbb{F},\<\_o\rangle$ Dedekind-complete, i.e. given a set $F\subseteq \mathbb{F}$ with an upper bound $f\_u,\forall f \in Ff\in o(f\_u)$ are there $f\_\inf$ and $f\_\sup$ s.t. $$\forall \Theta(f)\in F: \Theta(f\_\inf) \<\_o \Theta(f) \qquad{(1)}$$ $$\forall g: (g\text{ fulfills (1)} \Rightarrow g \in o(f\_\inf))$$

($f\_\sup$ is defined analogously)?

Note: We don't need to assume a lower bound, since there is no infinite strictly decreasing series of $n \in \mathbb{N}$, i.e. $\Theta(0)$ is always a lower bound.

Background: I'd like to consider $\inf \\{f \mid L \in N/DTIME/SPACE(f)\\}$ for some Language $L$, but that only makes sense if such a (class of) function(s) exist(s).

# Answer
Let $F$ be the set of all functions $f(n)$ such that $\sum\_n f(n)$ diverges. Then $F$ is bounded from below by $f(n) = 1/n^2$ (for example), but there is no infimum: for every divergent sequence, you can find a sequence which diverges more slowly. This is a classical result of Hausdorff.

Similarly, if $F$ is the set of all functions $f(n)$ such that $\sum\_n 1/f(n)$ converges, then $F$ is bounded from above by $f(n) = n$, but there is no supremum since for every convergent sequence you can find a convergent sequence which grows much faster.

Edit: This paper (among others) provides a proof of these claims.
> 7 votes

# Answer
No and no. If you have a supposed function $f(n)$ as infimum, the function $f(n) / n$ is smaller; if $F(n)$ is a supposed supremum, $n F(n)$ is larger.
> 0 votes

---
Tags: landau-notation
---


title: $st$-path with fewest leaving edges

text:
# Question
Title: $st$-path with fewest leaving edges
Given an undirected unweighted multigraph $G=(V,E)$ and $s,t \in V$ find a simple $st$-path $P$ s.t. the number of edges leaving $P$ (i.e. the edges with exaclty one endpoint in $P$ ) is minimized.

Does anybody have any idea how to solve this? I first thought about replacing edges by two arcs and weight them according to some node degrees but the edges staying in $P$ make life difficult.

# Answer
> 2 votes
Suppose input graph is simple (without parallel edges), now, If you solve your problem, you can check existence of Hamiltonian path, actually if s-t path of cost zero for some pair exists means there is Hamiltonian path and you can check this for all pair of vertices as (s,t), so you are unlucky to have polynomial time algorithm except $P=NP$.

---
Tags: algorithms, graphs
---


# Question
Title: Common Algorithms without Asymptotically Tight Bounds
I can think of functions such as $n^2 \sin^2 n$ that don't have asymptotically tight bounds, but are there actually common algorithms in computer science that don't have asymptotically tight bounds on their worst case running times?

# Answer
This is somewhat of an anomaly, but yes - technically you could say that there are such algorithms. For example, consider an algorithm that checks whether a number in unary encoding is a prime - the first thing the algorithm can check is whether the number is even, this takes $O(n)$ time.

If it is, the algorithm rejects, otherwise it applies some primality test that takes $\omega(n)$ (at the very least by first converting it to binary, which takes $\theta(n\log n)$).

The point is that on every input of even length, the algorithm stops "quickly", so there is no asymptotically tight bound.

But this is clearly a stupid example. One way to avoid this problem is to define the running time of an algorithm on inputs of length $n$ to be the worst case running time on inputs of length *at most* $n$. This way you can get a tight bound.
> 3 votes

# Answer
A real-life example is any of the simple sorting algorithms. E.g. insertion sort takes $\Omega(n)$ and $O(n^2)$, and those bounds can't be improved (best case is already ordered, in which case it just checks it is ordered in linear time; worst case is reverse order, and the time is quadratic).
> -1 votes

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


title: Studying advice

text:
# Question
Title: Studying advice
I don't know much when it comes to computers,

But If I wanted to learn how to programm algorithms that perform symbolic calculations and other techniques used to solve or aid mathematical problems, and to be able to classify the efficiency of different types of algorithms in terms of different factors, what sub field of computer science should I study, and how would I start studying it?

So that I can gain these techniques. In addition, I would like to start studying some enumerative combinatorics, is there some way I could study them together or at the same time? In terms of my educational background, I am familiar with parts of elementary number theory, and know about arithmetic functions, I also have about a thorough high school education in calculus, and all proceeding k-12 math courses, but other then that, I don't have any technical skills, and have no experience when it comes to using computers.

I hope this is an appropriate question for this site, and I would greatly appreciate any advice.

# Answer
> 2 votes
Symbolic algebra is a vast area... perhaps you should sniff around the sites for maxima, Pari/GP, or SAGE, all open source (full details on how they are built is available, essentially) packages. There are specialized journals on computer algebra and symbolic computation in general.

For enumerative combinatorics, Richard Stanley's homepage should give a starting point (also look at lecture notes on OCW, and courses on Coursera), check out the book by Flajolet and Sedgewick "Analytic combinatorics" and (a somewhat simpler exposition) Sedgewick and Flajolet's "An Introduction to the Analysis of Algorithms". Note that the stuff I cite is heavy going, more targeted at graduate students.

But before diving into this specialized stuff you'd need a solid ground on computer programming, data structures and other basic CSc stuff. Your interests aren't exactly bread-and-butter computer science, probably more in the line of graduate studies. Check if the schools you are considering have research in the areas that interest you.

---
Tags: education
---


# Question
Title: Are functions in O(n) that are nor in o(n) all in Θ(n)?
One of my lectures makes the following statement:

$$( f(n)=O(n) \land f(n)\neq o(n) )\implies f(n)=\Theta(n)$$

Maybe I'm missing something in the definitions, but for example bubble sort is $O(n^2)$ and not $o(n^2)$ but it's also not $\theta(n^2)$ since it's best case run time $\Omega(n)$.

What am I missing here?

# Answer
What you are missing is a very important point: An algorithm is never $O()$ of anything, since it is usually not a even a real-valued function.

When we say that bubble-sort is $O(n^2)$, what we mean is that in the function $f$, that represents the *worst case run-time* of bubble sort, is $O(n^2)$.

In this case, this function is indeed $\theta(n^2)$, since in the worst case, the run-time is bounded from below and from above by $c\cdot n^2$ for the relevant constants $c$.

To be more precise, the function that we refer to as the worst case runtime of an algorithm $A$ is defined by $$f\_A(n)=\max\_{x: |x|=n}\\{\text{runtime of $A$ on input x}\\}$$ And it is this function that we analyze for the worst case run time.

The best case run-time can be analyzed as well, of course. As you suggest, the best case run time of bubble sort is not $\theta(n^2)$, but rather $\theta(n)$.
> 11 votes

# Answer
Tell the lecturer they're wrong. Take the function $$ f(n) = \begin{cases} n & n \text{ is even}, \\ 1 & n \text { is odd}. \end{cases} $$ This function is $O(n)$ but neither $o(n)$ nor $\Theta(n)$.

Here is a monotone example, which might be more convincing: $$ g(n) = \exp \exp \lfloor \ln \ln n \rfloor. $$
> 15 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Solve a recurrence by drawing the recursion tree?
I'm studying for an entrance exam and I have sample questions. One of the questions is this

> Prove that recurrence $T(n) = T(n/5) + T(4n/5)+n/2$ has a solution $T(n) = \omega(n \log n)$.
>
> Solve by drawing the recursion tree.

This is what I drew on my paper:

```
root:  n/2 => (4n/5)/2

           => (n/5)/2

right sub tree:  (4n/5)/2 => (16n/25)/2

                          => (4n/25)/2

left sub tree:   (n/5)/2  => (4n/25)/2

                          => (n/25)/2

```

From what I saw online when I was searching for a solution to this question I noticed people were drawing the trees and saying Big O something as an answer. I'm wondering how do they determine that Big O notation is the correct answer for this question or if my tree is correct?

# Answer
> 1 votes
Use the Akra-Bazzi method. In terms of the notation there you have: $$ \begin{align\*} g(x) &= \frac{x}{2} = O(x^c) \\ a\_i &\> 0 \quad \forall i \\ 0 &\< b\_i \< 1 \quad \forall i \\ \end{align\*} $$ The requisites check out (and the somehow implied differences $h\_i(x)$ due to truncation if the divisions don't come out exact also check out). So we need the $p$ for which: $$ \left( \frac{1}{5} \right)^p + \left( \frac{4}{5} \right)^p = 1 $$ which is seen to be $p = 1$. Plugging into the equation: $$ T(x) = \Theta \left( x^p \left( 1 + \int\_1^x \frac{g(u) d u}{u^{p + 1}} \right) \right) = \Theta (x (1 + \frac{1}{2} \ln x)) = \Theta (x \ln x) $$

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


# Question
Title: Need help about solving a recurrence relation
I have a recurrence relation which is like the following:

$T(n) = 2T(\frac{n}{2}) + \log\_{2}n$

I am using recursion tree method to solve this. And at the end, i came up with the following equation:

$T(n)=(2\log\_{2}n)(n-1)-(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$ where $k=\log\_{2}n$

I am trying to find a theta notation for this equation. But i cannot find a closed formula for the sum $(1\times 2 + 2\times 2^{2} + \ldots + k\times2^{k})$. How can I find a big theta notation for $T(n)$?

# Answer
> 2 votes
For $\sum\_{0 \le r \le k} r \cdot 2^r$, start with: $$ \frac{1 - z^{k + 1}}{1 - z} = \sum\_{0 \le r \le k} z^r $$ As this is a polynomial, the following mangling doesn't need any justification: $$ z \frac{d}{dz} \frac{1 - z^{k + 1}}{1 - z} = \sum\_{0 \le r \le k} r z^r $$ Doing the operations indicated: $$ \sum\_{0 \le r \le k} r z^r = \frac{z^k (k z^2 - (k + 1) z) + z}{(1 - z)^2} $$ Finally: $$ \sum\_{0 \le r \le k} r 2^r = (2 k - 2) 2^k + 2 = \Theta(k 2^k) = \Theta(n \log n) $$

# Answer
> 2 votes
This looks like the running time of a divide-and-conquer algorithm. You can apply the Akra-Bazzi method here. The method works for recurrences of the form:

$$T(n)=\sum\_i^k a\_iT(b\_i n+h\_i(n))+g(n), \forall n\ge n\_0$$

In your case:

$k=1$

$g(n)=\log n$

$a=2,b=1/2$

$h(n)=0$

For this to work, we have to find a number $p$ satisfying $ab^p=1$. That's easy,let $p=1$.

The method tells us that $T(n)=\Theta(n^p(1+\int\_1^n\frac{g(x)}{x^{p+1}}dx))$

I computed the integral on WolframAlpha. The answer is $1-\frac{\log n + 1}{n}$.

Therefore, $$T(n)=\Theta(2n-\log n)=\Theta(n)$$

---

Here is another way of solving this. Let $n=2^m$

$T(2^m)=2(2T(2^{m-1})+(m-1))+m=2^2T(2^{m-2})+m+(m-1)=\dots=2^kT(2^{m-k})+m+(m-1)+\dots+m-k+1=2^m\Theta(1)+m(m-1)/2=\Theta(2^m)$.

So $T(n)=\Theta(n)$

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


# Question
Title: How does one deduce small step operational semantics?
This question arises from my reading of "Types and Programming Languages" (WoldCat) by Benjamin C. Pierce.

For the small step operational semantic evaluation rules for the arithmetic expressions (NB) in Figure 3-2 on page 41, there is the rule

> $pred\\;(succ\\;nv\_1)\rightarrow\\;nv\_1$

My understanding is that it is to keep out invalid input like

> $pred\\;(false)$

but how did he come to that exact syntax for the rule? Is there some algorithm that is used to massage the rules into the necessary form? Is there some book or paper that explains how to formulate rules for small step operational semantics?

Note: I am aware that there is a forum dedicated to questions for the book here.

# Answer
> 6 votes
Devising an operational semantics of a programming language requires ingenuity, just like engineering a new car does. Nevertheless, there are some principle and correctness criteria by which we can judge whether a given semantics is "good".

For example, a good operational semantics should make sure that "valid programs do not do bad things". In practice this translates to "if a program succesfully compiled it is not going to dump core when we run it". Some languages are unsafe in this respect (C/C++), some are designed with safety in mind (Java, Python), and some are proved to be safe (Standard ML).

One way of translating "valid programs do not do bad things" is to interpret "valid program" as "well typed program" and "bad thing" as "getting stuck during evalution, even though we have not reached a final value". For this to make sense you have to define what "well typed" and "value" means. The central theorem then is

> **Safety:** If a program $p$ has type $\tau$ then its evaluation diverges or terminates in a value of type $\tau$.

The theorem is typically proved by combining two lemmas:

> **Type preservation:** If $p$ has type $\tau$ and $p \mapsto p'$ then $p'$ has type $\tau$. Remember this as "types do not change during evaluation".
>
> **Progress:** If $p$ has type $\tau$ then it is either a value or there is a program $p'$ such that $p \mapsto p'$.

On the other hand, it does not matter what the operational semantics does with senseless programs, such as $\mathtt{pred}(\mathtt{false})$ because those do not have a type. It is the combination of typing and operational semantics that ensures safety. You cannot ensure safety just with the operational semantics, unless you are willing to make bizarre evaluation rules that will make your language awfully hard to debug.

# Answer
> 1 votes
The operational semantics is determined by what the language designer wants programs to do. If you define $\mathrm{pred}$ by $\mathrm{pred} \\: \mathrm{false} \to \mathrm{true}$ and $\mathrm{pred}$ by $\mathrm{pred} \\: \mathrm{true} \to \mathrm{false}$, that's perfectly fine mathematically speaking. On the other hand, humans are likely to puzzle as to why you called that operator $\mathrm{pred}$ instead of $\mathrm{not}$.

Informally, the predecessor of an integer $n$ is the integer $m$ such that $n$ is the successor of $m$: $\mathrm{pred}(m) = n$ when $n = \mathrm{succ}(n)$. The purpose of an operational semantics is generally to simplify expressions. Simplifying $\mathrm{pred} \\: (\mathrm{succ} \\: m)$ to $m$ is obvious.

You might wonder why not simplify $\mathrm{succ} \\: (\mathrm{pred} \\: n)$ to $n$. It's possible to prove that (for a reasonable calculus) this is unnecessary: with only the first rule, all *normal forms* contain only $\mathrm{succ}$ and no $\mathrm{pred}$ except inside functions that couldn't be evaluated for lack of an argument (this is covered a bit later in the book).

The asymmetry between $\mathrm{succ}$ and $\mathrm{pred}$ comes from $\mathrm{succ}$ being a constructor, and $\mathrm{pred}$ being the corresponding destructor. $\mathrm{succ}$ is a constructor because unary integers are defined as being either $0$ or $\mathrm{succ}(n)$ where $n$ is a unary integer. $\mathrm{succ}$ is a way to build an integer from something more primitive (a smaller integer). $\mathrm{pred}$ is a destructor: from what you feed it, it returns a more primitive integer. Rules of the form `destructor(constructor(thing)) → thing` are common.

---
Tags: semantics, operational-semantics, types-and-programming-languages, small-step-semantics
---


# Question
Title: What is the exact relation between programming languages and Turing machines?
I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, \Sigma, \delta, q\_0, F)$ where $Q$, $\Gamma$, $b \in \Gamma$, $\Sigma \subseteq \Gamma \smallsetminus \\{ b \\}$ as input, $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \\{ L, R, N \\}$ as transition function where $L$ = number of steps to the left, $R$ = number of steps to the right, $N$ = "standby", $q\_0 \in Q$ is the initial state and $F \subseteq Q$ is the set of end states.

How similar is implementing a programming language to implementing a Turing machine? Can it be said that what is done when a programming language is implemented is that a Turing machine like the above is defined? If yes, how come we can't just use a model that looks like the definition of a Turing machine when a programming language is defined? Instead something else like BNF seems to be the standard.

# Answer
Maybe I'm misreading the question, but it sounds like there's some confusion in the comparison between Turing machines and programming languages.

The definition and method of defining a Turing machine constitute a programming language. Turing machines represent programs in that language.

Language syntax and semantics (e.g., in BNF) can constitute a programming language, and artifacts which satisfy those syntactic and semantic constraints are programs in that language.

So it's not really precise (IMHO; of course we can think about what TMs do in different ways, and in some of these ways of looking at TMs, you could think of individual TMs as defining programming languages. Indeed, a classically constructed universal Turing machine defines a very clear programming language, i.e., representations of Turing machines as strings) to compare implementing a programming language to implementing a Turing machine. Implementing a programming language involves defining the rules of the game, much like Turing defined the rules of the game (or whoever it was, whatever) when he defined what it meant for something to be Turing machine.

"Implementing" a programming language, and defining Turing machines, is a very difficult activity. Writing programs in a language, and defining specific Turing machines, is also a difficult activity. But they are quite different activities (except in those exceptional cases where you're writing a Turing machine to act as an interpreter, in which case maybe it makes sense to talk about designing a programming language via writing a TM... but I'm not sure this is what you were after).
> 10 votes

# Answer
The Turing machine model is a *theoretical* model of what "computing" is all about. As a theoretical model it was designed so it is simple to manipulate and to prove things about it, specifically to explore what can or can't be computed. It also serves as a simple model in which to discuss (and prove things about) the time required to do a computation, or how much space (memory) is required. The emphasis is on *simplicity* (specially in using only basic mathematical concepts).

A programming language, in contrast, is designed to make it easy to write (and read!) by humans, often also such that the concepts of its application area are handled directly. For example, a language like Perl handles operations on strings, even complex stuff like searching for patters, directly. SQL is tailored to operating on relational databases, doing queries searching for data with certain constraints and manipulating the database. And so on.

The Church-Turing thesis asserts that anything that can be computed in any meaningful sense of the term can be computed by a Turing machine. This is the final outcome of a decade-long frenzy in comming up with models of computation, all of which turned out equivalent. So, in theory, yes, they are equivalent (as far as the definition of the language and its implementation, and the machine on which it runs are correct). But as the saying goes, in theory, theory and practice are the same thing; in practice, they are very different. To write down a Turing machine to do even simple tasks is a lot of painstaking work, and that might be just one simple line in your favorite programming language.
> 5 votes

# Answer
True, all (general purpose) programming languages are believed to be equivalent to the Turing machine. (According to the Church-Turing thesis, they will not compute more, and usually it is clear how to simulate a TM in your favourite language). That does not mean that programming a Turing machine is a practical thing to do. Far from it. To do real programming better languages are developed. In fact those languages evolve over time, when we learn what features make programming languages simpler to use, or less error prone.

Still, the Turing machine is around. It serves as a yard stick to define complexity, and computability.

(added.) As noted in the comments, not every programming language is designed to be of Turing power, some deal with specific tasks, like regular expressions. On the other hand, there are powerful exotic languages disgned in such a way to make programming virtually impossible. For fun.
> 4 votes

# Answer
nice question, but you're overthinking this. getting lost in the symbols. lets look at it all in a simple, basic way. a programming language is in ASCII or say just 0/1 bits for characters. now imagine the TM has 0/1 bits to simplify it, or say ASCII as input characters.

the key realization, and analogy, is that TM state table doubles as reading the input character set, and containing the programming language/program encoding.

this can be realized by building or examining simple TMs & their state tables to compute basic calculations eg sums or whatever. another very useful approach is to play with TM simulators.\[3\]

all this would be much more obvious if in some classes they taught CS using real TM compilers that would take an arbitrary program (source code) and compile it into a TM state table (similar to object code). unfortunately, nobody believes that is useful right now.\[1\] <sup>(plz vote to reopen if you disagree! =)</sup>

but if you play with TM simulators, it will help you build this basic intuition. \[2\] is possibly the most sophisticated available in the world right now.

\[1\] https://cs.stackexchange.com/questions/2916/is-there-a-compiler-from-high-level-language-to-turing-machine

\[2\] TM compiler in ruby with example source/object code & output (for a nonhalting $a+b=b+a$ commutative addition law verifier)

\[3\] https://cs.stackexchange.com/questions/10379/top-turing-machine-simulators-on-the-web
> -1 votes

---
Tags: turing-machines, formal-grammars, programming-languages, computation-models
---


# Question
Title: Are probabilistic search data structures useful?
A SkipList provides the same $O(\log n)$ bounds for search as a balanced tree with the advantage that rebalancing isn't necessary. Since the SkipList is constructed using random coin flips, these bounds only hold as long as the structure of the SkipList is sufficiently "balanced". In particular, with probability $1/n^c$ for some constant $c\>0$, the balanced structure might be lost after inserting an element.

Let's say I want to use a skip list as a storage backend in a web application that potentially runs forever. So after some polynomial number of operations, the balanced structure of the SkipList is very likely to be lost.

Is my reasoning correct? Do such probabilistic search/storage data structures have practical applications and if so, how is the above problem avoided?

Edit: I'm aware that there are deterministic variants of the SkipList, which, are much more complicated to implement in comparison to the (classic) randomized SkipList.

# Answer
I don't think there is a polynomial probability for losing 'balance'. After you insert an element in a skip list, you build a tower of copies above it by flipping a coin until it comes up heads.

So you have layers with fewer and fewer elements as you reach the top. Since a tower has height $k$ with probability $2^{-k}$, there is an element at height $k$ with probability (union bound) of less than $n/2^k$. Hence having an element at level $c\log n$ has probalitiy less than $1/n^c$. Towers of height $\omega(\log n)$ have subpolynomial probability. Let $M$ be the maximum level, then we have

$$E\[M\] = \sum\_{k\geq 1} Pr(M\geq k) \leq \log(n) + \sum\_{k\le \log(n)} n/2^k = \log(n) + 2.$$

Furthermore, on level $k$ there are $n/2^k$ elements with very high probability, as this is the sum of $n$ independent random variables and you can use Chernov's bound.

Since you can also show that you only do a constant number of steps per level (with very high probability!), search costs are logarithmic.

So you would have to be very unlucky indeed to end up with an unbalanced list. Note that 'luck' here is independent of your data, unlike for example in unbalanced search trees. Coin flips in Skip Lists are always random.

As far as I know, skip lists are of great practical interest, because it is relatively easy to implement them as lock-free search structures, with the obvious benefits. B-trees on the other hand are rather difficult to make performant under concurrent accesses.
> 6 votes

# Answer
Skip lists have other properties which might make them attractive in situations where operations other than just insert/lookup/delete are used.

For instance, skip lists have $O(1)$ expected time local updates when the modification location is known. This is certainly possible in $O(1)$ worst-case time with certain balanced binary search trees, but those structures tend to be pretty complicated to implement.

Additionally, skip lists have been a popular way to implement concurrent comparison-based search structures. Historically, balanced search trees have not performed as well under high concurrent contention.
> 1 votes

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


# Question
Title: Context free grammar for {a^mb^n | m ≠ n}
I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\\{{a, b}\right\\}$, but I am having difficulty accounting for the condition $m \neq n$.

This is what I have so far, but it clearly doesn't satisfy the above condition:

$\begin{align} &S \rightarrow aAb &\\ &S \rightarrow a &\\ &S \rightarrow b &\\ &A \rightarrow aA &\\ &A \rightarrow bA &\\ &A \rightarrow \lambda \\ \end{align}$

I have spent about an hour on this, and haven't found a solution. Any ideas?

# Answer
Hint: Start with a CFG for the language $\\{ a^{n+t} b^n : n \geq 0, t \geq 1 \\}$.
> 0 votes

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


# Question
Title: Complexity of a while loop that divides by parameter by three each iteration
I've learned that a while loop such as

```
int i = 100;
while (i >= 1){
     ...
     ///Stuff
     i = i/2
}

```

will run in logarithmic time, specifically, `O(logn)`, since it keeps dividing in half each time (like a binary search).

However, what if my while loop looks like this

```
 int i = 100;
    while (i >= 1){
         ...
         ///Stuff
         i = i/3
    }

```

Is the complexity still `O(logn)`?

Can someone explain yes/no and why?

# Answer
> 3 votes
Hint: The number of times the loop is run, assuming it starts at $n$ and divides by $b$ each time, is exactly $\lfloor \log\_b n \rfloor + 1$.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


title: What is a "reduction", really?

text:
# Question
Title: What is a "reduction", really?
I am studying computational theory with Sipser's textbook. I can't quite understand the definition of "reduction". For example, "this problem can be reduced to ATM ..."

What exactly does "to reduce" mean? I can't draw the picture in my head. Can anyone can help me understand this definition?

# Answer
> 13 votes
This is kind of a broad question, and there are a lot of well-written references. This answer is just a basic starting point.

Intuitively, when we reduce a problem $A$ to a problem $B$, we mean that if we know how to solve $B$, this somehow induces a solution to $A$ (the "somehow" is the reduction). Taking the contra-positive, this also means that if we know that $A$ is unsolvable (according to some fitting notion of unsolvability), then $B$ is also unsolvable.

In undergrad computability course, we usually talk about mapping reductions. A mapping reduction from $A$ to $B$ is a computable function $f:\Sigma^\*\to \Sigma^\*$, such that for all $x\in \Sigma^\*$ it holds that $x\in A$ iff $f(x)\in B$.

The intuition behind this definition is that, assuming we have an algorithm that solves $B$, then we can solve $A$. Indeed, given an input for $A$, we use the reduction $f$ to transform it to an input for $B$, and solve $B$ using our algorithm. The "iff" property of the reduction ensures that the answer we get on $B$ induces an answer for $A$.

As a concrete example, let's consider the halting problem: given a TM $M$ and input $w$, decide whether $M$ halts in its run on $w$. We want to reduce $A\_{TM}$ to the halting problem. That is, we want to show that if we could solve the halting problem, then $A\_{TM}$ is also solvable. So what we need to show is a function that takes an input $M,w$ for $A\_{TM}$, and transforms it into an input $M',w'$ for the halting problem, such that the $M$ accepts $w$ iff $M'$ halts on $w'$.

We do this as follows. Given input $M,w$, construct $M'$ to be the machine that behaves exactly like $M$, except that we replace the rejecting state of $M$ with a self-loop (that never halts). We then output $M',w$. Now, it is not hard to prove that $M$ accepts $w$ iff $M'$ halts on $w$, and thus we have a reduction. Also note that this reduction is computable, since computing $M'$ from $M$ is a simple matter of changing the behavior of a state.

---
Tags: terminology, reductions
---


# Question
Title: Witness length independent $\exists$-Operator
Short version:

Is there an operator $\exists$ (on complexity classes) s.t. $\exists P = NP$ and $\exists REC=RE$, i.e. you can use the same operator on multiple interesting classes without explicitly stating a class of functions that limits the length of the witnesses? The construction should not rely on the existence of a definition of the class using any specific computation model (like Turing machines), i.e. it should be defined for any class of languages.

---

Long Version:

For any complexity class $\mathcal{C}$, any language $L$ and any class of functions $F\subseteq\\{f|f:\mathbb{N}\rightarrow\mathbb{N}\\}$ define

$$\exists^{f,\\#} L =\\{x \in (\Sigma\setminus\\{\\#\\})^\*|\exists w\in(\Sigma\setminus\\{\\#\\})^\*: x\\#w \in L, |w| \leq f(|x|) \\}$$ $$\exists^F \mathcal{C} =\\{L|\exists\\#\exists f\in F\exists L'\in\mathcal{C}:L=\exists^{f,\\#} L'\\} \qquad .$$

Note: If $F=\mathbb{N}^{\mathbb{N}} = \\{f|f:\mathbb{N}\rightarrow\mathbb{N}\\}$ the length of the witness $w$ becomes unrestricted (set $f(n)$ to be the maximum length of a witness for all inputs of size $n$).

It is well known that $NP=\exists^pP$, where $p$ is the set of all polynomials (see WP:Polynomial hierarchy) and $\exists^{\mathbb{N}^{\mathbb{N}}}REC=RE$ (see WP:Arithmetical hierarchy).

Now I'd like to know, if one could get rid of the class of functions $F$ or define $F$ depending on the class $\mathcal{C}$ without using a certain way to define the class (Not: If $\mathcal{C}$ is the class of languages accepted by a TM in $\mathrm{DTIME}(\dots)$, then $F:=\dots$)

---

Things I've tried so far:

1. $\exists\mathcal{C} = \exists^F\mathcal{C} \text{ where } \exists^{o(F)}\mathcal{C} \subseteq \mathcal{C} \text{ and } \exists^F\mathcal{C}\nsubseteq \mathcal{C}$
2. $\exists\mathcal{C} = \exists^{F'}\mathcal{C} \text{ where } F'=\\{2^f|f\in F\\} \text{ and } F \text{ maximal s.t. } \exists^{F}\mathcal{C} \subseteq \mathcal{C}$

---
3. (**added:**) $\exists\mathcal{C} = \exists^F\mathcal{C} \text{ where } F=\\{f\\,|\\,\forall L\forall\\#\notin\Sigma(L):\\, \\{\\#^{f(|w|)}w|w\in L\\} \in \mathcal{C} \Leftrightarrow L \in \mathcal{C}\\}$, i.e. those functions s.t. $\mathcal{C}$ is "invariant" under padding ($\Sigma(L)=\\{a|\exists i\exists w\_1,\dots,w\_k \in L:\\, w\_i = a \\}$).

1 and 2 don't work for P, I'm not sure about 3.

# Answer
> 0 votes
As already suggested by Yuval Filmus and Steven Stadnicki, (3) works for $\mathrm{P}$. I'll elaborate on this:

Let $\Sigma(L)=\\{a\mid\exists i\exists w\_1,\dots,w\_k \in L:\\, w\_i = a \\}$ the set of symbols used by any word in $L$. Now take a symbol $\\#\notin\Sigma(L)$ and a function $f:\mathbb{N}\rightarrow\mathbb{N}$, we define: $$\mathrm{padded}(L,f,\\#) = \\{\\#^{f(|w|)}w \mid w\in L\\}\qquad.$$

We observe, that if $f$ can be computed in $\mathrm{FL}$:

$$\mathrm{padded}(L,f,\\#) \equiv\_1^{\log} L\quad,$$

since we only need to remove the padding (constant space) or count the symbols, calculate $f(|w|)$ and pad (logarithmic space). As a result polynomials are allowed (s.b.) for all classes s.t. a polynomial longer input does not offer extra resources (e.g. $\log (|w|^k)=k\log |w|$).

For any complexity class $\mathcal{C}$ define $$\mathrm{FPR}(\mathcal{C})=\\{f\mid\forall L\forall\\#\notin\Sigma(L):\\, \mathrm{padded}(L,f,\\#) \in \mathcal{C} \Leftrightarrow L \in \mathcal{C}\\}$$ the class of functions under which $\mathcal{C}$ is *resistant to padding*.

Also, we define an equivalence on function classes $F,F'$ where each one is an upper bound for the other:

$$F \lessapprox F' :\Leftrightarrow \forall f \in F\exists f'\in F'\forall x\in\mathbb{N}:f(x)\leq f'(x)$$ $$F \approxeq F' :\Leftrightarrow F \lessapprox F' \wedge F' \lessapprox F$$

Then, by using the space hierarchy theorem, the time hierarchy theorem and a variant for alternating TMs (see cstheory.se/4895) to exclude super polynomial (super linear) padding:

$$\mathrm{FPR}(\mathrm{L}) \approxeq \mathrm{FPR}(\mathrm{P}) \approxeq \mathrm{FPR}(\mathrm{NP})\approxeq \mathrm{FPR}(\Sigma\_i^p)\\ \approxeq\mathrm{FPR}(\mathrm{PSPACE}) \approxeq \mathrm{FPR}(\mathrm{EXP}) \approxeq p$$ $$\mathrm{FPR}(\mathrm{LINSPACE}) \approxeq \mathrm{FPR}(\mathrm{E}) \approxeq l$$

where $p$ / $l$ ist the set of all polynomials/linear functions respectively.

So if we define $$\exists\_{\mathrm{FPR}}\mathcal{C} := \exists^{\mathrm{FPR}(\mathcal{C})}\mathcal{C}\cup \mathcal{C}\qquad,$$ we get an operator that works like $\exists^p$ for $\mathrm{P}$ and the entire $\mathrm{PH}$ (including $\exists\_{\mathrm{FPR}}\Sigma^p\_i=\Sigma^p\_i$).

To apply the operator to $\mathrm{REC}$, we observe that for any $L \in \mathrm{REC}$ a TM accepts $w\in L$ halting after a computable number of steps. Since we can use the series of configurations as a witness, $\exists\_{\mathrm{FPR}}\mathrm{REC} = RE$, even though $\mathrm{FPR}(\mathrm{REC}) \not\approxeq \mathbb{N}^\mathbb{N}$ (e.g. WP:Buzy Beaver).

# Answer
> 2 votes
You don't need a witness at all. You can allow the Turing machine to make a non-deterministic "guess" at any time. A string is accepted iff there is a sequence of guesses that make the Turing machine accept it, otherwise it is rejected.

Edit: If you want a definition which does not rely on the machine model, then it would be a bit awkward. Here is one example, which includes a cheat - using the associated function class. Given a (time) complexity $C$ and its associated function class $FC$, the allowed witness lengths are parametrized by $f \in FC$: the lengths are given by $n \mapsto |f(0^n)|$.

---
Tags: complexity-theory
---


# Question
Title: Pointwise mutual information vs. Mutual information?
I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. Here are my questions.

* Is MI values a non-negative value or it can be either positive or negative? If it is always a non-negative value, why is it ?
* As I search online, the PMI can be positive or negative values and the MI is the expected value of all possible PMI. However, expected value can be positive or negative. If MI is really the expected value of PMI, why is it always positive ?

Did I misunderstand anything of MI and PMI here ? Thank you very much,

# Answer
> 4 votes
PMI can clearly be negative, since if $p(x,y)\<p(x)p(y)$, then taking $\log \frac{p(x,y)}{p(x)p(y)}$ gives a negative number.

But MI is always non-negative, as it can be written as $d\_{KL}(p(x,y)||p(x),p(y))$, where $d\_{KL}$ is the Kullback–Leibler divergence which is non-negative (the proof of the latter is not completely trivial).

Intuitively, this happens because if there is a point such that $p(x,y)\<p(x)p(y)$, then the probability must "compensate" for this later, with a pair $p(x',y')\>p(x')p(y')$.

---
Tags: probability-theory, information-theory, entropy
---


# Question
Title: TAPL: Explanation and example(s) for satisfied
This question arises from my reading of "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce.

On page 36 is the definition for *satisfied*

> A rule is *satisfied* by a relation if, for each instance of the rule, either the conclusion is in the relation or one of the premises is not.

On page 36 is the definition for *instance*

> An *instance* of an inference rule is obtained by consistently replacing each metavariable by the same term in the rule's conclusion and all its premises (if any).
>
> For example
>
> `if true then true else (if false then false else false) -> true`
>
> is an instance of **E-IFTRUE**, where both occurrences of $t\_2$ have been replaced by `true` and $t\_3$ has been replaced by `if false then false else
>  false`.

On page 15 is the definition for *relataion*

> An n-place *relation* on a collection of sets $S\_1, S\_2,..., S\_n$ is a set $R\subseteq S\_1\times\\;S\_2\\;\times\\;...\\;\times\\;S\_n$ of tuples of elements from $S\_1$ through $S\_n$. We say that the elements $s\_1\in \> S\_1$ thorugh $s\_n\in S\_n$ are related by $R$ if $(s\_1,...,s\_n)$ is an element or $R$.

On page 36 is the definition for *one-step evaluation relation ($\rightarrow $)*

> The *one-step evaluation relation $\rightarrow $* is the smallest binary relation on terms satisfying the three rules of Figure 3-1. When the pair $(t,t')$ is in the evaluation relation, we say that "the evaluation statement (or judgment) $t \rightarrow t'$ is derivable."

On page 34 are the three rules from Figure 3-1

**E-IFTRUE**

> \begin{equation}if\\;true\\;then\\;t\_2\\;else\\;t\_3\\;\rightarrow\\;t\_2\end{equation}

**E-IFFALSE**

> \begin{equation}if\\;false\\;then\\;t\_2\\;else\\;t\_3\\;\rightarrow\\;t\_2\end{equation}

**E-IF**

> \begin{equation}\frac{t\_1\rightarrow\\;t\_1'}{if\\;t\_1\\;then\\;t\_2\\;else\\;t\_3\\;\rightarrow\\;if\\;t\_1'\\;then\\;t\_2\\;else\\;t\_3}\end{equation}

Can someone explain this definition and give an example for parts of the defintion.
1. The conclusion is in the relation.
2. One of the premises is not.

Note: I am aware that there is a forum dedicated to questions for the book here.

Note: You can use Google Scholar to see more of the details to this question in context.

EDIT

To connect some of the dots about my comment regarding unification and term rewriting.

When I saw

$$(A\rightarrow B)\equiv (\neg A \vee B)$$

it reminded me of Horn claues from Prolog, that along with the example then connected with my understanding of term rewriting. Having the book "Term Rewriting and All That" (WorldCat) by Franz Baader and Tobias Nipkow, I quickly looked up satisfiability and found satisfiable on page 58. This is actually the start of whole chapter on Equational Problems; but it also covers unification. At that point I realized that the definition was dealing with Satisfiability and from there is was a topic I was already familiar. What threw me was the way Benjamin defined it. He used a very precise definition right up front in a manner I didn't associate with my knowledge.

If you work through the code as I am and understand logic programming, then the definition makes perfect sense.

# Answer
> 7 votes
One way of reading the definition of *satisfied* that might help is to change

> A rule is satisfied by a relation if, for each instance of the rule, either the conclusion is in the relation or one of the premises is not.

to the logically equivalent statement

> A rule is satisfied by a relation if, for each instance of the rule, if all the premises are in the relation, then the conclusion is in the relation.

Thus if the rule says, for instance,

$$ \dfrac{A \to B \quad B\to C} {A\to C} $$

Then binary relation $R$ satisfies this rule whenever for each instance of the rule, such as

$$ \dfrac{a \to b \quad b\to c} {a\to c} $$

if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.

Another way of stating this is that $R$ is closed by the rule (though this probably doesn't make it clearer).

Now let's return to the original statement. What

> A rule is satisfied by a relation if, for each instance of the rule, either the conclusion is in the relation or one of the premises is not.

is saying is that is it okay to have $(a,c)$ in the relation without the premises, but if all of the premises are in the relation, then $(a,c)$ must be. That is, it is okay to have not all of the premises in the relation, without imposing any additional constraint.

Personally, I think that thinking about this definition in terms of an implication is simpler, so I help this explanation helps.

# Answer
> 2 votes
As Dave Clarke pointed out the Definition of *satisfied* is actually an implication, remember in propositional logic: $$(A\rightarrow B)\equiv (\neg A \vee B)$$

This is no coincidence, inference rules are also used to define provability in formal logic.

---

Example for **E-IFTRUE**:

premise(s):

* There is no premise, this rule is an axiom (or rather a set of axioms for all terms $t\_2$,$t\_3$).

conclusion:

* the pair $($ `if true then true else (if false then false else false)`$,$ `true`$)$

Since the rule **E-IFTRUE** has no premises, **all** of the premises are in **any** relation for **every** instance. So a relation $R$ satisfying this rule has to contain all instance's conclusions, i.e. all pairs of terms $(t,t')$ such that $t'$ can be derived from $t$ using **E-IFTRUE**. So

$\\{($ `if true then true else false` $,$ `true` $), ($ `if true then false else false` $,$ `false` $), ($ `if true then false else true` $,$ `false` $),\dots \\} \subseteq R$.

---

Example for an instance **E-IF**:

premise(s):

* the pair $($ `if true then false else true`$,$ `false`$)$

conclusion:

* the pair $($ `if (if true then false else true) then true else false` $,$ `if true then true else false`$)$

Here we have two choices to satisfy a rule $R$: Either we leave out $($ `if true then false else true`$,$ `false`$)$ or we also have to include $($ `if (if true then false else true) then true else false` $,$ `if true then true else false`$)$. But actually, leaving out the premise is not an option, since the evaluation relation has to satisfy **E-IFTRUE** too and this rule requires the inclusion of $($ `if true then false else true`$,$ `false`$)$.

---

As Dave Clarke pointed out it may contain other pairs not required by any of the rules. This has to be allowed for each single rule because we want a the evaluation relation to satisfy multiple rules. By choosing the minimal relation we ensure that it's not possible to derive terms not captured by any rule.

---
Tags: satisfiability, term-rewriting, operational-semantics, small-step-semantics, types-and-programming-languages
---


# Question
Title: Could I simulate the implementation of memory components
I am currently reading the IEEE paper A Memory-Efficient Parallel String Matching Architecture for High-Speed Intrusion Detection by Kai Zheng, Bin Liu, Xin Zhang, and Yunhao Liu.

In the paper they propose a model for a memory-efficient multiple-character-approaching architecture consisting of multiple parallel DFAs.

I have read the paper and I have understood to an extent.

But when I think of implementation, could I simulate the SRAM, LE,BCAM etc.. as in the case of a network simulator (NS-2,OPNET,OMNET).

# Answer
> 1 votes
You can simulate the architecture using a **hardware-description language**.

Try VHDL (http://esd.cs.ucr.edu/labs/tutorial/) or Verilog ( http://www.asic-world.com/verilog/veritut.html) two of the most popular hardware description languages.

---
Tags: computer-architecture, simulation
---


# Question
Title: What are some of the practical applications of CSP process algebra?
CSP is used for the description and representation of concurrent systems, how it is used in practice (theoretically and programmatically)?

What are the application areas (other than concurrent and parallel systems) where it is used?

# Answer
One of the most celebrated applications of CSP and was the use of the CSP tool FDR in the analysis of the Needham-Schroeder protocol. It has had other applications in analyzing protocols and software design.

> Breaking and fixing the Needham-Schroeder Public-Key Protocol using FDR, Gavin Lowe, TACAS 1996
>
> Using CSP to detect errors in the TMN protocol, Gavin Lowe , Bill Roscoe, IEEE Transactions on Software Engineering 1997
>
> Model-Checking CSP-Z: Strategy, Tool Support and Industrial Application, Science of Computer Programming 2001
>
> Practical Application of CSP and FDR to Software Design, Jonathan Lawrence, Communicating Sequential Processes. The First 25 Years, 2005
> 1 votes

# Answer
CSP is the formal basis of the programming language Occam which compiled to INMOS Transputers. Transputers appeared in all sorts of devices, such as set-top boxes for satellite TV. Eventually, however, the company doing all of this work failed to achieve commercial success, and was eventually absorbed by another company.
> 3 votes

---
Tags: process-algebras
---


# Question
Title: Using the appropriate machine learning algorithm
I am not sure if this is the right forum to ask this.

I have some data of the houses, like their size(in square meters), if they use aircondition, how many residents live in, I have their electricity consumption as well. I want to train any Machine Learning Algorithm to the dataset above, in order to create a model that estimates the houses consumption.

I tried many different algorithms (using weka), but I did not have good results. I was said that SVMs could solve this problem, with the right preprocessing. However, i did not have good results either.

Can anyone help me, in the way i should approach this problem?

Thanks in advance

# Answer
There are not an appropiate algorithm for each problem, you must to research and compare results between your algorithms or techniques with an error measure (MSE, etc.).

In general, machine learning algorithms are empiric models (approximated functions). There are arised from the problem itself and a set of suppositions with no revealing the hidden model (many of them, are non-linear problems).

First of all, is necessary to be careful with the variables in the input and output layer, this can be categorical, symbolic or numeric (best case), and you have to model your own representation to preserve some features of interest (topology, etc.)

I will recommend you first of all, try with a multiple linear regression and explore the eventual correlations between variables to find any linear dependence, before do something.

Its a very good practice, normalize the numerical data in the training process, to get a well fitted bias.

Then, for instance, you could try with a multilayer feed forward neural network or SVD o fuzzy inference system.

I understand the machine learning problem as a research with a set of methods to get a good explanation for a given problem, and improvements on that methods.
> 1 votes

---
Tags: algorithms, machine-learning, artificial-intelligence
---


# Question
Title: If xor-ing a one way function with different input, is it still a one way function?
Suppose $f(x)$ is a one way function. What about $h(x)=f(x\_1) \\, \oplus \\,f(x\_2)$, where $x=x\_1 || x\_2$ and $\lvert x\_1 \rvert = \lvert x\_2\rvert$?

* $\oplus$ is exclusive disjunction (xor)
* $||$ is concatenation
* $|u|$ is the length of $u$

# Answer
> 8 votes
The function $h$ may not be one-way anymore.

We construct a counter example—a specific one way $f$ whose $h$ is not one-way anymore—in the following way. Assume $g$ is a one-way function that preserves size, and define $f$ on input $w=bx\_1x\_2$ in the following way, $$f(bx\_1x\_2) = \begin{cases} g(x\_1)\\,x\_2 & b=0 \\ x\_1\\, g(x\_2) & b=1 \end{cases}$$ (assuming $b\in\\{0,1\\}$ and $|x\_1|=|x\_2|$.) It is easy to see that $f$ is also one-way — to invert it, you need to either invert $g$ on the first half or invert $g$ on the second half.

Now we show how to invert $h$. Assume you are given $h(u,v)=Z$, we write it as $h(u,v)= z\_1z\_2$ with $|z\_1|=|z\_2|=n$. Then a possible preimage of $Z$ is $$u=0 \\,0^n \\,\langle g(0^n)\oplus z\_2\rangle$$ $$v=1 \\, \langle g(0^n)\oplus z\_1\rangle \\, 0^n$$

because $f(u) = g(0^n)\\, \langle g(0^n)\oplus z\_2\rangle$ and $f(v) = \langle g(0^n)\oplus z\_1\rangle \\, g(0^n)$ thus their XOR gives exactly $z\_1\\,z\_2$ as required.

---
Tags: cryptography, one-way-functions
---


# Question
Title: Acyclic Tournament Digraphs and Hamiltonian Paths
I am studying MIT OCW lecture notes but they do not have solutions for the following problem.

**Directed Acyclic Tournaments**

In a round-robin tournament, every two distinct players play against each other just once. For a round-robin tournament with no tied games, a record of who beat whom can be described with a tournament digraph, where the vertices correspond to players and there is an edge $x \rightarrow y$ iff $x$ beat $y$ in their game.

A *ranking* is a path that includes all the players. So in a ranking, each player won the game against the next lowest ranked player, but may very well have lost their games against much lower ranked players —whoever does the ranking may have a lot of room to play favorites.

1. Give an example of a tournament digraph with more than one ranking.
2. Prove that if a tournament digraph is a DAG, then it has at most one ranking.
3. Prove that every finite tournament digraph has a ranking.
4. Prove that the greater-than relation, $\>$, on the rational numbers, $Q$, is a DAG and a tournament graph that has no ranking.

I got stuck at questions 2, 3, and 4. I have no idea how to solve it. I tried induction on b without a luck but still induction does not even help for infinite DAG cases.

# Answer
> 3 votes
I am completing Nicholas's answer because I think there are problems with his answers to 3 and 4 and explaining why is a bit too long for comments.

For 3. you need to show there is a simple path in the tournament that visits every vertex (this is called a hamiltonian path). You can do this simply by induction. Clearly this is true for a tournament on 2 vertices. Now assume you have a tournament $T = (V, A)$ on $n$ vertices. Remove some arbitrary $v$ from $V$ and find a hamiltonian path $v\_1, \ldots, v\_{n-1}$ in the induced tournament on $V \setminus \\{v\\}$. If for all $i \leq n-1$, $(v\_i, v) \in A$, then $(v\_{n-1}, v) \in A$ and you can append $v$ to the existing path. Otherwise, there exists some edge from $v$ to the $\\{v\_1, \ldots, v\_{n-1}\\}$; let $i$ be the *smallest* integer such that $(v, v\_i) \in A$. Either $i = 1$ and you can pre-pend $v$ to the existing path, or, since $i$ was the smallest $i$ such that $(v, v\_i) \in A$, you know that $(v\_{i-1}, v) \in A$, and, therefore, you can take the path $v\_1, \ldots, v\_{i-1}, v, v\_i, v\_{i+1}, \ldots, v\_{n-1}$.

For 4., I also don't think it's enough to say that the rationals have no infimum or supremum. That's true of the integers too, but there exists a path through the integers which is infinite in both directions. I think the crucial property of the rationals that causes problems is that they are *dense*: there is a rational between every two rationals. In particular, assume for contradiction there exists a path that visits all rationals in the graph defined in the question. Take any edge $(x, y)$ in the path: $x \< \frac{x+y}{2} \<y$, so $\frac{x+y}{2}$ cannot precede $x$ in the path and it cannot succeed $y$, so it cannot be in the path - a contradiction.

# Answer
> 1 votes
For clarity let $T= (V,E)$ be a tournament and let $a \rightsquigarrow b$ denote a path from $a$ to $b$ in $T$.

1. A simple directed cycle clearly gives a tournament with more than one ranking.
2. Suppose there is more than one ranking. Then there exists subpaths $a \rightsquigarrow b$ and $b \rightsquigarrow a$ in their respective rankings. This implies a cycle in the original tournament $T$, which contradicts the fact that $T$ is a DAG.
3. Topologically sort $T$. Suppose $v\_i, \rightsquigarrow v\_{i+1}$ does not hold under this ordering. Then by definition of DAG $v\_{i+1} \rightsquigarrow v\_i$ must be true. But this is a contradiction with our topological ordering.
4. I may be wrong, but there must be a "winner" (i.e. supremum) in a tournament and there is no such rational number in $\mathbb{Q}$.

---
Tags: graphs, proof-techniques
---


# Question
Title: Is the 2nd parity bit in RAID 6 a simple calculation?
I'm trying to understand how the 2nd parity bit or byte is set in RAID 6. I'm reading a paper by H. Peter Anvin, and it goes into Galois field algebra, which is somewhat new to me. Anyway, a rep from HP was trying to explain RAID 6 to me and she thought it was merely two XOR operations, one for the 1st parity bit and one for the 2nd. This doesn't make sense to me, but since I'm still working through the paper I don't know if it reduces to something simple for RAID 6 as opposed to RAID n. It looks to me like the 2nd parity bit is quite a bit more complicated than the XOR based 1st parity bit. Is that true?

# Answer
The general case is indeed a bit complicated.

However, in the case of **4 disks** you can simplify it a lot; you do not really need to know any fancy math. You only need to know how to store **4 bits** redundantly, and then you already know everything; just repeat the same scheme for each group of 4 bits that you need to store.

We can represent the scheme as 4 x 4 tables. The first 2 bits of our data determine the row and the last 2 bits of our data determine the column.

**Disk 1:** Just store the first 2 bits. That is:

```
00 00 00 00
01 01 01 01
10 10 10 10
11 11 11 11

```

**Disk 2:** Just store the last 2 bits. That is:

```
00 01 10 11
00 01 10 11
00 01 10 11
00 01 10 11

```

So far so good. Given disk 1 + disk 2, we can recover our original data: disk 1 tells us the row (the first 2 bits of the original data) and disk 2 tells us the column (the last 2 bits of the original data).

**Disk 3:** This is what we do on RAID5, just XOR the bits:

```
00 01 10 11
01 00 11 10
10 11 00 01
11 10 01 00

```

Again, everything is still fine. You can recover the original data using disk 1 + disk 3 or disk 2 + disk 3. A key observation is that the lookup table for disk 3 forms a Latin square: all elements of each row are distinct, and all elements of each column are distinct. For example, if you know the data on disk 1, you know the right row, and then you can use the data on disk 3 to recover the column. Conversely, if you know the data on disk 2, you know the right column, and then you can use the data on disk 3 to recover the row.

**Disk 4:** Here we can use the following lookup table:

```
00 01 10 11
10 11 00 01
11 10 01 00
01 00 11 10

```

Don't worry how it is constructed; we do not really care about that. The crucial properties are:

* The lookup tables of both disk 3 and disk 4 are Latin squares. Therefore if you know 1 + 3 or 1 + 4 or 2 + 3 or 2 + 4, you can recover both row and column (i.e., the original data).
* The lookup tables of disk 3 and disk 4 form orthogonal Latin squares, which makes it possible to recover the data if we only have disks 3 + 4.

Let's elaborate on the second point. By concatenating the lookup tables of disk 3 and disk 4, we get this matrix:

```
0000 0101 1010 1111
0110 0011 1100 1001
1011 1110 0001 0100
1101 1000 0111 0010

```

Now note that each 4-bit string occurs in this table exactly once. That is, if we know what is stored on disks 3 + 4, we know where we are on this table. We know both the row and the column, and hence we can recover the original data.

---

If you insist on seeing the connection to Galois fields, consider the field $F = GF(2^2)$. Label the elements of the field with $F = \\{0,1,x,x+1\\}$; these correspond to 2-bit strings ($0$ ≈ `00`, $1$ ≈ `01`, $x$ ≈ `10`, $x+1$ ≈ `11`). Now any 4-bit string can be encode as a pair $(a,b)$, where $a,b \in F$.

A pair $(a,b)$ is now stored as follows:

* Disk 1 stores $a$.
* Disk 2 stores $b$.
* Disk 3 stores $a+b$.
* Disk 4 stores $xa+b$.

Now given, for example, just $p = a+b$ and $q = xa+b$, you can solve $a$ and $b$. Using the rule $2 \equiv 0$, you can find

* $p + q = (xa+b) + (a+b) = (x+1)a + 2b \equiv (x+1)a$,
* $p + xq = (xa+b) + x(a+b) = 2xa + (x+1)b \equiv (x+1)b$.

Then divide by $x+1$ to get $a$ and $b$, etc. But in the end, this approach gives you precisely the same lookup tables as what was presented above.
> 14 votes

# Answer
The computation for $Q$ is *definitely* more difficult than the XOR computation needed for $P$ though it is in one sense the same kind of calculation: a polynomial evaluation.

Stripped of the detailed computational techniques described in the link, the idea is to regard the $n$ data bytes/drives $D\_0$, $D\_1, \ldots, D\_{n-1}$ as the coefficients of a polynomial $D(x) = D\_0 + D\_1x + \cdots + D\_{n-1}x^{n-1}$. Then,

$\qquad \begin{align\*} P &= D(1) = D\_0 \oplus D\_1 \oplus \cdots \oplus D\_{n-1}\\ Q &= D(\alpha) = D\_0 \oplus D\_1\cdot\alpha \oplus \cdots \oplus D\_{n-1}\cdot\alpha^{n-1}\\ &= ((\cdots(D\_{n-1}\cdot\alpha \oplus D\_{n-2})\cdot\alpha \oplus \cdots \oplus D\_1\cdot\alpha) \oplus D\_0 \end{align\*}$

where $\alpha$ is an element (denoted by $\\{02\\} = (00000010)$ in the paper cited by the OP) of the Galois field GF$(2^8)$ (also denoted $\mathbb F\_{2^8}$) whose $256$ elements are the $256$ $8$-bit bytes, and the second line of the equation for $Q$ can be recognized as Horner's rule. Of course, the computation for $P = D(1)$ can also be thought of as using Horner's rule except that we are ignoring the multiplications by $1$ as NOPs and eliding all the parentheses in Horner's rule since they are unnecessary.

After the drives have been written,

* If either or both of $P$ and $Q$ fail, there is no problem; $P$ and $Q$ can be recomputed and stored on replacement drives.
* If the only failure is one data drive, say the $i$-th drive, then its contents can be recomputed since $$D\_i = D\_0 \oplus D\_1 \oplus \cdots \oplus D\_{i-1} \oplus D\_{i+1} \oplus \cdots \oplus D\_{n-1} \oplus P.$$
* If one data drive and $Q$ fails, the data drive can be recomputed as described above, and then $Q$ can be recomputed.
* What to do in the other cases: one data drive and $P$ failing or two data drives failing are more complicated to describe, but the methods can be understood more easily using the polynomial perspective described here. For example, if the $i$-th and $j$-th drives have failed, reconstruction is effectively the solution of the simultaneous equations: $$\begin{align\*} D\_i \oplus D\_j &= P \oplus \sum\_{k: k \neq i, j} D\_k\\ \alpha^i\cdot D\_i \oplus \alpha^j \cdot D\_j &= Q \oplus \sum\_{k: k \neq i, j} D\_k\cdot\alpha^k. \end{align\*}$$ where the right hand sides can be computed from the contents of the non-failed drives.
> 7 votes

# Answer
It looks pretty damned complicated to me.

> Thus, in the formula above, the calculation of P is just the XOR of each stripe. This is because addition in any characteristic two finite field reduces to the XOR operation. The computation of Q is the XOR of a shifted version of each stripe.

(P being the first parity bit and Q being the second.)

So it sounds like the explanation you got is a valid high level description of the calculation, without getting into the mathematical theory and details that neither you or her (or me, or most anyone else) actually understand.
> 1 votes

# Answer
The **three disk** raid-6 is trivial: Just store the same information on disk 1, disk 2 and disk 3. Any two disks may fail and you can still recover the data. So a three disk raid-6 is basically just a three disk raid-1.

In the **four disk** case, there are two data "disks" (let's call them $A$ and $B$) and two parity "disks" (let's call them $P$ and $Q$). Furthermore, we have to operate on two bits from each disk at a time, so the minimum data item (whose parity generation is shown here) is four bits: Two bits on disk $A$ and two bits on disk $B$. This will generate two bits of parity $P$ and two more bits of parity $Q$. If we have more bits, we just repeat this scheme as needed.

The first parity $P$ is calculated normally, using a standard XOR ($⊕$) scheme:

> $P = A ⊕ B$

For the second parity $Q$, we have to mangle one of the data items before we do the XOR, so that it becomes different from $P$:

> $Q = A ⊕ B^\*$

The mangled $B^\*$ is calculated from $B$ as follows: The first bit of $B^\*$ is the XOR of both bits from $B$, and the second bit of $B^\*$ is a copy of the first bit of $B$:

> $B^\* = (B^\*\_1, B^\*\_2) = (B\_1 ⊕ B\_2, B\_1)$

The above formula leads to the following table for the calculation of $B^\*$ from $B$:

> $00 \rightarrow 00$
> $01 \rightarrow 10$
> $10 \rightarrow 11$
> $11 \rightarrow 01$

Note, that the value $00$ remains unchanged, when mangled, while the other values go through a cycle of three: $01 \rightarrow 10 \rightarrow 11 \rightarrow 01$.

Unmangling is rather straightforward: Because of the cyclic property, just repeat the mangling twice to do an unmangle. Or invert above formula for $B^\*$, which leads to:

> $B = (B^\*\_2, B^\*\_1 ⊕ B^\*\_2)$

So, unmangling is somewhat symmetrical to mangling.

Now comes the magic, that will later enable us recovery in the scenario, that the two data disks fail and only the parity disks survive: What happens, if $B$ and $B^\*$ get XORed? Now, let's have a look:

> $B ⊕ B^\* = (B\_1, B\_2) ⊕ (B\_1 ⊕ B\_2, B\_1) = (B\_1 ⊕ B\_1 ⊕ B\_2, B\_1 ⊕ B\_2) = (B\_2, B\_1 ⊕ B\_2)$

The nice result: XORing $B$ and $B^\*$ is identical to performing an unmangle step on $B$. Thus $B$ can be recovered from $B ⊕ B^\*$ by applying a mangle to it: $B = (B ⊕ B^\*)^\*$. And as $(B ⊕ B^\*)$ is the result of XORing the two parity values $P$ and $Q$, recovery from the parity disks alone becomes possible.

Now, we have everything together: To store $A$ and $B$ on a RAID-6, we calculate first the mangled datum $B^\*$, and then the standard parity $P$ from $A$ and $B$ and the mangled parity $Q$ from $A$ and $B^\*$:

> $B^\* = (B\_1 ⊕ B\_2, B\_1)$
> $P = A ⊕ B$
> $Q = A ⊕ B^\*$

Recovery after failure of two disks is as follows:

* If $A$ and $B$ survive, just recompute $P$ and $Q$.
* If $A$ and $P$ survive, recover $B = P ⊕ A$, then recompute $Q$.
* If $B$ and $P$ survice, recover $A = P ⊕ B$, then recompute $Q$.
* If $A$ and $Q$ survive, recover $B^\* = Q ⊕ A$, then recover $B$ from $B^\*$ via an unmangle operation (or a double mangle), then recompute $P$.
* If $B$ and $Q$ survive, calculate the mangled $B^\*$ from $B$, then recover $A = Q ⊕ B^\*$, then recompute $P$.
* If $P$ and $Q$ survive, use the formula explained above $B = (P ⊕ Q)^\*$, then recover $A = P ⊕ B$.

In the **five disk** case, there are three data disks $A$, $B$ and $C$ and again two parity disks $P$ and $Q$. The most notable difference is, that the mangle is performed *twice* on $C$, when calculating $Q$:

> $P = A ⊕ B ⊕ C$
> $Q = A ⊕ B^\* ⊕ C^{\**}$

Recovery in the five disk case follows the same principles as for the four disk case. In those cases, that two data disks and either $P$ or $Q$ survives, one has to take out *two* values from the parity instead of just one, and follow with the correct unmangle function in case of $Q$. For example, $C$ is recovered from $A$, $B$ and $Q$ as follows: $C = (Q ⊕ A ⊕ B^\*)^\*$.

The most tricky case is, if disks $A$, $P$ and $Q$ survive. Then $A$ is first XORed out of $P$ and $Q$, and then $(P ⊕ A)$ is mangled before XORing with $(Q ⊕ A)$. That maps out $B$ and leaves plain $C$:

> $(P ⊕ A)^\* ⊕ (Q ⊕ A) = (A ⊕ B ⊕ C ⊕ A)^\* ⊕ (A ⊕ B^\* ⊕ C^{\**} ⊕ A) =$
> $= (B ⊕ C)^\* ⊕ (B^\* ⊕ C^{\**}) = (B^\* ⊕ C^\*) ⊕ (B^\* ⊕ C^{\**}) =$
> $= B^\* ⊕ C^\* ⊕ B^\* ⊕ C^{\**} = B^\* ⊕ B^\* ⊕ C^\* ⊕ C^{\**} = (C ⊕ C^\*)^\* =$
> $= (C^{\**})^\* = C^{\***} = C$

For **six or more disks**, the principle remains the same, but the mangle operation needs to be replaced with one that has a longer cycle. This also requires the use of more bits. With four bits, a possible mangle op is:

> $M^\* = (M\_1 ⊕ M\_4, M\_1, M\_2, M\_3)$

$0000$ is again mapped on $0000$, while all other values go through a 15-stage cycle: $0001 \rightarrow 1000 \rightarrow 1100 \rightarrow 1110 \rightarrow 1111 \rightarrow 0111 \rightarrow 1011 \rightarrow 0101 \rightarrow 1010 \rightarrow 1101 \rightarrow 0110 \rightarrow 0011 \rightarrow 1001 \rightarrow 0100 \rightarrow 0010 \rightarrow 0001$

With its 15-stage cycle, this mangle op can be used for up to 15 data disks and two parity disks. For the $P$ parity, all values are XORed together as is, and for $Q$, the first disks datum is not mangled, the second disks datum is mangled once, the third disks datum is mangled twice, and so on.
> 1 votes

---
Tags: operating-systems, storage, error-correcting-codes
---


title: Select optimal subintervals from array

text:
# Question
Title: Select optimal subintervals from array
I have an input array and I have to select an indefinite number of intervals from it so that the "profit" is maximal and I have exactly T elements selected in total, where T is given. Profit means the sum of all the elements of an interval, except for the first element. An interval can consist of a single element, meaning that the profit for such an interval is 0. The array may contain negative numbers. Apparently dynamic programming is the answer to this problem, but I cannot think of an efficient algorithm to solve it. This is homework, so I would appreciate any help.

# Answer
> 1 votes
Search for maximum subsequence sum problem, here you will find a linear time solution. Bentley's "Programming Pearls" gives several alternative algorithms and some history. The linear time solution is obvious in hindsight, but it took several tries by experts to come up with it...

---
Tags: dynamic-programming
---


title: Number of cycles in a graph?

text:
# Question
Title: Number of cycles in a graph?
Can the number of cycles in a graph (undirected/directed) be exponential in the number of edges/vertices?

I'm looking for a polynomial algorithm for finding all cycles in a graph and was wondering if it's even possible.

# Answer
> 3 votes
Assuming you mean simple cycles (otherwise the number is infinite) - yes, of course the number can be exponential: consider the complete graph on $n$ vertices, then every sequence of distinct vertices can be completed to a simple cycle. So you get at least $n!$ cycles.

Even if you ignore cyclic permutations of a cycle, this is still exponential: you can take only cycles of length $n/2$, and you have more than ${n\choose n/2}$ such cycles.

# Answer
> 3 votes
The problem you want to solve is #CYCLE. Unless P=NP, it cannot be solved, for a proof look at the chapter on Counting Complexity in Arora and Barak. It is a gadget construction that reduces solving Hamiltonian path to #CYCLE and hence unless P=NP, Hamiltonian cycle - a NP-Complete problem cannot have a poly time solution.

As for the first question, as Shauli pointed out, it can have exponential number of cycles. Actually it can have even more - in a complete graph, consider any permutation and its a cycle hence atleast n! cycles. Actually a complete graph has exactly (n+1)! cycles which is $O(n^n)$.

---
Tags: graphs
---


# Question
Title: Algorithm to find the probability of a given text to be about a large topic
I want the conditional probability for each topic (being the word that we give as input). For example, the text being

> have seen and reviewed your requirements you posted here. If you can give me the fix criteria/category of your data mining then I can do this job. If you want me to define and allot criteria and categorize it in then charges will be extra for per categorization included.
>
> I have seen and reviewed your requirements you posted here. If you can give me the fix criteria/category of your data mining then I can do this job. If you want me to define and allot criteria and categorize it in then charges will be extra for per categorization included.

---

Assume that I give a word called **research** as an input, I want to know

```
What is the likelihood/probability that the text relates to research?

```

What algorithms we should create to get the above?

# Answer
You can try simple probabilistic graphical models, the simplest one being Naive Bayes.

One way to do this would be to represent a portion of text as a word frequency vector, that will be associated with a topic (the "class variable"). Then you use many such texts that are associated with topics to train your model (i.e. you model the probability of a frequency vector given a certain topic). Finally, given a new text you can ask what is the most likely topic assignment.

Naive Bayes, the simplest graphical model, would miss dependencies between the frequencies of the various words, but it is worth a shot as it is easy to implement. More complicated models could be used to capture these dependencies.
> 3 votes

# Answer
Try Latent Semantic Analysis or the similar Latent Semantic Indexing which reduces documents to vectors, and typically finds principal components via singular value decomposition, SVD that roughly relate or correspond to intrinsic or latent "subjects". It had major or key success in the Netflix datamining contest. Similarity is computed using vector algebra e.g. the cosine similarity or similar metrics.
> 1 votes

---
Tags: machine-learning, natural-language-processing
---


# Question
Title: How do we know to what community a vertex belongs to in the Girvan-Newman algorithm?
So I've been doing some reading on community detection in graphs as I'm planning on working on my thesis for it. I've been reviewing papers regarding the same and came across the Girvan-Newman algorithm. I've read the paper and have a doubt which I couldn't really figure out.

The algorithm works by removing the edge which has the highest value of "edge betweenness" in every iteration. Suppose I have a graph $G(V, E)$ such that $V = \\{ v\_{1}, v\_2, \cdots , v\_n\\}$. Now suppose this graph is such that it has 2 distinct communities (something we already know but that's what the algorithm should detect). After the first iteration, it would remove the edge which has the highest value of edge betweenness. Now my question is, after this is done (or even after a few iterations), say I have any vertex $v\_i$, how do we know which community this vertex belong to? Am I missing something here?

# Answer
> 4 votes
This is hierarchical clustering method. As you remove edges, at some point the graph will become disconnected: the connected components are your top-level communities. As you keep removing edges, the top-level communities become disconnected too, and you can think of the new smaller connected components as sub-communities. So you can think of the algorithm as building a tree of finer and finer communities, where the leaves are individual vertices.

---
Tags: algorithms, graphs, network-analysis
---


title: Complexity of slightly tricky for loop

text:
# Question
Title: Complexity of slightly tricky for loop
I'm trying to determine the complexity of this for loop:

```
for (int j =3; j <= n-2; j+=2) {
   ....
}

```

By trying out lots of examples, I came up with $\frac{n-4}{2} + 1$. This seems to work with every number now.

However, I am looking for a systematic and quick way to find these sorts of complexities. For example, can you show me the proper way to find the complexity for the above loop?

# Answer
There is no systematic way, since the expressions in the loop may be arbitrary. For your particular case, assuming that the statements executed are $O(1)$, then the complexity is obviously $O(n)$. If you instead want to determine the exact number of iterations, you may reason as follow. As noted by @blob, you are counting odd numbers starting from 3.

The number of iterations depend on the parity of $n$, i.e., you must consider two cases: $n$ is even or odd. Another thing you must take into account is that the loop is executed one more time simply to test the termination condition, without executing the loop statements.Since you are executing this last iteration without counting the corresponding odd number, you may consider that, equivalently, you are including 1 (which is excluded since you start from 3).

Let $n = 2k, k\in N\quad$. In this case, the total number number of iterations is $(n-2)/2 \quad$ including the last one that simply terminates the loop without executing the loop statements. Now, since $n$ is even, from $n = 2k \quad$ you can immediately derive that the total number of iterations is also given, equivalently, by $k - 1$.

Let $n = 2k + 1, k\in N \quad$. Reasoning as before, let $x = n + 1 \quad$, which is the even successor of $n$. Since $x = 2k + 2 = 2 * (k+1) \quad$, you can conclude immediately that the total number of iterations is given by $k + 1 - 1 = k \quad$ when $n$ is odd.

Then, you may simply say that the total number of iterations is simply $\lceil n/2 \rceil - 1\\:$ or $\lceil (n - 2)/2 \rceil \quad$, without taking into account the parity of $n$. Note that this is equivalent to your own answer $\lceil (n - 4)/2 \rceil + 1\\:$.

Example: for $n = 10 = 2 * 5 \quad$, the iterations are 5 - 1 = 4. For $n = 9 = 2 * 4 + 1 \quad$, the iterations are 4.
> 1 votes

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


title: Constructing PDA for $a^{2n} b^{3n}$

text:
# Question
Title: Constructing PDA for $a^{2n} b^{3n}$
So I have been given the task of creating an PDA that recognises the language

$\\{a^{2n} b^{3n} \mid n = 0,1,2,\dots\\}$.

Am I right in thinking that it needs to have at least 3 times number of $b$'s than $a$'s?

So for example: $aabbb$ would be accepted $aaabb$ would NOT be accepted However, how do I show that using JFlap because I am unfamiliar with the software?

# Answer
The following pushdown automaton should do the trick. I publish this only because the existing answer can be improved upon. (Note, I am using $e$ to denote $\epsilon$- (or $\lambda$-) transitions.

The idea is that the left-hand part counts the number of $a$'s (modulo 2). Each time it has seen two $a$'s, it pushes $3$ $b$'s onto the stack. Nondeterministically, the machine can change to the right-hand state. It then matches a $b$ from the string fro each $b$ on the stack.
> 7 votes

# Answer
Yes the number of b's is at least 3 times the number of a's except when n=0 in which case you get the empty string. Your language is equivalent to $\\{(aa)^n(bbb)^n:n=0,1,\dots\\}$. So if you can find a PDA for $\\{a^nb^n\\}$, then you can find one for your language. Here is the transition function $\delta$ (the stack initially contains the symbol \\$ and $q\_5$ is the accepting state):

$\delta(q\_1,\epsilon,\epsilon)=(q\_5,\epsilon)$

$\delta(q1,a,Z)=(q\_1,aZ)$

$\delta(q\_1,b,aZ)=(q\_2,Z)$

$\delta(q\_2,b,aZ)=(q\_3,Z)$

$\delta(q\_3,b,aZ)=(q\_4,Z)$

$\delta(q\_4,b,aZ)=(q\_2,Z)$

$\delta(q\_4,\epsilon,\\$)=(q\_5,\epsilon)$
> 0 votes

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


# Question
Title: Implement queue with a linked list; why would it be bad to insert at the head and remove at the tail?
In my textbook, Data Structures and Algorithms in Java, the author says when implementing a queue using a linked list you choose the front of the queue to be at the head of the list, and the rear of the queue to be at the tail of the list. In this way, you remove from the head and insert at the tail.

The author then asks cryptically, "Why would it be bad to insert at the head and remove at the tail?" without providing an answer.

I can't see what the difference really is. In effect, "Head" and "Tail" are just arbitrary names we define. What would be so bad if to enqueue() we add a head and create a reference to the old head, and to dequeue() we take from the tail and move the tail over?

What is the answer to the author's question?

# Answer
In a single linked list, every element has a pointer to the next element. If you have an additional pointer to the tail element, it takes you a constant number og operations to *add* to the list at the tail: get the tail pointer, add an element after the tail, put this new element as new tail. Removing from the head also takes a constant number of operations: make you new item new, head, point to old head.

However, *removing* from the tail demands a pointer to the predecessor to the current tail. This takes you as many operations as there are elements, namely linearly many.

Another solution is to use a doubly linked list, then you can choose what you will, but it uses twice as much memory.
> 11 votes

# Answer
Removing from the head and inserting at the tail are both constant time operations with a singly linked list, assuming head and tail pointers. Inserting at the tail is also constant time. But removing from the tail means moving the tail pointer toward the head, and since you don't have a back pointer you can't do that without traversing the whole list to find the element previous to the tail. This makes insertion a linear time instead of a constant time operation and that's why it's worse.
> 5 votes

---
Tags: time-complexity, linked-lists, abstract-data-types
---


# Question
Title: What is the maximum number of shortest paths between any pair of vertices in a chordal graph?
A graph $G$ is *chordal* if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a *clique tree* representation. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a *minimal separator*. In general, $G$ can have more than one clique tree representing it. A graph is said to be *geodetic* if the shortest path between any pair of vertices is unique.

Consider a chordal graph $G$ in which every minimal separator is a singleton set. I can prove such a graph is geodetic, but this property doesn't hold once minimal separators get larger. For example, consider a graph with a minimal separator $S = \\{2,3\\}$ of size 2 below. It already has 2 shortest paths between the vertices 1 and 4.

In fact, consider two adjacent vertices in a clique tree of a chordal graph. Let $S$ be the minimal separator corresponding to the edge between them. Now consider two distinct vertices $u$ and $v$ in these adjacent cliques such that $u,v \notin S$. The number of shortest paths from $u$ to $v$ is the size of the minimal separator between them. This is because, roughly speaking, it takes one step to move from any vertex in a clique to a separator, and likewise any vertex in a clique can be reached with one step from the separator.

Finally, consider an example like below. The graph has 3 maximal cliques, and the minimal separators are $\\{ 4,5 \\}$ and $\\{ 2,3 \\}$. Now the number of shortest paths from 1 to 6 is $2 \times 2 = 4$.

> Given a connected chordal graph $G$ (with no loops nor parallel edges), what is the maximum number of shortest paths there can exist between any pair of vertices? How can it be bounded (in terms of $n$ and $m$)?

# Answer
> 7 votes
It can be exponential in $n/2$. The following graph has $2^{(n/2) - 1}$ shortest paths between the endpoints:

This graph has $2^{(14/2)-1} = 2^6 = 64$ different shortest path, each corresponding to a selection of "ups" and "downs".

---
Tags: graphs, combinatorics, shortest-path, discrete-mathematics
---


# Question
Title: Proving that a specific language is a CFL, and that another language is not a CFL
I have two languages $C\_1$ and $C\_2. \left(\Sigma=\\{0,1\\}\right)$:

$C\_1=\left\\{xyz\mid x,z \in \Sigma^\*, y \in \Sigma^\*1\Sigma^\*, \text{ where } |x|=|z| \geq |y|\right\\}$, and $C\_2=\left\\{xyz\mid x,z \in \Sigma^\*, y \in \Sigma^\*1\Sigma^\*1\Sigma^\*, \text{ where } |x|=|z| \geq |y|\right\\}$

I want to show that $C\_1$ is a CFL, while $C\_2$ is not a CFL. I'm trying to create a grammar / pushdown automata that accepts $L(C\_1)$, but the $|x|=|z| \geq |y|$ part is throwing me off. I plan on using the pumping lemma for $C\_2$, but I'm not sure which string to pump.

# Answer
> 2 votes
First you have to realize that the extremes of the strings are of the form $0^n10^{2n-1}$ and $0^{2n-1}10^n$. You can get a language similar to that by the grammar $S \to 1 \mid 0S00 \mid 00S0$. From this some fine-tuning is needed. First to get $1$'s at the places where now only $0$'s are. Then to get the boundary conditions exactly right.

For the non-context-free other language I would also consider an "extreme" string, similar to $0^n10^n10^n$. That is not exactly one from the language, but close enough for a start.

(Nice exercise, that problem 2.48a in Sipser)

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


title: Optimize a linear recurrence

text:
# Question
Title: Optimize a linear recurrence
$$\begin{align\*} T\[1\] &= 1 \\ T\[2\] &= 2 \\ T\[i\] &= T\[i-1\] + T\[i-3\] + T\[i-4\] & \text{for \\(i \gt 2\\)} \\ \end{align\*}$$

I have to calculate $T\[N\]$, but $N$ is too big ($\approx 10^9$), how can I optimize it?

# Answer
As Bartek commented, you are missing a base case. You can compute large values of $T$ in several ways:

* Bartek's suggestion: Use an array to store all the entries computed so far.
* You can optimize the previous method, dramatically reducing the memory needed: store only the last $4$ entries of the array at each point in time.
* Use matrix powering. There are vectors $x,y$ and a matrix $A$ such that $T\[N\] = x'A^N y$. This approach is very similar to the previous one.
* Find an explicit solution to your recurrence $T\[N\] = \sum\_{i=1}^4 c\_i \lambda\_i^n$ (there are other possible forms, but this is the most probable), and use this formula to calculate $T\[N\]$ directly.
> 7 votes

# Answer
Imagine your solution now is Gn = Gn-1 + Gn-2 + Gn-3

The solution just changes to

```
[ Gn Gn-1 Gn-2 ] = [ Gn-1 Gn-2 Gn-3 ] [ 1 1 0 ]
                                      [ 1 0 1 ]
                                      [ 1 0 0 ]

```

Similarly

```
[ Gn-1 Gn-2 Gn-3 ] = [ Gn-2 Gn-3 Gn-4 ] [ 1 1 0 ]
                                        [ 1 0 1 ]
                                        [ 1 0 0 ]

```

So finally,

```
[ Gn Gn-1 Gn-2 ] = [ G3 G2 G1 ] [ 1 1 0 ] ^n-3
                                [ 1 0 1 ]
                                [ 1 0 0 ]

```

Calculating power of a matrix, $$M^n$$ can be done in **O(log n)**.

For your case, the Matrix will be

```
[ Gn Gn-1 Gn-2 Gn-3] = [ Gn-1 Gn-2 Gn-3 Gn-4 ] [ 1 1 0 0]
                                               [ 0 0 1 0]
                                               [ 1 0 0 1]
                                               [ 1 0 0 0]

```
> 3 votes

# Answer
There aren't enough initial values, but still. Define: $$ A(z) = \sum\_{n \ge 0} T\[n\] z^n $$ Properties of ordinary generating functions give for the recurrence: $$ T\[n + 4\] = T\[n + 3\] + T\[n + 1\] + T\[n\] $$ $$ \frac{A(z) - T\[0\] - T\[1\] z - T\[2\] z^2 - T\[3\] z^3}{z^4} = \frac{A(z) - T\[0\] - T\[1\] z - T\[2\] z^2}{z^3} \+ \frac{A(z) - T\[0\]}{z} \+ A(z) $$ This finally leads to form: $$ A(z) = \frac{p(z)}{z^4 - z^3 - z - 1} = \frac{A\_1}{1 - \phi z} \+ \frac{A\_2}{1 - \overline{\phi} z} \+ \frac{B z + C}{1 + z^2} $$ Here $A\_1$, $A\_2$, $B$ and $C$ are constants depending on the initial $T$ values, and $$ \begin{align\*} \phi &= \frac{1 + \sqrt{5}}{2} \\ \overline{\phi} &= 1 - \phi = - \frac{\sqrt{5} - 1}{2} \end{align\*} $$ The first two are geometric series, the last one adds terms alternating between 0 and 1 to the solution. And as $\lvert \overline{\phi} \rvert \approx 0.618$ while $\phi \approx 1.618$, the first term dominates. The value at large $n$ is approximately $T\[n\] \approx A\_1 \phi^n$.
> 1 votes

---
Tags: algorithms, dynamic-programming, recursion
---


# Question
Title: Can I use infinite numbers in a reduction?
I have to reduce $L\_\text{empty}$ to $L\_\text{inf}$

where

$\qquad L\_\text{empty} = \\{e \mid |L(P\_e)| = 0 \\}$ and
$\qquad L\_\text{inf}= \\{e \mid |L(P\_e)| = \infty \\}$.

where $P\_e$ is the program with Gödel number $e$, and $L(P\_e)$ the language it accepts.

So can I define a program $P$ like this

```
input n
Run Pe on 1...n for n steps
if Pe accepts any number then
  enter an infinite loop and start accepting infinite number
if Pe does not accept any number then
  accept 1

```

Now if I can define program P like above then asking the question whether the index of $P$ is in $L\_\text{inf}$ will tell me whether the language accepted by $P\_e$ is empty or not.

# Answer
A language cannot contain infinite numbers, since by definitions it is a set of *finite* numbers. The language itself could be infinite, though: it could contain infinitely many numbers.

In your solution, in the first case, you first enter an infinite loop and then "start accepting infinite numbers", but once you've entered an infinite loop, you're not accepting anything.

Your reduction $f$ has to satisfy the following two properties:

* If $e \in L\_{\mathrm{empty}}$ then $f(e) \in L\_{\mathrm{inf}}$.
* If $e \notin L\_{\mathrm{empty}}$ then $f(e) \notin L\_{\mathrm{inf}}$.

In plain English:

* If $L\_e$ accepts no inputs then $L\_{f(e)}$ should accept infinitely many inputs.
* If $L\_e$ accepts at least one input then $L\_{f(e)}$ should accept finitely many inputs.

Try to see if you can come up with such a function $f$. The basic idea is similar to yours - on input $n$, $f(e)$ should check whether $L\_e \cap \\{1,\ldots,n\\} \neq \emptyset$. You should just be more careful in what happens next.
> 3 votes

---
Tags: computability, reductions, undecidability
---


# Question
Title: How to do amortized analysis for an expanding array?
If you have an array that expands when it is completely filled and the new size is `N = N + 1 + ceiling(log2(N))` (N is the current size, and then N becomes the new size) (log2 is log base 2).

How can you do an amortized analysis for this? It is confusing because the size of the expansion of the array increases as N increases.

# Answer
This looks like a homework problem, so I will try to highlight the skeleton of the proof.

1. The cost of inserting and taking an element out of an array is 1
2. The cost of resizing an array is equal to the number of elements moved to the new/bigger array.
3. As a simple case, consider you increase the size of array by 1. Calculate the total cost of resizing?

Repeat the above analysis by doubling the size of array and check which one is better i.e. doubling the size OR increasing by 1? Calculate the amortized cost for both cases? Then you should be good to answer your own question...
> 1 votes

---
Tags: amortized-analysis
---


# Question
Title: Hash function - uniformity / strong universality
I am currently learning how randomised Hashing works. So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$.

That class is called "strongly universal" or "pairwise independent" if $\forall x,y \in U, x \neq y: \forall z\_1,z\_2 \in N: \Pr\limits\_{h \in H}\[h(x) = z\_1 \land h(y) = z\_2\] \leq \frac{1}{|N|^2}$. In words: pick any two elements from the universe and two from the hash table. If you pick a hash function from the hash class at random, the probability that these two elements are mapped to each other by $h$ is less or equal than $\frac{1}{|N|^2}$.

Now, what is confusing me is that, since $x$, $y$, $z\_1$ and $z\_2$ are all completely independent, it looks to me like you could just "remove" one pair from the equation and still get the same result. That would be $\forall x \in U: \forall z \in N: \Pr\limits\_{h \in H}\[h(x) = z\] \leq \frac{1}{|N|}$. This, however, is called "uniformity" of a hash class.

Could someone explain to me why these two attributes are different from one anoter?

# Answer
Arnab provided the answer. The family $\mathcal{H} = \\{h\_i : i \in N\\}$, where $h\_i(x) = i$ for all $x \in U$, is uniform but not pairwise independent. Similarly you can come up with families which are pairwise but not $3$-wise independent, and so on.

To give a simple example, let $X,Y$ be two independent uniformly random coin tosses. Each of the possibilities $(H,H),(H,T),(T,H),(T,H)$ has the same probability. Now let $X'$ be a uniformly random coin toss, and let $Y' = X'$. Now it is not true that each of the four possibilities of $(X',Y')$ has the same probability, but each of $X',Y'$ by itself is a uniformly random coin toss.
> 2 votes

---
Tags: data-structures, hash-tables, hash
---


title: CFG to Chomsky normal form

text:
# Question
Title: CFG to Chomsky normal form
I've read this part like 3-4 times and I'm not understanding what is going on.

Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The series of grammars presented illustrates the steps in the conversion. Rules show in bold have just been added. Rules shown in gray have just been removed.

Specific steps/instructions from the book

1.The original CFG G6 is shown on the left. The result of applying the first step to make a new start variable appears on the right.

```
S→ASA|aB         S0→S
A→B|S             S→ASA|aB
B→b|ε             A→B|S
                  B→b|ε

```

2. Remove ε rules B→ε, shown on the left, and A→ε, shown on the right.

```
S0→S              S0→S
 S→ASA|aB|**a**        S→ASA|aB|a|**SA|AS|S** from?
 A→B|S|**ε**           A→B|S|ε
 B→b|**ε**             B→b

```

3a. Remove unit rules S→S, shown on the left, and S0→S, shown on the right.

```
S0→S                  S0→S|**ASA|aB|a|SA|AS**
 S→ASA|aB|a|SA|AS|S    S→ASA|aB|a|SA|AS
 A→B|S                 A→B|S
 B→b                   B→b

```

3b. Remove unit rules A→B and A→S

```
S0→ASA|aB|a|SA|AS     S0→ASA|aB|a|SA|AS
 S→ASA|aB|a|SA|AS      S→ASA|aB|a|SA|AS
 A→B|S|**b**           A→S|b|**ASA|aB|a|SA|AS**
 B→b                   B→b

```

4. Convert the remaining rules into the proper form by adding additional variables and rules. The final grammar in Chomsky normal form is equivalent to G6, which follows. (Actually the procedure given in Theorem 2.9 produces several variables Ui, along with several rules Ui→a. We simplified the resulting grammar by using a single variable U and U→a.)

```
S0→AA1|UB|a|SA|AS
 S→AA1|UB|a|SA|AS
 A→b|AA1|UB|a|SA|AS
A1→SA
 U→a
 B→b

```

I don't understand why they added the "bold" (\** \**) items. I also don't understand 4. Can someone please explain this to me. Thank you!

# Answer
> 2 votes
Removing $\epsilon$ transitions:

Consider the rule $B\to \epsilon$. We want to remove it. To do so, we look for occurrences of $B$ in the grammar, and whenever we see on (e.g. in $S\to aB$), we add the option of choosing $B\to \epsilon$. So the rule $S\to aB$ becomes $S\to a$. Similarly, $A\to B$ becomes $A\to \epsilon$ (which we will have to remove in the next step).

Since $A\to \epsilon$ was introduced when removing $B\to \epsilon$, we now add rules where $A$ appears. For example, the rule $S\to ASA$ becomes $S\to ASA|SA|AS|S$, according to the different options of using $A\to \epsilon$ after $S\to ASA$.

In step 4 - for every rule that yields more than a pair of variables (e.g. in this case $S\to ASA$) we split this into pairs as follows. Introduce a new variable $T$, we add the rules $S\to TA$ and $T\to AS$. Then, applying these forces us to actually have $S\to ASA$.

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


# Question
Title: Can we say anything about the complement of a regular language?
Given a regular language $L$, can we say anything about its complement $\overline L$? One thing that is trivial to say is that the DFA's for both languages are equal in size as complementing the language is simply a matter of changing all accepting states into rejecting states and vice-versa. Are there any other things to conclude? Is there anything one can say about the number of states of a (minimal) NFA?

# Answer
Complementing an NFA may involve an exponential blowup.

While there are concrete examples for this, it can also be deduced (in a way) by the fact that NFA universality is PSPACE complete. Indeed, if complementing an NFA could be done in polynomial time, then universality would also be possible in polynomial time.

This is not exact, since complemetation could also be only sub-exponential, but not polynomial.

As for a concrete example: Let $p\_1,p\_2,\dots$ be an enumeration of the prime numbers. Consider the language: $L\_k=\\{1^n: \exists 1\le i\le k\ \text{ s.t. }\ p\_i \not\mid n\\}$. It is easy to construct an NFA for $L\_k$ with $\sum\_{i=1}^kp\_i$ states.

However, it is also not hard to prove that a minimal NFA for $\overline{L\_k}$ needs $\prod\_{i=1}^k p\_i$ states, which is exponential in $\sum\_{i=1}^kp\_i$.
> 6 votes

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


# Question
Title: Proving a language is not regular with pumping lemma
I'm having a little bit of an issue with a pumping lemma problem. I've successfully completely all my other problems but this is the last one and I'm a little confused I must say. If anyone can help me out, it'd be much appreciated.

\begin{equation} A = \\{a^n b^m c^l \mid n\leq m \vee m\leq l\\} \end{equation}

# Answer
To expand a little on Ran G.'s comment, given a pumping length of $p$, we can take the string $s=a^{p}b^{p} \in A$, then splitting into $s=xyz$, the $y$ section (the part that can be pumped) must be all $a$s, so pumping up leaves us with a string $s'=a^{p+k}b^{p} \notin A$.
> 1 votes

---
Tags: automata, pumping-lemma
---


# Question
Title: How to compute amoritized cost for a dynamic array?
I am trying to understand how to do the amortized cost for a dynamic table. Suppose we are using the accounting method.

Let A of size m be an array of n elements. When $n = m$, then we create a new array of size $4m$, and then copy the elements of A to the new array. When $n = \frac{m}{4}$, then you create a new array of size $\frac{m}{4}$, and copy the elements to that array.

What I am confused about is how to calculate the costs. From what I know so far: Before the first expansion, you pay two dollars to insert. `1$` for the insert, and `1$` you just store with the element, so that you can use that later for a copy operation.

Then when you expand it, you use that stored `$` to move the element to the new array. Now in the new array the elements won't have any `$` with them. But now as you insert a new element, you use `3$`. `1$` for the insert, then one more for itself (for a future copy), and one more for the previous element that was just copied.

The problem here is, what if you have an array like this:

`1$ 2$`

Then insert an element

`1$ 2 3$ _ _ _ _ _`

Now how do you handle a delete operation?

# Answer
> 1 votes
I think your particular structure does not have amortized $O(1)$ cost, and you identified the problem.

Your general approach is salvageable, but you either need to grow less aggressively or shrink less aggressively. The standard solution is to grow from capacity & size $n$ to capacity $2n$ and to shrink from capacity $n$ and size $n/4$ to capacity $n/2$.

---
Tags: data-structures, algorithm-analysis, amortized-analysis
---