# Question
Title: Lambda calculus didn't seem abstract. And I can't see the point of it
**The underlying question:**

What does lambda calculus do for us that we can't do with the basic function properties and notation generally learned in middle school algebra?

First of all, what does abstract mean in the context of lambda calculus? My understanding of the word abstract is something that is divorced from the machinery, the conceptual summary of a concept.

However, lambda functions, by doing away with function names, prevents a certain level of abstraction. For example:

```
f(x) = x + 2
h(x, y) = x + 5 y

```

But even without defining the machinery of these functions, we can easily talk about their composition. For example:

```
1. h(x, y) . f(x) . f(x) . h(x, y) or
2. h . f . f . h

```

We can include the arguments if we want, or we can abstract away completely to give an overview of what's happening. And we can quickly reduce them to a single function. Let's look at composition 2. I can have student layers of detail I can write with depending on my emphasis:

```
g = h . f . f . h
g(x, y) = h(x, y) . f(x) . f(x) . h(x, y)
g(x, y) = h . f . f . h = x + 10 y + 4

```

Let's perform the above with lambda calculus, or at least define the functions. I'm not sure this is right, but I believe the first and second expressions increment by 2.

```
(λuv.u(u(uv)))(λwyx.y(wyx))x

```

And to multiply by 5y.

```
(λz.y(5z))

```

Rather than be abstract, this seems to get into the very machinery of what it means to add, multiply, etc. Abstraction, in my mind, means higher level rather than lower level.

Furthermore, I am struggling to see why lambda calculus is even a thing. What is the advantage of

```
(λuv.u(u(uv)))(λwyx.y(wyx))x

```

over

```
h(x) = x + 5 y

```

or a combined notation

```
Hxy.x+5y

```

or even Haskell's notation

```
h x y = x + 5 * y

```

Again, what does lambda calculus do for us that we can't do with the f(x)-style function properties and notation many are familiar with.

# Answer
> 25 votes
There are many reasons why the lambda calculus is so important.

A very important reason is the lambda calculus allows us to have a model of computation in which computable functions are first-class citizens.

One cannot express *higher-order functions* in the language of middle school algebra.

Take as example the lambda expression

$$\lambda f. \lambda g. \lambda x. f(g(x))$$

This simple expression shows us that, within the lambda calculus, function composition is itself a function. In middle school algebra, this is not easily expressed.

In the lambda calculus, it is very easy to express that a function will return a function as its result.

Here is a small example. The expression (where I here assume an applied lambda calculus with addition and integer constants)

