# Question
Title: My algorithm is different from CLRS' -- is it wrong?
Exercise 2.3-7 from "Introduction to Algorithms" by Cormen et al. Third Edition, states:

> Describe a O(n lg n)-time algorithm that, given a set *S* of *n* integers and another integer *x*, determines whether of not there exist two elements in *S* whose sum is exactly *x*.

At first, I had no idea how to solve it since I thought you couldn't access elements of a set by index, but assuming you could, here was my solution:

First off, we sort the set *S*, and then for every element *y* in *S*, we search if *x - y* exists in *S*. If *x - y* exists then we are done, otherwise continue the process until we have looked at all elements in *S*.

Since we sort at the beginning it's O(n log n) and then we perform a binary search for every element, so total cost would be O(n log n) + O(n log n), therefore O(n log n).

But the solution they give in the Lecture Notes is:

> The following algorithm solves the problem:
>
> 1. Sort the elements in *S*.
> 2. Form the set *S'*= {*z* : *z* = *x**y* for some *y**S*}.
> 3. Sort the elements in *S'*.
> 4. If any value in *S* appears more than once, remove all but one instance. Do the same for *S'*.
> 5. Merge the two sorted sets *S* and *S'*.
> 6. There exist two elements in *S* whose sum is exactly *x* if and only if the same value appears in consecutive positions in the merged output.

And they go on to say:

> Steps 1 and 3 require O(n lg n) steps. Steps 2, 4, 5, and 6 require O(n) steps. Thus the overall running time is O(n lg n).

So obviously they assume a set is just a regular array (you can access elements by index and the elements don't have to be unique). (And just to clarify my assumption, from the beginning of the book up to this point, they haven't put forth their definition of set, so it was easy to assume they were referring to an actual set).

It seems to me that even though their solution is O(n log n), my solution not only does it reduce the "hidden costs" greatly, it's also much more straightforward than theirs.

(To account for the possibility of repeated elements, nothing needs to be modified since the current *y* is not inside the searching subarray)

I've checked the published erratas (I know it wouldn't be a mistake *per se* anyway, but I thought it might've said something there), and there is nothing. So my question is: why is my solution wrong? Is my algorithm incorrect or is it my analysis?

# Answer
> 4 votes
You are right, there is a assuption that the set is available as an unsorted array, but I think that most set representations will allow you to obtain all elements in linear time. I also agree with you that your solution is straightforward, and uses no funny tricks.

I guess their solution is to impress you that only sorting and merging is needed, no such complicated things as binary search. (insert smiley here.) Perhaps binary search was not yet introduced at that point?

To illustrate the point Raphael makes — there are infinitely many implementations — here is mine. I believe it is correct, and uses only one sort, and a linear pass over the array. So: sort the array (from small to large). To check whether $y,z\in S$ exist such that $y+z=x$ move over the array from both sides. If the sum of the two elements of the array is larger than $x$ move the larger element one down, if it is less than $x$ move the smaller element one up. (How does this compare to your proposal?)

Nevertheless I would not consider their solution as incorrect. I like to think that it is good to have several solutions available. In some circumstances one implementation may outperform another. E.g., if the set was to be given as a sorted linked list, your solution would be hard to implement. (And mine only works if the list is doubly linked.)

# Answer
> 4 votes
The core issue here is not a factual one, but one of expectations and (meta) logic:

> But the solution they give in the Lecture Notes is \[different from mine\]. So my question is: why is my solution wrong? Is my algorithm incorrect or is it my analysis?

That's a glaring non sequitur!

1. There are infinitely many algorithms for every problem. The fact alone that you and somebody else have found different algorithms alone does not imply that either is wrong.

Try to prove yours correct and analyse its cost to compare the two approaches!
2. We often know even multiple *useful* algorithms per problem. Every author picks *one*¹. What people consider straight-forward differs (a lot), and there are other motiviations for choosing one algorithm over another.

In algorithms (and many other places), comparing answers with an answer key *is not good enough*. You need a better strategy to check your work.

You have to provide your own proof of correctness and cost analysis. Of course, checking the solution from the book in the same way is advisable; books contain errors, always.

---

1. If the topic is not so fundamental that they think their book should include most if not all commonly used algorithms. This often happens with sorting or shortest paths.

# Answer
> 1 votes
Well, your algorithm is correct but there's just one small thing -- you need to modify binary search so that it does not return index $i$ itself when searching for an index $ j$ such that $S\_i + S\_j = k.$ For example, say you had $k=6$ and element 3 of the set ($S\_3$) is $3$, your binary search must exclude index $3$ from its search space. This shouldn't be too tough to do though.

---
Tags: algorithms, algorithm-analysis, sets
---


# Question
Title: In what way can Google deepdream be extended? Is there an image dataset which can use hallucinations produced? Any deepdream useful application?
Is there a particular section of image data which when trained on deepdream algorithm and given some input image produce a resulting image from which we can conclude that the deepdream can be used for this image set (other than just producing hallucinations on input image for fun) ?

# Answer
Google deepdream can be extended and has been extended in many ways as below:

1. Image segmentation (link)
2. Beautifying pictures/photos and human faces and bodies
3. Image upscaling
4. Greyscale to Color
5. Censoring and go on..

Here, somebody using MIT's places data to train the deepdream (video)

Most of the problems in the list are at amateur stage still its one step to perfection.

If interested, you should play/improve/contribute with the code here GitHub
> 2 votes

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


# Question
Title: What's the step for build a SLR table for the following CFG?
(r1) E → E+T

(r2) E → T

(r3) T → T F

(r4)T →F

(r5) F → F∗

(r6) F → a

(r7) F → b

I am just doing the exercise on the workshop. I just knew how to the build the SLR state machine for this CFG. After built the State machine. I have found the FOLLOW and FIRST set for this CFG. But I can not find the way that how to build an SLR table from the state machine,FOLLOW and FIRST set.

# Answer
Given grammar

> (r1) E → E + T
>
> (r2) E → T
>
> (r3) T → T F
>
> (r4) T → F
>
> (r5) F → F ∗
>
> (r6) F → a
>
> (r7) F → b

As you know how to develop the graph (wont be explained), the parse table construction will be based on the graph in the question.

The Augmented Grammar:

E' → E // New rule added, that's it

E → E + T

E → T

T → T F

T → F

F → F∗

F → a

F → b

**Step 1**

Draw a empty $n$ x $m$ table , and label it appropriately.

$n$ = number of states in the graph

$m$ = number of all non‐terminals and all terminals in the grammar.

**Terminal** symbols are literal symbols which may appear in the outputs of the production rules of a formal grammar and which cannot be changed using the rules of the grammar. Here, a,b,+,\*

**Nonterminal** symbols are those symbols which can be replaced. Here, E,T,F

$ - end of string

```
╔══════════════════╤═══╤═══════════════════╤══════════════╗
║                  │   │     Terminals     │ Non Termails ║
╠══════════════════╪═══╪═══╤═══╤═══╤═══╤═══╪════╤════╤════╣
║                  │   │ a │ b │ + │ * │ $ │ E  │ T  │ F  ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 0 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 1 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 2 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 3 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║ Number of states │ 4 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 5 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 6 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 7 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 8 │   │   │   │   │   │    │    │    ║
║                  ├───┼───┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 9 │   │   │   │   │   │    │    │    ║
╚══════════════════╧═══╧═══╧═══╧═══╧═══╧═══╧════╧════╧════╝

```

**Notation:**

s1 = Shift in r1 (rule) in the given grammer

r1 = Reduce in r1 in the given grammer

and so on..

1. **Shift :** A Shift step advances in the input stream by one symbol. That shifted symbol becomes a new single-node parse tree. (*for easy understanding, when* **dot** *is not at the end of the rule, its shift*)
2. **Reduce :** A Reduce step applies a completed grammar rule to some of the recent parse trees, joining them together as one tree with a new root symbol. (*for easy understanding, when* **dot** *is at the end of the rule, its reduce*)

**Step 2**

Look into the graph, observer the transition from node 0.

You can find transitions:

*(node 0,E) = node 1* // non terminal E involved

*(node 0,T) = node 5* // non terminal T involved

*(node 0,F) = node 6* // non terminal F involved

*(node 0,a) = node 3* // terminal 'a' involved

*(node 0,b) = node 4* // terminal 'b' involved

These transitions should be added to the table.

Row 0 of the table should be filled with transitions from node 0

When we take :

*(node 0,a) = node 3*

The intersection cell of row node 0 and column 'a' terminal can be filled by **s3** as transition from node with E goes to node 3 is a **shift**.

```
╔══════════════════╤═══╤════════════════════╤══════════════╗
║                  │   │     Terminals      │ Non Termails ║
╠══════════════════╪═══╪════╤═══╤═══╤═══╤═══╪════╤════╤════╣
║                  │   │ a  │ b │ + │ * │ $ │ E  │ T  │ F  ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 0 │ s3 │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 1 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 2 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 3 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║ Number of states │ 4 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 5 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 6 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 7 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 8 │    │   │   │   │   │    │    │    ║
║                  ├───┼────┼───┼───┼───┼───┼────┼────┼────╢
║                  │ 9 │    │   │   │   │   │    │    │    ║
╚══════════════════╧═══╧════╧═══╧═══╧═══╧═══╧════╧════╧════╝

```

*(node 0,b) = node 4*

The intersection cell of row node 0 and column 'b' terminal can be filled by **s4** as transition from node with E goes to node 4 is a **shift**.

```
╔══════════════════╤═══╤═════════════════════╤══════════════╗
║                  │   │      Terminals      │ Non Termails ║
╠══════════════════╪═══╪════╤════╤═══╤═══╤═══╪════╤════╤════╣
║                  │   │ a  │ b  │ + │ * │ $ │ E  │ T  │ F  ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 1 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 2 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 3 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║ Number of states │ 4 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 5 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 6 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 7 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 8 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 9 │    │    │   │   │   │    │    │    ║
╚══════════════════╧═══╧════╧════╧═══╧═══╧═══╧════╧════╧════╝

```

as we don't have any more terminal transition, we can move to non terminals.

*(node 0,E) = node 1*

The intersection cell of row node 0 and column 'E' non terminal can be filled by **1** as transition from node with E goes to node 1.

*(node 0,T) = node 5*

The intersection cell of row node 0 and column 'T' non terminal can be filled by **5** as transition from node with E goes to node 5.

*(node 0,F) = node 6*

The intersection cell of row node 0 and column 'F' non terminal can be filled by **6** as transition from node with E goes to node 6.

**Note:** No shift or reduce for non terminals

```
╔══════════════════╤═══╤═════════════════════╤══════════════╗
║                  │   │      Terminals      │ Non Termails ║
╠══════════════════╪═══╪════╤════╤═══╤═══╤═══╪════╤════╤════╣
║                  │   │ a  │ b  │ + │ * │ $ │ E  │ T  │ F  ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │   │   │   │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 1 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 2 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 3 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║ Number of states │ 4 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 5 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 6 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 7 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 8 │    │    │   │   │   │    │    │    ║
║                  ├───┼────┼────┼───┼───┼───┼────┼────┼────╢
║                  │ 9 │    │    │   │   │   │    │    │    ║
╚══════════════════╧═══╧════╧════╧═══╧═══╧═══╧════╧════╧════╝

```

and so on..

**Note :** The intersection cell of row node 1 and column '$' terminal can be filled by **acc** (accepted) as rule added to make your grammar an Augmented Grammar is reduced.

```
╔══════════════════╤═══╤════════════════════════╤══════════════╗
║                  │   │       Terminals        │ Non Termails ║
╠══════════════════╪═══╪════╤════╤════╤═══╤═════╪════╤════╤════╣
║                  │   │ a  │ b  │ +  │ * │  $  │ E  │ T  │ F  ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │    │   │     │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 1 │    │    │ s2 │   │ acc │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 2 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 3 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║ Number of states │ 4 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 5 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 6 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 7 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 8 │    │    │    │   │     │    │    │    ║
║                  ├───┼────┼────┼────┼───┼─────┼────┼────┼────╢
║                  │ 9 │    │    │    │   │     │    │    │    ║
╚══════════════════╧═══╧════╧════╧════╧═══╧═════╧════╧════╧════╝

```

**Step 3**

node 3 has reduce to **r6** and no further transition are allowed form node 3, thus all the intersecting cells with Follow(F) are marks as **r6**.

$Follow(F) = \\{ a,b,+,\*,\\$ \\} $

**Note :** Follow(F) is taken because reduction is to the rule (r6) F → a, Follow of rigth hand side should be taken.

```
╔══════════════════╤═══╤═════════════════════════╤══════════════╗
║                  │   │        Terminals        │ Non Termails ║
╠══════════════════╪═══╪════╤════╤════╤════╤═════╪════╤════╤════╣
║                  │   │ a  │ b  │ +  │ *  │  $  │ E  │ T  │ F  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │    │    │     │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 1 │    │    │ s2 │    │ acc │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 2 │ s3 │ s4 │    │    │     │    │ 8  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 3 │ r6 │ r6 │ r6 │ r6 │ r6  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║ Number of states │ 4 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 5 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 6 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 7 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 8 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 9 │    │    │    │    │     │    │    │    ║
╚══════════════════╧═══╧════╧════╧════╧════╧═════╧════╧════╧════╝

```

node 5 has both reduce (to r2) and shift (with a,b) to **r2**.

The intersecting cells node 5 with Follow(E) are marks as **r2**.

$Follow(E) = \\{ +,\\$ \\} $

*(node 5,a) = node 3*

The intersection cell of row node 5 and column 'a' terminal can be filled by **s3** as transition from node with 'a' goes to node 3.

*(node 5,b) = node 4*

The intersection cell of row node 5 and column 'b' terminal can be filled by **s4** as transition from node with 'b' goes to node 4.

```
╔══════════════════╤═══╤═════════════════════════╤══════════════╗
║                  │   │        Terminals        │ Non Termails ║
╠══════════════════╪═══╪════╤════╤════╤════╤═════╪════╤════╤════╣
║                  │   │ a  │ b  │ +  │ *  │  $  │ E  │ T  │ F  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │    │    │     │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 1 │    │    │ s2 │    │ acc │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 2 │ s3 │ s4 │    │    │     │    │ 8  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 3 │ r6 │ r6 │ r6 │ r6 │ r6  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║ Number of states │ 4 │ r7 │ r7 │ r7 │ r7 │ r7  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 5 │ s3 │ s4 │ r2 │    │ r2  │    │    │ 9  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 6 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 7 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 8 │    │    │    │    │     │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 9 │    │    │    │    │     │    │    │    ║
╚══════════════════╧═══╧════╧════╧════╧════╧═════╧════╧════╧════╝

```

and so on..

Repeat the process until all transitions are exhausted.

**Final result :**

```
╔══════════════════╤═══╤═════════════════════════╤══════════════╗
║                  │   │        Terminals        │ Non Termails ║
╠══════════════════╪═══╪════╤════╤════╤════╤═════╪════╤════╤════╣
║                  │   │ a  │ b  │ +  │ *  │  $  │ E  │ T  │ F  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 0 │ s3 │ s4 │    │    │     │ 1  │ 5  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 1 │    │    │ s2 │    │ acc │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 2 │ s3 │ s4 │    │    │     │    │ 8  │ 6  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 3 │ r6 │ r6 │ r6 │ r6 │ r6  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║ Number of states │ 4 │ r7 │ r7 │ r7 │ r7 │ r7  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 5 │ s3 │ s4 │ r2 │    │ r2  │    │    │ 9  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 6 │ r4 │ r4 │ r4 │ s7 │ r4  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 7 │ r5 │ r5 │ r5 │ r5 │ r5  │    │    │    ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 8 │ s3 │ r4 │ r1 │    │ r1  │    │    │ 9  ║
║                  ├───┼────┼────┼────┼────┼─────┼────┼────┼────╢
║                  │ 9 │ r3 │ r3 │ r3 │ s7 │ r3  │    │    │    ║
╚══════════════════╧═══╧════╧════╧════╧════╧═════╧════╧════╧════╝

```
> 1 votes

---
Tags: formal-grammars, parsers
---


title: runtime of problems vs algorithms

text:
# Question
Title: runtime of problems vs algorithms
I know that a solving a specific problem can have different runtimes on different models of computation. But can a specific algorithm have different runtimes on different models of computation?

Also, would an algorithm be considered the high level description or the implementation level description of the procedure you need to do?

# Answer
Yes it can. When you take RAM model and your algorithm has a lot of multiplications (dominant operation), your multiplications take unit time. Even if the numbers are $2048$ bit numbers. But if you take multitape Turing Machine as your model, the cost of multiplication matters and will be included in complexity.

Algorithm is high level description, implementation will vary. Getting back to multiplication, algorithm describes that in one step you have to multiply two numbers, but if numbers are bigger than computer words instead of writting "\*" you have to implement it.
> 1 votes

---
Tags: algorithms, runtime-analysis, computation-models
---


title: Side effect and recursion

text:
# Question
Title: Side effect and recursion
My algorithm professor said a recursive function should not have side-effects since it's a methodological error because recursion is "pure". Anyway I don't understand why, even because I find side-effects useful and difficult to replace a recursive side-effect function with a "pure" one.

# Answer
Recursion is orthogonal to side effects.

You can have a recursive function with side effects, or without. You can also have a non-recursive function with side effects, or without. It's a matter of opinion and taste whether it's better to avoid side effects in any particular situation. As far as I know, there is no scientific evidence to support a claim that "you should always avoid side effects in any recursive function".

There are reasons to be wary of side effects. They make programs more complex to reason about. This doesn't mean you should never use side effects, but they have tradeoffs. Perhaps one could argue that recursive functions are especially tricky to code and thus one should be especially wary of recursive functions with side effects -- personally, I don't know that I'm particularly persuaded by it. Ultimately, I think it's a matter of taste and judgement, and it's unlikely that any "one-size-fits-all" rule will be scientifically justified.
> 2 votes

---
Tags: recursion, software-engineering, recursion-theory
---


# Question
Title: Complexity of testing membership in a disjoint set
I have a disjoint set data structure (sometimes known as a union-find data structure) where I store a value in each "node". I want to look up a node by value. How can I do this?

The representations normally discussed in literature, both linked list and forests, deal with operations being given nodes (of the linked list or forest), not values contained therein, which avoids any difficulty caused by having to find the node that contains a given value. From what I can see, the question of whether a given disjoint set contains in any subset a given value, or finding the node that contains a given value if one exists, is scarcely touched by the literature.

However, given values, this question needs to be addressed for an implementation of what the CLRS *Introduction to Algorithms* calls `Make-Set(x)` if one wishes to not trust the user of the API to always know what is and is not in the set, as it has a prerequisite that `x` does not already exist in the set.

With both representations, I see no way better than $O(n)$ to check membership, as one must always check all nodes for equality. Obviously one could maintain a separate mapping of values to nodes for the set, with $O(log n)$ lookup given an ordered value type, but this means duplicating the whole set in memory. Is there any way to represent a disjoint set while being able to test set membership in less than $O(n)$ time without duplicating the data?

# Answer
There's an easy way to find the node that contains a given value. You have two data structures: a union-find data structure (that keeps track of which nodes are in the same equivalence class), and a hashtable (that maps from a value to the node(s) that contain that value).

The MakeSet operation adds a new set to the union-find data structure and adds a new entry to the hashtable. The Union operation and Find operations use only the union-find data structure. The "look up a node by value" operation uses the hashtable.