$$(\lambda f. \lambda g. \lambda x. f((g(x)))(\lambda x. x+2)$$

will reduce to

$$\lambda g. \lambda x. g(x)+2$$

Notice also that within the lambda calculus, functions are *expressions* and not definitions of the form $f(x) = e$. This frees us from the need to name functions and to distinguish between a syntactic category of expressions and a syntactic category of definitions.

Also, when it becomes impossible (or just notationally cumbersome) to express higher-order functions, one will also have problems with assigning types to expressions.

Function composition has the polymorphic type

$$\forall \alpha.\forall \beta. \forall \gamma. (\beta \rightarrow \gamma) \rightarrow ((\alpha \rightarrow \beta) \rightarrow \gamma)$$

in the Hindley-Milner type system.

A very strong selling point for the lambda calculus is precise the notion of *typed lambda calculus*. The various type systems for functional programming languages such as Haskell and the ML family are based on type systems for lambda calculi, and these type systems provide strong guarantees in the form of mathematical theorems:

If a program $e$ is well-typed and $e$ reduces to the residual $e'$, then $e'$ will also be well-typed.

And if $e$ is well-typed, then $e$ will not exhibit certain errors.

The *proofs as programs* correspondence is particularly noteworthy. The Curry-Howard isomorphism (see e.g. https://www.rocq.inria.fr/semdoc/Presentations/20150217\_PierreMariePedrot.pdf) shows that there is a very precise correspondence between the simply typed lambda calculus and intuitionistic propositional logic: To every type $T$ corresponds a logical formula $\phi\_T$. A proof of $\phi\_T$ corresponds to a lambda term with type $T$, *and* a beta-reduction of this term corresponds to performing a cut elimination in the proof.

I urge those who feel that middle school algebra is a good alternative to the lambda calculus to develop an account of higher-order, polymorphically typed middle school algebra together with an appropriate notion of Curry-Howard isomorphism. If you can even work out an interactive proof assistant based on middle school algebra that would allow us to prove the many theorems that have been formalized using lambda calculus-based proof assistants such as Coq and Isabelle, that would be even better. I would then start using middle school algebra, and so, I am sure, would many others with me.

# Answer
> 6 votes
When functions are first described to youngsters, they are essentially identified with graphs (plots), or perhaps with formulas; this is the way functions were understood historically before the advent of formalist trends in mathematics. Nowadays functions, as taught in first year calculus, are real functions, that is, functions from $\mathbb{R}$ to $\mathbb{R}$.

The functions in lambda calculus are much more general. The exact definition depends on whether your lambda calculus is typed or untyped. In pure untyped lambda calculus everything is a function. This is much more general than the real functions of calculus.

Even procedural languages sometimes use ideas from lambda calculus. The sorting function in C accepts as a parameter a *comparison function*, which it uses to compare elements. Lambda calculus goes much further – functions not only accept functions as inputs, but can also output them.

Lambda calculus is a model of computation equivalent in power to Turing machines. It is a system complete unto itself. Pure lambda calculus doesn't have "5" or "+" as primitive terms – they can be defined inside the calculus, just like "5" and "+" are not primitives of set theory. (Practical programming languages implement natural numbers natively for reasons of efficiency.)

I suspect that one of the reasons that you are not impressed with lambda calculus is that its ideas have pervaded the programming discourse so much that it no longer looks innovative.

# Answer
> 4 votes
One of the basic ambiguities of common mathematical notation is that sometimes $x^2$ is used to denote a number (the square of the number $x$), and sometimes $x^2$ is used to denote a function (the function that returns the square of its argument).

Lambda calculus removes this ambiguity; you can write $\lambda x.x^2$ to refer to the function, making it unambiguous that $x^2$ refers to a number, like it should.

Yes, you could break the flow of an argument or calculation to say "now define $f$ by $f(x) = x^2$" and then use $f$, but that gets cumbersome fast. Lambda abstraction lets you do that inline without making an interruption.

The use of lambda expressions in programming languages has a similar advantage; you can write what the function does right there where it's needed rather than having to define a whole new function elsewhere in your program.

You can even see lambda abstraction implicit in mathematics; e.g. students of calculus are only taught about derivatives of *functions*, so to reconcile Leibniz notation $\frac{d}{dx} x^2$ with derivatives of functions, you can interpret $\frac{d}{dx}$ as implicitly performing a lambda abstraction on $x^2$ to interpret it as a function. You're more or less forced to do so, if you don't want to have the ambiguity described in the opening paragraph.

---

Also, people are often uncomfortable with function-valued functions in traditional notation; e.g. the usual map $\theta : V \to V^{\**}$ that identifies a finite-dimensional vector space with its double dual is defined by

$$ \theta(v)(f) = f(v) $$

Many people find this double-evaluation notation confusing and/or unsettling, as well as this recursive use of pointwise definition of a function. The lambda abstraction version

$$ \theta = \lambda v . \lambda f . f(v) $$

doesn't have that problem.

---

Finally, there's a theorem of abstract nonsense that "simply typed lambda calculus" is basically the same thing as "cartesian closed category" — so if you ever find yourself wanting to do calculation in a cartesian closed category, it's probably a good idea to use simply typed lambda calculus to do so.

# Answer
> 4 votes
I'll say up front I'm not an expert on this topic, but I did just spend a bit of time studying it and one of the most fascinating things to me in any topic is the history behind it. So to me understanding a bit of the history behind lambda calculus helps explain *why* it is useful.

The short summary is that in the early 1900s after set theory started to take off and math was re-envisioned based on sets, some mathematicians noticed that while a set theory definition allows you to claim that a certain structure exists they do *not* tell you *how* to construct it and calculate it. So set-theoretic definitions are **nonconstructive**. Mathematicians began wondering if there was a way to develop **constructive** definitions that would go beyond proving that something *is* and instead prove *how it is*.

From Wikipedia:

> In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also known as an existence proof or pure existence theorem) which proves the existence of a particular kind of object without providing an example.

Turing developed the Turing Machine automata to answer the question, and Church developed the lambda calculus also to answer the question. Kleene also developed a method involving the Kleene Star $\*$ which were adopted into regular expressions, and there was someone else (can't recall offhand) who developed yet another method. All of these were developed in an attempt to build a system of math on a basis that would allow constructive definitions from the beginning.

It was then shown that lambda calculus and the Turing machine could both represent any computable function and are thus equivalent.

In theory *any* mathematical function or concept can be encoded in lambda calculus form and computed. This means that lambda calculus can be a completely separate basis for mathematics, though obviously an extremely tedious one.

Lambda calculus isn't "useful" in the sense that you aren't going to write code using it, but it does form the basis for *denotational semantics* which is used to *describe* programs and their dynamic effects. This is used in discussions of program correctness and semantic meaning. It also obviously heavily influenced the development of functional programming languages, which draw their entire concept of execution from lambda calculus.

Hope that helps.

**Edit to add:** I was just pointed to this paper showing the relationship between topology, lambda calculus, and physics. Skimming over it briefly I ran across this fantastic statement:

> While a Turing machine can be seen as an idealized, simplified model of computer *hardware*, the lambda calculus is more like a simple model of *software*. ... Poetically speaking, the lambda calculus describes a universe where everything is a program and everything is data: *programs are data*.

The point is that the lambda calculus is an *idealized model* of software computation, and as such isn't tied to a particular *implementation* in any programming language. It models *pure computation*.

# Answer
> 3 votes
As Yuval pointed out in the comments Haskell is based on the $\lambda$-calculus. Another reason why lambda calculus is so important is the Church-Rosser Theorem, which justifies the existence of lazy evaluation. (Which is one of Haskell's many cool features)

# Answer
> 3 votes
Lambda calculus wasn't designed to be a programming language. Indeed, it was created in the 1930s, decades before we even had programmable computers. Rather, it was created as a formal model for studying computation, itself. If you're disappointed in how easily it expresses code, or mathematical functions, that's because that's not what it's for.

# Answer
> -2 votes
Lambda calculus exists so that anonymous (aka lambda) functions can be created. If you don't do away with function names, then the namespace can get cluttered and one can run out of available function names. This is especially important when dealing with so-called "higher order functions" that return functions (or function pointers) for obvious reasons.

Essentially, lambda functions are equivalent to locally scoped variables. Functional programming without lambda functions is analogous to procedural programming without any local variables, ie, a terrible idea.

"why lambda calculus is even a thing" mathematicians love redundancy. lambda calculus is rarely used in math because as you've discovered the notation isn't very useful.

"If you can even work out an interactive proof assistant based on middle school algebra that would allow us to prove the many theorems that have been formalized using lambda calculus-based proof assistants such as Coq and Isabelle, that would be even better. I would then start using middle school algebra, and so, I am sure, would many others with me." Have you heard of metamath? No lambda calculus involved there, can prove many of the coq/isabelle theorems

---
Tags: lambda-calculus, programming-paradigms
---


title: Heuristics for the $n$-puzzle

text:
# Question
Title: Heuristics for the $n$-puzzle
An admissible heuristic for an n-puzzle is the Manhattan distance. Now if the cost of a transition is equal to the number of the piece that is moved, is it true that the Manhattan distance is still an admissible heuristic?

In my opinion yes, because during the search, for any node, we won't have any overestimation as a misplaced tile will have to move at least the number of spots between itself and the correct position. Is this correct?

And also, would it be correct to say that the Manhattan distance multiplied by the mean of all tiles (eg 8-puzzle -\> 4.5) is a heuristic that dominates the Manhattan distance in this case?

Thank you,

(Having troubles with my 1st AI class)

# Answer
> 4 votes
First of all, a heuristic is said to be *admissible* if and only if $h(n)\leq h^\*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^\*(n)$ is the cost of an optimal path from $n$ to the goal.

Now, when considering the sliding-tile puzzle, the Manhattan distance can be shown to be an admissible heuristic function as it results from a *constraint relaxation* \[1\].

From here, consider your first question: if the Manhattan distance is an *admissible* heuristic function for the sliding-tile puzzle where the cost of each movement is 1, it is also an *admissible* heuristic function for the case where the cost of each movement is strictly greater or equal than 1 (because all tiles are numbered 1 onwards).

Regarding your second question, a heuristic function $h\_1(n)$ is said to dominate another heuristic function $h\_2(n)$ if and only if $h\_1(n)\geq h\_2(n)$ for all states $n$. For some restrictive models (a unique goal, constant branching factor, no duplicates, etc.) it can be shown that more informed heuristics (i.e., $h\_1(n)$ in the previous definition) expand less nodes when using A$^\*$. From here, if you enhance your heuristic function with the average of all tiles, then it is necessarily more informed than pure Manhattan but watch out, it should be easy for you to note that this second heuristic function is not necessarily *admissible* as it can very easily overestimate the effort to reach the goal. Thus, using this second heuristic it is very likely that you will expand less nodes but you cannot guarantee that the solution returned is optimal.

Hope this helps,

Bibliography

\[1\] Pearl, Judea. Heuristics - Intelligent Search Strategies for Computer Problem Solving. Addison Wesley, 1984.

---
Tags: artificial-intelligence, heuristics, search-problem
---


title: TM - reject definition and complement

text:
# Question
Title: TM - reject definition and complement
I have couple of questions about Turing machines:

1. What is the definition of the "reject" state in TM? If the input was very small and, after one step, the machine gets to the end of the input, but it stands on regular state, it counts as "reject"? Or there is a special "reject" state, and if it won't get to this/those states, it doesn't count as a reject? (I know that in DFA, the reject states are just all the states that aren't "accept".)
2. I know that in aDFA, if we swap the reject and the accept states, we get the complement language. Does this work on TMs?
3. If I use only the TM's input cell (including changing their content), does it means I used $\mathrm{SPACE}(1)$ or $\mathrm{SPACE}(n)$?

Thanks a lot!

# Answer
1. There's a special reject state. Unlike a DFA, which is terminated by the definition when it reaches the end of the input, the machine decides when it stops, by jumping to one of the halting states (depending on exactly what definition you're using, there might be just one "halt" state, or there might be separate "accept" and "reject" states).
2. Almost. If the Turing machine accepts or rejects every input, then swapping accept and reject does indeed compute the complement, since you reject every string that you would have accepted, and vice-versa. However, we can also define languages in a weaker way, where the Turing machine accepts all strings in the language but, for a string not in the language, it might reject or it might just get stuck in an infinite loop (this is called "accepting", "recognizing" or "semi-deciding" a language). In this case, just swapping the accept and reject states doesn't complement the language, since the inputs that loop forever don't reach either state, so you'd conclude that such a string is neither in the language nor it's complement, which can't possibly be right.
3. No. Normally, when defining space classes, we use a slightly different model. When considering space-bounded computations, we Turing machines with three tapes: a read-only input tape, a write-only output tape and a read/write working tape. In this model, we only count the space used on the working tape. Because the input tape is read-only, you're not allowed to write to its input, unless you first copy the input to the working tape, in which case you're using space $n$.
> 4 votes

# Answer
1. There is a special reject state, and since the transition function is total, if after one step the machine finds an empty cell, and there are no moves for the current state reading an empty cell, the machine goes to the reject state (you don't have to explicitly write that in the transition function, it's implied).
2. If the TM M decides the language L - which means that the union between the accepted and the rejected words covers all the strings on the alphabet - you can swap the states and obtain a TM M' that decides not-L. If M only recognizes L - some input exists on which M doesn't stop - you can't swap.
3. It means you used SPACE(n). In fact the space complexity of a TM M on an input of length x is always \>= x. However there is an alternative definition of space complexity for TMs which counts only the "work tape" ignoring the "input tape". This version allows to define a class of problems which use sublinear space (see L and NL).
> 3 votes

# Answer
(1) depends on how you define the machine. The most natural way is to augment the set of the machine's states with two special states to indicate that the machine halts accepting or rejecting, respectively. You may as well use a single halting state (or no halting state at all, having the machine halt the first time the transition function is undefined) and read the output from a tape. All those definitions are equivalent.

(2) yes, given a Turing machine $T$, you can certainly build another machine $T'$ that accepts whenever $T$ rejects and vice-versa. However, bear in mind that a generic machine could not halt on some inputs.

(3) in complexity theory, a different model, the $k-$IO T.M. is generally used. In such a machine, you have $k$ tapes, where the first and the $k$-th are reserved for input and are read-only, meaning that you can never move backwards on those tapes. Only tapes $2$ through $k-1$ count towards the space complexity. Therefore, you are simply not allowed to write over the input.
> 3 votes

---
Tags: complexity-theory, turing-machines, space-complexity
---


title: Find longest overlapping interval

text:
# Question
Title: Find longest overlapping interval
Given a set $S$ of $n$ overlapping intervals, where each interval is in the range of \[1..O(n)\], preprocess $S$ so we can efficiently answer the following query: Given an interval \[i,j\] output the interval from $S$ that has the longest overlap with \[i,j\] (i.e., their intersection is as large as possible). Note that \[i,j\] may or may not be one of the intervals in $S$.

It is relatively easy to get *all* overlapping intervals. You store an array Endpt\[1..n\] such that Endpt\[t\] equals the rightmost endpoint of all intervals in the set that begin at location t. You ask repeated Range-maximum queries on the range 1..j. As long as the answer is \>j, you are getting an overlapping interval. This takes O(#answers) time since range-max is done in O(1) time.

The challenge of this question is that we want a more efficient way to find the interval with the longest overlap. To this end, we can consider 3 cases:

1. intervals that begin before i
2. intervals that end after j
3. intervals that begin after i and end before j (i.e., that are contained within \[i,j\]).

For case 1, we can query Endpt array for range-max in the range 1..i-1 and find the longest overlapping interval of type 1 efficiently. Similarly, for case 2 we can store a Startpt array and query for range min.

Case 3 has me stumped. We could store a length array for all intervals, and ask for the range-max in i..j; however, this will not give the longest overlapping interval, since there will be intervals that begin after i and end after j. Is there a way to efficiently preprocess $S$ so that, given \[i,j\], we can efficiently find the longest interval contained within \[i,j\]? Or is there some other efficient way to solve the original problem?

# Answer
You're just a step away from the answer.

Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is **totally ordered**, i.e. for any two interval $\[l,r\]$ and $\[l',r'\]$, either $l\<l'$ and $r\<r'$ or $l\>l'$ and $r\>r'$. Now it's not hard to find the first interval $\[l,r\]$ s.t. $l\ge i$ and the last interval $\[l',r'\]$ s.t. $r'\le j$, and a range-max of length array on the interval $\[l, l'\]$ gives you the answer.
> 3 votes

---
Tags: algorithms, data-structures, computational-geometry, trees, intervals
---


# Question
Title: Maximum number of states in NFA concluded from the converted DFA
Assume I have a DFA with 20 states, is it possible to know the maximum number of states of the NFA which it was converted from?

I know that the *minimal* number of states would be 5 (because you cannot have created a DFA with 20 states from an NFA with 4 states).

But I don't really understand how can I know if there's a *maximum* that can be determined.

# Answer
No, because there is no maximum. There are infinitely many NFA's that are all equivalent and accept the same language. For instance, you can take any NFA you think it might have come from and add some extra disconnected states, and the new NFA will also have the same language and thus could correspond to the same DFA.

(Your only hope is that if you know exactly what conversion procedure was used, and if the conversion procedure retains useless states and forms a bijection from NFAs to DFAs, then maybe. But in practice I would not expect ordinary conversion procedures to have that property.)
> 3 votes

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


# Question
Title: Explanation of an explanation of Turing's proof to the halting problem?
I am reading the transcription of a lecture from a professor Scott Aaronson, specifically the section titled *Turing Machines*. In this section he describes Turing's proof of the Halting Problem.

> But can we prove there's no program to solve the halting problem? This is what Turing does. His key idea is not even to try to analyze the internal dynamics of such a program, supposing it existed. Instead he simply says, suppose by way of contradiction that such a program P exists. Then we can modify P to produce a new program P' that does the following. Given another program Q as input, P'
>
> ```
> runs forever if Q halts given its own code as input, or
> halts if Q runs forever given its own code as input.
>
> ```
>
> Now we just feed P' its own code as input. By the conditions above, P' will run forever if it halts, or halt if it runs forever. Therefore P' -- and by implication P -- can't have existed in the first place.

How would P(x) be defined here, the algorithm which can compute the halting problem?

```
halts if x halts
otherwise does ...

```

Is P allowed to "output" something or only halt or not halt? It can write to a tape correct? So it could output 1 if x halts or 0 if it does not and then halt itself?... By attempting to define P am I trying to disprove Turing?..

Would we not need to know the source code of P to modify it to produce P'?

Is the overall idea of the proof that a machine to solve the halting problem would not be able to prove that it itself halts given its own source as input?

# Answer
> 1 votes
P should take two arguments: a TM M and a string x. P accepts if M halts on input x, otherwise rejects. Definition of P:

P(M, x): execute M on x and if it halts, go to the accepting state. If M doesn't halt on x, go to the reject state.

The language of the words accepted by P is Turing recognizable but not decidable. So you can define P, but the machine won't stop for all the inputs, and this is what you're trying to demonstrate.

You don't need to know the code source of P to produce P'. P' can be seen as:

P'(Q): execute P(Q, 'Q'), where 'Q' is the encoding of the TM Q, and if P accepts then don't halt, else halt.

The point is: if you suppose that a machine P that decides the Halting Problem exists, you're going to get a contraddiction. In fact you can produce a machine P' for the complement (you can do this because we are presuming the Halting Problem is decidable), so that it stops if the machine given in input doesn't and viceversa. If you try to use P' on P', then you get an antinomy.

I'm not sure this answer to your questions..

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


title: Shuffle an array based on some rules

text:
# Question
Title: Shuffle an array based on some rules
I have a set of images. The length is variable. It could be anything up to about 30 images. Each image can have up to 10 tags. Images may share some, all or none of their tags. I need to select a random 5 from this set of images. This selection should follow the following rules in order of high priority to low:

1. Two images with the exact same tag(s) MUST NOT appear next to each other unless no other option is available.
2. Which two images appear next to each other should be decided by a weight system that favours images that share less tags or none at all. The more different tags two images have, the more likely they should be to appear side by side and vice versa.
3. Rule 2 also applies to the entire set of 5, but to a lesser degree. It means we prefer the selected 5 to share as few tags with one another as possible, but this should not take priority over rule 1 and 2.
4. (Optional) When selected images share tags, the more tags they share, the further apart they should be from each other.
5. (Optional) As a bonus, it would be nice not to sacrifice randomness because of rule 3 and 4, but this is more of a nice-to-have and is not necessary.

I'm looking for an algorithm that can help me solve the above problem. This is part of a real-world application UI and as a result, it'd be best if it doesn't take more than a second to calculate the set of 5. Anything longer than a second is bad. Even a second is too long.

If anyone has a solution that takes up to a minute or so, I might be able to do some pre-processing on the data so I am still open to it.

# Answer
> 1 votes
I would like you to note that the selection **cannot be fully random**.. Assume there are 10 total images.

* 5 have the same tags
* 5 have a single but unique tag

Then the algorithm will Always choose the same 5 images (And will Always skip the other 5 images).

Luckily there's an algorithm that can help you easily. Note that this algorithm skips points 4/5 (which you claim are optional).

```
Foreach image => sort its tags alphabetically

Find the longest tag

Postfix the same letter to all the tags in order to make them the same lenght

```

In example if you have the tags `cherry`,`optimization`,`google` those tags are transformed into

```
cherryXXXXXX
optimization
googleXXXXXX

```

Foreach image, make a string that is made by concatenation of all its tags. Then sort those strings alphabetically.

In Example:

* Image1 - tags: B, EE, A
* Image2 - tags: A, C
* Image2 - tags: Z

The final strings would be

```
AXBXEE
AXCX
ZX

```

Put your strings in a doubly linked, linkedlist, select a random element, then skip "some elements" (in example if you have 300 strings, you can select the first random and then skip 40-60 strings ) and take another element.

This algorithm is not complex, and not cheap, but is a good start point, note that your algorithm have to be a euristic-based (or greedy) algorithm because I fear your problem has a big computational complexity (still checking that, I'll update later this answer).

**An alternative algorithm complexity (n number of images)**

Assume the number of tags is limite to 10.

```
set all scores to 0
foreach img in images
    foreach img2 in images
       img.score -= TagsInCommon(img,img2)

for (int i = 0; i<5; i++)
{
    images.SortBy( x => x.score);
    img = images.RemoveFirst(); // pick image with highest score
    foreach img in images // (we have removed the first image here)
       foreach img2 in images
           img.score -= TagsInCommon(img,img2) //adapt score slightly
}

```

The above algorithm has a complexity of roughly

```
O(n^2 + nlogn + n)

```

where n is number of images (I did not check complexity ineherent in string lenghts, number of tags etc.).

This algorithm basically is another algorithm with a greedy approach, image with unique tags will be the first selected images, while images that are heavily tagged will be putted to the end of the list (and possibly are never sorted out). Plus we are adapting the score during execution to remove tags that we have already drawed.

A better alternative would be (instead of removing Always the first element) to select a random element with a distribution that favours the elements with higher score (but at same time do not forbid to draw elements with low score).

This algorithm will probably will take less of a second even with something like 100 thousand images.

A distribution like the following would suffice:

---
Tags: arrays, randomized-algorithms
---


# Question
Title: Why are combinators important in lambda calculus?
I just recently learned a little about the lambda calculus, from the brief intro in the text *Programming Language Pragmatics* and this outstanding 4-video sequence from Adam Doupé. Basically I learned the gist of lambda calculus, $\alpha$-conversion and $\beta$-reduction, a bit of Church numerals, addition/subtraction, and the $Y$ combinator.

In this I learned the concept of a combinator, i.e. that it is an abstraction with no free variables. Simple concept. And there seemed to be this idea I kept reading between the lines, that we can/should turn non-combinator abstractions into combinators by wrapping them in abstractions that bind the free variables. For example, we can take the abstraction $(\lambda x. xy)$ and wrap it in $(\lambda y. \lambda x. xy)$ to bind the $y$.

But it was never really explained **why** it is important or useful to prefer combinators.

I'm *assuming* its because combinators allow us to easily combine expressions (surprise surprise) without the need of any externally-supplied variables. So in other words we could evaluate an arbitrary-length series of combinator applications without having to provide any initial conditions ahead of time. Which to me sounds like the equivalent in programming of avoiding global variables so as to avoid looking up values outside the current scope, in order to make it easier to understand the program and reduce errors. It also seems to align with the idea of a "pure functional" language that has no variables and no side-effects, which would imply such a language is effectively a series of combinator applications.

Is that correct?

# Answer
The word "combinator" has some connotations that you don't seem to be intending here and sometimes a stricter definition. Another term for the definition you gave is a **closed term**. The opposite is an **open term**. The programming language equivalent of an open term would be an expression referring to a variable that's simply not in scope. Not just not in the current scope, but not in any containing scopes either. Most languages simply don't allow this. We can model `let` expressions that locally bind a name with lambda abstraction and application. In particular, `let x = E in B` becomes $(\lambda x.B)E$. The top-level, or global, scope can then be thought of conceptually as just a short-hand for wrapping your program in a bunch of `let` expressions. The point being, even global names are bound. The analogy to an open term, in this context, would be a term with one or more completely undefined variables in it.

Now clearly a closed term is self-contained which is useful. Further, for the purposes of computation, we never need to consider anything other than closed terms (assuming we start with nothing but closed terms). More precisely, for computation we usually care about weak (head) normal form which is the normal form for call-by-value(/name) reduction. An important aspect of these reduction strategies is they never reduce under a lambda. As such, any instance of $\beta$-reduction using these reduction strategies will only involve closed terms and will only ever produce a closed term assuming the initial term was closed. So, for the purposes of programming and computation closed terms are all that matters. Optimizing compilers, though, manipulate programs and often do perform reduction under a lambda and as such do need to deal with open terms. Proof assistants also need to deal with open terms as they usually need to reduce to normal form to compare lambda terms for equality. (Actually, they can often avoid going all the way to normal form.)

The focus on "combinators" isn't driven by software engineering concerns. It's simply a fact that for many purposes you only need to consider closed terms. The theory and formal manipulation of open terms is quite a bit hairier than for closed terms, so it is useful to limit to closed terms when possible.
> 8 votes

# Answer
A combinator is a lambda expression with no free variables.

So, λx.x is a combinator but λx.y is not a combinator.

Consider the following:

(λxy.xy)(λx.y) = (λy.xy)\[x := λx.y\] = (λy.(λx.y)y)

Notice how the final lambda expression is incorrect because the previously free variable y in λx.y has become bound. That's why when you're combining lambda expressions with free variables you have to follow renaming rules to ensure that the expression that results has the same meaning it had at the start.

Hence, this seems to me to be one of the reasons combinators are important:

> When substituting with combinators your reduced expression will never change in meaning.

**P.S.** *I'm now learning this stuff so I could be wrong.*
> 2 votes

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


# Question
Title: Push down automaton for Language of same number of as and bs
**The task**

> Find a pushdown automaton $M$, so that $L(M)=\\{w \in \\{a,b\\}^\*\ |\ |w|\_a=|w|\_b\\}$, where $|w|\_a$ denotes the number of $a$s in a word $w$.

**My solution**

I'm using the Wikipedia notation. $$M = (Q, \Sigma, \Gamma, \delta, q\_0, Z\_0, \\{q\_0\\})$$ $$Q=\\{q\_0\\}, \Sigma = \\{a,b\\}, \Gamma = \\{Z\_0, A,B\\}$$ $$\delta\text{ has the following instructions:}$$ $$(q\_0, \varepsilon, Z\_0, q\_0, \varepsilon),$$ $$(q\_0, a, Z\_0, q\_0, AZ\_0),$$ $$(q\_0, b, Z\_0, q\_0, BZ\_0),$$ $$(q\_0, a, A, q\_0, AA),$$ $$(q\_0, b, A, q\_0, \varepsilon),$$ $$(q\_0, b, B, q\_0, BB)\text{ and}$$ $$(q\_0, a, B, q\_0, \varepsilon).$$

**Questions**

1. Is this correct? Can it be simplified?
2. If so, how can I argue (not neccessarily proof) its correctness?

# Answer
As adrianN and Yuval say, correctness is shown by explaining your ideas, in particular what the automaton stores in its states and stack.

Just as a fun fact: you have constructed a single state PDA, which essentially means you have constructed a context-free grammar. The construction is reverse from the one given in a remark in Wikipedia (concerning CFG in Greibach normal form).

In this case your productions are equivalent to

$Z\to \varepsilon$, $Z\to aAZ$, $Z\to bBZ$, $A\to aAA$, $A\to b$, $B\to bBB$, $B\to a$.

You can shave off one production and use less nonterminals by starting with the grammar $S\to SS$, $S\to aSb$, $S\to bSa$, $S\to\varepsilon$, which is a variant of the well-formed parenthesis grammar in wikipedia. This is not yet a PDA,to this you need a more Greibach-like format:

$S\to SS$, $S\to aSB$, $S\to bSA$, $S\to\varepsilon$, $A\to a$, $B\to b$.

More efficient perhaps, but the stacks of your original PDA have a clear meaning, helping its correctness proof.
> 1 votes

# Answer
The usual approach is to prove by induction the following kind of statement:

> The set of configurations reachable from the initial state upon reading a word $w$ is ...

Here ... depends on $w$. Having proved this kind of statement, you can deduce which words are accepted by your machine, hence proving its correctness.
> 2 votes

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


title: Version of knap sack problem

text:
# Question
Title: Version of knap sack problem
> The are cuisenaire rods with N differnt lengthes $x\_1,x\_2,...,x\_n$ (each length is a natural number), the number of the Cuisenaire rods is unlimited. Given a natural number B. you should tell if you can pick a bunch of Cuisenaire rods with exactly the length of B.
>
> for example: if the cuisenaire rods are $3,11,19$ and $B=20$ so you should return true because $3+3+3+11=20$. but for $B=19$ return false.

I made a $(N+1)\times(B+1)$ table named "opt", checked for all $0\leqslant i\leqslant n$ and for all $0\leqslant b\leqslant B$ if i can get a length using the lengthes $x\_1,x\_2,...,x\_i$ and weights $0\leqslant b\leqslant B$

For the given example he output should be (this is my output also)

```
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1

```

My idea:

fill in with zeros the first line and the first column, i.e `opt[0][b]=0` for all b and `opt[n][0]=0` for all n

Here `cuisenaire={0,3,11,19}` is array with the cuisenaire lengths

```
 for n=1 to N+1
        for b=1 to B
            opt[n][b]=opt[n-1][w];//copy the previos row
            if w modulu cuisenaire[k]=0
                opt[n][w]=1;

            if w >=cuisenaire[n] and n>1 and (w+cuisenaire[n]-1)module (cuisenaire[n-1])=0)
                opt[n][w]=1;

```
1. my Idea works only for small B's $\implies $ wrong idea but maybe close, e.g for $B=100$ and `cuisenaire={0,13,19,29}` my idea doesn't work
2. can't think on recursive idea

# Answer
> 2 votes
Your question is equivalent to the decision version of the unbounded knapsack optimization problem. The decision is whether the maximum value (after optimization) is equal to the upper bound. Moreover, the weights and values are identical in your question (i.e. the length is both the weight and the value).

# Problem Formulation

The unbounded knapsack optimization problem is as follows:

> Given a set of $n$ objects where object $i$ has weight $w\_i$ and value $v\_i$,
>
> $\\\>\\\>$ maximize $\sum\_{i=1}^{n} v\_i m\_i$
>
> $\\\>\\\>$ subject to $\sum\_{i=1}^{n} w\_i m\_i \leq W, \\ m\_i \in \mathbb{N}$
>
> where $m\_i$ denotes the multiplicity of object $i$, and $W$ is some upper bound.

*(note that we're using the definition of $\mathbb{N}$ that includes zero here)*

The decision version of this problem can be formulated in terms of the optimization version:

> Is the maximum value of the unbounded knapsack optimization problem over the given set of objects $(w\_i,v\_i)^\*$ and upper bound $W$ equal to $V$?

Now let's map these descriptions to your particular question. First, note that length of a cuisenaire rod is equal to both its weight and its value. So we can replace every $w\_i$ and $v\_i$ with just $x\_i$. Similarly, the upper bound on the weight is also the target value for the decision problem. So we can replace both $W$ and $V$ with $B$. Finally, since the selection variable $m\_i$ is already using the definition of the natural numbers that includes zero, let's be precise and replace every instance of "natural number" in your problem description with "positive integer".

This results in the following problem formulation:

> Given some $B$ and a set of $n$ cuisenaire rods of lengths $x\_1, x\_2, ..., x\_n$ where $B \in \mathbb{Z^+} \land \forall x\_i (x\_i \in \mathbb{Z^+})$,
>
> is the result of maximizing
>
> $\\\>\\\>\\\>\\\>\\\>\\\> \sum\_{i=1}^{n} x\_i m\_i$
>
> subject to
>
> $\\\>\\\>\\\>\\\>\\\>\\\> \sum\_{i=1}^{n} x\_i m\_i \leq B, \\ \\\>\\\>\\\>\\\>\\\>\\\> m\_i \in \mathbb{N}$
>
> equal to $B$?

# Solution as Recurrence Relation

Since $\forall x\_i(x\_i \in \mathbb{Z})$, we can most easily solve this knapsack problem by formulating a recurrence relation for it. So let $M\[b\]$ denote the maximum length less than or equal to $b$ of an unbounded combination of the given cuisenaire rods. The base case is $M\[0\] = 0$, since we can always select a combination of zero cuisenaire rods (i.e. set every $m\_i$ to $0$) whose sum is the maximum value less than or equal to zero (i.e. zero itself).

The recursive case is formulated in terms of reducing the allowable maximum length by the different cuisenaire rod lengths. The idea is to see whether specifying that we have used one of rod $x\_1$, $x\_2$, ..., or $x\_n$ gets us closer to $B$. In specifying that we have used one of rod $x\_i$, we may remove that rod from the tally and recurse on the smaller value, i.e. $M\[b-x\_i\]$. In order to find the maximum value, we add the value of the rod that we just removed to whatever the maximum length of the smaller limit is, i.e. $M\[b\] = x\_i + M\[b-x\_i\]$. More specifically, $M\[b\]$ is equal to the *maximum* possible value that we could achieve between selecting one rod from all the different rods, i.e. $M\[b\] = max\_{i=1}^{n} (x\_i + M\[b-x\_i\])$.

Note that since this is the *unbounded* knapsack problem, we cannot say whether we will use the selected rod (or any other rod) again in the solution. In terms of formulating the recurrence relation, all we can say for certain is that the selected rod is used at this specific step. The decision about what rod to select next (or even to select this rod again) is left entirely up to the next step in the recursion.

Putting this all together, and assuming that both $B \> 0$ and $\forall x\_i (x\_i \> 0)$ in order to avoid wonky edge cases, we get the following recurrence relation:

> $ \\\>\\\> M\[0\] = 0, \\ \\\>\\\> M\[b\] = max\_{i=1}^{n}(x\_i + M\[b-x\_i\]) $

Note that $M\[b\]$ is undefined for any $b \< 0$. If we want to be really precise about it, we could express this formally as $ M\[b\] = max\_{\\{x\_i | b-x\_i \geq 0\\}}(x\_i + M\[b-x\_i\]) $.

We can now find the maximum length less than or equal to $B$ of any unbounded combination of cuisenaire rods by evaluating $M\[B\]$. This solves the optimization problem. To solve the decision problem, simply check if $M\[B\] = B$.

# Dynamic Programming

Since $\forall x\_i(x\_i \in \mathbb{Z})$, we can easily apply dynamic programming by instantiating an array (with all elements initialized to zero) of length $B$. Store and lookup the value of each term in this recurrence relation in that array.

We can optimize this dynamic programming solution in two main ways. First, we can reduce the runtime by iteratively filling in the array from $M\[0\]$ to $M\[B\]$ in order to avoid the function call overhead of recursively starting at $M\[B\]$.

Second, we can reduce the space by observing that a circular array of size $\mathcal{max\_{i=1}^{n}(x\_i)}+1$ is sufficient to hold as many previously calculated values as is required to calculate any $M\[b\]$. This is because for any $b$, in order to calculate $M\[b\]$ we will only need to look as far "back" in the array as $max\_{i=1}^{n}(x\_i)$. For example, if $x\_1 = 5$ and $x\_2 = 7$, then to calculate $M\[20\]$ we would only need to look at $M\[20-5\]$ and $M\[20-7\]$.

Furthermore, if desired, we can also preprocess the set of rods to determine if there is a simpler solution (i.e. check if $\exists x\_i (B \\\> mod \\\> x\_i \equiv 0)$, to remove rods that cannot be part of the solution (i.e. $x\_i \> B$), to remove redundant rods (i.e. $x\_i$ is redundant if $\exists j \neq i (x\_j \\\> mod \\\> x\_i \equiv 0)$), etc.

# Example

Here is a working example in Python (without any of the preprocessing optimizations):

```
def cuisenaire(B, rods):
    """
    B is a positive integer that serves as the targeted upper bound (inclusive).
    Rods is a list of cuisenaire rods with positive integer lengths listed
    in ascending order.
    """

    dp = [0] * (max(rods)+1)  # dynamic programming workspace

    for i in range(1,B+1):  # iteratively fill DP workspace (1 to B, inclusive)

        for rod in rods:  # evaluate each first-order subproblem

            if i - rod >= 0:  # dp[index] undefined for index < 0
                temp = rod + dp[(i - rod) % len(dp)]  # the core recurrence relation
                if temp > dp[i % len(dp)]:  # if this value is greater than other,
                    dp[i % len(dp)] = temp  # then update DP cell to greater value
            else:
                break  # optimization, not required for correctness

    return dp[B % len(dp)] == B  # solve the decision problem

```

The time complexity of this code is $O (B \cdot n)$ which is `B * len(rods)`.

The space complexity of this code is $O (max\_{i=1}^{n}(x\_i))$ which is `max(rods)`.

# Answer
> 2 votes
The problem is similar to coin denomination with infinite number of coins available.

Let me know if this works ... http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/

For every length which you encounter, you have two options, you can either use this rod or ignore this rod length and continue to the next one. In both the cases you can check if you could reach the target. If you can return true, else false.

So lets say you have a function `canFindTarget( inputArray[], idx , sum )` which returns true if you can make `sum` using `inputArray[0..idx-1]` else false. Your answer would be `canFindTarget( inputArray[], idx-1, sum ) || canFindTarget( inputArray[], idx, sum - inputArray[idx - 1])`.

---
Tags: algorithms, dynamic-programming, knapsack-problems, java
---


# Question
Title: Shouldn't every algorithm run in pseudo-polynomial time?
Wiki says a numeric algorithm runs in pseudo-polynomial time if its running time is polynomial in the numeric value of the input, but is exponential in the length of the input – the number of bits required to represent it.

This answer very well explains why primality test algorithm of running time $O(n)$ is actually pseudo-polynomial time. Simply put A very simple way of thinking about it is that if you double the limit, the size of the input only increases by one bit (since the limit is part of the input), while the run time is doubled. That is clearly exponential behavior with respect to the input size.

That is, add one extra bit in the bit representation of your input and the running time will increase exponentially.

Okaaay, My doubt is, isn't it applicable to every algorithm then? Like in sorting. One might say "The main difference is that, in pseudo-polynomial time algorithms, n represents a number in the input, while in other algorithms (sorting) n represents the number of things"

To which I think, how does that matter? Searching maximum in an unsorted array of size $n$ takes $O(n)$ time, add one extra bit to $n$ and the running time will grow exponentially. Hence Shouldn't every algorithm run in pseudo-polynomial time?

# Answer
The running time is always considered with respect to the length of the input.

If the input is a natural number $N\in\mathbb{N}$, then the length of the input is $n=\log N$. In that case, running time of $\Theta(N)$ is actually exponential in the length of the input, $n$.

Suppose now that we're dealing with a problem where the input is a collection of $n$ elements. For simplicity, assume each member in the collection can be represented by a constant number of bits, independent of the input. Lets denote this constant by $c$, so the number of bits required to represent this collection is at most $cn$. In that case, if upon receiving a collection with $n$ elements (which is a $cn$ length input) you preform only $O(n)$ operations, then the running time is linear.

When saying the input is a number $N$, or a list of size $n$, we already talk about the semantics of the input (how we intend to interpret the given sequence of bits). You can count the running time in terms of those "interpretations", e.g. $O(N)$ for naive primality testing, or $O(n)$ for finding a maximum in a list, but in the end you have to remember how those objects relate to the actual input's size. If we denote the length of the input by $l$, for primality testing we have $l=\log N$, so $T(l)=N(l)=2^l$, and for finding maximum $T(l)=n(l)=\frac{1}{c}l$.
> 8 votes

# Answer
If you search for the maximum of an array of n elements, the input isn't n. It's n and an array of n elements. The input size is not log n, but a least some multiple of n.

And there are many, many problems where known algorithms are nowhere near pseudo-polynomial. For example: Given n \> 0, find the first two consecutive primes p, q such that p - p ≥ n. Or given n \> 0, find the n-th Fermat prime.
> 1 votes

---
Tags: complexity-theory, pseudo-polynomial
---


# Question
Title: Increment and Decrement on binary semaphores when their values are $1$ and $0$ respectively?
What happens if we increment binary semaphore $x$ when it is equal to $1$. E.g A process executes $V(x)$ when $x==1$; What are the possible cases then-

* Process would be blocked till $x$ becomes $0$. The moment $x$ becomes $0$,it is incremented.
* Process would be blocked and no present or future changes will be there for $x$. i.e Process assumes as if there was never a $V(x)$.
* Other. (If there is please mention).

Same query for $P(x)$ operation as well when $x=0$.

---

* Actually, Galvin doesn't mention in pseudo code what to do during such condition.
* Better if Someone could provide standard code for $P(x)$ and $V(x)$... Also, $P$ is wait operation whereas $V$ is signal operation.

# Answer
> 4 votes
A binary semaphore has the wait() and the signal() method. The one which causes a process to stop is the wait() method, while the one that increments the counter x in the semaphore is signal(). If signal is called when x=1, then the call is just ignored because the queue of blocked processes is empty, and x has already its maximum value. The process that called signal() doesn't block.

# Answer
> 0 votes
Actually, a semaphore doesn't ignore signal calls. A signal call counteracts a wait call - even if the signal happens before the wait call.

The typical sequence is: Create a semaphore S. Start an action on a different thread that will eventually signal S. Do some work or not. Wait on the semaphore. After the wait call returns, the action on the other thread has succeeded.

We don’t know how long it takes the other thread to perform the action and get to the Signal call, and it mustn’t matter. So if the Signal happens before the Wait, it is not just ignored. The semaphore records it, and when the Wait call happens, it returns immediately without stopping. So after the Wait return, the action has finished.

It Must work this way, otherwise the behaviour if the Signsl happens a nanosecond before or after the Wait call would be completely different.

---
Tags: operating-systems, synchronization, critical-section
---


# Question
Title: calculate the effective (average) access time (E AT) of this system
A computer with a single cache (access time 40ns) and main memory (access time 200ns) also uses the hard disk (average access time 0.02 ms) for virtual memory pages. If it is found that the cache hit rate is 90% and the page fault rate is 1%

I have to work out the EAT time for this and the speedup due to use of cache. I'm really confused about how to do this because I have seen two different ways of doing this and I'm not sure which is correct

solution 1: 0.90\*40 + 0.10\[0.01\*20,000 + 0.99\*200\]=75.8 ns

solution 2: 0.90\*40 + 0.10\[0.01\*(20,000+200) + 0.99\*(2\*200)\]= 95.8 ns

In the second one, it accesses main memory twice when there is a page hit and accesses disk and main memory when there is a page fault. Which one is correct?

And for the speedup, which equation do I use?: Memory access time/(Memory + Cache access EAT) OR EAT without cache/EAT

# Answer
I would approach it this way : Consider 1000 requests made by the processor - the number arrived at by ensuring whole number of requests to each storage. 90 % or 900 of those are served by the cache. Of the 10 % or 100 which are not, only 1 % or a single request faces a page fault and 99 are served by main memory.

The Expected time per request = ( 900 * 40 + 99 * 200 + 20000 ) / 1000 = 75.8 ns.

The speedup due to the cache is based on the ratio of number of cycles spent on a set of operations without the cache to the same set with a cache.
> 2 votes

# Answer
AFAIK this is how we calculate EMAT.

**Assuming no page fault** Consider your TLB access time is $t$, main memory (RAM) access time is $m$ ($\gg t$) and TLB hit ratio is $h$. Given $n$-level paging is used. Then $$EMAT=h(t+m) + (1-h)(t+(n+1)m)\\,.$$

**Assuming no TLB** Consider demand paging where page hit ratio is $p$, main memory access time is $m$, page fault service time is $S$ ($\gg m$) and $n$-level paging is used. Then $$EMAT=p(n\*m) + (1-p)S\\,.$$ Here $S$ includes (page fault overhead + swap page out + swap page in + restart overhead)
Notice: here we'll take $n$ and not $n+1$ because the page hit means you've already found the page in the page table.

**EMAT with TLB and page fault** Consider your TLB access time is $t$, main memory (RAM) access time is $m$ ($\gg t$) and TLB hit ratio is $h$. If the page hit ratio is $p$, page fault service time is $S$ ($\gg m$) and $n$-level paging is used. Then $$EMAT=h(t+m)+(1-h)\[t+p(n\*m)+(1-p)S\]\\,.$$ Basically

```
EMAT=
TLB hit*(TLB access time + Memory access time)
+ TLB Miss*(TLB access time + PageHit*[n * memory access time]
+ PageMiss*PageFaultServiceTime)

```

In your question, it should be $0.90(40+200) + 0.10\[ 40+ 0.99(2\*200) + 0.01(S) \]$. Hence your question is incomplete without page fault service time.
> 0 votes

---
Tags: computer-architecture
---


title: Multiplexer output

text:
# Question
Title: Multiplexer output
The multiplexer is a device that selects one of several analog or digital input signals and forwards the selected input into a single line.

Please consider a, for example, four data input multiplexer.

If I am not wrong, the last OR gate can produce as output only 1 and 0. How are these outputs interpreted as result of the input A, B, D or D?

# Answer
You are ignoring the control bits, which are also part of the input.

A 4-1 multiplexer also receives two control bits, $s\_1s\_2$ (sometimes called selection bits). Those bits determine what entry from the four inputs you want to select (pass forward as your output). Since you have four possible inputs, you need two control bits to specify which of one of $A,B,C,D$ you want to select.

Your single bit output is simply equal to the input bit determined by the control (say, if the control is $10$, then the output of the multiplexer is $C$). Wikipedia's entry has better drawings and explanations.
> 1 votes

---
Tags: computer-architecture, logic
---


# Question
Title: Sliding Window Protocol, waiting Time calculation
With regard to this explanation in finding Round Trip Time I tried attempting the following question

**Question**

Frames of $1000$ bits are sent over a $10^6$bps duplex link between two hosts. The propagation time is $25$ ms. Frames are to be transmitted into this link to maximally pack them in transit (within the link).

Let I be the minimum number of bits ($I$) that will be required to represent the sequence numbers distinctly assuming that no time gap needs to be given between transmission of two frames.

Suppose that the sliding window protocol is used with the sender window size of $2^l$ , where I is the numbers of bits as mentioned earlier and acknowledgements are always piggy backed. After sending $2^I$ frames, what is the minimum time the sender will have to wait before starting transmission of the next frame? (Identify the closest choice ignoring the frame processing time.)

> NB : $I$ is found to be 5 bits from the link mentioned above

**My Approach**

Propogation TIme (given) = 25ms

Bandwidth (given)= $10^6$ bps

So, to fully utilize the channel, we must send 106 bits into the channel in a second, which will be 1000 frames per second as each frame is 1000 bits

I = 5, $\Rightarrow$ $2^I$ = 32 frames are sent.

Transmission time (for a frame of size 1000 bits) = $\frac{1000}{106} = 1$ ms. So, transmission time for $32$ frames = $32$ ms.

$R\_{TT}$ (Round Trip Time ) as calculate in the above link is 25ms. Hence the Waiting time would be $32-25=7ms$

But actual answer is given as $20$ms

What is the correct approach to this question ? please explain in detail how $R\_{TT}$ should be calculated

# Answer
You have not calculated the $R\_{TT}$ you just used the **Propagation Time** that a frame needs to travel one way of the duplex link.

This is how you calculate the $R\_{TT}$:

$R\_{TT} =$ **\[Propagation time for frame\] + \[Transmission time for frame\] + \[Propagation time for ACK\] + \[Transmission time for ACK\]**

Since ACK is piggybacked we assume that its frame size will also be 1000bits, so the $R\_{TT}$ is:

$R\_{TT} = 25ms + 1ms + 25ms + 1ms = 52ms $

Therefore waiting time is: $52ms - 32ms = 20ms$
> 1 votes

---
Tags: computer-networks, network-flow
---


# Question
Title: Clarifying "operation" in the definition of data type
A definition of data type I've seen is along the lines of "a **set of values** and a **set of operations**".

What exactly does an operation in this set comprise?

For instance, might an operation be considered as:

* an identifier (e.g. integers have an operation, +)
* an identifier with signature (e.g. + operates on two integers and results in an integer)
* an identifier with signature and established behaviour (e.g. 1 + 2 = 3)
* an identifier with signature and behaviour, together with some underlying implementation

or some other concept?

# Answer
It sounds like you might be asking about an abstract data type. If so, the answer is the third option: "an identifier with signature and established behaviour".

If you are asking about a data type, then I'm not sure there's a clear answer that applies to all type systems and all programming languages. Syntactically, I think it falls closest to your second option: "an identifier with signature" -- the type checker doesn't know anything about the intended behavior. However, in practice programmers might associate other things with a type: for instance, the type might indicate the intended meaning of the data, it might indicate the intended behavior of the operations, it might indicate how the data is represented or stored, and it might even encode other distinctions -- though many of these might not be checked by the compiler's type checking or might not be visible to the compiler.
> 1 votes

---
Tags: terminology, type-theory
---


title: Extracting the Root of a Leftist Tree

text:
# Question
Title: Extracting the Root of a Leftist Tree
A leftist tree is a variant of a binary heap, where the height of the left side of the tree is usually greater than the right side. Can a leftist tree's height ever increase after extracting the root? I am pretty sure it is impossible. How can a tree's height increase after taking away a node?

# Answer
When extracting the root, the subtrees of the root remain and have to merged. Merging two leftist trees is done by "zipping" the trees along their rightmost paths. Two short paths together might be rather long. Try some examples.
> 2 votes

# Answer
It is, indeed, possible that the height of a leftist tree increases after an *extract minimum* operation. This is because, after extracting the root, the left and right subtrees have to be merged, and the merge operation is done recursively towards the right until you hit a node with an empty child. Below, you can see an example of a leftist tree that goes from a height of 2 to a height of 3 after extracting the minimum element, which, in this case, is 1.
> 2 votes

---
Tags: binary-trees
---


title: How many decision problems do exist?

text:
# Question
Title: How many decision problems do exist?
Are there countable infinte decision problems or uncountable infinite?

Thank you

# Answer
Uncountable. In fact you can see a decision problem P as a language L (the words corresponds with the inputs that are accepted by P) on alphabet Σ. A language can be encoded by an infinite binary string generating all the strings in Σ\* in lexical order and associating 1 if the current string belongs to L, 0 otherwise.

The set of infinite binary strings S is uncountable infinite. Let's assume it is countable infinite. Then we can find an association between natural numbers and the strings in S, and list them. But if we take the string composed of the complement of the bits on the diagonal, then we obtain a new infinite binary string which belongs to S but is not in the list. Contraddiction.

So the set of languages (and the set of decision problems) is uncountable infinite.
> 5 votes

---
Tags: decision-problem
---


# Question
Title: Finding a Simple Distribution In a Binary String
Unsupervised feature discovery of text that started with its bit string representation would need to discover octets were the first-order parse of such a bit string. This raises a question:

What is the technique called that can discover that a binary string, for example:

`0100100111110010101010101011111011001000111000100101110001111110111010111110010111001010100011111110001101100101001010101111000111101011010011111001111101001111101011111011110011011001111000010100110001`

has the simple model (with `A x B` meaning A occurs B times in the bag):

`{00 x 1, 01 x 2, 10 x 3, 11 x 4}`

even though it knows only that it should group bits in substrings (tokens) of the same bit length (ie: it doesn't know it should group bits in pairs)?

That is to say, if the binary string input was generated by a `perl` program:

`for(0..100){print ( (('00') x 1, ('01') x 2, ('10') x 3, ('11') x 4)[rand(10)])}`

the technique would reject, as less predictive, the distribution (model):

`{0 x 7, 1 x 13}`

and it would also reject a model that used 2 bit tokens on odd-numbered bit boundaries, as well as models that used 3 bit, or longer, tokens.

A related, more difficult technique, would find the model for a string generated by sampling the bag:

`{0 x 1, 1 x 1, 00 x 1, 01 x 2, 10 x 3, 11 x 4}}`

That is to say the bit string is a mix of token sizes.

# Answer
TL;DR: use maximum likelihood and discrete optimization.

## Evaluating candidate models: the maximum likelihood principle

If you have a candidate model, you can evaluate how well it fits the data using the maximum likelihood principle.

If $M$ is a model and $x$ is a string, let $P(x|M)$ denote the probability of outputting string $x$ when $M$ is the true model. Here I assume a generative model that produces $x$ as follows: at each step, it randomly picks one term $g\_i \times n\_i$ from $M$, appends $n\_i$ copies of the string $g\_i$ to the output, and repeats until some stopping point (say, stops once we've generated a string of fixed length).

Of course in practice we have the reverse problem: we have observed a fixed string $x$, and want to infer $M$. Now we'll treat the observation $x$ as fixed. We define the likelihood of $M$ to be $L(M) = P(x|M)$. If we have observed multiple strings $x\_1,\dots,x\_m$, then we define the likelihood of $M$ to be $L(M) = P(x\_1|M) \times \cdots \times P(x\_m|M)$.

The intuition is: models with larger likelihood fit the data better. So, if you have a choice of multiple models, choose the one with the largest likelihood -- that's the one that seems most consistent with the data.

In practice, for computational reasons, we often deal with the log-likelihood, $\log L(M)$. We choose the model whose log-likelihood is largest. Since the log is monotone, this doesn't change anything fundamental.

if you're comparing a simple model to a complex model, this introduces the risk of overfitting. The likelihood alone doesn't account for Occam's razor: the principle that, all else being equal, simpler models are more likely to represent the truth. This can be fixed by introducing some kind of regularization.

Finally, note that the likelihood of a model can be computed efficiently using dynamic programming. We each prefix $w$ of $x$, we compute $L(w)$ in terms of shorter prefixes, starting from shorter prefixes to longer prefixes, until we have computed $L(x)$. If you don't immediately see how to do this computation, ask a separate question; it's a standard dynamic programming exercise. If you're dealing with long strings, you might want to compute using log-likelihoods rather than likelihoods, to avoid underflow.

## Fixed-length tokens

If all tokens have the same length, it's probably fairly easy to find a good model. Assume know the length $\ell$ of all tokens in the model; if we don't, we can try each possibility for $\ell$, one at a time, and take the one that yields the best model.

Since we know the length $\ell$, we can divide the string $x$ up into tokens of length $\ell$. In this way we can see the set of all tokens that appear in $x$, say $t\_1,\dots,t\_k$. Now we know that the model must be of the form

$$M = \\{t\_1 \times n\_1, \dots, t\_k \times n\_k\\}$$

and we merely need to infer the numbers $n\_1,\dots,n\_k$.

Let's focus on the token $t\_1$ and see how to infer $n\_1$. We can find all occurrences of $t\_1$ in $x$, and combine them into sequences of contiguous repeats, and let $S\_1$ denote the set of repeat lengths. For instance, if at one place we see $t\_1$ repeated 3 times consecutively, and at another place we see $t\_1$ repeated 9 times consecutively, then we have $S\_1 = \\{3,9\\}$. At this point we simply take $n\_1 = \gcd S\_1$, i.e., $n\_1$ is the largest number that divides every element of $S\_1$.

We'll of course repeat this for each token $t\_i$. We end up with a complete model, as desired.

A technical detail: This assumes that each token $t\_i$ is listed only once in $M$, with a single repeat-factor $n\_i$. In other words, it assumes the model is allowed to look like $\\{00 \times 4\\}$ but not $\\{00 \times 2, 00 \times 3\\}$ (the latter has the token $00$ with two different repeat-factors). If you want to consider the latter kind of model, the problem reduces to finding a set of repeat-factors $R\_1$ such that every element of $S\_1$ can be expressed as a linear combination of $R\_1$. The optimal solution will depend on the form of regularization you use; without regularization, the optimal solution will always be to simply take $R\_1$ to have a single element, $R\_= \\{\gcd S\_1\\}$. So if you want to consider models where the same token appears twice, you'll need to specify a particular form of regularization (ask a new question). For now, I'll assume such models aren't of interest.

So this shows how to solve the problem, in the easy case where all tokens have the same length.

## Variable-length tokens

Handling models where the lengths of the tokens are not all the same looks much more challenging. I can suggest one possible approach, but the best approach will probably depend on the parameter settings you're encountering in practice.

I suggest reducing this to a discrete optimization problem. In particular, I suggest you identify a set of tokens $t\_1,\dots,t\_k$ that you're confident will be a superset of the ones in the real model, and then use optimization methods to solve for the repeat-factors $n\_1,\dots,n\_k$ that maximize the likelihood of the model.

In more detail: Fix the set of $t\_1,\dots,t\_k$. Now the model looks like

$$M = \\{t\_1 \times n\_1, \dots, t\_k \times n\_k\\}$$

where the $t\_i$'s are known and the $n\_i$'s are unknown (variables). Consequently we can think of the likelihood $L(M)$ as a function of the $n\_i$'s: given any candidate values for $n\_1,\dots,n\_k$, we can compute $L(M)$ using dynamic programming.

So, I'd suggest you use some existing optimization strategy to find $n\_1,\dots,n\_k \in \mathbb{N}$ that maximize $L(M)$. A natural approach is probably some form of local search, e.g., hillclimbing, hillclimbing with random restarts, or simulated annealing. A suggestion for a set of "local moves" would be to pick a single $n\_i$ and change it via one of the following operations: multiply $n\_i$ by a small prime number; divide $n\_i$ by a small prime divisor of it; set $n\_i$ to zero; change $n\_i$ from zero to a small number; increment $n\_i$; decrement $n\_i$.

How do we find the set $t\_1,\dots,t\_k$ of tokens? Here a convenient fact is that we don't have to get this set exactly right; it suffices for it to be a *superset* of the true set of tokens in the actual model. In particular, setting $n\_i=0$ is equivalent to removing the token $t\_i$ from the model entirely. So, we can choose a larger-than-necessary set of tokens $t\_1,\dots,t\_k$ and let the optimization routine effectively solve for which tokens should be retained and which should be eliminated. One heuristic would be to choose $t\_1,\dots,t\_k$ to be the set of all bit-strings of a certain range of lengths (e.g., all bit-strings of length 2 or 3). Another heuristic would be to use some kind of filtering condition: use the set of all bit-strings $t$ that appear at least some minimum number of times in $x$. The nice thing is that we can try each of these choices in turn, apply the optimizer to each, get a list of candidate models, and choose the best one (using the maximum-likelihood principle). For instance, it might not be clear how to choose a threshold for the filtering, but we can try multiple values in a exponentially decreasing sequence and keep the best model obtained.

Similarly, it's also possible to come up with heuristics for the initial values of $n\_1,\dots,n\_k$ to feed to the optimizer (this will help some optimizers converge to a better solution). For instance, for each token $t\_i$ and each candidate repeat-factor $r$, you could count the number of times that $t\_i$ appears repeated $r$ times in a row, then choose the value of $r$ that has the highest count as the initial guess for $n\_i$.

How well will this work? I don't know. It will probably depend a lot on the parameters of the problem instances you run into in practice. I would suggest you try it on your data sets, with several different optimization methods and fiddling with the parameters a bit. If it doesn't work, ask another question where you show us what you've tried, and also show us the typical range of values for the most important parameters: the number of tokens in the model ($k$), the range of lengths of the tokens themselves, the range of values of the repeat-factors $n\_i$, the length of the string $x$.
> 0 votes

---
Tags: machine-learning, pattern-recognition
---


# Question
Title: How to solve F(n)+1 = (F(n-1)+1)*(F(n-2)+1) this recurrence relation?
I am trying to solve this recurrence relation for a while but not getting anywhere. Actually, the sequence is given as,

> **F(n) = F(n-1) + F(n-2) + F(n-1)\*F(n-2)**

where, F(0) and F(1) will be given. I added 1 on both sides to factorize it. I tried to solve it by taking ***log*** on both sides but unable to come to a conclusion.

P.S. I can't use simple `for` loop as n can go upto 10^9 so it'll result into a timeout.

# Answer
You already solved a major part of the problem. Now just take logarithm of the both sides: $$ \log(F(n)+1) = \log(F(n-1)+1) + \log(F(n-2)+1)$$ Then define $G(n) = \log(F(n)+1)$. Now you have a Fibonacci-like recursive relationship: $$G(n)=G(n-1)+G(n-2)$$ You might know that Fibonacci sequence has a closed form solution in terms of inital terms as follows: $$ U\_n=\frac{U\_1-U\_0\psi}{\sqrt{5}}\times \phi^n+ \frac{U\_0\phi-U\_1}{\sqrt{5}}\times \psi^n $$ where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$. Now just replace $U\_n$ with $G(n)$, then you have the following: $$ G(n)=\frac{G(1)-G(0)\psi}{\sqrt{5}}\phi^n+ \frac{G(0)\phi-G(1)}{\sqrt{5}}\psi^n $$ Now get back to the $F(n)$ by using $F(n)=e^{G(n)}-1$ which is: $$F(n)=e^{(\frac{\log(F(1)+1)-\log(F(0)+1)\psi}{\sqrt{5}}\phi^n+ \frac{\log(F(0)+1)\phi-\log(F(1)+1)}{\sqrt{5}}\psi^n)}-1$$
> 2 votes

# Answer
It can be computed in a completely analytical way. Take:

$$ F\_n = F\_{n-1} + F\_{n-2} + F\_{n-1}F\_{n-2} $$

Adding $1$ to both sides and factorizing we obtain:

$$ F\_n + 1 = (F\_{n-1} +1)(F\_{n-2}+1) $$

Now let $G\_n = F\_n + 1$ :

$$ G\_n = G\_{n-1} G\_{n-2}$$

Taking the logarithm in some base $b$ :

$$ \log\_b{G\_n} = \log\_b G\_{n-1} + \log\_b G\_{n-2}$$

Which we rewrite, letting $H\_n = \log\_b{G\_n}$ , as:

$$ H\_n = H\_{n-1} + H\_{n-2} $$

This suggests an effective way to compute $F\_n$ . First of all we compute $H\_0 = \log\_b(1 + F\_0)$ and similarly $H\_1$. Then we determine $H\_n$ in closed form. Since $H$ is a second-order recurrence with constant coefficients, $H\_n$ is in the form:

$$ H\_n = A\phi^n + B\psi^n $$

where $\phi, \psi$ are the solutions to the associated polynomial equation $h^2 = h +1$, namely $\frac{1 \pm \sqrt{5}}{2}$. Knowing $H\_0$, $H\_1$, we can determine $A, B$ as the solutions to the following system:

$$ \left \\{ \begin{array}{r c l} H\_1 & = & A\left( \frac{1 - \sqrt{5}}{2} \right) + B\left( \frac{1 - \sqrt{5}}{2} \right) \\ H\_0 & = & A + B \end{array} \right . $$

Now, remembering that $H\_n = \log\_b{G\_n}$ and $G\_n = F\_n + 1$, we can finally compute:

$$ F\_n = b^{H\_n} -1 $$
> 3 votes

---
Tags: recurrence-relation, mathematical-programming
---


title: Superscript on complexity class?

text:
# Question
Title: Superscript on complexity class?
What does it mean when one complexity class has another complexity class superscript?

For example, sometimes in papers I see $P^P$ or $P^{NP}$.

# Answer
> 2 votes
It's a synthetic notation for complexity classes of oracle machines. Let $\mathcal{A}$ be a class and $L$ be a language. We define:

$$ \mathcal{A}^L $$

to be the complexity class of the languages decidable by a machine in class $\mathcal{A}$ with access to an oracle for $L$.

If $\mathcal{A}$ and $\mathcal{B}$ are classes, we define:

$$ \mathcal{A}^\mathcal{B} = \bigcup\_{L \in \mathcal{B}} \mathcal{A}^L $$

Therefore, $\mathcal{P}^\mathcal{P}$ is the class of languages decidable in polynomial time by a machine with an oracle for any language of $\mathcal{P}$, and $\mathcal{P}^\mathcal{NP}$ is the class of languages decidable in polynomial time by a machine with an oracle for any language of $\mathcal{NP}$.

# Answer
> 2 votes
That's referring to a complexity class defined in terms of oracle machines. See the Wikipedia article on that topic for more.

For example, $P^L$ means the class of all problems that can be solved in polynomial time using a machine that has an oracle for $L$ (essentially, a subroutine you can invoke that magically tells you in $O(1)$ time whether $x \in L$ for any $x$ of your choice). Also, $P^P$ means the union of $P^L$ over all $L \in P$, i.e., all problems that can be solved in polynomial time using a machine that has an oracle for any language in $P$ of your choice.

---
Tags: complexity-theory, np, oracle-machines
---


# Question
Title: How to prove this "np-complete" problem?
I have a problem that I need to prove its np-completness: My original question

I need to reduce it from some problem, i´m trying to do it from some other than knapsack, that´s why I ask again. I need two sets $A$ and $B$ of equal cardinality $|A|=|B|$ and $\sum{A}\leq V$ and $\sum{B}\leq V$.

* It is like **Partition**, but sums must not be the same, must be less or equal than a fixed $V$, and **cardinality** must be equal.
* It is also like **Bin-Packing problem** with $k = 2$ (numbers of bins), but need to guarantee equal **cardinality**.
* I tried also with **Sub-Set-Sum**, but need to guarantee that the elements sum at most $k$, not exactly $k$.

Note: The problem with knapsack is that knapsack can select any items in no particular order from the list of objetcs, and my problem need to select (if selects) the first $k$ objects if they fit in the two sets.

PS: If anything is unclear, please comment and I'll explain!

# Answer
Assuming that you have a set $S=\\{b\_1,\ldots,b\_n\\}$ and a number $V$ and you would like to find two subsets $X$ and $Y$ of $\\{1,\ldots,n\\}$ such that $\sum\_{i\in X}b\_i\leq V$ and $\sum\_{i\in Y}b\_i\leq V$ and $|X|=|Y|$.

Given an instance of EQUAL-PARTITION (EP) $E=\\{a\_1,\ldots,a\_n\\}$, are there two subsets $A$ and $B$ of $\\{1,\ldots,n\\}$ such that $\sum\_{i\in A}a\_i=\sum\_{i\in B}a\_i=\frac{\sum\_{i=1}^na\_i}{2}$ and $|A|=|B|$?

You construct an instance of your problem as follows:

$$b\_i=a\_i+\frac{2}{n}V-\frac{\sum\_{i=1}^na\_i}{n}.$$

Now, EP is solved iff your problem is solved.

* For the *only if* case, assume that EP is solved, that is there are two subsets $A$ and $B$ of $\\{1,\ldots,n\\}$ such that $\sum\_{i\in A}a\_i=\sum\_{i\in B}a\_i=\frac{\sum\_{i=1}^na\_i}{2}$ and $|A|=|B|$. Take $X=A$ and $Y=B$. You will find that $\sum\_{i\in X}b\_i=V\leq V$ and $\sum\_{i\in Y}b\_i=V\leq V$ and $|X|=|Y|$.
* For the *if* case, assume that you find two subsets $X$ and $Y$ of $\\{1,\ldots,n\\}$ such that $\sum\_{i\in X}b\_i\leq V$ and $\sum\_{i\in Y}b\_i\leq V$ and $|X|=|Y|$. Take $A=X$ and $B=Y$. You will find that $\sum\_{i\in A}a\_i\leq \frac{\sum\_{i=1}^na\_i}{2}$ and $\sum\_{i\in B}a\_i\leq \frac{\sum\_{i=1}^na\_i}{2}$ and $|A|=|B|$. Since $\sum\_{i\in A}a\_i+\sum\_{i\in B}a\_i=\sum\_{i=1}^na\_i$, you get $\sum\_{i\in A}a\_i=\sum\_{i\in B}a\_i=\frac{\sum\_{i=1}^na\_i}{2}$
> 0 votes

---
Tags: np-complete, reductions, knapsack-problems, partitions
---


# Question
Title: Any ideas on implementation of a certain image process?
I recently found this music video. While the music is mislabeled, the video part caught my eye. It seems to be transitioning between two images based on shape? I think its a fade-in/fade-out with the images being streched and transformed, but it seems to be specific on the shape in the image. This may be manual, but anybody have ideas on how one might go about something like this automatically? I was thinking it could be possible if you find the "flow" of an image by assigning pixels vectors based on their color compared to their neighbor's colors.

# Answer
The first effect that appears at the video is a hue change. Later this is morphing, which is a feature based operation.

It seems like some similarity between images is used to set the morphing points (looking at the consecutive changes the points that do not move are chosen separately per transition).

The part of comparing two images (your last sentence) is used to make transition smoother, otherwise it would resemble warp. This is known as the Temporal Coherence, another technique includes Structural Similarity. Techniques yielding the best results are semi-automatic or manual due to a big complexity involved in finding smooth, minimal transition well perceived by people and also lack of good formula evaluating "how natural" transition looks like. The optimal transition calculated as minimal sum of changes does not yield nice looking morphing.

Sometimes a motion blur is added on top of the morphing (between patches) to make transition look better.
> 1 votes

---
Tags: image-processing
---


# Question
Title: Recover PRNG description from consecutive outputs
Given the outputs of the pseudorandom numbers generator how can one determine the type (e.g. Linear Feedback Shift Register), Multiply-With-Carry, Linear Congruential Generator etc.) and recover the function and the seed?

The given array of numbers is for sure generated by PRNG (not Cryptographically Secure) - this is known in advance. The outputs are clean, the PRNG is a black box returning consecutive numbers (no modified, no skipped values. Now the task is to find the function and seed from the values.

The simple idea is try all schemes until match is found, but I am interested in more algorithmic approach.

# Answer
> 10 votes
There's no single method to determine the type of the PRNG. Indeed, for a cryptographic-strength PRNG you can't distinguish its output from truly random, so you can't determine the type of such PRNGs solely by looking at their output.

Instead, for each of the schemes that you list, there *is* a way to recover the seed and predict future bits from its output. The way to do that is different for each type of PRNG. So, the natural approach is: for each candidate type, try the method for recovering the seed that works for that type of PRNG, and see if you're successful. If you are, you've figured out the type of PRNG.

I don't think there's a more efficient or general technique. And, frankly, I don't think a more efficient one is needed. For the types you list, there are very efficient algorithms for cryptanalyzing them, given enough output. So, I suspect it's going to be hard to beat the "try all schemes" approach.

This works if your set of PRNG types contains only PRNGs that are cryptographically weak, i.e., where it is possible to predict future outputs given enough past outputs.

For details of how to do this for any specific type of PRNG, I suggest you ask a separate question focused on that one type of PRNG. Here are some resources on some of the PRNG types you listed:

---
Tags: algorithms, pseudo-random-generators
---


title: Counting trees in a graph

text:
# Question
Title: Counting trees in a graph
I would like to know how to modify DFS/BFS in order to return the number of the trees present in a graph. I know that a tree is an acyclic connected graph, and I think that I have to initialize a counter somewhere, but I don't know where. I made the procedure "is-tree(G)" where G is the graph. It returns true if the subprocedure "is-connected(G)" also returns true and if the number of the arcs in G = number of nodes in G - 1, otherwise the procedure returns false. At this point I don't know how to count all the possibile subgraphs which are also trees.

# Answer
One way to approach the problem is through Euler Tour for Trees and hashing.

1. For each node in the graph:

1.1 Perform DFS starting from this node. Store all encountered nodes in the Euler Tour Tree format ( eg., while moving from say node 3 to node 1, you add an entry `[ 3 - 1 ]`, but dont add nodes while backtracking ) . Let's denote this by set 'S'.

1.2 Sort 'S' and compute a unique hash for the set. If the hash has already been seen before, then ignore the set and go back to 1. . Else go to 1.3. (This step is to make sure that you are not counting isomorphic trees multiple times.)

1.3 If size of the set(S) = N, number of subtrees = N * (N+1) / 2;
2. Sum all the number of subtrees obtained in step 1.
> 0 votes

# Answer
So here is a pseudo code of what i proposed. Maybe i was not clear.

1) Start with a node (Your start node)

2) For each node from root node, try to find a node (if it exists) that has atleast one node that is not visited. (If the graph is a cyclic, this condition is true). To do this, you may use a hashset of visited children for each iteration.

3) do the above till you reach a node which has no children. Thats the end of the algo where you found 1 tree in the graph. For back tracking i think you want to maintain a hashmap of all the nodes that you started with and the value field contains all the connected nodes to the graph. The point you reach a leaf node without violating point(2), you start back tracking to find the parent of the current node; ie the leaf node to the start node.

Thats your subgraph which is a tree.

PS- Leaf node in this case would be a node which has no nodes connected to it/all the other nodes connected to it are already visited previously/only inward connections
> 0 votes

# Answer
So for each node in the graph, initially treat it as a n-ary tree, where it contains the following `class node{
int val;
List<node> = [List of all connected nodes]
}`

Since you are doing BFS/DFS, you are sure to visit every node. `- For each node Check if the nodes in the above list has a leaf node.
- Keep a backtracking mechanism (using a map or any other data structure) which
links to the root from where you started.` Thats your Tree inside the graph. Repeat it till all nodes are visited while updating the count when you get a tree.
> -2 votes

---
Tags: algorithms, graphs
---


# Question
Title: How is Dijkstra's algorithm related to breadth first search(BFS)?
I've read in Introduction to algorithms(CLRS) that Dijkstra's algorithm uses ideas similar to those of BFS? I think it really makes sense with respect to Dijkstra's algorithm with relationship to BFS when there are multiple short paths. Consider the following problem for conclusion if you can see.

# Answer
> 3 votes
Yes the shortest path trees produced by djikstra's and BFS are identical in the case where the graph edge weights are represented by hop counts or in other words all the edge weights are ***1*** . Multiple Short Paths don't actually signify any relation with BFS . For finding the shortest Paths with BFS in a weighted graph we have modified versions of the algorithm.

---
Tags: algorithms, graphs, greedy-algorithms
---


# Question
Title: We can control tcp/udp traffic using router. Then why is it in Network layer and not transport layer?
Routers make use of the IP address, etc to shape the traffic. So obviously they must reside in at least the Network layer. However we can also shape the traffic using tcp/udp. Routers usually have the port forwarding feature which allows them to shape the tcp/udp traffic.

The IP header has a field for protocol. However that doesn't show whether the traffic is udp/tcp. This information must be present inside the payload part of the IP packet. Then why is the router able to see that information despite being in the Network Layer?

# Answer
> 2 votes
Because routers are real concrete devices, not theoretical constructs. They aren't limited by layering diagrams. Layering is a form of abstraction, which is a *convention*; there's nothing that prevents a device from inspecting and acting on the rest of the packet.

Separately: layering diagrams are a model, but not a perfect one. Real devices violate layering from time to time. The OSI 7-layer model is especially approximate -- don't take it too seriously. See, e.g., Till which layer does the loopback packet goes? and can network layers communicate between each other?.

---
Tags: computer-networks
---


# Question
Title: how to make a Turing machine of a cipher?
For example, lets consider the simplest model of cipher: the Caesar cipher. According to the theory I read the Caesar cipher consist in substitute a letter by another in considering a shift in an alphabet given by a certain number.

I know that a Turing machine consist of: a tape, a header that writes or reads information from that tape, and a set of states that consist in moving to the left or right on the tape. Also the initial state and the final state and reject states.

So if I would like to make a TM that accept the Caesar cipher I suppose that the information that would be on the tape, for example, the message "hello", that I want to convert to a cipher text by a shift of n=3 in each character so I will get the word "khoor".

Because I need to put that message on a TM tape I guess that I can convert it into a binary string, would that be necessary or can I work with original characters?

For example if my TM tape look like this (I am supposing that "h" is 0011 and that "k" is 1010 for example):

```
|0|0|1|1|e|e|e|e|

```

where e is the empty character and the header is in the leftmost position pointing to 0, so if I want to convert this "h" into "k" I can read one by one each binary digit (from left to right), converting into its corresponding binary digit to the converted letter and writing it in some beginning position at the right. Would that be ok? So I will have something like:

```
|e|0|1|1|e|1|e|e|

```

After the first iteration, I have read the leftmost digit, 0, changed into 1 and then copy it after the empty position. I can do the same with all the remaining digits.

Would that approach be good enough, in this case, to simulate the Caesar cipher in a TM, and also if I want to decipher the converted text can I do a similar process?

Bottomline, maybe somebody could show a model for a Caesar cipher using a TM?

Thanks for your help.

# Answer
> 1 votes
Honestly, the answer to "How do I model X using a Turing Machine is:"

* Implement the algorithm using a programming langauge, probably a simple one like lambda-calculus
* Translate from that language into a Turing Machine

We could tell you how to write a machine that does a Caesar cipher, but it would just be us doing the above steps for you.

Turing Machines are very un-intuitive to program in, and they're usually not used to model algorithms directly, more as a theoretical baseline of what an algorithm is. But while there are lots of proofs that model Turing Machines in general, usually you don't deal with specific machines.

If you really need to model things directly with TMs, try using a variant of them, such as RAM machines (which would probably be much easier for modelling a Caesar Cipher), and/or multi-tape TMs, then use the known translations to ordinary machines.

---
Tags: turing-machines
---


# Question
Title: how can i find the Maximum Degree of Concurrency?
i'm studying Parallel Processing ,

and i'm confused how can i calculate the max number of concurrency in a given dependency graph ?

i know that the maximum number of concurrency is the largest number of concurrent tasks at any point of the execution , but i can't calculate it from the graph

can someone explain how can i find the solution from the following graph ?

thank you ALL

# Answer
Graph a:

Phase 1: Task 1, Task 2, Task 3 and Task 4 can be executed parallelly (if you have more than 3 processors). So the degree of concurrency in this phase is the sum of the weights of those four nodes: 10+10+10+10 = 40.

Phase 2: Task 6 and Task 5 can be executed parallelly (if you have more than 1 processor). So the degree of concurrency in this phase is: 9+6 = 15.

Phase 3: You can execute only Task 7, so the degree of concurrency here is 8.

The maximum number of concurrency is max(40, 15, 8) = 40. The average degree of concurrency is (40+15+8)/(10+9+8) = 63/27.

Graph b:

Phase 1: Task 1, Task 2, Task 3 and Task 4 can be executed parallelly (if you have more than 3 processors). So the degree of concurrency in this phase is: 10+10+10+10 = 40.

Phase 2: You can execute only Task 5, so the degree of concurrency here is 6.

Phase 3: You can execute only Task 6, so the degree of concurrency here is 11.

Phase 4: You can execute only Task 7, so the degree of concurrency here is 7.

The maximum number of concurrency is max(40, 6, 11, 7) = 40. The average degree of concurrency is (40+6+11+7)/(10+6+11+7) = 64/34.
> 1 votes

---
Tags: parallel-computing
---


# Question
Title: Number of states and alphabet to fulfill definition of DFA?
I have some questions about DFA.

Can the alphabet of a DFA have one element?

Can a DFA have zero states?

Does a DFA require final state(s)?

Thanks

# Answer
1. Yes, the alphabet can have only one element. For example the DFA that recognizes a\* has Σ={a}.
2. No. A DFA is defined as {Σ, Q, δ, q0, F}, where q0 is the initial state. So the number of states for a DFA is \>= 1.
3. A DFA with no final states rejects every input, so it's an automaton that recognizes L=∅. So no, DFA doesn't require final states.
> 1 votes

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


# Question
Title: find if a string is periodic using a suffix tree, and prove it
A string `s` of length `n` is periodic if there is a string $u$ of length \<= n/2 such that $s = u^ku'$, where $k$ is an integer \>=2, $u^k$ is the concatenation of k copies of $u$ , and $u'$ is a prefix of u.

The smallest period of $s$ is the shortest $u$ (largest $k$) for which this holds.

For example, if s=ACACACACA, then k=4, u=AC, u'=A.

I want a linear-time algorithm for determining if s is periodic.

This SO answer gives a nice lead for a suffix tree solution. I want to use it, but I can't prove that it will work if and only if s is periodic.

Can you sketch it for me?

# Answer
> 2 votes
It's wrong. Consider $aaaabb$, so you'll find that $aaa$ repeat twice and consider it as an answer, while it is obviously not.

Check each suffix with length $n\>l\ge\frac{n}{2}$. If it's also a prefix of $s$, $s$ is periodic and $u$ is the prefix with length $n-l$. If you can't find such suffix $s$ is not periodic. The proof is straight forward: $s\[i\]=s\[i+n-l\]$ for $1\le i \le l$. So you can easily prove that $s\[n-l+1..2(n-l)\]=u$, and so on. Since $n-l\le\frac{n}{2}$, $u$ repeat at least twice. The converse is similar, by proving $s\[i\]=s\[i+len(u)\]$.

KMP or Z-algorithm are sufficient to do this, but if you really need a suffix tree solution:

Check each node on the path from root to the leaf which represents the whole string. If a node on this path represents a suffix with length $\ge\frac{n}{2}$ (except the whole string), we find the answer. (Note that each node on this path represents a prefix.)

---
Tags: correctness-proof, suffix-trees
---


# Question
Title: Reducing time complexity for finding all possible triplets in an array?
So I have an array sized N. It is sure that array has all distinct elements.

I need to find sum of all possible triplets in that array and for that i need to find all possible triplets.

What i did: looping through array with three nested $for$ loops but that gives O(n^3).

I want to optimise the algorithm as n is very large(upto 10000)

Eg: Array==\> {1,2,3,4,5}

Possible triplets: {1,2,3} {1,2,4} {1,2,5} {1,3,4} {1,3,5} {1,4,5} {2,3,4} {2,3,5} {2,4,5} {3,4,5}

# Answer
Finding all the triplets is in fact useless. Let $|A| = n$. Observe that each $a \in A$ appears in exactly $\binom{n-1}{2}$ triplets.

Therefore, the requested sum is just:

$$ \sum\_{a \in A} \binom{n-1}{2}a = \binom{n-1}{2} \sum\_{a \in A} a $$
> 3 votes

# Answer
Let n be the length of the array A

```
for (i = 0, i < n - 2, i++)
     for (j = i + 1, j < n - 1, j++)
          for (k = j + 1, k < n - 0, k++)
               sum += i + j + k

```

You are iterating each result exactly once. I don't think you are going to do better on the iteration. It is O($\binom{n}{3}$). You can get number from combination.

If you look at as every element will appear with every other pair (2) from a set of n-1 then combin(n-1,2) for each element. Just sum the array and multiply by that number.

$\sum\_{a \in A} \binom{n-1}{2}$
> 1 votes

---
Tags: algorithms, optimization, arrays
---


# Question
Title: Protecting data unequally using Error Correction Codes
Say I'd like to transmit a 100-bit packet which has a field containing a continuous value. I'd like to protect this value with an error correction code but an error in the MSB of this value is much more catastrophic than an error in the LSB, so how do I have to design the code so that it will be optimal by means of protection (more redundant bits for the important parts)?

For example, let's assume my continuous field is Temperature. My problem is that the temperature is represented by X bits but they are not equally important. If the temperature is 23.452298 degrees than I can't risk an error in the integer part (23) but if I'll get an error in the fractional part I'll be able to live with it (though I prefer protecting it too, with less "protection" bits).?

# Answer
> 2 votes
Since error correction here is essentially discrete, it might not be easy to come up with an optimal transient encoding, however you can approximate this by applying different encoding schemes for different parts of your data. In your temperature digits example, you might consider an encoding with $d=5$ Hamming distance for integer part and $d=3$ for fractional part, which will eventually provide a two-bit correction for the integer part and one-bit correction for the fractional part. This partitioning can be varied.

# Answer
> 2 votes
Schulman's tree code may come in handy: This is a prefix code where future symbols of the codeword give some information about the prefix up to that point. Using that code, there is better probability to deocde correctly the prefix of the message than it's suffix.

---
Tags: error-correcting-codes, crc
---