The running time of the MakeSet, Union, and Find operations is as in the underlying union-find data structure. (MakeSet incurs an extra $O(1)$ (expected, amortized) time to insert into the hashtable, but this doesn't change the overall running time of MakeSet.) The running time of looking up a node by value is $O(1)$ (expected, amortized) time, if you have a good hash function and if each value is only found in a single node.

This doesn't require duplicating the data, if you use pointers in lieu of duplicating: each entry in the hashtable can have a pointer to the node, and each node has a pointer to the value, so values and nodes aren't duplicated. Of course, this does increase the memory usage (by at most a constant factor); nothing is free in life.
> 1 votes

---
Tags: data-structures, dictionaries, union-find
---


# Question
Title: How do I show this variant of the longest path problem is NP-hard?
The problem is as follows:

"Given a weighted graph G and a path p, show that p is the longest simple path in G."

I'm thinking a reduction from HAMPATH would work, but after 3 hours of racking my brain over this, I have no idea how to do it. What makes the reduction difficult is that I'd need to somehow "know" the path, since the input to this longest path variant requires the path along with the graph.

Any tips/hints/help would be appreciated.

# Answer
> 1 votes
Hint 1. The graph doesn't have to be connected.

Hint 2. Mouse-over the following for a slightly more detailed hint.

> Arrange for there to be two components. One of them has quite a long path, which you can easily find.

---
Tags: complexity-theory, np-complete
---


# Question
Title: Structure of a Pumping Lemma proof: contradiction or counterexample?
This site is full of Pumping Lemma questions, and I do admit I've not read them all. I've tried some proofs myself and they seem to work, but I can't find anywhere what is the (general) exact structure of a proof where you show a language is not regular or context-free?

Wikipedia and most proofs start with "Suppose $L$ is a regular language", which would mean it is a proof by contradiction, because it isn't.

But the lemma has the quantifiers $\exists, \forall, \exists, \forall$ in order. And in the proof you assume a given constant given by the first $\exists$, and then you come up with some word (the first $\forall$), format it in some given substring division (the second $\exists$) and again come up with some $k$ (second $\forall$) for which you show it is not in $L$.

This seems to me like a counterexample proof ("this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma"), and not a proof by contradiction?

# Answer
> 4 votes
> this is not context-free/regular because I can come up with a counterexample which fails the pumping lemma

You are missing that in order to construct this counterexample you have to *assume* that $L$ is regular. Then you *apply* the Pumping lemma, which yields the Pumping length $p$. Only *then* do you construct your (counter)example string (using $p$!) and show that it contradicts the Pumping lemma. Hence, the assumption must be false.

So while you can say that you derive the contradiction using a counterexample, the outer-most proof is by contradiction.
With the assumption, you wouldn't have $p$!

Note that proofs can be nested, so you don't need to see only one proof technique. For instance, induction proofs often use a proof by contradiction inside the inductive step.

# Answer
> 1 votes
The formulation of the Pumping Lemma, with explicit quantifiers, is as follows:

$$\forall L\in REG, \exists p\>0, \forall w\in L,|w|\>p\Rightarrow \exists x,y,z\in \Sigma^\*, w=xyz\wedge c\_1\wedge c\_2\wedge c\_3$$ where $c\_1,c\_2,c\_3$ are the conditions of the lemma.

Thus, a proof that a language is not regular is indeed by contradiction. In order to see the general structure of a proof, it is convenient to this of ourselves as trying to contradict the lemma, while an adversary is trying to prove the lemma holds.

Thus, the general structure is as follows. The lemma claims something for every regular language, so we choose a certain language we want to "attack".

Now, the adversary gets to choose $p$, so we write "for every $p\>0$". Next, the lemma says something for every $w\in L$ such that $|w|\>0$, so we get to pick $w$, but in order to make it useful, we need to pick $w\in L$ such that $|w|\>p$ (otherwise the adversary wins vacuously).

Now, we have $\exists x,y,z$, so the adversary chooses them. We thus write "there exist $x,y,z$ such that $w=xyz$". Next, we want to show that at least one of the conditions $c\_1,c\_2,c\_3$ does not hold. Technically, if $c\_1$ or $c\_2$ don't hold, then the adversary chose "stupidly", and we're done. Thus, we assume that $c\_1$ and $c\_2$ do hold, and we show that $c\_3$ (the pumping argument) fails, and thus we win.

So overall we get the following proof structure:

Assume by way of contradiction that $L\in REG$, then let $p\>0$ be its pumping constant. Consider the word $w=...$(something clever). Let $x,y,z\in \Sigma^\*$ such that $w=xyz$, and $|xy|\le p$, and $|y|\>0$, we show that there exists $i\ge 0$ such that $xy^iz\notin L$, in contradiction to the pumping lemma.

Thus, $L\notin REG$.

# Answer
> 1 votes
In general, proving things is a creative enterprise. As such, there is no "standard template": you're free to do whatever you want, as long as it's logically valid.

In particular, as long as you understand why a proof works, you shouldn't worry too much about whether it's a proof by contradiction, or a proof by counterexample, or something else. That's a bit like a poet wondering whether a particular phrasing they've used is a zeugma or a syllepsis. As long as it's effective imagery, who cares except the critics?

---
Tags: proof-techniques, pumping-lemma
---


# Question
Title: Common name for inverse of beta reduction
For some transformation, I am currently working on, it is useful to "pull out" subexpressions and replacing them with variables.

i.e. $\textbf{transform}(42 + 3 * 4) = (\lambda x. 42 + x) (3\*4)$

This has, of course, the same result (if it does not extract bound variables and is correct only modulo evaluation order, i.e. termination properties might change).

Such a basic operation probably has an established name, but I never heard it. Is it "beta-expansion"?

# Answer
> 7 votes
Yes, it's called beta expansion. Usage examples: Horwitz, Miller, Galbiati and Talcott, Coq manual, …

Similarly $M \to (\lambda x. M \\, x)$ (the converse of eta reduction) is called eta expansion, and so on.

---
Tags: terminology, lambda-calculus
---


# Question
Title: What are these questions in the PoplMark challenge asking?
I was reading the paper *Mechanized Metatheory for the Masses: the PoplMark Challenge* by Aydemir et al (PDF) and I found the following three questions on page 13 of the PDF a bit confusing.

> Challenge 3: Testing and Animating with respect to semantics.
>
> 1. Given $\mathrm{F}\_{\texttt{\<:}}$ terms $t$ and $t'$, decide whether $t\rightarrow t'$.
> 2. Given $\mathrm{F}\_{\texttt{\<:}}$ terms $t$ and $t'$, decide whether $t \rightarrow^\* t' \not\rightarrow$, where $\rightarrow^\*$ is the reflexive-transitive closure of $\rightarrow$.
> 3. Given an $\mathrm{F}\_{\texttt{\<:}}$ term $t$, find a term $t'$ such that $t\rightarrow t'$.

I think question (3) is saying reduce a term $t$ to $t'$ until which is no longer can be reduced (or become a value). What about question (1), are they just saying check the result if it is equal to some term $t'$? and question (2).

Could someone explain me their differences?

# Answer
The reduction relation is beta reduction (for term and type variables) as defined in the description of Challenge 2B. It's a single reduction step, not repeated reduction until a value is reached.

(3) says to find *a* term $t'$ such that $t \to t'$ because if one exists, then there are infinitely many such terms in $F\_{\<:}$: all the terms in the same alpha equivalence class. Usually we say that beta reduction is deterministic, i.e. $t'$ is unique, but that's because we reason on alpha equivalence classes. PoplMark is concerned with the representation of variable binding, so here terms are a concrete representation where variable binding is treated explicitly. For example, in a nominal representation, $(\lambda \texttt{x}. \texttt{x}) (\lambda \texttt{x}. \texttt{x}) \to (\lambda \texttt{x}. \texttt{x})$, and $(\lambda \texttt{x}. \texttt{x}) (\lambda \texttt{x}. \texttt{x}) \to (\lambda \texttt{z}. \texttt{z})$; (3) allows finding any of these since they are all equally valid.

Similarly (1) asks to check whether $t'$ is *a* possible result of reducing $t$, not *the* result: the implementation of the reduction (item (3)) might find a different representative of the alpha equivalence class from the one submitted by the user.

Only (2) is about reducing to a value. It says so explicitly: $t$ reduces to $t'$ in any number of steps, and $t'$ cannot be reduced.
> 4 votes

---
Tags: programming-languages, semantics, formal-methods
---


# Question
Title: Can LOOP-Programm stop when its value goes below 0?
I am wondering, if in the LOOP programing language, whether instances of the `LOOP x DO P END` are defined to stop in the case $x \< 0$.

The definition only says "Execute $P$, $x$ times" for the above program.

IT is perfectly clear for $x = 0$. However, I believe in order to keep the language simple the definition doesn't extend to the case $x \< 0$.

If it were possible, then it would for instance basically shorten a $x\_1\ div\ x\_2$ operator to just one line:

```
x_0 = 0;
LOOP x_1 DO x_1 = x_1 - x_2; x_0 = x_0 + 1; END

```

If it is not possible, is there any other reason except for reasons of convention?

# Answer
> 3 votes
Variables in LOOP programs are non-negative, so the problem never arises; the instruction $x\_1 = x\_1 - c$ assigns $x\_1$ the value of $\max(x\_1-c,0)$.

Note that the instruction $x\_1 = x\_1 - x\_2$ isn't allowed: the second operand has to be a constant. However, since $x\_1 = x\_1 - x\_2$ can be implemented in LOOP, the programming language "LOOP with instructions of the form $x\_i = x\_i - x\_j$" has the same power as LOOP.

---
Tags: computability, programming-languages, loops
---


# Question
Title: Best starter resources for learning about AI
I want to start learning of AI and have an idea to program "social evolution simulator" but want to hear any advice to avoid creation "well known bicycles" and get strong knowledge-base. Will be grateful for online resources and/or books. Thanks.

Also, I understand, that any programming language can be used for this, but probably some language is already more suitable for.

# Answer
Artificial intelligence is vast.

*A seminal paper by Marvin Minsky (1963)* will be best place to start. I consider it to be a fundamental resource. Minsky wrote this paper in 1963, and set the foundations of much of the modern terminology of AI.

Minsky, Marvin. "Steps toward artificial intelligence." Proceedings of the IRE 49.1 (1961): 8-30.

**Books**

* "Artificial Intelligence: A Modern Approach" by Russell and Norvig
* Overview of constraint programming "Principles of Constraint Programming by Krzysztof Apt".
* Advanced book "Foundations of Statistical Natural Language Processing by Christopher D. Manning and Hinrich Schuetze".
* Machine learning methods "Machine Learning by Tom M. Mitchell".
* Intelligence by Jeff Hawkins and How to Create a Mind by Ray Kurzweil
* The Emotion Machine by Marvin Minsky
* Artificial Intelligence: A Modern Approach by Peter Norvig and Stuart J. Russell
* Artifical Intelligence - A Modern Approach by Russell and Norvig
* Sciences of the Artifical by Herb Simon
* "INTRODUCTION TO MACHINE LEARNING" from Nils J. Nilson
* "An Introduction to Neural Networks" from Ben Krose and Patrick van der Smagt
* "Information Theory, Inference, and Learning Algorithms" part V, from David J.C. MacKay

**Online material**

**Language** (my prioritizes)

1. Python
2. Java

**Open Source Software Library**
> 3 votes

# Answer
If you want to learn a new subject I will strongly recommend you to take up a online course on that. That way you will be motivated to finish up the course and can see it through the end. Also, in a course instructor will take you step wise through the material as well there are additive benefits of assignments. So here are few online courses that I have tried.

There is this course on AI offered by UC berkely professor, Pieter Abeel. Here is the link to all the material of that course, http://ai.berkeley.edu/lecture\_videos.html. I thoroughly enjoyed the course because he explained things very well using the help of diagrams and all.

Another course that you can try is on Udacity. Here is the link to the course, https://www.udacity.com/course/intro-to-artificial-intelligence--cs271. It is instructed by one of the author of famous AI book named as "Artificial Intelligence: A Modern Approach" by Russell and Norvig.

And I will recommend python as language because it is very easy to use.
> 0 votes

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


# Question
Title: Capacity of binary not symmetrical channel
I have to solve this exercise in information theory:

*A binary not symmetrical channel has probability of transition from 0 to 1 $P(output=1|input=0)=p$ and probability of transition from 1 to 0 $P(output=0|input=1)=q$. I have to calculate the channel capacity and the input distribution that leads to this capacity value.*

I thought that the channel was the following:

So: $$P(Y|X)=\begin{pmatrix} 1-p & p\\ q & 1-q \end{pmatrix}$$

Then I tried to calculate the capacity:

$$C=\max\_{p(x)}I(X;Y)$$

where

$$I(X;Y)=H(Y)-H(Y|X)$$

where

$$H(Y)=-(1-p+q)\log (1-p+q) - (p+1-q) \log (p+1-q) = ?$$

I don't think is correct. How do I calculate $H(Y)$ and $H(Y|X)$?

---

I tried to solve the exercise in this way.

$$\pi = Pr(X=0), 1 - \pi = Pr(X=1)$$

$$H(Y)=H(\pi(1-p)+(1-\pi)q, \pi + p(1-\pi)(1-q))$$

If I call: $$\pi(1-p)+(1-\pi)q = a$$ $$\pi + p(1-\pi)(1-q) = b$$ then $$H(Y)=H(\pi(1-p)+(1-\pi)q, \pi + p(1-\pi)(1-q)) = -a \log a - b \log b$$

Now I have to calculate: $$H(Y|X)=Pr(X=0)H(Y|X=0)+Pr(X=1)H(Y|X=1) = \pi H(Y|X=0)+ (1- \pi)H(Y|X=1)$$ where

$$H(Y|X=0) = -P(Y=0|X=0) \log P(Y=0|X=0) - P(Y=1|X=0) \log P(Y=1|X=0) = -(1-p) \log (1-p) - p \log p$$ $$H(Y|X=1) = -P(Y=0|X=1) \log P(Y=0|X=1) - P(Y=1|X=1) \log P(Y=1|X=1) = - q \log q-(1-q) \log (1-q) $$

So: $$H(Y|X)=Pr(X=0)H(Y|X=0)+Pr(X=1)H(Y|X=1) = \pi \[-(1-p) \log (1-p) - p \log p\]+ (1- \pi)\[- q \log q-(1-q) \log (1-q)\]$$ and if I call: $$\[-(1-p) \log (1-p) - p \log p\]=c$$ $$\[- q \log q-(1-q) \log (1-q)\]=d$$ then $$I(X;Y)=H(Y) - H(Y|X)=-a \log a - b \log b + \pi c + (1-\pi)d$$

it's right? Thanks

# Answer
> 1 votes
You need to compute $H(Y)$ by its definition:

$$ H(Y) \triangleq \Pr(Y=0) \log \frac{1}{\Pr(Y=0)} + \Pr(Y=1)\log\frac{1}{\Pr(Y=1)}$$

To be able to compute this formula, you need to figure out what is $\Pr(Y=1)$ and $\Pr(Y=0)$. These two measures actually depend on the distribution of $X$.

To compute $H(X|Y)$ again, use the definition. $$H(Y|X) \triangleq \Pr(X=0) H(Y| X=0) + \Pr(X=1)H(Y|X=1)$$

where $H(Y | X=0)$ is easy to compute from the original entropy definition $H(Z)$, for a random variable $Z$ that is distributed same as $(Y|X=0)$. This is immediately given by your $P(Y|X)$.

In order to compute the channel's capacity, you will need to find the distribution $p(x)$ that **maximizes** $H(Y)-H(Y|X)$.

---

Maybe you should also check a textbook about information and entropy. For instance, try Cover & Thomas, "Elements of Information Theory", Chapter 7 (Channel Capacity).

---
Tags: information-theory, coding-theory, error-correcting-codes
---


# Question
Title: An FPT algorithm for Hamiltonian cycle running parameterized by treewidth
I'm looking for an algorithm that solves the Hamiltonian cycle problem parameterized by treewidth. In particular, I'm curious about such an algorithm running in $\text{tw}(G)^{O(\text{tw}(G))} \cdot n$ time.

In other words, once you have the treewidth, an algorithm that says if the input graph has a Hamiltonian cycle.

# Answer
If you want an FPT algorithm for the problem (parameterized by treewidth $t$), you want an algorithm working in time $f(t) \cdot n^{O(1)}$, where $f$ is any computable function (depending solely on $t$). Of course, it would be nice to make $f$ as appealing as possible.

In addition to the mentioned algorithm running in $O(t^t n)$ time, you can also get a faster (randomized) algorithm using the Cut'n'Count technique of Cygan et al. \[1\]. In particular, you get an algorithm running in time $4^t n^{O(1)}$. It is also possible to get a deterministic algorithm working in $c^t n^{O(1)}$ (for some small constant $c$) using a rank-based approach of \[2\].

---

\[1\] Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J. M., & Wojtaszczyk, J. O. "Solving connectivity problems parameterized by treewidth in single exponential time." IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.

\[2\] Bodlaender, H. L., Cygan, M., Kratsch, S., & Nederlof, J. "Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth." Automata, Languages, and Programming. Springer Berlin Heidelberg, 2013. 196-207.
> 8 votes

# Answer
There is an outline of the algorithm you want in these slides: http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2. Given a nice-tree decomposition of width $w$ for $G$, the algorithm runs in time $O(w^w \cdot n)$. As it is based on a nice-tree decomposition, you will need to show what happens in the case of a forget node, an introduce node, and a join node when added to the solution of a smaller sub-problem. These details can be found in the slides as part of their case-by-case analysis.

This, of course, assumes that you are given a nice-tree decomposition of width $w$, as finding the treewidth of a graph $G$ is NP-hard.

The following paper - http://www.sciencedirect.com/science/article/pii/S0196677496900498 \- shows how to go from a regular decomposition to a nice one, in an efficient manner.
> 5 votes

---
Tags: algorithms, parameterized-complexity, hamiltonian-circuit
---


# Question
Title: Is finding all cycles in a graph using some version of Johnson's algorithm (code provided) really polynomial (benchmark provided)?
This is the algorithm I'm using: https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs/14115627#14115627

Specifically C#, but the linked thread has numerous languages.

Worst case time complexity should be O(|V|^{2}\log |V|+|V||E|)} https://en.wikipedia.org/wiki/Johnson%27s\_algorithm

My findings running benchmarks using the first algorithm linked:

\[polygons (each 3 vertices and 3 edges): milliseconds\]

* 10: 332 ms (~30 vertices, 30 edges)
* 11: 789 ms
* 12: 2344 ms
* 13: 7524 ms
* 14: 16788 ms
* 15: 54182 ms (~45 vertices, 45 edges)

That's exponential growth!

My only question: Is this a polynomial time algorithm that I'm using to find all cycles in a graph or not?

Thanks :)

# Answer
> 3 votes
The question seems based on a faulty premise. There are multiple algorithms that Johnson invented, and you're confusing them. One of his algorithms is for finding shortest paths (that's the one Wikipedia article talks about), another is for enumerating all cycles (that's the one the Stack Overflow answer cites). They don't have the same running time.

Second, you're using some random person's code, but maybe that code sucks and isn't a good/valid implementation of the algorithm. We don't do questions about code here.

Also, as David Richerby says, you obviously can't output all cycles in polynomial time if there are exponentially many of them (where there can be). Therefore, you shouldn't expect an algorithm to enumerate all cycles with polynomial running time.

Finally, you can't disprove an asymptotic running time analysis by benchmarking it on 6 points.

I think you need to read Johnson's original paper, understand it, and implement it yourself. Sometimes there are no shortcuts.

---
Tags: graphs, time-complexity, asymptotics, graph-traversal
---


# Question
Title: Is this an instance of a well-known problem?
# Context

I am developing an application and came across a problem that seemed difficult to solve. Before attempting to reinvent the wheel (and trying to solve an NP complete problem on my own), I would like to get some feedback. Below you will find an abstract version of the problem.

# The Problem

Input:

* A bag of colored balls. A ball may have many colors (e.g. red, blue and yellow) or only one (e.g. green). Each ball has also a score. Since we are talking about a bag, elements may be repeated.
* A set of colored boxes, one per color. Each box is labeled with a natural number.

Problem: each colored box must be filled with the exact amount of balls specified by its label.

Constraints:

* The color of the balls in a box must match the color of the box (e.g. a green ball goes in a green box).
* A ball of many colors can be assigned to a box of any of those colors (e.g. a ball that is both red and green can either go in a red box or in a green one).

The solution to the problem can be represented by the following information: for each box, a list of the balls it contains (a ball is represented as a list of colors and a score).

Output of the algorithm: the solution with the highest score. The score of a solution is the sum of the scores of all balls in the boxes (of course, there may be many solutions, but in that case we just pick one of them).

# Current research

Somehow this problem makes me think of Sudoku, which is an instance of the exact cover problem. However, I haven't been able to come up with a way to model this problem in terms of exact cover and am afraid I may be missing a more straightforward approach.

As suggested in the answers, another possibility would be to model this using max-flow. However, this approach is unable to generate all possible solutions such that each box is filled to its capacity. Furthermore, the max flow value is known to be the sum of the capacities of the boxes (it is assumed the number of balls is large enough for this to happen).

# Questions

Is this an instance of the exact cover problem? If yes, how would you model it in terms of exact cover? If no, is it an instance of any other well-known problem?

# Answer
Isn't this a case of **max-flow**?

Model your problem as a bipartite graph, from ball to boxes, with an edge from each ball to the boxes with matching colour. Each of these edges has capacity 1. Now add source and target vertices. From source to each ball with capacity 1. From each box to target, capacity is the capacity of the box.

Now you want to enumerate all solutions to this max-flow problem (i.e., output all flows whose value achieves the maximum possible). But that might be a lot of solutions!

(edit) A recent update has added scores to the balls, and the target is to maximize the scores of the balls that are put into the boxes. I would suggest **maximal bipartite matching** where you have as many copies of nodes for each box as the capacity of that box. As there will be balls that do not fit into the boxes I would suggest adding boxes for overflow balls (to obtain complete matching, when necessary). Wikipedia suggests the Hungarian algorithm.
> 6 votes

# Answer
This is an instance of the assignment problem, i.e., finding the maximum-weight matching in a weighted bipartite graph.

On the left side of the bipartite graph, each vertex represents a ball. On the right side, a box labelled with the number $k$ corresponds to $k$ different vertices. You have an edge between a ball and a box if the box's color is one of the colors on the ball. The weight of that edge is equal to the score of the ball.

Now the optimal solution to your problem will be the maximum-weight matching for this bipartite graph, i.e., the solution to the corresponding assignment problem. There are polynomial-time algorithms for the assignment problem.
> 3 votes

---
Tags: complexity-theory, optimization, np-complete
---


# Question
Title: Can we write a program that can say if any 2 given programs do the same w.r.t input - output pairs
I'm new to theoretical CS research. I have the following question: Given 2 different computer programs, each generating certain outputs for a given set of inputs. Assuming we are given the range of values for input variables (i.e., min to max values), is it possible to check with another program whether these 2 programs will give the same output values for all possible input values, without actually running the 2 programs for all input values?

Thanks.

# Answer
No. That's undecidable. Suppose the first program is

```
return 42

```

and the second program is

```
if (f(x) halts)
    return 0
else
    return 42

```

where `x` is the input.

Do these two programs yield the same output, for all possible inputs? That depends whether `f` always halts on all inputs. And that is exactly the halting problem, which we know is not decidable. It's easy to see that, as a consequence, this problem can't be decidable either (if it were, you could decide the halting problem).
> 1 votes

---
Tags: computability, undecidability
---


# Question
Title: Trouble seeing the contradiction in diagonalization proof
I've seen the proof on a pdf online, and I'm having trouble seeing the contradiction.
If $(\langle T\rangle,z)=w \in D$, so when we emulate $T(w)$ with $U$ (universal machine), it accepts within the time bound, so $M\_D(w)=1$ and also $T(w)=1$.
Aren't you supposed to define $D$ as above, but accept only $x=(\langle M\rangle,z)$ where $M$ rejects $x$ within the time bound?

# Answer
> 2 votes
There is no contradiction, and the proof does not hold water. You are right: 'accepts' should be changed to 'rejects', and $D$ should be defined as

$$D=\\{\langle M, x\rangle \quad | \quad M \underline{\underline{\text{ rejects }}}\langle M, x \rangle \text{ within }n\log(n) \text{ steps} \\} $$

with $n=|\langle M, x\rangle|$, the length of the input. This way, the proof goes according to plan:

Proof. Suppose a $an+b$-time machine $T$ solves $D$. Take a sufficiently long $x$. Does $T$ accept input $\langle T, x\rangle$?

Suppose yes. Then $T$ accepts its input $\langle T,x\rangle$ within $an+b$, so $T$ accepts within $n\log(n)$. That's a contradiction, because by definition of $D$, $\langle T,x\rangle \in D \implies T \text{ rejects } x$.

Suppose no. Then $T$ rejects its input $\langle T, x\rangle$ within $n\log(n)$ steps, so $\langle T, x\rangle$ should be an element of $D$, so $T$ should have accepted. Contradiction $\square$

---
Tags: complexity-theory
---


title: Counting specific subgraphs

text:
# Question
Title: Counting specific subgraphs
For a given undirected graph **G**, I want to count all the subgraphs **H** that satisfies the following conditions:

* **H.V** = **G.V** (The subgraph will containt all the original graph nodes)
* **H** is connected

(Note: I don't care if two subgraphs are isomorphic)

The graphs which I will be working with will have **|G.V| \<= 15**

# Answer
Your problem is known as counting the number of connected spanning subgraphs, and is pretty hard even for restricted classes of graphs. See this question on cstheory.

The number of connected spanning subgraphs of a graph $G$ equals $T\_G(1,2)$, where $T\_G$ is the Tutte polynomial of $G$ (this is mentioned in one of the answers to the linked question). Hence this paper of Björklund et al., which shows how to compute said polynomial in vertex-exponential time (i.e., $\exp O(n)$), gives us hope, since in your case $n$ is pretty small ($n \leq 15$).
> 4 votes

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


# Question
Title: Choosing a non-cryptographic hash function for language with no unsigned integers
I'm implementing a hash table in pure UnrealScript, which only has support for signed 32-bit integers. This means no 64-bit integers and no unsigned integers. I was in the middle of implementing an FNV hash function, but ran into a potential problem.

> The offset\_basis for FNV-1 is dependent on n, the size of the hash: 32 bit offset\_basis = 2166136261

Well, `2166136261` converts to `-2128831035` when the bits are turned into an signed integer representation. My question is whether or not this will negatively affect the hash distribution and result in more collisions.

For quick reference, here is the psuedo-code for the FNV hash:

```
hash = offset_basis
for each octet_of_data to be hashed
    hash = hash * FNV_prime
    hash = hash xor octet_of_data
return hash

```

Thank you for your time.

# Answer
> 2 votes
The offset is unlikely to matter. As the FNV web page says:

> almost any offset\_basis will serve so long as it is non-zero

The multiplication is potentially more important. The FNV-1 hash is defined to use unsigned multiplication modulo $2^{32}$, but if UnrealScript only has signed 32-bit integers, presumably you have no way to do that kind of unsigned multiplication. At that point you're no longer using the official FNV-1 hash; you're using something different. I suspect it's still fine, though.

---
Tags: hash
---


# Question
Title: Sipser exercise : variant of CNF is NL-complete
I'm stuck rather badly on a Sipser exercise, 8.21 in my edition:

> **8.21** Let $CNF\_{H1}$ = {\<$\phi$\> | $\phi$ is a satisfiable cnf-formula where each clause contains any number of positive literals and at most one negated literal. Furthermore, each negated literal has at most one occurrence in $\phi$}. Show that $CNF\_{H1}$ is $NL$-complete.

My problem is, if we remove the second condition (each negated literal occurs at most once), the language becomes $P$-complete, so we must use that second condition to get anywhere, but I have no idea whatsoever how to do that? I can't even prove that the language is in $NL$.

To deal with a clause $\lnot x\_1 \lor x\_2 \lor ... \lor x\_n$, all of my efficient algorithms convert it to the equivalent $\lnot x\_2 \land ... \lnot x\_n \Rightarrow \lnot x\_1$, and use that form to deduce in some cases that $x\_1$ must be false. With such an approach, however, the second condition can't possibly help. If the negated $\lnot x\_1$ appears twice, it simply means that we have more opportunities to deduce that $x\_1$ is false, which can't hurt the algorithm?

# Answer
> 2 votes
Let's assume for simplicity that each negated literal appears exactly once. Let $C\_i$ be the clause containing $\lnot x\_i$. Consider the graph whose vertices are the variables, and $x\_i$ is connected to $x\_j$ if $x\_j \in C\_i$. This is a kind of implication graph: in order to deduce that $x\_i$ is false from $C\_i$, we must have first deduced that $x\_j$ was false from $C\_j$.

Show that $x\_i$ is forced to be false (i.e., unit propagation shows that $x\_i$ has to be false) iff the set of vertices reachable from $x\_i$ contains no directed cycle, something which can be checked in NL (using coNL=NL). The formula is unsatisfiable iff there exists a positive clause in which all variables are forced to be false (and so unit propagation gets stuck at this clause).

This shows that your problem is in NL. To show that it is NL-complete, reduce from directed reachability. Encode all edges incoming to $x\_i$ by a clause of the form $\lnot x\_i \lor \cdots$.

---
Tags: complexity-theory
---


# Question
Title: Clock solitaire game and principle of deferred decision
I have been reading the randomized algorithm book by Rajeev Motwani and Prabhakar Raghavan. In section 3.5 they have introduced principle of deferred decision which is a different probability space. The example they provided is a clock solitaire game. The game is as follows. Initially 52 cards are randomly grouped into 4 cards of 13 piles. The piles are labeled $1,2,3,...,10,Q,J,K,A$. The game starts by drawing a card from $K$ labeled pile. The next draw will be taken place from the pile with the face value of the drawn card. For an example suppose the drawn card is 7, then we go to the pile labeled $7$ and pick a card from this pile. We continue in this fashion. The game ends when we reach an empty pile. And one wins if all the piles are empty when the game ends. It is easy to show that the last card drawn must have face value $K$.

Now, to analyze the probability of winning, the author assumes a different probability space named "Principle of deferred decision". The idea is to "let the random choices unfold with the progress of the game, rather than fix the entire set of choices in advance." With this, they conclude that the probability of winning i.e., the probability that 52nd card being $K$ is 1/13. Can anyone explain why this is 1/13?

# Answer
> 2 votes
You can show that as long as the game goes on, the next card being picked is a random card chosen uniformly among the cards not already picked. We can imagine the same process continuing even if the game does stop. From that point of view, what we have is a completely random order of the deck; the game stops once the fourth king is reached; we win if the fourth king is the last card. Now the probability that the fourth king is the last card is the same as the probability that the last card is a king, which is 1/13.

---
Tags: probability-theory, randomized-algorithms, probabilistic-algorithms
---


title: Zero-knowledge proof: Abstract example

text:
# Question
Title: Zero-knowledge proof: Abstract example
So I was reading about ZKP on wikipedia, the abstract example in summary goes like this:

> Peggy wants to prove to Victor that she knows the secret to a door inside a cave that connect A and B together (see diagram) without revealing the secret word to Victor.
>
> * Peggy takes a random entry not know to Victor
> * Victor shouts to Peggy to come out of path A or B (randomly choosen)
> * and so it follows that she must know the secret word in order to come out of the path that Victor chooses without revealing to Victor the secret word. Victor builds confidences the more times this is done.

However, why is Victor not allowed to see which path Peggy chooses to enter from? As this does not reveal any extra information about what the secret word is.

Why can't Victor see which way she enters and asks her to demonstrate the 4 possibilities, that is:

* Enter from A and exit from A
* Enter from A and exit from B
* Enter from B and exit from A
* Enter from B and exit from B

# Answer
> 7 votes
I believe this is done to illustrate two things.

**(i)** The small probability, that $P$eggy ($P$rover) might be lying. If she really does not know the magic word and $V$ictor ($V$erifier) sees her taking Path $A$, he would always ask her to come back via path $B$, thus the probability of $P$ succeeding when cheating is $0$.

However, $ZKP$s usually involve a small chance of $P$ succeeding while cheating, which is illustrated by $V$ not seeing the path $P$ takes to get to the magic door.

**(ii)** $V$ does not learn the secret. If $V$ stands at the crossroad of the paths $A$ and $B$, while $P$ walks to the magic door to say her magic word, it might be conceivable for $V$ to be able to hear $P$ saying her secret word. The only way to make sure that $V$ does not learn the magic word, is for him to wait outside of the cave, until $P$ has chosen a path.

# Answer
> 3 votes
The article tries to illustrate the property that a zero knowledge proof is only convincing to the observer. In other words, the observer would not be able to convince someone else later.

It does so by considering the presence of a coin and a video camera:

> Further notice that if Victor chooses his A's and B's by flipping a coin on-camera, this protocol loses its zero-knowledge property; the on-camera coin flip would probably be convincing to any person watching the recording later.

Just like this coin flip, recording Peggy entering side A and leaving through side B would be convincing to any third party aware of the magic door's presence. This would deem it a deterministic proof, rather than a probabilistic proof. This further illustrates Riyil's second point: there is a nonzero probability $P$ such that the prover cheated.

---
Tags: algorithms, cryptography, security, authentication
---


# Question
Title: How much data could I store on a Rubik's Cube?
Google tells me that a standard 3x3x3 Rubik's Cube has 43,252,003,274,489,856,000 permutations. If I wanted to store data on that Rubik's Cube, how much could I store?

The only way I see to store data on a Rubik's Cube is to assign an integer to each permutation, then convert that integer into binary. It would take 66 bits to store an integer of that size, so the Cube could theoretically hold 65 bits of information by my calculations.

Is there any way to eke out more than 65 bits of storage from a Rubik's Cube?

# Answer
> 5 votes
If you consider the cube as living in a physical space, then you can get an extra factor of 24 from its orientation: assume it's sitting on a table and note the uppermost face (six options) and the face that's facing north (four more options). That gives you $\lfloor \log\_2 (24\times 43\ 252\\,...)\rfloor = 69\\,\text{bits}$, and you could get even more by considering more fine-grained notions of orientation, at the risk of losing information by somebody jostling the cube.

---
Tags: combinatorics, information-theory
---


# Question
Title: Relating memory complexity and decidablity
Given a language $L\_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L\_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a constant and $p(n)$ a polynomial, can we decide whether $L\_u \in R$ or not?

Memory complexity represents the largest difference of indices of used slots of the tape. So I believe $L\_u \in EXPSPACE$, although here it is defined using a constant, whereas most articles use a 2 to the power of some polynomial. This is why I'm not sure about that fact.

Basically, what I'm asking is:

Is $L\_u \in EXPSPACE$?

If it is, can this fact be used to derive whether $L\_u \in R$, and how?

If not, how can the fact that $L\_u \in RE$ and that the turing machine has a memory complexity of $c^{p(n)}$ be used to determine whether $L\_u \in R$, and how?

# Answer
Any language accepted by a non-deterministic Turing machine is decidable, since non-deterministic Turing machines can be simulated by deterministic Turing machines. See for example the Wikipedia article.

There is some subtlety you might be worried about: the non-deterministic Turing machine might always halt (on a given input), but its running time could be unbounded, and then the trivial simulation which just tries all possible guesses wouldn't halt. Fortunately, König's infinity lemma shows that if the running time is unbounded, then there is some infinite computation, so the running time must be bounded.
> 1 votes

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


# Question
Title: Evaluation functions of Minimax algorithm
Let's say we have the following relationship between $f\_1$ and $f\_2$:

$$f\_2(s) = \sqrt{1 + f\_1(s)}$$

And $f\_1$ returns a positive value. Why is it that minimax search using $f\_2$ is guaranteed to the same action as using $f\_1$ but is not guaranteed to return the same action as $f\_1$ when used in expectimax search?

I understand that expectimax takes into account the weight of the arcs to compute the possible path. But I am still not able to understand how the aforementioned conclusion is being made.

# Answer
An example for Expectimax (root node is a Max node):

<sub>*(image from CSE AI Faculty / Dan Klein, Stuart Russell, Andrew Moore)*</sub>

changing the evaluation function changes the action taken.

For Minimax, since $f\_1(s\_i) \ge f\_1(s\_j) \implies f\_2(s\_i) \ge f\_2(s\_j)$, the best node (action taken) doesn't change (Minimax is insensitive to monotonic transformations):
> 3 votes

---
Tags: artificial-intelligence, game-theory
---


# Question
Title: Example Turing Machine for a time-constructible function
I am currently reading "Computation Complexity: A Modern Approach" by Arora and Barak and have a question about time-constructible functions. In particular, I can't construct a turing machine for a simple function $f(n)=n$ using the definitions in the book.

The authors start by introducing $k$-tape turing machines: $1$ read-only input tape and $k-1$ read/write work tapes with the last one being the output tape. The tapes are one-directional and they are initialized in the leftmost cell via a special start symbol $\triangleright$. The input tape also contains the input $x$ after the $\triangleright$ symbol, in binary notation. All remaining cells contain the blank symbol $\square$. The tape-heads start on the $\triangleright$ symbol.

> A TM $M$ computes a function $f$ in $T(n)$-time if for every $x$, after $M$ is initialized in start configuration on input $x$, using at most $T(|x|)$ steps, $M$ halts with $f(x)$ written on its output tape.

They then define time-constructible functions

> A function $T \colon \Bbb N \to \Bbb N$ is time-constructible if $T(n) \geq n$ and there is a TM $M$ that computes the function $x \mapsto \llcorner T(|x|)\lrcorner$ ($\llcorner T(|x|)\lrcorner$ denotes the binary representation of $T(|x|)$) in time $T(n)$.

I have a problem constructing TMs $M$ for the functions $F(n)=n$ and $G(n)=n^2$. Let's say $x = 3$, so $|x|=2$. The machine for $F$ will have to halt after $F(|x|)=|x|=2$ steps and output $\llcorner x \lrcorner$. How is this possible if the machine heads start on the $\triangleright$ symbols?

In $2$ steps, the machine can't even read the input, since the first step is wasted by moving right from the $\triangleright$ symbol.

Shouldn't the definition make use of asymptotic notation?

# Answer
> 1 votes
I think you're right, we should use asymptotic notation, for the reason you mention, but maybe somebody more knowledeable than me can weigh in if that's wrong. Here are my thoughts: A function $T$ works as a function of the number of bits on the tape, with $|x|=\lfloor\log(x)\rfloor$. Consider the function $T(n)=n$. This function maps $x\mapsto T(|x|) = T(\lfloor\log(x)\rfloor)=\lfloor\log(x)\rfloor$. This means is must count the number of bits on the tape, erase the input, and write the number, but it has only exactly enough time to read the input, and then it must halt. But since $\log(x)\<x$ for some $x$, this means the machine must, on most inputs, also move back on the tape, at least to the beginning. With a multitape Turing Machine, I can think of a $(3n+\log(n))$-time machine which computes $T(n)=n$, so I think it makes more sense to use asymptotic notation.

Note that in order to make a Turing Machine, if you have trouble when $n$ is small because $T$ doesn't grow fast enough for you, you can just hardcode the first billion values into your TM, and run an honest algorithm on the remaining numbers. This is how you overcome the problem of computing, for example, $n\cdot \log(\log(\sqrt{n}))$, which requires a lot of computation but grows very slowly.

A machine which computes $x\mapsto 2^{|x|}$: read the first $1$ on the tape, then replace all subsequent numbers by $0$ and add one $0$ to the end. And you did it in $n+1$ steps exactly! That is exponentially faster than the available time.

According to this question (link), there is an alternative source of Arora and Barak which does use asymptotic notation and one by Sipser, although it doesn't provide any explicit references. As far as I know, all other definitions (like $\text{TIME}(n)$ and $\text{SPACE}(n)$) are built around asymptotic notation anyway, so it should be perfectly legal to use asymptotic notation here.

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


# Question
Title: In which O-class does my Θ-result belong?
In a multiple-choice test, I'm asked to solve the recurrence $T(n)=2T(n/2)+n/2$. I've done this using the master theorem: $f(n)=n/2$, $a=2$, $b=2$, so we're in the second case and $T(n)=\Theta(n\log n)$.

But the possible answers are $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$ and $O(n^2/\log n)$ and more than one may be correct. What do I do now?

# Answer
You've solved the recurrence more precisely than the test-setter was expecting you to. You know that $T(n)=\Theta(n\log n)$, which means that $T(n) = O(n\log n)$ and $T(n) = \Omega(n\log n)$, and that gives you the answer.

(By the way, I didn't check that you solved the recurrence correctly, but you can do that yourself. Answer checking is off-topic here, and you didn't ask for it, so I focused on the rest of your question.)
> 2 votes

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


# Question
Title: How do nondeterministic Turing machines compute general function problems?
(Hope this hasn't been asked before, but I didn't find anything.)

In my understanding, nondeterminism applies to decision problems only, due to the requirement of the **existence of an accepting path**. In Wikipedia, the class $NP$-easy is defined to be solvable in deterministic poltime, with access to an oracle for a **decision problem** in NP. So this seems to back my assumption.

My question is: Is there an accepted way to define a non-deterministic Turing machine to compute a general function problem? (And is it always by a detour over an oracle for a decision problem?)

# Answer
One accepted definition is as follows: a function $f$ (whose output is at most polynomial in its input) is in the class $\mathsf{FNP}$ if given $x,y$ one can decide in polynomial time whether $f(x)=y$. Compare this to the class $\mathsf{FP}$, which contains those functions $f$ such that given $x$, the value of $f(x)$ can be computed in polynomial time.
> 7 votes

# Answer
First off, whenever you talk about nondeterminism you need to get rid of the idea of having an algorithm you execute to get a result. Nondeterministic models are descriptive only, not operational; there is no way to "execute" a nondeterministic algorithm. Sometimes, teachers say things like "the machine always guesses right" or "we execute all branches in parallel" but these intuition statements fall short in one way or the other.

So, accept that a nondeterministic machine *describes* some formal object. Period.

---

There are two ways to gain intuition about nondeterministic automata. From the lower end, consider finite-state transducers. They are essentially finite automata with output; obviously, FA reduce to them. In the non-deterministic case, each input can (but need not!) result in multiple outputs. Therefore, it makes sense to define the "result" of an FT $A$ on $w$ as the set of all outputs $A$ can produce on $w$. Now you can happily take the union over several input words, or consider preimages, and so on.

From the other end of the spectrum, consider NTM. The same idea works: for every input $w$, define as output the set of all tape contents you can have when the machine halts (in an accepting state) on $w$.

Note that nothing prevents you from requiring the automaton to have only one output per input, for instance when defining a complexity class.

It is similar for resource restrictions; the ideas used for defining decision problem classes should mostly carry over.
> 4 votes

---
Tags: turing-machines, computation-models, nondeterminism
---


# Question
Title: Can a RAM calculate its own Gödel number?
You can get the Gödel number of a RAM by making it a list of commands and making this list an integer.

So, what I thought is something like "The RAM that would return its own Gödel number (say, $x$) would have to have the information $x$ in it, so the integer would be greater than $x$, so it would not return its own Gödel number."

But then I noticed that for specific numbers you could do compressing, such as calculating $10^{9999}$ instead of writing 100000...000 in the code of the RAM. Probably the Gödel number would not be $10^{9999}$ though, but at least it *could* be.

**Question:** Is there a RAM that calculates its own Gödel number? Can there be such?

# Answer
> 17 votes
Consider the computable function $Q\colon \mathbb{N}\times\mathbb{N}\to\mathbb{N}$ given by $Q(x,y) = x$. By Kleene's second recursion theorem, there is some $p$ such that the program with Gödel number $p$ computes the function $f(y) = Q(p,y)=p$, i.e., a program which outputs $p$ for every input. This is exactly the program you're looking for: for any input, it outputs its own Gödel number.

Such a program is known as a quine, and they exist in any Turing-powerful model of computation.

---
Tags: computability
---


# Question
Title: Difference between cross edges and forward edges in a DFT
In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal).

There are some leftover edges connecting some of the other nodes. What is the difference between a cross edge and a forward edge?

From wikipedia:

> Based on this spanning tree, the edges of the original graph can be divided into three classes: forward edges, which point from a node of the tree to one of its descendants, back edges, which point from a node to one of its ancestors, and cross edges, which do neither. Sometimes tree edges, edges which belong to the spanning tree itself, are classified separately from forward edges. If the original graph is undirected then all of its edges are tree edges or back edges.

Doesn't an edge that is not used in the traversal that points from one node to another establish a parent-child relationship?

# Answer
> 30 votes
Wikipedia has the answer:

All types of edges appear in this picture. Trace out DFS on this graph (the nodes are explored in numerical order), and see where your intuition fails.

This will explain the diagram:-

Forward edge: (u, v), where v is a descendant of u, but not a tree edge.It is a non-tree edge that connects a vertex to a descendent in a DFS-tree.

Cross edge: any other edge. Can go between vertices in same depth-first tree or in different depth-first trees. (layman)
It is any other edge in graph G. It connects vertices in two different DFS-tree or two vertices in the same DFS-tree neither of which is the ancestor of the other.(formal)

# Answer
> 12 votes
A DFS traversal in an undirected graph will not leave a cross edge since all edges that are incident on a vertex are explored.

However, in a directed graph, you may come across an edge that leads to a vertex that has been discovered before such that that vertex is not an ancestor or descendent of the current vertex. Such an edge is called a cross edge.

# Answer
> 3 votes
In a DFS traversal, nodes are finished once all their children are finished. If you mark the discover and finish times for each node during traversal, then you can check to see if a node is a descendant by comparing start and end times. In fact any DFS traversal will partition its edges according to the following rule.

Let d\[node\] be the discover time of node, likewise let f\[node\] be the finish time.

> Parenthesis Theorem For all u, v, exactly one of the following holds:
> 1. d\[u\] \< f\[u\] \< d\[v\] \< f\[v\] or d\[v\] \< f\[v\] \< d\[u\] \< f\[u\] and neither of u and v is a descendant of the other.
>
> 2. d\[u\] \< d\[v\] \< f\[v\] \< f\[u\] and v is a descendant of u.
> 3. d\[v\] \< d\[u\] \< f\[u\] \< f\[v\] and u is a descendant of v.
>
> So, d\[u\] \< d\[v\] \< f\[u\] \< f\[v\] cannot happen.
> Like parentheses: ( ) \[\], ( \[ \] ), and \[ ( ) \] are OK but ( \[ ) \] and \[ ( \] ) are not OK.

For example, consider the graph with edges:
A --\> B
A --\> C
B --\> C

Let the order of visiting be represented by a string of the nodes labels, where "ABCCBA" means A --\> B --\> C (finished) B (finished) A (finished), similar to ((())).

So "ACCBBA" could be a model for "(()())".

Examples:
"CCABBA" : Then A --\> C is a cross edge, since the CC is not inside of A.
"ABCCBA" : Then A --\> C is a forward edge (indirect descendant).
"ACCBBA" : Then A --\> C is a tree edge (direct descendant).

Sources:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

---
Tags: algorithms, terminology, graphs, graph-traversal
---


# Question
Title: Automorphism of a Graph with a given Set of Permutations
Given a graph $H$. A set of permutations $\alpha$ which contains permutations of vertices of $H$.

The permutation set $\alpha$ has automorphisms of subgraph $H\_1, H\_2,..... H\_x$ where $x$ is the number of total subgraphs. These subgraphs are connected. These permutations can be extended to the automorphism of $H$. By extending, we mean that automorphism of subgraphs can be extended to the automorphism of graph $H$. This concept is similar to E. Luks' paper of graph siomorphism of bounded valence.

Each subgraph has constant number of vertices. The adjacency matrix of $H$ is -

$$H = \begin{bmatrix} H\_{(x)} & R\_{(x, x-1)} & R\_{(x,x-2)} & \dots & \dots & R\_{(x,1)} \\ R\_{(x,x-1)^{T}} & H\_{(x-1)} & R\_{(x-1,x-2)} & \dots & \dots & R\_{(x-1,1)} \\ \vdots & \vdots & \vdots & \ddots & \ddots & \vdots \\ R\_{(x,1)^{T}} & R\_{(x-1,1)^{T}} & R\_{(x-2,1)^{T}} & \dots & \dots &H\_{1} \end{bmatrix}$$

The adjacency matrix of graph $H\_k \cup H\_e$ is $M\_{(k,e)}$ where $M\_{(k,e)} =\left( \begin{array}{ccc} H\_e & R\_{k,e} \\ R\_{k,e}^{T} & H\_k\\ \end{array} \right) $, where, $R\_{k,e}$ is the non symmetric sub-matrix of adjacency matrix $H$. Here, $R\_{k,e}$ represents edges between $H\_k, H\_e$.

**Problem:** How to find an automorphism of $H$ in polynomial time (in $\alpha$)?

**Note:**

1. $\alpha$ is the generating set of autmorphsim group of $H$.

# Answer
If you only want an automorphism, then just consider the identity permutation. That's an automorphism -- the trivial automorphism.

If you want a non-trivial automorphism, then if I understand your problem statement, this is as hard as the graph automorphism problem. No polynomial-time algorithm is known for this problem. It's not known to be NP-complete (it's not even known to be GI-complete). Nonetheless, finding a polynomial-time algorithm for this problem is an open problem, so you shouldn't expect it to be easy to find a polynomial-time algorithm for your problem, either.

In practice you can use open-source tools like Nauty, BLISS, or SAUCY to find an automorphism; on most graphs they (empirically) are very fast.

---

Justification of claim that this is as hard as graph automorphism:

We can reduce graph automorphism to your problem. Let $G$ be an arbitrary undirected graph, with $n$ vertices. Construct an undirected graph $H$ with $2n$ vertices as follows: for each vertex $v$ of $G$, add another vertex $v'$, and add an edge $(v,v')$. Keep all the edges between unprimed vertices, but don't add any edges between primed vertices.

Note that the automorphisms of $G$ are in one-to-one correspondence with the automorphisms of $H$. If $\pi$ is an automorphism of $G$, it can be extended to an automorphism of $H$ simply by permuting the primed vertices in the same way as the unprimed vertices. If $\pi'$ is an automorphism of $H$, by projecting it to the vertex set of $G$ we obtain an automorphism of $G$.

Now define $H\_1,\dots,H\_n$ as follows: each $H\_i$ is the subgraph induced by the two vertices $v\_i,v'\_i$. In other words, $H\_i$ has vertex set $\\{v\_i,v'\_i\\}$ and has a single edge $(v\_i,v'\_i)$. Thus, $H\_i$ has a non-trivial automorphism that swaps $v\_i$ and $v'\_i$, and this corresponds to a permutation $\pi\_i$ of $H$ (one that leaves all other vertices of $H$ fixed). Define $\alpha$ to be this set of permutations.

Now if you can find a non-trivial automorphism of $H$, you can immediately obtain a non-trivial automorphism of $G$ (i.e., you've found a way to solve the graph automorphism problem on an arbitrary graph $G$). If $H$ has no non-trivial automorphism, neither does $G$. This completes the reduction.
> 2 votes

---
Tags: algorithms, graphs, graph-isomorphism
---


# Question
Title: Does a polynomial solution for an NP-complete problem that can only be implemented for small N *still* imply P=NP?
Basic sanity check on NP-complete solutions:

Suppose there was a polynomial time solution for an NP-complete problem, but the size of NP-complete problems that could be solved is still relatively small (i.e. N = 32-64) due to limits in technology.

Would this show that P = NP? Or would this be more like the pseudo-solution that the unary subset sum is in P?

# Answer
> 29 votes
If you mean that the polynomial-time algorithm only works for inputs up to some fixed size, it shows nothing at all. Any problem at all (even if it's undecidable, let alone **NP**-complete) becomes a finite language when restricted to instances of constant size. All finite languages can be decided in constant time.

If you mean that the polynomial-time algorithm works for all inputs but it's still so inefficient that current computers can only run it on small instances then, sure, that would prove that **P$\\,=\\,$NP**. The idea that "polynomial" means "efficiently and effectively solvable" is just a short-hand. The actual definitions of **P** and **NP** don't depend on that short-hand.

# Answer
> 8 votes
Time complexity "for small inputs" simply doesn't make sense, because the *definition* of time complexity is based on the limit of the running time as the input size grows to infinity.

# Answer
> 4 votes
I present one possible interpretation of your question such that the answer is "YES."

Suppose that you could solve the satisfiability problem in polynomial time, but the leading term of the polynomial had a large exponent, e.g. $n^{20}$. Then it would be, indeed, the case that the solution is not practical, i.e., you can only solve the satisfiability problem on small instances using this hypothetical algorithm. Nonetheless, NP would still collapse to P. Sometimes, this exact reasoning is used to point out that the definition of P does not quite capture the notion of "practical algorithms," to which the response is that algorithms that we come up with tend to have small exponents of leading terms.

---
Tags: complexity-theory, np-complete, p-vs-np
---


# Question
Title: Is this classic puzzle book game NP-complete?
There is a classic puzzle book game very similar to a crossword puzzle, except a list of words is given and then a $N \times N$ square board made up of unit squares is given, with some squares blacked out just like a cross-word, and some squares have a letter already pre-written in them. The goal is to write each word from the list once and only once in the puzzle, where each word is written either horizontally (left to right) or vertically (top down) into non-blacked out consecutive squares, and when you write a word, the two squares flanking the ends of the word must either be blacked out or off the board. Also for the letters pre-written into some squares, the words written that overlap these squares must respect the pre-written letter.

Now, if we assume a fixed size alphabet for the words, is deciding whether we can fill the board with a valid solution using exactly each word on the list once and only once an NP-complete problem, if the side length of the board is not fixed?

# Answer
> 6 votes
Sorry for answering an old post.

I´ve been thinking about it and i think that the problem with a fixed alphabet is NP-complete as well.

I´m going to reduce positive 1-in-3 SAT to this word problem

Yesterday i was having trouble coming with ideas for solving the problem. I had trouble making each variable different until i looked again at the question and i realized that you allowed having squares with planted symbols. This simplified the reduction a lot. My other idea was to have words of different length for each different variable.

**THE REDUCTION**

Now i´m going to describe the gadgets we are gonna use:

**Variable gadget**

We label each variable with a different numerical index and we will have a different number for each variable. We pick the biggest index and we represent the number in binary, we will call this binary chain $n$.

Then we create two different vertical words for each variable. All words will have a length of $3 + |n|$ (Only if we allow duplicate words in the list of words), where $|n|$ is the length of the binary chain $n$.

For instance, let the biggest index be the number $4$. When we transform this number in binary we obtain the chain $100$ in binary, this chain has a length of three. So each variable word will have a length of $6$ in this example.

Now we create two different words for each variable. One word will have the symbol $3$ at the beginning, then the symbol $2$ below, then a binary chain that represents the index of the variable and we pad with zeroes the chain so that it has the same length that chain $n$ and finally the symbol $3$ at the end. Of course the symbols can be changed.

The other word is almost the same but it will have the symbol $4$ instead of the symbol $3$.

For instance, let the biggest index be the number $4$. We will have the following two words for the variable with index $1$:

$320013$ and $420014$

As we see we have padded the binary reperesentation of the number $1$ with zeroes so that it has a length of $|n|$

We have to copy these words many times, we will need one copy of each word for each occurence of a variable in the SAT instance. This will create duplicates in the list of words. We can get rid of the duplicates by adding another binary chain to the binary chain that uniquely identifies the variable. This new chain will uniquely identify each ocurrence of a variable.

To do that, we simply assign each ocurrence of the variable another binary chain and we olace that chain at the end of the binary representation of the variable.

To create this new binary chain first we have to create a different index for each variable, we call the biggest number in each index $n\_i$ where $i$ is an identifier for each variable. After that, we transform the number $n\_i$ into a binary chain and then we count the length of the chain, we call this number $|n\_i|$. Then, for each index, we create a different binary number for each ocurrence of the variable. We pad the number with zeroes until the length of the binary chain becomes $|n\_i|$ so that all the words that belong to each ocurrence of the variable have the same length.

This will get rid of duplicates inside the variable words.

For instance, suppose that variable $x\_2$ appears three times in the SAT instance. We create the following words:

$32010013$ $42010014$, $32010103$ $42010104$ and $32010113$ $42010114$

**Clause gadget**

For each clause gadget, we will create three new horizontal words, each clause word will have a length of $6$ squares (Only if we allow duplicate words in the list of words). These are the words that we will create for each clause:

$535354$, $535453$ and $545353$

We have a different clause word for each possible way of satisfyng the clause, the symbol $4$ represents a literal set to true and the symbol $3$ represents a literal set to false. The number $5$ is used to indicate that it is a clause word.

There will be repeated words in the list of words, we can get rid of the repetitions by using the procedure that we used to uniquely identify the variable words. That is, we create a different binary chain for each clause and we append each chain to the clause words corresopnding to each clause. To do that we create a new index for the clauses and we pick the biggest number of the index, we will call this number $m$. We represent $m$ as a binary chain and we call the length of this binary chain as $|m|$. Now, we create a different binary number for each clause, starting with the number 1, and we pad the number with zeroes to make a binary chain that has a length of $|m|$. We append each binary chain to the clause words that belong to the clause.

Now, let´s see a picture of a clause gadget in the board:

This example represents the clause $(x\_2 \lor x\_3 \lor x\_4)$ and the 1 in 3 instance being reduced is $(x\_1 \lor x\_2 \lor x\_3) \land (x\_2 \lor x\_3 \lor x\_4) $

As we see, there are written squares. The vertical columns have written symbols to indicate which literals are inside the clause. The end and the beginning of the column are blank squares. This lets the player choose the value of the variable. The marked symbols in the horizontal row force the player to put a clause word in that row. Because all clause words have only a single symbol $4$ that means that only one of the literals that is inside the clause gadget can be set to "true".

If we don´t allow duplicates inside the list of words we will have to modify the image.

The clause row in the image will become: $5b5b5b10$ and the literal columns will be, from left to right:

$b201010b$, $b201110b$ and $b21001b$

Where the symbol $b$ means blank square

See an example:

**Variable consistency gadget**

This is a gadget that ensures that the player can only asign the same value for all literal columns of a variable.

We will have a new gadget for each variable

We will create two new words for each gadget.

The length of the word will depend on the number of ocurrences of a variable. The length of a word will be $2 * k$ where $k$ is the number of ocurrences of a variable. So if variable $x\_2$ appears two times in the sat instance, the words will have a length of four. One of the two words is formed by repeating the chain $63$ $k$ times, where k is the number of occurrences of the variable. The other word is formed by repeating the chain $64$ $k$ times, where k is the number of occurrences of the variable in the SAT instance being reduced.

For instance if a variable $x\_2$ has two ocurrences, the words that belong to the corresponding variable assignment gadget will be:

$6363$ and $6464$

If we want to avoid repeated words, notice that each consistency gadget belongs to a different variable. So we can append the binary chain that identifies each variable to the two words that we created for this gadget.

Now let´s see an example picture of this gadget:

This gadget is for the variable $x\_2$ and the 1 in 3 instance being reduced is $(x\_1 \lor x\_2 \lor x\_3) \land (x\_2 \lor x\_3 \lor x\_4) $.

As we see, there are two horizontal rows, the symbols written inside the rows make sure that we can only place words containing those symbols, those words are the words that we created for this gadget. In one of the rows, we see that there are two columns coming into it, because of the symbols that are placed in the columns we make sure we can only place variable words. Because the only words we can only place on the variable consistency row have only the symbol $3$ or only the symbol $4$ in them, we force the player to place all variable words with that symbol inside the gadget. This means that the only variable words that are available to be placed inside the clause gadgets have only the symbol $3$ or only the symbol $4$. We can place the remaining word of this gagdet in the other row

If we don´t allow duplicates in the list of words, the words inside the example picture will be:

For the rows:

$6b6b010$ and $6b6b010$

For the columns:

$b201001b$ and $b201010b$

Where the symbol $b$ means blank square

See an example:

**Clause dump gadget**

This is a gadget created to place the unused clause words. To do that, we have only to place two rows for each clause word in an empty part of the board. These rows are not connected to any other row or column.

With this we finish the reduction, as we claimed we only need 6 symbols for the reduction.

**Example**

If the previous explanation was confusing, here is an example picture of an instance of positive 1 in 3 SAT that has been reduced to this word problem:

If we disallow repeated words:

The instance that has been reduced is:

$(x\_1 \lor x\_2 \lor x\_3) \land (x\_2 \lor x\_3 \lor x\_4) $

# Answer
> 4 votes
I think the following reduction from Directed Hamiltonian path works:

Given a graph $G=(V,E)$ and a two vertices $s,t\in V$, we output the following puzzle:

The alphabet is $V\cup \\{\*\\}$, with $\*$ being some symbol not in $V$.

The words are $v\*v$ for every $v\in V$, and $vu$ for every edge $(u,v)\in E$.

The board consists of two parts. The first looks like $|V|$ horizontal "stairs" of length 3, stacked on top of each other, as depicted here:

The second part consists of $|E|-(|V|-1)$ disjoint spaces of length 2.

Also, we set in the first (bottom) step of the stairs the word $s\*s$ (and remove it from the word list), and in the last step we put $t\*t$.

Now, in order to fill the stairs, only vertex-words can be put within the steps, and in order to connect two vertices, an edge word must be put between them, which corresponds to an existing edge in the graph. The unused edges can be put in the second part of the board. The second direction is trivial.

I think this works (the correctness proof I sketched is hand-waved at best, but still).

---
Tags: complexity-theory, np-complete, board-games
---


# Question
Title: Languages reducible to and from context-free
Let $L'$ be a context-free language. If $L \leq\_M L' \leq\_M L''$, where $\leq\_M$ denotes mapping reducibility (aka many-one reducibility), what can we know about $L$ and $L''$?

I think they're both decidable languages but that's all I can say.

# Answer
From $L \leq\_M L' \leq\_M L''$, we can only conclude that $L$ is decidable. It is because $L'$ is a context free language and hence decidable (If you need a proof, you can take a look at this Are all context-free and regular languages efficiently decidable?) . So, we can convert $L$ to $L'$ and then decide $L$.

But we can not do the same for $L''$. Because it might be possible to reduce $L'$ to $L''$ but after reduction we can not say that it can be decided in that reduced form.
> 1 votes

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