# Question
Title: Shunting Yard Algorithm extension and AST generation
Let me introduce you to my current project (that obviously yields the problem I face hence I post here). I am writing a so-called "compiler" for a simplistic language. I have already built a VM to run the produced bytecode, the associated Lexer (all this project is an optional assignment). My problem lies in the Expression parsing bit. I use the Shunting Yard Algorithm by Dijkstra to convert my postfix expressions into the corresponding AST structure, and I am incapable of adjusting the algorithm correctly to generate the correct AST if -and only if- I try to implement function calls and array subscript.

Here a sample of the algorithm implementation (everything is pretty self-explanatory I believe)

```
func (p *parser) shuntingyard(input token.TQueue) *ast.Node {
    var operands ast.NStack
    var operators *token.TStack

    operands = make(ast.NStack, 0)
    operators = token.TokenStack()

    for tok := input.Dequeue(); tok.Sym != "EOF"; tok = input.Dequeue() {
        switch tok.Kind {
        case "LParen":
            operators.Push(tok)
        case "RParen":
            for {
                // pop item ("(" or operator) from stack
                if operators.Empty() {
                    p.errorf("Unmatched parenthesis on line %d, expected '(' to match closing parenthesis in expression", p.lno)
                }

                op := operators.Pop()
                if op.Sym == "(" {
                    break // discard "("
                }

                if isUnary(op.Sym) {
                    node := ast.MakeNode(*op)
                    node.AddChild(operands.Pop())
                    operands.Push(node)
                    break
                }

                RHS := operands.Pop()
                LHS := operands.Pop()
                operands.Push(ast.MakeParentNode(*op, RHS, LHS))
            }
        default:
            if o1, isOp := prOps[tok.Sym]; isOp {
                // token is an operator
                for !operators.Empty() {
                    // consider top item on stack
                    op := operators.PeekTop()
                    if o2, isOp := prOps[op.Sym]; !isOp || o1.prec > o2.prec || o1.prec == o2.prec && o1.rAssoc {
                        break
                    }

                    // top item is an operator that needs to come off
                    op = operators.Pop()
                    if isUnary(op.Sym) {
                        node := ast.MakeNode(*op)
                        node.AddChild(operands.Pop())
                        operands.Push(node)
                        break
                    }
                    RHS := operands.Pop()
                    LHS := operands.Pop()
                    operands.Push(ast.MakeParentNode(*op, RHS, LHS))
                }
                // push operator (the new one) to stack
                operators.Push(tok)
            } else {
                operands.Push(ast.MakeNode(*tok))
            }
        }
    }

    // drain stack to result
    for !operators.Empty() {
        if operators.PeekTop().Sym == "(" {
            p.errorf("Unmatched parenthesis on line %d, expected ')' to match previous parenthesis in expression", p.lno)
        }

        RHS := operands.Pop()
        LHS := operands.Pop()
        operands.Push(ast.MakeParentNode(*operators.Pop(), RHS, LHS))
    }

    result := operands.Pop()
    for !operands.Empty() {
        result.AddSibling(operands.Pop())
    }

    return result
}

```

The idea is pretty straightforward when you encounter a binary operator from the operator stack, you pop off of the operand stack two nodes that you set as children of the operator encountered (or one if the operator is unary). And you push the resulting node on the operands stack.

For instance, this input:

```
c = 0;
a = 1 << 3 + 2;

```

results in the (valid) AST:

```
┣━ Assign           =
┃   ┣━ Identifier       'a'
┃   ┗━ Lshift           <<
┃       ┣━ Number           1
┃       ┗━ Plus             +
┃           ┣━ Number           3
┃           ┗━ Number           2
┗━ Assign           =
    ┣━ Identifier       'c'
    ┗━ Number           0

```

However, the output is being wrong whenever I try to nest function calls:

```
 foo(bar(0))

```

the result is (obviously) not correct:

```
┣━ Number           0
┣━ Function         bar
┗━ Function         foo

```

when I should have had:

```
┗━ Function         foo
    ┗━ Function         bar
        ┗━ Number        0

```

My first question is: **What modification do I have to bring to my implementation to support AST generation for function calls ?** Since all I have found on the Internet regarding the SY Algorithm is always generating an RPN string ...

Another thing is that an input such as:

```
-i++;

```

generates the valid output:

```
┗━ UnaryMinus       -u
    ┗━ PlusPlus         ++
        ┗━ Identifier       'i'

```

but `(-i++);` reports and unbalanced parenthesised expression ?

The `map` used to work with operators is:

```
var prOps = map[string]struct {
    prec   int
    rAssoc bool
}{
    "++" : {50, false}, "--" : {50, false},

    "."  : {40, false}, "["  : {40, false},

    "!"  : {30, true}, "~"   : {30, true},
    "-u" : {29, true}, "--u" : {29, true}, "++u": {29, true},
    "**" : {28, true},

    "*"  : {27, false}, "/"  : {27, false}, "%" : {27, false},
    "+"  : {26, false}, "-"  : {26, false},
    ">>" : {25, false}, "<<" : {25, false},
    ">"  : {24, false}, ">=" : {24, false}, "<" : {24, false}, "<=" : {24, false},
    "==" : {23, false}, "!=" : {23, false},
    "&"  : {22, false},
    "^"  : {21, false},
    "|"  : {20, false},
    "&&" : {19, false},
    "||" : {18, false},

    "="  : {10, true}, "+="  : {10, true}, "-=" : {10, true}, "*="  : {10, true},
    "/=" : {10, true}, "**=" : {10, true}, "^=" : {10, true}, "~="  : {10, true},
    "|=" : {10, true}, "&="  : {10, true}, "%=" : {10, true}, "<<=" : {10, true},
    ">>=": {10, true},
    ","  : {9, false},
}

```

Where `-u`, `++u`, `--u` are the instances of the meant operator, but unarily.

On the other note, is the Shunting Yard Algorithm what I **truly** need ? I mean, if parsing an object-oriented expression with this algorithm is feasable, is that my best choice ?

I also read (a lot) on parsers in a larger sense. I believe, from what I read, that writing a Recursive Descent parser is my best chance to achieve my goal within reasonable amount of time. I read some source codes, but parsers tend not to be reader-friendly. **What is a guideline I should keep for this project regarding the parser and AST generation ?**

Please tell me if I did anything wrong with this thread :) And do ask if I missed to link/give any ressources needed !

In the hope of having some helpful answers.

# Answer
> 2 votes
I would recommend using a hybrid recursive descent parser that uses your existing shunting yard to parse expressions. For the examples you have shown, very little would change, but you would add a function to parse an atom that could be a number, an identifier, or a function call.

Something like this:

```
def parse_atom():
  tok = next_token()
  if tok is number:
    return AST.Number(value = tok.value)
  if tok is symbol:
    if peek_token() is '(': # look ahead at the next token but leave it on the stream
      <parse arguments here by calling shunting_yard>
      return AST.FunCall(function = tok.value, arguments)
    else: # variable
      return AST.Variable(name = tok.value)

```

Using a pure recursive descent parser to parse infix expressions is a pain, but mixing in something like shunting yard or precedence climbing works very well.

I have used a similar method to this (with precedence climbing instead of shunting yard) in several projects and had a good time with it. See, for example here and here.

I'd be happy to answer any questions you may have.

Some resources:

---
Tags: algorithms, algorithm-analysis, compilers, parsers
---


title: Expressing 3-SAT in first-order logic

text:
# Question
Title: Expressing 3-SAT in first-order logic
i read that First-Order Logic is strong enough to formalise all of Set Theory and thereby virtually all of Mathematics. How would you express in First-Order Logic the theorem: 3SAT is NP-complete?

# Answer
> 6 votes
There has been a lot of work on formalizing mathematics, and in all of this work one needs to express definitions, theorems and proofs within the logic that one is using for formalization.

This is always quite involved.

To describe the statement that 3SAT is NP-complete, we will need a version of first-order logic with a term language that will allow us to express notions of languages, time complexity, Turing machines, polynomial-time reducibility, propositional logic and conjunctive normal forms.

Once we have an appropriate term language, we will need to describe 3SAT and NP-completeness in it. This requires us to be able to express the definitions of these notions, and this in turn involves the definition of first-order predicates that correspond to these notions and the notions that were used to define them.

Let us take a brief look at a part of this construction - this should convince you that this is indeed fairly involved. A language $L$ is NP-complete if

1. $L \in \mathrm{NP}$
2. For every $L' \in \mathrm{NP}$ we have that $L'$ polynomial-time reduces to $L$

We define a predicate $NPC(x)$ which holds if the following conjunction holds for $x$

1. $x$ is a language in $\mathrm{NP}$
2. for every $y$, if $y$ is a language in $\mathrm{NP}$, then $y$ polynomial-time reduces to $x$

We therefore need a predicate $NP(x)$ that captures that $x$ is a language in $\mathrm{NP}$, and we need a predicate $PTR(x,y)$ that captures that $y$ polynomial-time reduces to $x$. If we have these, then we can define

$$ NPC(x) = NP(x) \wedge \forall y. NP(y) \Rightarrow PTR(x,y) $$

The definition $NP(x)$ must capture the following

1. $x$ is a language.
2. There exists a nondeterministic Turing machine $M$ with polynomial-time complexity such that for all $w$, $M$ will accept $w$ if and only if $w$ is an element of $x$.

And this in turn requires us to define predicates $L(x)$, which must describe that $x$ is a language, $TM(y)$ which must describe that $y$ is a nondeterministic Turing machine, $ACC(m,w)$ which must describe that $m$ is a Turing machine that accepts string $w$, $TC(x,c)$ which describes that $x$ is a Turing machine within $c$ steps and $POL(c,p,n)$ which describes that $c$ is bounded by the polynomial $p(n)$.

Once we have defined these, we may have needed to introduce and define further predicates. And once this has been done, we need to define $PTR(x,y)$. Here, we can make use of some of the predicates that we already have, but we also need to introduce some new ones as well.

I hope that this outlines that this process of formalization is a involved and not entirely trivial task, and I hope this also explains why I do not present the entire construction of the first-order formula here.

---
Tags: logic, first-order-logic, 3-sat
---


# Question
Title: Is a Neural Network's weight selection dependent on its architecture?
Would an optimum combination of weights for a given topology necessarily be the the optimum for a different topology ?

# Answer
> 3 votes
**No**, an optimum combination of weights for a given topology not necessarily be the the optimum for a different topology.

Weight of a given neural network depends on the **structure of the network** and **training data** which vary network to network (or problem to problem).

Always the weights of a network are adjusted to match our desire output to achieve our goal.

Network topology also have a critical role in selection an optimum combination of weight.

Network with one hidden layer:

Network withe two hidden layer:

In above figures shows classification of a linearly separable data on two different network topology.

Here, thick dash line shows strong connection(higher weight) and thin dash line shows poor connection(lower weight).

You can visualize how weights get changes when we fed same data to two different network.

I recommend you to go to http://playground.tensorflow.org/ and play around different setting and observe the changes.

---
Tags: artificial-intelligence, neural-networks
---


title: Methods to prevent overfitting

text:
# Question
Title: Methods to prevent overfitting
I am aware of three approaches to prevent over-fitting of data when trying to model it on a neural net.

The first two approaches I know suggest to train on more data and employ bootstrap aggregating. The third approach is to use a model that has the right capacity, one that has enough to fit the true regularities but not the weaker/dubious regularities (the noise). However, I don't quite understand this 2nd approach. How do we create a distinction and choose a model that detects this? Can someone expand on the second approach? I am aware of ways to limit the capacity such as early stopping(which is self explanatory), penalty for peculiar weights, etc. But an explanation on why these specific methods limit the capacity to fit the right data but not the wrong one would be helpful.

# Answer
When choosing a specific model, to which you will try to fit your data into, you must know something about the problem. There is no way around it, machine learning cant do this magic for us, we have to know something.

First, convince yourself why complicated models can cause overfitting. Suppose I'm trying to learn some real valued function $f$, and I'm given $n$ samples of the form $S=(x\_1,y\_1),...,(x\_n,y\_n)$. If i choose to model my data by some polynomial (of arbitrary degree) then for any set of samples $S$, i can find a function in my model with zero training error, although it is likely to have high generalization error (a degree $n$ polynomial passing through all points in $S$ can always be found, regardless of any structure of the points in $S$). Perhaps using polynomials of degree$ \le 3$ will be good enough to model my data (it doesn't suffer from the previous problem). Why 3? I don't know, this depends on the specific types of functions I'm trying to learn.

A more concrete example, suppose you want to learn what is the appropriate dosage of some medicine, and you are given samples of the form $(x\_1,y\_1),...,(x\_n,y\_n)$ where $x\_i\in\mathbb{R}$ denotes the dosage, and $y\_i\in\left\\{\text{'good'},\text{'bad'}\right\\}$ tells you whether the dosage $x\_i$ worked (it can be too high or too low). Allowing your algorithm to choose some arbitrary function can result in strange outputs. For example if you received the samples $(1,\text{'bad'}),(2,\text{'good'}),(3,\text{'good'})$ then a function $f:\mathbb{R}\rightarrow\left\\{-1,1\right\\}$ which satisfies $f(1)=-1,f(2)=f(3)=1$, but is random everywhere else, is consistent with the samples. Such $f$ will probably have no indication on the true effect of the medicine. Now, I'm no doctor, but perhaps it is worth considering functions of the form:

$I\_{a,b}=\begin{cases} +1, & x\in \[a,b\] \\ -1, & \text{otherwise} \end{cases}$.

When choosing to model my data using such functions (segments), i use my knowledge on how medicines work (there is some appropriate dosage interval, while large deviations to any side could be dangerous).
> 1 votes

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


# Question
Title: Average number of collisions before successful insertion into hash table
I want to compute the average number of collisions before sucessfully adding an item into a hash table. Let $m$ be the size of a hash table $H$.

I was thinking that since it is a linear probing and we do not know where the free slots in the hash table are, the probability that first slot is free is $(m-n)/m$ where $n$ denotes the amount of 'bad' slots, i.e. there are $n$ items stored in our hash table. If the second slot is free then $(m-n)/(m-1) \> (m-n)/n$ and so on.

So the expected number of collisions is $1/p = 1/ (1-\alpha)$ where $\alpha := n/m$ is our load factor.

But my friends got totally different numbers. Am I going into the right direction?

# Answer
1 / (1 - alpha) is about right, if you ignore that for the second slot the chance is (m - 1 - n) / (m - 1) and so on. But when that difference becomes relevant, you should have increased the size of your hash table :-)

What also will happen if you visit consecutive slots on collisions is that once your table is reasonably full then you might have large ranges of occupied slots, which could very much change the situation. Say you have 1,000,000 slots and 999,500 used entries: It's quite likely that the 500,000 slots from 0 to 499,999 are all used.

But all this depends on having a good hash function. Your hash function needs to rarely map different items to the same hash code. And if your hash table visits consecutive slots for collisions, then your hash function mustn't map similar items to consecutive hash codes. Otherwise the average number of slots might be a lot larger.

On the other hand, the cost of visiting a few or a dozen used slots is usually very low to the cost of computing a hash code, if the hash table stores hash codes. It gets really expensive when you have a collision not in slot numbers, but in hash codes. That's when you actually have to compare values. So the most important thing would be a good hash function.

Added: Assume that you have a hash table with 1,000,000 slots, and that 999,500 slots are used. Which is obviously a much higher load factor than a hash table should ever be allowed to have. If the used slots were perfectly random, then inserting a new element would require visiting 2,000 slots on average.

But if you had a range of 500,000 consecutive used slots (which would be quite likely if inserting always visited the next available slot), and you inserted the next item: There would be a 50% chance that the next item gets inserted into that range, visiting from 500,000 to 0 slots, or 250,000 on average. And a 50% chance that the next item gets inserted into the other range which has 0.1% empty slots, or 1,000 on average. So the total average is 125,500 slots visited.
> 3 votes

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


# Question
Title: Using AI / Machine learning to find the most time and space efficient solutions to an algorithm
As programmers, we are always trying to find the most efficient space and time complexity solutions to algorithms.

Is it forseeable in the future that we have languages or techniques such as AI/machine learning to automatically find such optimum solutions to any generic algorithm?

# Answer
No.

With all the hype about AI/Machine learning, sometimes people forget that there are known limitations to computers, which can be **proven**, so it doesn't matter how fast your computer is, how sophisticated is your neural net, you just cant do it.

I'll try to address your specific question. First, you have to define exactly what is the task that you expect your AI algorithm to solve. Suppose your input is a description of the problem, given in the form of an encoding of a Turing machine $\langle M\rangle$ which solves it, or as a valid code in your favorite programming language. Now, say we want to output an equivalent program, with optimal (asymptotic) time complexity.

The decision version corresponding to your problem is, given a program in your language, decide if there exists an equivalent program with better (asymptotic) time complexity.

This is not possible for any computer, or in more technical terms, this language is undecidable. We can reduce the halting problem to the above in the following way:

Given a pair $(\langle M \rangle,w)$, Let $M\_w$ be the machine which, given input $x$, runs $M$ on $w$ for $|x|$ steps. If $M$ halted then $M\_w$ accepts iff $x$ is a palindrome. If $M$ didn't halt within $|x|$ steps, $M\_w$ rejects. We can build $M\_w$ such that $M\_w$ runs in $O(n^2)$ time.

If $M$ halts on $w$ after $n$ steps, then $L(M\_w)=\left\\{x \big| |x|\ge n \land \text{x is a palindrome}\right\\}$, otherwise $L(M\_w)=\emptyset$. Since we know that checking whether a string is a palindrome requires $\Omega(n^2)$ time on a single tape Turing machine, then if $M$ halts on $w$, $M\_w$ decides $L(M\_w)$ with optimal time complexity. Otherwise it doesn't (the empty language can be decided in constant time, just output "no" without even reading the input). This means that $M$ halts on $w$ iff $M\_w$ has optimal time complexity.

This shows that for general programs, this task is hopeless. Perhaps, for a specific subset of programs, you can decide optimality, and this doesn't necessarily mean using some fancy AI algorithm, see Program optimization.
> 4 votes

---
Tags: algorithms, algorithm-analysis, optimization, machine-learning, artificial-intelligence
---


# Question
Title: How to measure the complexity of the discrete logarithm problem?
The answers to this question on Crypto Stack Exchange basically says that, to measure the complexity of the logarithm problem, we have to take the length of the number representing the size of the group into account. It seems arbitrary, why don't we chose the size of the group as the argument? Is there a criterion to know what argument to chose? In fact, I know I overlooked something important since the complexity changes hugely if we do it by the size of the group.

# Answer
> 5 votes
It doesn't matter whether you choose the size of the group $|G|$ or the size of the integer representing it $n$ as a parameter, since $n \approx \log |G|$. There are two reasons that usually the complexity is described in terms of $n$ rather than $|G|$:

1. $n$ is the length of the input (more accurately, the input has length $\Theta(n)$), and we usually measure the complexity of algorithms as a function of the input length.
2. Usually $n$ is a small number such as $1024$, whereas $|G|$ is a huge number such as (roughly) $2^{1024}$.

---
Tags: time-complexity, discrete-mathematics, cryptography
---


# Question
Title: Problem using the Arden's Lemma on one automata
I am trying to find the regular expression of this automata using the Arden's Lemma:

Let $L\_{i}$ be the language accepted from the state $i$, this is what I got:

* $L\_{1} = 1^{\*}0L\_{2}$
* $L\_{2} = 1L\_{1} + 0L\_{3}$
* $L\_{3} = \epsilon + 0^{\*}1L\_{2}$

As the first state is the initial one, I have to solve $L\_{1}$. As $L\_{1}$ is expressed using $L\_{2}$, I have to first solve $L\_{2}$.

$L\_{2} = 1(1^{\*}0L\_{2})+0(\epsilon + 0^{\*}1L\_{2}) \\ L\_{2}=11^{\*}0L\_{2} + 0\epsilon + 00^{\*}1L\_{2} \\ L\_{2}=(11^{\*}0+00^{\*}1)L\_{2} + 0$

Using Arden's Lemma, I get $L\_{2}=(11^{\*}0+00^{\*}1)^{\*}0$

Thus we have now:

$L\_{1}=1^{\*}0L\_{2}=1^{\*}0((11^{\*}0+00^{\*}1)^{\*}0)$

Yet, based on this expression, the word "000" isn't accepted. Where is my issues?

# Answer
> 2 votes
The mistake is in the equation for $L\_3$: it should be $0^\*$ instead of $\epsilon$.

---
Tags: automata, regular-expressions
---


# Question
Title: Does the process exiting from critical section will always call signal instruction?
I have seen many solutions to critical section problems in process synchronization chapter . Many of them first acquire resources , execute critical section and leave . My Question is a process exiting from the critical section should **always** call $V(S)$ (or release/signal/ up ) instruction ? Can any process exit from critical solution by calling wait instruction ? If so give an example and explain how it works .

For example , all the problems regarding semaphore are executed in the following manner . Where $P(s) $ and $V(s)$ has usual meaning .( up and down operator )

```
s=1
P(s)
< Critical Section >
V(S)

```

I have never seen an solution like this

```
s=0
V(s)
< Critical Section >
P(S)

```

Does any critical section problems could be solved like this ? if so please explain me how it would works .

# Answer
Assuming s is a binary semaphore.

If s=0, a V(s) will be successful operation making s=1

If s=1, a V(s) will be successful operation making s=1

If s=0, a P(s) will be unsuccessful operation by retaining s=0

If s=1, a P(s) will be successful operation by making s=0

> s=0
> V(s)
> \< Critical Section \>
> P(s)

Let process ${p\_1,p\_2,p\_3,.,p\_k,.,p\_n}$ are waiting go get a chance to access CS (Critical Section).

For the first time $p\_1$ tries V(s), successfully increase s by 1,and get an access to CS.

While $p\_1$ still in CS $p\_k$ tries V(s), successfully increase s by 1 and get an access to CS and so on.

With V(s) at the entry of the CS, will never guarantee blocking others from getting into CS.

With this implementation all process waiting to access CS will get into CS, thus violation mutual exclusion.

Here talking about exiting operation P(s) is useless as it doesn't help the event by any means.

> s=1
> P(s)
> \< Critical Section \>
> V(s)

Here, if $p\_1$ tries P(s) for the first time, successfully decease s by 1 and get access to CS.

With P(s) at the entry of the CS, will guarantee blocking others from getting into CS.

While $p\_1$ still in CS $p\_k$ tries to enter CS by executing P(s), but fails as s=0 already and cant decrease anymore.

Thus always guarantee mutual exclusion.

See what happens if we doesn't have signal operation at CS exit:

> s=1
> P(s)
> \< Critical Section \>
> // remove exit operation V(s)

Without $p\_1$ signaling, non of the waiting process ${p\_2,p\_3,.,p\_k,.,p\_n}$ can access CS. no one can execute the entry operation P(s),since 's' value is still 0.

All processes waiting for CS will be blocked infinity.

Thus, deadlock kind of event happens here where resource is available but cant be accessed.
> 2 votes

---
Tags: operating-systems, concurrency, synchronization, mutual-exclusion
---


# Question
Title: Physical significance of Don't cares in Digital Logic design
In many Digital functions we come across don't care conditions where we use don't cares to minimize functions.
What is the significance of these don't cares in real world scenario where we actually implement the functions using logic gates?

# Answer
> 3 votes
Yes they do have physical significance.
Input combinations for which value of a function ( or a device) is not specified are called don't care conditions.
They are met when the number of inputs are more than expected.
For example, conversion of binary to BCD. Both are 4 bits long but using 4 bits 16 binary numbers are possible whereas only 10 BCD numbers.

Consider another example: Suppose there are 8 locations to be addressed and we have a total of 4 address lines. To address 8 locations we only need 3 bits hence three address lines. The forth extra address line is like dont care. We actually don't care the logical value of contained in that address line.

Actually don't cares allow us to choose from a class of many functions.
Each don't care bit represents 2 values {0 or 1}, hence a function containing 'k' don't care bits correspond to a class of $2^k$ distinct functions ( as 'k' inputs can give rise to $2^k$ combinations).
The task is to choose a function out these $2^k$ functions which has the most minimal representation. Thereby decreasing the number of inputs hence making the implementation faster.

---
Tags: digital-circuits
---


# Question
Title: On complete problems for $P/poly$ and $BPP$
Is there a complete problem for $P/poly$?

Decision version of permanent more or less acts as a complete problem for $PP$ while its weaker sibling has no known complete language. Why? I saw wiki reason but it is not clear to me. In https://en.wikipedia.org/wiki/PP\_(complexity)#Complete\_problems\_and\_other\_properties it is stated 'Unlike BPP, PP is a syntactic, rather than semantic class. Any polynomial-time probabilistic machine recognizes some language in PP. In contrast, given a description of a polynomial-time probabilistic machine, it is undecidable in general to determine if it recognizes a language in BPP'.

# Answer
There are no $P/Poly$ complete languages (relative to polynomial time or even computable reductions).

Suppose for the purpose of contradiction that there exists some language $L$ which is complete for $P/Poly$. In that case the mapping $f:P/Poly\rightarrow \mathbb{N}$, which maps any language in $P/Poly$ to its corresponding reduction to $L$ (we refer to the encoding of this reduction as a natural number), is an injection from $P/Poly$ to the natural numbers. This of course leads to a contradiction, since $P/Poly$ is of cardinality $2^{\aleph\_0}$.

In light of Ricky Demer's comment, we should note that since computable reductions are of no use to $P/Poly$, one needs to introduce the notion of non-uniform reductions. One example is projection reductions.

A family of boolean functions $f\_n(x\_1,...,x\_n)$ is said to be projection reducible to the family $g\_n(y\_1,...,y\_n)$ if for all $n\in\mathbb{N}$ there exists some $m\le p(n)$ with polynomial $p$, and a rewiring of $g$'s inputs, $\sigma:\left\\{y\_1,...,y\_m\right\\}\rightarrow\left\\{0,1,x\_1,\overline{x\_1},...,x\_n,{\overline{x\_n}}\right\\}$, such that $f\_n(x\_1,...,x\_n)=g\_m\left(\sigma(y\_1),...,\sigma(y\_m)\right)$. Intuitively, this means that given a circuit for $g$ (perhaps with polynomialy more inputs), we can compute $f$ just be rewiring the inputs accordingly. We denote this by $f\le\_{proj} g$.

Note that if $g\in P/Poly$ and $f\le\_{proj} g$ then $f\in P/Poly$, the advice for input $x$ would be the rewiring $\sigma$, together with the $m(|x|)$ inputs circuit for $g$.

The following is a (very) short sketch of the proof that the circuit value problem, $CVP$, which takes as input a circuit $\mathcal{C}$ and input $x$, and asks whether $\mathcal{C}(x)=1$ is $P/Poly$ hard under such reductions. Given $L\in P/Poly$, let $\mathcal{C}\_n$ be the polynomial circuit family for $L$. For any string $x$, You can hardwire $\mathcal{C}\_{|x|}$ as input to $CVP$ (using the constants $0/1$), and use the rest of the variables to input $x$.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: How do analogue computers perform logical operations?
My idea of analogue computers had been that they were the discrete version of digital computers, with fuzzy logic operations returning values in the interval \[0, 1\] instead of Boolean operations.

However looking at schematics, they seem to be built for directly computing differential equations.

I'm struggling to connect this to dicrete computation. How do analogue computers perform simple logical operations?

# Answer
As you point out, electronic analog computers were designed to compute differential equations, not simple logical operations. You can model an arbitrary linear differential equation with a circuit made of op-amps, resistors, and capacitors, where the variables in your equation are represented by voltages and currents in your circuit.

For non-linearities you can add a diode. The Shockley diode equation gives a good approximation for the behavior of a diode:

$$I = I\_s ( e^{\frac{V}{nV\_T}} - 1 )$$

(where $V$ is the voltage across the diode terminals, $I$ is the current, and $I\_s$ and $n V\_T$ are constants that depend on the construction of the diode.) So now we can implement exponentials and logarithms.

So now to actually answer your question: logic circuits in modern digital computers are non-linear analog circuits where some circuit voltage or current is taken to represent the boolean value. For example, we might say that a voltage greater than 5V represents `true` and a voltage less than 1V represents `false`. (Any voltage between 1V and 5V is assumed to be an error).

In the 1950s this was sometimes implemented using diode logic. For example the Wikipedia page shows this diagram of an `or` gate:

When this is followed by an inverting amplifier we get both a logical `not` operation, and restoration of any voltage levels that have degraded away from 0V or 6V. For example a *common emitter* amplifier has this characteristic,

The point of all this is not that you have to use diodes and transistors to implement logic, but rather that *any analog physical system with non-linearities and amplification* can emulate boolean logic. Hydraulic pumps, for example would have done just as well as diodes and transistors.
> 1 votes

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


# Question
Title: Correctness proof of greedy algorithm for 0-1 knapsack problem
We have a 0-1 knapsack in which the increasing order of items by weight is the same as the decreasing order of items by value. Design a greedy algorithm and prove that the greedy choice guarantees an optimal solution.

Given the two orders I imagined that we could just choose the first k elements from either sequence and use them to fill knapsack until it was full. This would be similar to choosing the items with the greatest ratio of value to weight. But I don't think that is an optimal solution.

So what I need help with is whether or not this solution is optimal. And how would I prove the correctness of a greedy algorithm.

# Answer
> 3 votes
Hint: Let $x$ be the item of smallest weight (and so of highest value). Take any solution which doesn't contain $x$. If there is room for $x$, add it to the solution. Otherwise, remove some element and add $x$ (why is that possible? does it necessarily improve the solution?). Conclude that the optimal solution always contains $x$. Apply this reasoning recursively to come up with a greedy algorithm.

# Answer
> 0 votes
A simple solution would be like this:

1. Generate solution using GREEDY technique.
2. Calculate **permutation of all possible answers**, and see for the **max profit satisfying weight constraint**
3. Now, you can check that your **solution generated by GREEDY technique**, and the **permutation which yields max profit satisfying constraint** is the ***same***, then you can say that your algorithm is **correct.**

# Answer
> -2 votes
**Let O be the optimal solution.**

```
O = {o1, o2, o3 ..., oj}

```

**Let G be our greedy solution.**

```
G = {g1, g2, g3, ..., gk}

```

**K = Initial Weight = Empty Knapsack**

```
K = k - 0              //Initially

```

If g1 is in O then we are done.

**But if g1 does not exist in O, then there might be another optimum solution.**

```
O' = O - {g1}          Equation : 1
K' = K - {g1}          Equation : 2   //Which means w1(least weight)

```

**If O' does not make an optimal solution then, our claim is wrong that g1 does not exist in O.**

*Therefore,*

```
O' = K'   // Since the optimum solution should have next weight possible
O' = K - {g1}          From Equation : 2
O' = O - {g1}          From Equation : 1
O - {g1} = K - {g1}    Equating

```

*So,* `O = K`

which proves that, The optimal solution after removing g1 from O' is still O.

**Q.E.D**

---
Tags: algorithms, algorithm-analysis, correctness-proof, greedy-algorithms, knapsack-problems
---


# Question
Title: What makes is the difference between a tree and a graph?
I have seen in some text books that they have started talking about a tree and then they use the terms such as vertices and edges and treat is as a graph.

What makes a graph a graph and what makes a tree a tree? I am getting the impression that a tree is a subset of a graph but what are these properties that make a graph a tree?

Is there a way to classify a graph from a tree?

# Answer
An *unrooted* tree is a connected acyclic graph, that is a graph in which any two vertices are connected, and which contains no cycles. In particular, it's a graph.

A *rooted* tree is a tree in which one of the vertices has been designated as *root*. Every other vertex has a *parent*, which is its unique neighbor closer to the root. Its other neighbors are known as its *children*.
> 2 votes

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


title: MSB and LSB in floating point number

text:
# Question
Title: MSB and LSB in floating point number
What is MSB and LSB in significant of a floating point number? If I have a significant for example 0011010000 (half-precision) but 1. bit is implicit what is MSB: 0 or 1? In this case LSB is 0, because it is on the end of significant?

# Answer
In the whole floating point number the MSB is a sign bit and LSB is in the mantisa (last bit).

In all floating point formats with exception of 10 byte IEEE real the mantissa MSB of normalised number is not stored because it is implicitly set to $1$ (and used in calculations).

So in the case of your significand (mantissa) $0011010000$ the MSB is $1$ (implicit) and LSB is $0$ (explicit).
> 1 votes

---
Tags: arithmetic, floating-point
---


title: On SUBEXP ⊆ P/poly

text:
# Question
Title: On SUBEXP ⊆ P/poly
According to answers here Are there subexponential-time algorithms for NP-complete problems? $\mathsf{NP}$ complete problems can be in $DTIME\[2^{n^{1/\alpha}}\]$ for $\alpha\>1$.

Now supposing $DTIME\[2^{n^{1/\alpha}}\]\subseteq\mathsf{P/Poly}$ holds for every $\alpha\>1$ then does it mean $\mathsf{NP}\subseteq\mathsf{P/Poly}$ holds?

What are the consequences of $DTIME\[2^{n^{1/\alpha}}\]\subseteq\mathsf{P/Poly}$?

Would this impact $\mathsf{subexp}\subseteq\mathsf{P/poly}$ problem?

# Answer
> 1 votes
If $DTIME\left\[2^{n^{\frac{1}{\alpha}}}\right\]\subseteq P/Poly$ for some $\alpha\>1$ then $NP\subseteq P/Poly$, since this means we can put an NP-complete problem in $P/Poly$, because as you mentioned, for all $\alpha\>1$ there exists some NP complete problem in $DTIME\left\[2^{n^{\frac{1}{\alpha}}}\right\]$. To see why the inclusion holds in that case, notice that for any other language in $NP$ you can first compute the reduction in polynomial time, and then work with the machine taking advice for the complete problem.

In order for the above to work, the reduction $f$ to our NP-Complete problem must have the property that $|f(x)|$ depends only on $|x|$ (the length of the output depends only on the length of the input, and not structure). However, we need not worry, since the reduction in Cook-Levin theorem has this property (verify), and the reduction from $SAT$ to padded SAT:

$SAT' = \\{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \\}$

also has this property.

A well known consequence of $NP\subseteq P/Poly$ is the Karp-Lipton theorem.

As for your second question, use the fact that $SUBEXP=\bigcap\limits\_{\epsilon\>0}DTIME\left\[2^{n^\epsilon}\right\]\subseteq DTIME\left\[2^{n^{\frac{1}{\alpha}}}\right\] $, for all $\alpha\>1$.

---
Tags: complexity-theory, complexity-classes
---


# Question
Title: Does a regular expression model the empty language if it contains symbols not in the alphabet?
Suppose $\Sigma = \\{ a,b \\}$ and the regular expression $(a^\*b+dc)^\*(b^\*d + ad)^\*$. Is it equal to $\varnothing$?

So I have a regular expression like this: $(a^\*b+dc)^\*$. As only $(a,b) \in \Sigma$, I see that:

* $dc=\varnothing$

So $(a^\*b+dc)^\*=(a^\*b)^\*$.

Then:

* $(b^\*d + ad)^\* = (\varnothing + \varnothing)^\*=(\varnothing)^\*$ and as $(\varnothing)^\*=\epsilon$, $(b^\*d + ad)^\*$ becomes $\epsilon$.

So my regular expression is simply $ (a^\*b)^\*$? Am I correct, or does the fact that the regular expression contain at least one symbol not in alphabet make it wrong immediately?

# Answer
> 9 votes
Regular expressions only use characters from the alphabet so, if you've fixed your alphabet to be $\\{a,b\\}$, then $(a^∗b+dc)^∗(b^∗d+ad)^∗$ isn't a regular expression. It doesn't describe any language, in just the same way that "seventy red" doesn't describe any number. In particular, it doesn't describe the empty language, in the same way that "seventy red" isn't equal to zero.

Now, if your alphabet includes all the symbols $a$, $b$, $c$ and $d$, you might want to ask what are the strings in $L((a^∗b+dc)^∗(b^∗d+ad)^∗)$ that contain only $a$'s and $b$'s. That is, what is $L((a^∗b+dc)^∗(b^∗d+ad)^∗)\cap \\{a,b\\}^\*$? And the answer to that is that it's all strings matching $(a^\*b)^\*$, as you derive in the question.

**Appendix.** One could attempt to sidestep these issues by redefining regular expressions in a way that gives them well-defined semantics if they include symbols not in the alphabet. However, the standard definition does not do this.

Indeed, trying to do so would seem to open up a huge can of worms. For example, suppose your alphabet is $\\{a,b\\}$. We could agree that, since $c$ is not a symbol in the alphabet, the regular-expression-like-object $abc$ matches nothing. OK, but $+$ is also a symbol that's not in the alphabet. Maybe you're happy with $ab+$ matching nothing because it's syntactically invalid – note, $ab+$, not $ab^+$! But, now, what does $a+b$ match? Does it mean "$a$ or $b$" or "$a$ followed by some symbol that's not in the alphabet followed by $b$, which is impossible, so it matches nothing"?

---
Tags: regular-languages, regular-expressions
---


# Question
Title: A specific version of a job scheduling problem
I'm looking for a solutions or book references to a given variation of a job scheduling problem:

Given $n$ machines (let's denote it by $m\_1, m\_2, \ldots, m\_n$) and $r$ tasks ($t\_1, t\_2, \ldots, t\_r$). Each task $t$ can be described as a tuple $\left( (a\_1, b\_1), (a\_2, b\_2), \ldots, (a\_k, b\_k) \right)$, where $a\_i$ is a number of some machine and $b\_i$ is a required time to complete task $t$ on machine $a\_i$. To complete the task, you need to start it on the first machine in the sequence ($a\_1$) for a given amount of time ($b\_1$), then start it on the second ($a\_2$) and so on, until you finish your job on all of the given machines. It could be possible that number of machines in job description is smaller than $n$.

We will assume that tasks are atomic and one machine can do only one task in the same time, so it's possible that some task need to wait for a moment when a given machine is free. Finally, we want to find the ordering of tasks to given machines to minimize the total time of all tasks.

# Answer
This scheduling problem is called *non-preemptive job shop scheduling*. The classic reference is

> Edward G Coffman, Jr, and Peter J Denning: *Operating Systems Theory*, Prentice-Hall, 1973.

Job-shop scheduling is discussed in Section 3.7 and 3.8 (although they mainly focus on a restricted version of the problem called the *flow shop problem* where the $a\_i$ are in the same order for every task.)

It is called job shop scheduling because most of the early work on it was done by industrial engineers who were trying to optimize work schedules for machines in a factory, rather than computers.
> 3 votes

# Answer
Two machines : $m\_1,m\_2$

Four Tasks: $t\_1,t\_2,t\_3,t\_4$

Tasks are:

$t\_1=((m\_1,2),(m\_2,3))\implies$ 5 instance of time

$t\_2=((m\_2,1),(m\_1,2))\implies$ 3 instance of time

$t\_3=((m\_2,3),(m\_1,1))\implies$ 4 instance of time

$t\_4=((m\_1,1),(m\_2,4))\implies$ 5 instance of time

where $(m\_2,1)$ and $(m\_1,2)$ are subtasks of $t\_1$ denoted as $t\_{11}$ and $t\_{12}$ respectively.

Considering all tasks arrives to the system at the same time.

**Approach 1:**

Schedule subtasks $t\_{ij}$ on the basis of its burst time (running time) such that no subtask $t\_{sj}$ is scheduled, if any unscheduled subtask $t\_{dj}$ exist where $d\<s$.

i.e., all subtask $t\_{1j}$ should schedule before all $t\_{2j}$

\begin{array} {|r|r|} \hline Machine \hspace{0.2cm} m\_1 &t\_{41} &t\_{11} &t\_{11} &t\_{32} &t\_{22} &t\_{22} &- &- &- &- &- \\ \hline Machine \hspace{0.2cm} m\_2 &t\_{21} &t\_{31} &t\_{31} &t\_{31} &t\_{12} &t\_{12} &t\_{12} &t\_{42} &t\_{42} &t\_{42} &t\_{42} \\ \hline Time &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11\\ \hline \end{array}

**Approach 2:**

Consider $t\_{hj}$ and $t\_{gj}$ be two subtask to be scheduled and $h\>g$.

Schedule subtasks $t\_{ij}$ on the basis of its burst time (running time).

Once $t\_{hj}$ completes its task, $t\_{h(j+1)}$ is also considered to be scheduled even if other $t\_{gj}$ is still not scheduled (on the condition that burst time of $t\_{h(j+1)} \< t\_{gj}$).

i.e., if subtask $t\_{11}$ is finished, $t\_{12}$ can be scheduled before $t\_{21}$ where burst time $t\_{12}\<t\_{21}$

\begin{array} {|r|r|} \hline m\_1 &t\_{41} &t\_{11} &t\_{11} &t\_{22} &t\_{22} &t\_{32} &- &- &- &- &- \\ \hline m\_2 &t\_{21} &t\_{12} &t\_{12} &t\_{12} &t\_{31} &t\_{31} &t\_{31} &t\_{42} &t\_{42} &t\_{42} &t\_{42}\\ \hline Time &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11\\ \hline \end{array}

Approach 2 is better than Approach 1, since we achieve better turnaround time for each task $t\_i$ .
> 0 votes

---
Tags: algorithms, optimization, reference-request, scheduling
---


# Question
Title: If direct mapping scheme was used instead what will be the size of the tag field?
A computer has a 32K main memory and a 4K fully associative cache memory. The block size is 8 words. The access time for main memory is 10 times that of main memory.

a. What is the size of tag field b. If direct mapping scheme was used instead what will be the size of the tag field?

# Answer
> 0 votes
Main memory bits = $log\_2(32k)$ = 15 bits
Cache size = 4k
Block size = 8 words

**Associate mapping:**

The data from any location in RAM can be stored in any location in cache.

Associate mapping addressing will be in the form:

\begin{array} {|r|r|} \hline Tag &Offset\\ \hline \end{array}

where,
offset bit = $log\_2(block size)$
Tag = Main memory address bit - offset bit

Here,
Offset = $log\_28$ = 3 bits
Tag = 15 - 3 =12 bits

\begin{array} {|r|r|} \hline 12 &3\\ \hline Tag &Offset\\ \hline \end{array}

**Direct mapping:**

Each location in RAM has one specific place in cache where the data will be held.

Direct mapping addressing will be in the form:

\begin{array} {|r|r|} \hline Tag &line &Offset\\ \hline \end{array}

where,
offset bit = $log\_2(block size)$
line bit = $log\_2(cache size/block size)$
Tag = Main memory address bit - (line bit + offset bit)

Here,
Offset = $log\_28$ = 3 bits line = $log\_2(4k/8)$ = 9 bits Tag = 15 - (9+3) = 3 bits

\begin{array} {|r|r|} \hline 3 &9 &3\\ \hline Tag &line &Offset\\ \hline \end{array}

**Answer:**
(a) 12 bits
(b) 3 bits

Recommended lecture notes on cache memory addressing by:

University of Washington
University of Minnesota
North Carolina A&T State University

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


# Question
Title: if (λ x . x x) has a type, then is the type system inconsistent?
If a type system can assign a type to `λ x . x x`, or to the non-terminating `(λx . x x) (λ x . x x)`, then is that system inconsistent as a consequence? Is every type under that system inhabited? Can you prove false?

# Answer
> 29 votes
Certainly, assigning a type to $\lambda x. x\ x$ is *not* enough for inconsistency: in system $F$, we can derive $$ \lambda x.x\ x:(\forall X.X)\rightarrow (\forall X.X)$$

in a pretty straightforward way (this is a good exercise!). However, $(\lambda x.x\ x)(\lambda x.x\ x)$ *cannot* be well typed in this system, assuming $\omega$-consistency of 2nd order arithmetic, as this implies that all such well-typed terms are normalizing.

Furthermore, system $F$ is consistent. This follows from either normalization, as one can show that any term of type $\forall X.X$ cannot have a normal form, or a much simpler argument, in which each type is assigned a set, either $\varnothing$ or $\\{\varnothing\\}$ and it can be shown that all derivable types are assigned $\\{\varnothing\\}$, and $\forall X.X$ is assigned $\varnothing$ (and is therefore not derivable).

The latter argument can be carried out in first-order arithmetic. The fact that $\lambda x.x\ x$ can be well-typed in a consistent system can be seen as somewhat disturbing, and is a consequence of the systems' *impredicativity*. It shouldn't come as a surprise that some people question the trustworthiness of impredicative systems of logic. However, no inconsistencies have been found so far in such systems.

On the other hand, to be able to make the more general assertion that $(\lambda x.x\ x)(\lambda x.x\ x)$ cannot be well-typed in a consistent system, you need to have enough "logical structure" in your type system to be able to clearly define consistency. Then you need to show that a term without a head normal form (like the one above) can have any type, which is also not obvious!

More details can be found in my answer to a related question: https://cstheory.stackexchange.com/a/31321/3984

---
Tags: lambda-calculus, dependent-types
---


# Question
Title: what is the regular expression for this language?
the language is: L={{0,1}\*|strings that contain the same number of 1's and 0's , plus there can't be three (or more) aces or zeros one after another}

for example the string cannot be: 111001 because the subword 111 contains three aces one after another (plus the number of aces is bigger than that of the zeros)

some of the accepted strings are: 01 10 0011 1100 0101 1010 0110 1001 100110 ...

# Answer
> 2 votes
Actually the language is not regular. Intersect with $\\{001,011\\}^\*$.

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


# Question
Title: Proof: Sum of weights of paths in a network
I was given problem 6.7 out of the book "Networks: An Introduction" as a question. The problem is defined as follows:

> Consider the set of all paths from node $s$ to node $t$ on an undirected network with adjacency matrix **A**. Let us give each path a weight equal to $\alpha^r$, where $r$ is the length of the path.
>
> a) Show that the sum of the weights of all the paths from $s$ to $t$ is given by $Z\_{st}$ which is the $st$ element of the matrix $Z = (I - \alpha A)^ {-1}$, where $I$ is the identity matrix
>
> b) What condition must $\alpha$ satisfy for the sum to converge?

Where do I even start on this problem? Since the graph is undirected, I know that **A** must be a symmetric matrix. Other than that I don't quite know what more information there is to go on.

# Answer
A few hints:

* Find out what the entries of $A^2$ mean. How about $A^k$? (Start by a very small adjacency matrix, multiply it with itself and try to think what each entry means).
* Lookup and understand the Taylor expansion of $f(x) = 1/(1-x)$.
* Realize that the sum of weights of all paths from $s$ to $t$ is the sum of weights of paths of length 0, 1, 2, ...
> 3 votes

---
Tags: graphs, matrices
---


# Question
Title: How can I fix this pseudocode of Kruskal's algorithm?
So here, I am not sure what the while statement means. In the lecture note there is no definition for T or N or u or v. My guess is T is the minimum spinning tree, but is N the node? Why condition T to be smaller than N - 1?

And how about the case of a cycle? shouldn't we take that into consideration as well?

I understand how Kruskal works but i am just not sure what this pseudocode means.

# Answer
> 3 votes
$|T|$ is the number of edges in the forest $T$, eventually $T$ will become the required minimum spanning tree. |N| is the number of nodes of the graph (for which you are finding a MST). You start by an empty forest and at each step you add an edge that does not form a cycle. You stop once you have picked exactly $|N| - 1$ edges.

# Answer
> 1 votes
**Goal: Compute MST of $G = (V, E)$.**

We have $ N = \lvert V \rvert $ in your pseudocode.

> In the lecture note there is no definition for T or N or u or v.

You can represent an edge $e \in E$ as a tuple $(u, v)$, where $u,v \in V$, meaning vertex $u$ has a link with vertex $v$.

Also, note that a Tree must have $N - 1$ edges, and no cycles. Kruskal deals with cycles by using a Disjoint Set Data Structure.

**Step 1: Initialization and Sorting**

Initialize $ ~ T = \emptyset $.

Sort $~E~$ by edge weigth.

**Step 2: Building T**

If you naively take only the first $n$ edges there's a chance that $ ~ T ~$ will contain a cycle, and therefore be a MST. That's why there's an **if** statement checking whether two vertices are already in the same component. Looking at the example I've modified from Wikipedia:

If you greedily chose edge $(D,B)$ you'll end up with a cycle, however both $D$ and $E$ are in same component **(green)**, so the if condition fails.

Now the next iteration will check the next edge in sorted $E$, i.e. $(B, E)$.

---
Tags: algorithms, graphs, minimum-spanning-tree
---


# Question
Title: Minimum number of rotations of a binary tree to convert it into another
I have the following binary tree, which I'm trying to convert into the target binary tree (second tree in the post) using minimum number of tree rotations. The theoretical minimum number of rotations for this tree is 5, however, the smallest value I can figure out is 6 rotations, I have copied the rotations as well, what am I missing?

**Tree:** `1
 \
 \
 3
 / \
 / \
 2 5
 / \
 / \
 4 7
 / \
 / \
 6 11
 / \
 / \
 9 12
 / \
 8 10`

**Target Tree:** `1
 \
 \
 11
 / \
 / \
 9 12
 / \
 / \
 3 10
 / \
 / \
 2 5
 / \
 / \
 4 7
 / \
 6 8`

The rotations I have tried so far (all of which require 6 rotations):

**Order1:** `Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 3 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9` **Order2:** `Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9`

**Order3:** `Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 3 and pivot 9`

**Order4:** `Rotate left with root 7 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 11
Rotate left with root 3 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9`

**Order5:** `Rotate left with root 7 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 3 and pivot 9`

# Answer
> 3 votes
First rotate 9 right around 11 to make a linear tree.

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


# Question
Title: Is following observation on Ladner's theorem correct?
> Suppose $NP\subseteq DTIME\[n^{f(n)}\]$ where $f(n)$ is any function satisfying $\omega(1)$ then is it true $P=NP$ holds?

Ladner's theorem states infinite time hierarchy between $P$ and $NP$. That is there are $NP$ problems in $DTIME\[n^{g(n)}\]$ for any $g(n)$ such that $n^c\leq n^{g(n)}\leq 2^{n^{1/c}}$ at some fixed $c\geq1$. If $NP\subseteq DTIME\[n^{f(n)}\]$ where $f(n)$ is any function satisfying $\omega(1)$ then for every such $g(n)$ we can find a $f(n)\ll g(n)$ and so Ladner's theorem is violated and so $P=NP$ has to hold.

And so if $P\neq NP$ there is $g(n)$ with $n^c\leq n^{g(n)}\leq 2^{n^{1/c}}$ such that $NP\subsetneq DTIME\[n^{g(n)}\]$ and $NP\subseteq DTIME\[n^{f(n)}\]$ where $f(n)$ is any function satisfying $\omega(1)$ implies $P=NP$. Are these observations correct?

> What if I replace $DTIME$ by $RTIME$? Would this yield $RP=NP$ by some randomized version Ladner's theorem?

# Answer
I'm annoyed at both \["any" being used as a quantifier\] and \[the placement of quantifiers making things even more ambiguous\], so I'll start with the two interpretations of your initial block-quote.

> Suppose there is a function $\hspace{.04 in}f$ in $\omega(1)$ such that  NP $\subseteq$ DTIME$\left\[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right\]$ .
> Does it follow that  P = NP ?

It's not known to, since    ($n\mapsto 2^{\hspace{.02 in}n}\hspace{-0.03 in}$)  $\in$  $\omega(1)$    and  NP $\subseteq$ EXP $\subseteq$ DTIME$\left\[\hspace{-0.02 in}n^{\hspace{.04 in}(2^{\hspace{.02 in}n})}\hspace{-0.04 in}\right\]$  are both known.

> Suppose that for all functions $\hspace{.04 in}f$ in $\omega(1)$,  NP $\subseteq$ DTIME$\left\[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right\]$ .
> Does it follow that  P = NP ?

Yes, since as described in this answer, there exists
a function $\hspace{.04 in}f$ in $\omega(1)$ such that  DTIME$\left\[\hspace{-0.02 in}n^{\hspace{.04 in}f(n)}\hspace{-0.03 in}\right\]$ = P .
The truth of your "That is ... fixed $c\geq 1$." sentence has nothing to do with Ladner's Theorem
\- The empty language and full language, for example, are such NP problems.
For the sentence after that, the g given by  g(n) = c  is such a g, and functions f cannot simultaneously be in $\omega(1)$ and satisfy  f(n) \<\< c ,  so where's the violation of Ladner's theorem?
By the function g I just mentioned, the part of your
"And so if ..." sentence before that sentence's "and" is true.
For the rest of that sentence, see this answer's two block-quotes and its responses to those.

This answer's response to its "there is" block-quote would still apply.
I *believe* this answer's response to its "for all" block-quote
would also still apply, by a similar argument.
> 3 votes

---
Tags: complexity-theory, time-complexity, randomized-algorithms, p-vs-np, np-intermediate
---


# Question
Title: How to use the Pigeonhole Principle to prove a DFA has a minimum number of states?
> $A = \\{w \in \\{a, b\\}^\* | $ 10th character from the **end** of $w$ is $b\\}$
>
> Prove if DFA $M$ has $L(M) = A$ then $M$ has at least 1024 states.

So there's only 2 characters possible at any state, aside from the 10th character, which has to be $b$. Any character after that can be a or b, since we know the 10th character from the end is $b$.

I was told that the Pigeonhole Principle would be used to prove this, as well as contradicting or using the contrapositive was the way to go.

My answer was that if we took a string $w$ with a length of less than the number of states, say 9, then the principle says that a state will have to be repeated. So a string of 10 $b$'s in a row won't reach an accepting state because the path will waste a transition to loop or repeat a state that has been traveled to. Because a string failed when it shouldn't have, that contradicts the language?

I also have a few other reasonings that may work with the Pigeonhole Principle, but I am just wondering if my reasoning makes sense.

# Answer
> 1 votes
http://www.owenstephens.co.uk/blog/2014/09/28/NFA\_DFA.html

https://cseweb.ucsd.edu/~ccalabro/essays/fsa.pdf

Evil's link and this other link seem to show how to apply the Pigeonhole Principle to show how to answer my problem. The second one explains it more visually and in a more noob friendly fashion.

---
Tags: automata, finite-automata, lower-bounds
---


# Question
Title: Any suggestions about a known NP-complete problem that can be reduced to the following problem?
> Given an undirected graph $G$, where nodes represent towns and edges represent roads, and given a positive integer $k$, is there a way to build $k$ McDonald's at $k$ different towns so that every town either has its own McDonald's, or is connected by a (direct) road to a town that does have a McDonald's?

I believe that this problem is NP-complete. I am trying to find a well-known NP-complete problem, so I can use it to prove that this problem is NP-complete, too. Any suggestions?

# Answer
This problem is called Dominating Set, and as pointed out by Raphael in the comments it's a special case of Set Cover (for each vertex, create a set for it and its neighbours). It's NP-hard.
> 3 votes

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


# Question
Title: Should two DFAs be complete before making an intersection of them?
In the slides given by my teacher, the third automaton is the product of the first two:

I tried to do the product myself by doing the transition table of both automata at the same time. I got stuck when I realised that the second automaton has no transition from state $2$ with $a$ as input symbol, thus the automaton should halt at that moment. In the third automaton, I can see there is no transition with input symbol $a$ in any of the states that have $2$ in (sorry for the bad expression, don't know how else to say it).

So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton? Or would it be wise to complete the automaton?

# Answer
> 7 votes
By definition, a deterministic finite-state automaton $(Q,\Sigma,\delta,q\_0,F)$ must have a total transition function: For every $q \in Q$ and $a \in \Sigma$, $\delta(q,a)$ must be defined.

Automaton no. 2 is not well-defined and for this reason it makes no sense to apply the product construction to the two automata given in your question.

(A note on grammar: The singular form is *automaton*, the plural is *automata* – we cannot speak of "an automata" or "two automatas".)

# Answer
> 9 votes
> So when doing the transition table of the two automata, if there is no transition, should I just ignore it like in the 3rd automaton?

If there is no transition in one of the automata, then that one won't accept the input word. Therefore, the automaton for the intersection should not accept either; not having a transition is one way to make sure of that.

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


# Question
Title: Is the difference between between an union and a product of two DFA lies in their accepting states?
It seems to me that in order to construct the union and the product of two DFA we use basically the same method.

The difference is that when we make the accepting states for the resulting DFA. Suppose $A\_{1}$ an DFA with $F\_{1}$ as an accepting state, and $A\_{2}$ an DFA with $F\_{2}$ as an accepting state. In the case of an union of $A\_{1}$ and $A\_{2}$, the accepting states have either $F\_{1}$ or $F\_{2}$ or both, and in the case of a product, the accepted state is {$F\_{1},F\_{2}$}. Am I correct?

# Answer
Please use the terminology correctly. The union operation is an operation defined on *sets*. It does not make sense to speak of the union of two automata.

The product construction can be used to give a constructive proof that the class of regular languages is closed under union. But with minor modifications, the product construction can also be used to show that the class of regular languages is closed under intersection as well as under set difference.

Assume that we have two DFA $M\_1 = (Q\_1,\delta\_1,\Sigma,q^1\_0,F\_1)$ and $M\_1 = (Q\_2,\delta\_2,\Sigma,q^2\_0,F\_2)$. In the case of intersection, define the set of accepting states as

$$F = \\{ (q\_1,q\_2) \mid q\_1 \in Q\_1 \wedge q\_2 \in Q\_2 \\} $$

For set difference, define the set of accepting states as

$$F = \\{ (q\_1,q\_2) \mid q\_1 \in Q\_1 \wedge q\_2 \notin Q\_2 \\} $$
> 6 votes

---
Tags: finite-automata
---


# Question
Title: Is it NP-complete to decide if chromatic and clique numbers agree?
It is known that finding chromatic number $\chi(G)$ and clique number $\omega(G)$ are both NP-complete problems.

Is the problem

> Given graph $G$, is $\omega(G)=\chi(G)$?

NP-complete as well?

Side question: is there a name for such graphs?

# Answer
Your problem is NP-complete. See for example this question on ResearchGate.

Your problem is in NP because to show that $\omega(G) = \chi(G)$ it is sufficient to exhibit a $k$-clique and a $k$-coloring, for some $k$.

Your problem is NP-hard by reduction from 3COL. Given a graph $G$, first check whether it contains a $K\_4$, and if so output some trivial No instance (say a $5$-cycle). Otherwise, add a triangle to your graph. The original graph is 3-colorable iff the new one satisfies your condition.
> 4 votes

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


title: Computer Science Book for Young Adults

text:
# Question
Title: Computer Science Book for Young Adults
What is a good beginner computer science book for a young adult, say, a 15 year old? I want to get started in CS, but have no idea where to start. I have limited experience in programming.

# Answer
Even this might be too basic for teenager, I nicely shows how to abstract problems, and is applicable for kids :

I highly recommend all CS people to take a look at: Computer Science Unplugged , just to see how CS can look different :).

For young CS minded people I recommend to develop intuition by solving programming tasks from problem solving contests, like programming contests: ACM ICPC, Olympiads in Informatics etc.

It's nice way to go into "Practical Algorithmic" , which gives you best from both worlds: programming and algorithms. Thanks to that you will be prepared to go in future in both directions: CS oriented industry (Google, Yahoo etc), and University CS.

Nice places to start:
> 15 votes

# Answer
Several favorite references which would be accessable to a highly motivated or advanced teenager.

\[1\] New Turing Omnibus by AK Dewdney. Has a grab bag of some of the more interesting key concepts of CS. A very visual approach. AK Dewdney has experience writing the mathematical games and puzzles column for Scientific American.

\[2\] Godel, Escher, Bach, the eternal golden braid by Douglas Hofstadter. Considered a classic by many. Focuses on Godel's theorem and incompleteness from a computational angle. Cited by many computer scientists as a favorite. See also Wikipedia reference

\[3\] Out of their minds: lives of 15 great computer scientists by Shasha and Lazere. Bios and interviews with many of the greats & some legends such as Cook, Knuth etc.
> 11 votes

# Answer
If you like, take one of the online courses following these links:

MIT OpenCourseWare

Coursera 2012
> 5 votes

# Answer
*The Pattern On The Stone: The Simple Ideas That Make Computers*, by Daniel Hillis, is a very good introduction, starting from the logic building blocks up to programming, algorithms and computer architecture.
> 5 votes

# Answer
A good introductory book for Computer Science is Brookshear - Computer Science: An Overview.

David Harel's Algorithmics is a classic.
> 4 votes

# Answer
I think Problem-Solving Strategy is an interesting book for teens. It does not need a deep mathematical background. However, if its math is too hard you can find an interesting and small book about discrete mathematics¹ to read first and then switch back to this book. I read it when I was in high school and this book motivated me to do stuff in CS.

---

1. I think what constitutes a discrete mathematics book for teens depends on native culture and language. I know a good one in my language, but I do not know any good ones in other languages. These are related Persian books: Alphabet of Mathematics and Computer Olympiad. Mathematics for teens by Yahya Tabesh. I couldn't find its link in the web, may be is too old. Also I'm not sure I said the name correctly, I remember it because of interesting images and its beautiful cover.
> 1 votes

# Answer
Algorithmic Puzzles, by Anany Levitin & Maria Levitin.

> Houses puzzles for all skill levels from readers with only middle school mathematics to seasoned puzzle solvers.

Starts with some Mathematical and Algorithmic background, sorts problems though Easy, Medium and Hard, gives both Hints and Solutions so it's great for self study.
> 1 votes

---
Tags: education, reference-request
---


# Question
Title: Why does the square root of n! grow exponentially faster than exponential functions?
I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.

In the proof of the theorem $6$ of the paper on page 632, the authors go on proving the difference between the probabilities of sampling all irreps, $|p - q|\_1$ of a subgroup inside the symmetric group $S\_n$.

$$ \begin{align} |p - q|\_1 &= \Sigma\_{\rho} \mid p\_{\rho} - q\_{\rho} \mid \\ &\le \Sigma\_{\rho} \frac{d\_{\rho}}{n!} 2^{O(n)} \sqrt{n}^{n / 2} \\ &\le \Sigma\_{\rho} \frac{\sqrt{n!}}{n!} 2^{O(n)} \sqrt{n}^{n / 2} \\ &\le \frac{2^{O(n)} \sqrt{n}^{n/2}}{\sqrt{n!}} \\ &= 2^{O(n)} \frac{\sqrt{\sqrt{n}^n}} {\sqrt{n!}} \\ &\le 2^{O(n)} \frac{1}{\sqrt{\left( n / 2 \right)!}} \lll 2^{-\Omega(n)} \end{align} $$

How is $2^{O(n)} \frac{1}{\sqrt{\left( n / 2 \right)!}} \lll 2^{-\Omega(n)}$?

# Answer
> 9 votes
Throwing away gutter, this is the claim:

$\qquad\frac{c^n}{\sqrt{(n/2)!}} \to 0$ with at least exponential rate as $n \to \infty$.

That is, the sqare root of $(n/2)!$ grow (at least) exponentially faster than exponential functions.

You can prove this by showing that

$\qquad\frac{c^n}{\sqrt{(n/2)!}} \sim 2^{-g(n)}$ for some $ g \in \Omega(n)$.

Use Stirling's approximation.

# Answer
> 9 votes
$\log(n!)=\Theta(n\log n)$, (see Stirling's approximation), hence

$\frac{2^{O(n)}}{\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\log\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\Theta(n\log n)}=2^{-\left(\Theta(n\log n)-O(n)\right)}=2^{-\Omega(n)}$.

# Answer
> 1 votes
You don't need any approximations. Compare $c^n$ and $(n!)^{1/2}$: As soon as $n \> c^2$, $(n!)^{1/2}$ grows exponentially faster because going from n to n+1, one grows by a factor c, and the other by a factor greater than c.

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


# Question
Title: Language Features Not Translatable into Lambda Calculus
Haskell is said to be a pure language because the language features are directly translatable into lambda calculus.

My question is: for languages considered to be non-pure functional languages (e.g. Scala, OCaml), which aspects of those languages are not translatable into lambda calculus?

# Answer
That's not what "pure" means. Pure means, generally, that there is no mutable state, and no way to interact with the outside world (i.e. IO).

Haskell is *not* "directly translatable" (what translation between language features really means needs to be defined fist, but let's ignore that for now) into either the untyped or simply-typed lambda calculus. There are many features that prevent it from being so, but a good example is polymorphism: there is no polymorphic identity function in the simply-typed lambda calculus.

Instead, Haskell and SML are actually derived from the Hindley-Milner type system, which is an *extension* of the simply-typed lambda calculus with polymorphism and type-constructors (aka higher-kinded types). Hindley-Milner has the nice property that type inference is decidable without *any* type annotations.
> 4 votes

---
Tags: lambda-calculus, functional-programming
---


title: Question Regarding ECLOSURE in ε-NFAs

text:
# Question
Title: Question Regarding ECLOSURE in ε-NFAs
I have a small question regarding the **ECLOSURE** of a certain state in an **ε-NFA**.

If we have a **transition** that has both **a** and **ε** transitions, is the **ECLOSURE** affected?

Also is there any rule that in **ECLOSURE** we should include the states that are accessible only from transitions containing **ε**?

# Answer
The $\epsilon$-closure of a state $p$ is the set of all states, including $p$ itself, that are reachable by *only* by a chain of consecutive $\epsilon$-moves. Transitions on other inputs are not considered when computing $\epsilon$-closure$(p)$. They come in to play in the next step, when you compute the transition function for the equivalent NFA without $\epsilon$-moves.
> 4 votes

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


# Question
Title: How to determine(with some confidence) if two extremely long lists of numbers (terabytes) are similar?
I have two very large files with numbers seperated by commas. What is most efficient/fastest way to say with some confidence that these two files have same numbers.

The main rule if if two distributions are the same, also the order of data does matter for example:
**A = {1 2 4 5 6}**
**B = {6 5 4 2 1}**
**C = {0.5 0.5 1 2 3 4 5 6}**

in above case A and C are still similar but A and B are totally different

To be more clear lets split the question into 3 main tasks

1. Given large lists A,B find if lets say 50% of A is contained in B (Most efficient technique without comparing all numbers from list)
2. Given A,B match above condition check that the overlapping numbers have similar order as mentioned above i.e. if 2 in A is followed by 1 same should happen in B. The positions of 1,2 can be different in B.
3. Select two independent batches from A and B and test if those are from Poission distribution, binomial distribution.

# Answer
Check out Jaccard Similarity, as it gives a measure of set similarity. See MinHash, locality sensitive hashing.
> 1 votes

# Answer
Anwser is hashing.

* Lists are small enough to fit in memory, are unsorted and scanning through them completely with a single machine counts as quick, then the idea of building a hash set out of the smaller list and then scan the larger for matches.
* One of the lists is small enough to fit in memory and you need to use more than one compute to make scanning the larger list fast enough, then scanning the small list on all machines or scanning on one and passing the hash set around will allow you some speedup.
* If the small list is too large, then building partial hash sets on many machines can work. Distribute the hash sets according to some modulo method. Each machine would then read part of the bigger list and send the list element according to the same hash modulo method the first list hashes were distributed.

MapReduce will help you in this journey too.

Breakthrough achievements:

Google Teams With Prodigal Son to Bust Data Sort Record

Breaking the Minute Barrier for TeraSort
> 0 votes

---
Tags: algorithms, comparison
---


# Question
Title: Analysis of a randomized algorithm for independent set construction
Suppose that $G = (V,E)$ is a 3-regular graph on $n$ vertices and $m$ edges. Below I propose a randomized algorithm for obtaining an independent set for $G$.

> Step $1$: Delete each vertex (independently) with $\frac{2}{3}$ probability.
>
> Step $2$: For each remaining edge, delete one of its endvertices.

I want to upper bound the probability that this $2$-step algorithm yields an independent set of size smaller than $\frac{n(1-\varepsilon)}{6}$, where $0 \< \varepsilon \leq 1$. My partial attempt is below.

Let $X\_1, X\_2, \dots, X\_n$ be independent Poisson trials satisfying $\textbf{Pr}\[X\_i = 1\] = \frac{1}{3}$. Hence, $X = \sum\_{i=1}^{n} X\_i$ gives us the number of vertices in $G$ that survive Step $1$, and $\textbf{E}\[X\] = \frac{n}{3}$.

Let $Y\_1, Y\_2, \dots, Y\_m$ likewise be independent Poisson trials satisfying $\textbf{Pr}\[Y\_i = 1\] = \frac{1}{9}$. Hence, $Y = \sum\_{i=1}^{m} Y\_i$ gives us the number of edges in $G$ that survive Step $1$, and $\textbf{E}\[Y\] = \frac{n}{6}$.

Thus, $X-Y$ gives us the minimum number of vertices remaining after the algorithm terminates.

Now, the following Chernoff bound seems especially pertinent to this problem, where $Z$ is a sum of independent Poisson trials, $\mu$ is its expectation, and $0 \< \delta \leq 1$:

> $\textbf{Pr}\[Z \< (1 - \delta)\mu\] \< \exp(\frac{-\mu \delta^2}{2})$

Of course, $X-Y$ is a lower bound on the size of the output independent set, but I'm not sure how I can apply the expression to the Chernoff bound. Can $X-Y$ can be conceived as a sum of Poisson indicator variables, which would be required if I wanted to put $X-Y$ in place of $Z$ in the above bound? If so, then it seems to me that I can use this Chernoff bound to derive an upper bound on the probability that the *minimum* size of the output independent set is smaller than $\frac{n(1-\varepsilon)}{6}$. How can I get from this to my objective: an upper bound on the probability that the *actual* size of the output independent set is smaller than $\frac{n(1-\varepsilon)}{6}$?

# Answer
You can obtain a weak upper bound by resorting to the Markov inequality instead. Specifically, let random variable $\small Z$ be the size of the independent set remained. We have then \begin{align} \small \Pr\left\[Z \leq \frac{n(1 - \epsilon)}{6}\right\] \leq&~\small\Pr\left\[X - Y \leq \frac{n(1 - \epsilon)}{6}\right\] \\ =&~\small\Pr\left\[n - (X - Y) \geq n - \frac{n(1-\epsilon)}{6}\right\] \\ =&~\small\Pr\left\[n - (X - Y) \geq \frac{(5 + \epsilon)n}{6}\right\] \\ \leq&~\small \frac{5n / 6}{(5 + \epsilon) n/ 6} = \frac{5}{5 + \epsilon} \end{align} where the last inequality is by Markov inequality and $\small \mathbb{E}\[n - (X - Y)\] = \frac{5n}{6}$.

---

Though the bound is weak, we can reduce it by repeating your algorithm multiple times (e.g., $\small \ell$) and then selecting the independent set with maximum size. The probability that the resultant size is still smaller than $\small \frac{n(1- \epsilon)}{6}$ then is at most $\small \left(\frac{5}{5+\epsilon}\right)^\ell$.
> 4 votes

---
Tags: algorithm-analysis, approximation, probabilistic-algorithms
---


# Question
Title: Can I say ≤ O(f(x)) rather than = O(f(x)) if the bound is not tight?
Suppose I just invented merge sort, but due to my limited ability was only able to prove that the running time is $O(n^2)$. However, I suspect that the running time is actually better (in reality it's $O(n \log n)$).

Technically in my paper I should say “runtime $=O(n^2)$”, but it’s somewhat misleading because people think I mean it's a tight bound (i.e. people generally think big O actually means big theta). Therefore, I am considering saying “runtime $\leq O(n^2)$”, even though it's technically redundant. Obviously I will explain in the text what I mean, but I'm saying it many times for different equations and I don't want to keep repeating myself.

I am aware of the definitions of big O, Omega, Theta, but which is clearer in a CS paper? The paper is related to machine learning.

# Answer
> 4 votes
> Technically in my paper I should say “runtime $=O(n^2)$”, but it’s somewhat misleading because people think I mean it's a tight bound

No, technically you should write "runtime $\in O(n^2)$".

> I am considering saying “runtime $≤ O(n^2)$”, even though it's technically redundant

I don't think "redundant" is the right word. In a way, it makes even less sense than "$= O(\\\_)$"

While you can not control your readers' misconceptions, you can try not to feed them. Why not make explicit what you mean?

> The running time is bounded by $O(n^2)$ but we suspect this bound can be improved to match the lower bound $\Omega(n \log n)$.

Or:

> We have thus shown that the running time is in $\Omega(n \log n) \cap O(n^2)$.

In formulae, my advice is to always use "$\in$" unless you can give more precise results. For instance,

$\qquad C(n) = 2n\log n - n \pm O(\log n)$

would be okay.

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


# Question
Title: Problem that is only solvable in a given space
I was wondering if a computational problem exists with the following properties:

* It should be solvable only having $K$ bytes of memory, or solvable with $K' \< K$ bytes of memory only in exponential time on $K - K'$ (or such an high degree polynomial in $K - K'$ that for any practical purpose the computation is unfeasible).
* The input to the problem should not be bigger than $O(\ln(K))$.
* The output to the problem should not be bigger than $O(\ln(K))$.
* The time complexity of the problem should be less or equal than $O(K \ln (K))$.

I have thought of many possible solutions but could always find a counterexample. Any sub-optimal suggestion or pointer is also very appreciated.

# Answer
This kind of question is studied in the cryptography literature under the name "memory-bound computation" or "memory-hard function". Such a function is one that can be computed efficiently using $K$ bytes of memory but takes much longer to compute if you have significantly less than $K$ bytes of memory. So, I suggest that you take a look at cryptographic constructions for memory-hard functions. It's an active area of research, and researchers focus more on practical complexity (concrete running time, not asymptotic running time) than on complexity theory, but you might find it useful.

See https://en.wikipedia.org/wiki/Memory\_bound\_function#Using\_memory\_bound\_functions\_to\_prevent\_spam for a high-level overview.
> 1 votes

---
Tags: complexity-theory, space-complexity
---


title: Arden's Lemma in case $X_{i}=AX_{i}$?

text:
# Question
Title: Arden's Lemma in case $X_{i}=AX_{i}$?
Arden's lemma is applied in cases where we have an equation that looks like this: $$ X\_{i}=AX\_{i} + B, $$ with the condition that $\epsilon \notin A$.

But if I have such situation: $$X\_{i}=AX\_{i},$$ so there's no B, or simply talking we have $B= \varnothing $, thus by the Lemma, we have $$X\_{i}=A^{\*}\cdot\varnothing$$ which equals to $$X\_{i}=\varnothing.$$

Is my reasoning correct?

# Answer
Your Reasoning is correct. The solution in this case is indeed $X\_i = \emptyset$.
> 2 votes

# Answer
What we have with

$\qquad X = AX + B$

is, quite literally, a *recurrence* of languages expressed in terms of the symbolic method. $B$ represents the *base case* of the recurrence. Arden's Lemma just tells you that the smallest fixpoint of this recurrence (read as an inductive definition) is $A^\*B$.

Now, if you drop the base case and only have

$\qquad X = AX$,

*there are no finite words* that can be constructed in this way. Now, the "recurrence" may make sense read as a coinductive definition (that is the solution would be an $X$ containing infinite strings) but not as an inductive one. Hence, the empty set is the only one that solves the equation.
> 5 votes

---
Tags: formal-languages
---


title: Inheritance problem (JAVA)

text:
# Question
Title: Inheritance problem (JAVA)
Here I have created 2 classes , $A$ is the super class of $B$ , i.e , $B$ inherits the features of class $A$.

Now I don't know exactly what statement (1) does but I am speculating as follows ,kindly correct me if I am wrong ,

An object of $B$ is created whose address has been assigned to the variable $ob$ of class $A$.

Now when statement (2) is called the $add$ function of the class $B$ is executed , but when statement (3) is executed it gives an error saying $e$ doesn't belong to $A$. Why is that ?

With my understanding , I thought statement (1) creates an object of class $B$ via its parent class $A$. Then why its object can't access its data member ? Can anyone explain ?

# Answer
> 1 votes
The variable $ob$ is an object reference variable of type $A$. As such, it can only reference those attributes and methods defined in $A$. The attribute $e$ is defined in $B$, not $A$, so $ob$ cannot reference $e$. It is okay to reference $add$ because it is defined in $A$, even though it is overridden in $B$.

---
Tags: java
---


# Question
Title: Can a queue automaton recognize palindromes?
Consider the language of even-length palindromes $L = \\{ WW^R \mid W \in \\{0,1\\}^\* \\}$. This language is surely context free and I need an NPDA to recognize it.

But, what if we replace the stack with a queue which supports insert and delete operations? Can a queue automaton accept $L$?

# Answer
The construction of a PDA except with a FIFO instead of a LIFO data structure attached can mimic any single tape TM as follows: it keeps the cell contents in the queue along with two special markers for the end of the tape and for the head of the TM. Every time you make a move, you just go through the entire queue and re-push everything you pop, making whatever slight modification in head position and tape contents you require.

So this is computationally equivalent to a Turing Machine, so in particular it can recognize $L = \\{ww^R \mid w \in \\{0, 1\\}^\*\\}$.
> 9 votes

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


# Question
Title: Theoretical CSPs where (in)equality constraints can be expressed as a single constraint?
I'm designing puzzles by running a MAX-CSP solver, and it works nicely in practice. For concreteness, my problems have the following form (in a pseudo-modeling language):

```
# set up vars & their domains
x_1 {1}
x_2 {0,1}
x_3 {0}
x_4 {0,1}
# constraints
(x_1 != x_2)
(x_2 = x_3)
(x_3 = x_4)
(x_1 != x_4)
(x_2 = x_4)

```

The objective is then to choose values from the domains of each variable so as to maximize the number of constraints satisfied.

More generally, in all of my instances, we have a fixed value of $k$. The domain of each variable is of size at most $k$. Every constraint involves two variables, and is an inequality or an equality constraint.

> When CSPs are studied from a theoretical viewpoint, is there a model that captures the above in a straightforward way?

# Answer
> 3 votes
In complexity theory, CSPs are usually specified as a set of allowed *predicates*. If the (finite) domain is $D$, a predicate of arity $d$ is an arbitrary subset of $D^d$ of allowed values. In particular, equality (or inequality) is a predicate of arity 2.

This is the point of view taken in Schaefer's dichotomy theorem as well as the more recent universal algebra approach (see for example a short survey by Libor Barto). Another example is the celebrated Raghavendra's theorem, which states that assuming the unique games conjecture, every CSP can be approximated optimally using semidefinite programming.

---
Tags: optimization, reductions, np-hard, constraint-satisfaction
---


# Question
Title: Complexity of shortest paths if paths have to use edges from different partitions
We are given a simple, undirected, weighted, incomplete graph $G=(V,E)$, where $V$ is the set of vertices, and $E$ is the set of edges. In addition, a collection of sets $S$ is given, which fully partitions $E$.

For any two vertices in $V$, I need to find the shortest path between them. The additional caveat is that no two edges which belong to the same partition may be in the path.

This has totally thwarted any polynomial algorithm I can think of. It confounds algorithms like Djikstra, because at any step during the process, it may be best to forgo the best available edge in favor of having a better choice still open in the future.

I've tried reducing it to the traveling salesman problem, and several others, but I can't quite get there. Proof-writing is not really my strongest suit. Any point towards proving this would be much appreciated.

EDIT: Yes, $S$ is a partitioning of $E$. This does seem to be perfectly analogous to rainbow graphs. Is it known that finding rainbow paths on an unweighted graph is NP-Hard?

# Answer
> 2 votes
If it helps, the problem you are trying to solve is looking for a "rainbow path" between the two vertices. It's a relatively new area of research, and there's now a book:

Rainbow Connections of Graphs X. Li and Y. Sun http://www.springer.com/la/book/9781461431183

Or here's an earlier paper: G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang. Rainbow connection in graphs. Mathematica Bohemica, 133(1):85–98, 2008.

The result you're looking for is likely in one of those places, something they cite, or something that cites them.

# Answer
> 0 votes
I don't have time to come up with and write out a full proof right now, but I can think of a reduction from 3SAT that I believe will work. Suppose we have $m$ variables $x\_1, \dots, x\_m$ and $n$ clauses $(a\_{i1} \vee a\_{i2} \vee a\_{i3})$, $1 \le i \le n$, $a\_{ij} \in \bigcup\_{1 \le j \le m}\\{x\_j, \bar x\_j\\}$. Basically, for each clause in the 3SAT instance, we make a gadget consisting of 3 paths, each containing $n$ edges and corresponding to a literal in the clause, as well as a source vertex that is connected to each of the 3 "leftmost" vertices of the paths and a target vertex that is connected to each of the 3 "rightmost" vertices of the paths. All these edges can be given unit weight. String these gadgets together "in series" -- that is, use the target vertex of the first clause's gadget as the source vertex of the second clause's gadget, etc. Finally, add an edge with huge weight between the very first source vertex and the very last target vertex. I believe that, after also constructing a partition $S$ of the edges as I describe below, the 3SAT instance will be satisfiable if and only if there is a path from the very first gadget's source vertex to the very last gadget's target vertex that is shorter than the path consisting of the single, huge-weight edge just mentioned.

The $j$-th path in the gadget for the $i$-th clause, $1 \le j \le 3$, will consist of the $n+1$ vertices $v\_{i,j,1}, \dots, v\_{i,j,n+1}$. The trick is to assign edges in these paths to parts in the partition $S$ in such a way that, if some clause uses an edge for some literal $x$, then *no* clause can construct a whole path for the negative of that same literal, $\bar x$: this will express the fundamental constraint of 3SAT, which is that no variable can be simultaneously TRUE and FALSE. (Note that $x$ may itself be a negative literal; $\bar{\bar x} = x$.)

To this end, notice that in order to build a path between the source and target of some clause's gadget, we need to use *every* edge on one of its 3 paths. So the core idea is: Each edge taken on the $x\_p$-path in some clause forbids some edge on the $\bar x\_p$-path in every clause that has such a path. Specifically, **the $k$-th edge on the $x\_p$-path in clause $i$ forbids the $i$-th edge on the $\bar x\_p$-path in clause $k$, and vice versa, whenever both edges exist**. We can achieve this by creating $mn^2$ parts $s\_{p,i,k}$ in $S$, with $1 \le p \le m$ and $1 \le i, k \le n$ and assigning:

* any edge $(v\_{i,j,k}, v\_{i,j,k+1})$ corresponding to a positive literal $x\_p$ to part $s\_{p,i,k}$, and
* any edge $(v\_{i',j',k'}, v\_{i',j',k'+1})$ corresponding to a negative literal $\bar x\_p$ to part $s\_{p,k',i'}$ (note the permuted indices).

Assuming that no variable appears more than once in any clause (if this actually happens, it can be easily remedied with standard techniques), from this construction it should be clear that at most one positive-literal edge and at most one negative-literal edge can appear in any specific part $s\_{p,i,k}$, so no $x\_i$-edge conflicts with any other $x\_i$-edge (in any clause), and no $\bar x\_i$-edge conflicts with any other $\bar x\_i$-edge (in any clause).

The remaining edges (which connect source or target vertices to path vertices) can all be put in additional singleton parts in $S$, which allows them to be chosen freely.

---
Tags: complexity-theory, np-complete, shortest-path, weighted-graphs
---


title: Lexicographically k-th small string

text:
# Question
Title: Lexicographically k-th small string
The origin problem is here. Now it is deleted.

Suppose I have 3 'available' copies of `a`, 2 of `b`, 3 of `c`, and 4 of `d`.

1. I want to know the number of different strings with length $l$ using these characters (but no more than the available copies).
2. Is there an efficient (i.e. $o(k)$) algorithm for computing the $k$-th smallest string of length $l$ in lexicographic order?

For example, The first string of length 1 is `a`, the second string of length 3 is `aab`, the 5th string of length 5 is `aaacc` (following `aaabb`, `aaabc`, `aaabd`, and `aaacb`), etc.

What kind of algorithm or math can I use to calculate?

# Answer
You are asking two questions. The first is an *enumeration* question, and the second is about *generation* or *encoding/decoding*. The enumeration question is a standard combinatorial exercise, which can be solved using exponential generating functions (and algorithmically, using dynamic programming). For example, the number of strings of length $\ell$ in your example is $\ell!$ times the coefficient of $x^\ell$ in the exponential generating function $$ \left(1 + x + \frac{x^2}{2!}\right) \left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!}\right)^2 \left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right). $$

For the generation problem, the idea is as follows. Suppose that we want the $k$th lexciographically smallest string of length $\ell$. We will uncover the letters one by one. To find the first letter, we count how many strings of length $\ell$ start with each letter—an instance of the enumeration problem mentioned above—and use this information to determine the first letter. We find the subsequent letters in a very similar way.
> 4 votes

---
Tags: algorithms, strings, permutations
---


# Question
Title: When should I learn artificial intelligence?
Straight to the point: I would really like to learn AI.

But I want some advice from experienced CS guys as to when I should jump into Artificial Intelligence.

What prerequisites are needed in order for me to better grasp the AI concepts?

# Answer
You will need some **discrete mathematics**. Graphs, trees, and so forth are the structures underlying AI.

You will need some **programming** skills, especially in languages such as Prolog and LISP. A lot of AI systems are programmed in these languages.

You will need some **logic**. Propositional and predicate calculus. Their syntax and semantics. Perhaps some modal logic. This will form the basis for learning about knowledge representation, which is the basis of AI.

During the first two years of a regular computer science degree, you usually obtain enough background to start studying AI.

But there is no limit to how complex AI can be. To get deeper into it, you'll need statistics, calculus, matrix algebra, and probably much more. Statistical learning theory (or more simply machine learning) depends on these areas.

My advice. Buy a book on Artificial Intelligence to read in your own time. A good one is Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig. Whenever you don't understand something, try to work out what background knowledge you are lacking. Then fill those gaps.
> 21 votes

# Answer
I would say right away.

Of course you'll need lots of different subjects, like the one Dave Clarke mentioned. Which ones you need really depends on which flavor of AI you go for. If you for towards the Machine Learning end of things, you won't need logic or discrete mathematics, but you will need big helpings of probability theory, statistics, linear algebra, optimization and multivariate calculus.

My point is that if you're learning these things in order to master AI, and not for their own sake, you'll need something to keep your motivation up. So I'd start just messing around. Instead of reading up on all this stuff, just try to write a chess player without any prior knowledge, or program a simple artificial life simulation. If you start on your own, it'll give you a context to place the stuff you'll learn later.

If you wait until you've completed all the subjects I mentioned above before you write your first AI program, you'll need a mighty resolve to hold on for the three years or so it takes to finish.

Once you've written a few toy programs, you can start with an overview book, to get tasters of all these subjects focused on AI. Russell and Norvig is a little heavy on the logic. Your best option depends on what subfields you're interested in. If you go for Machine Learning, then Tom Mitchell's "Machine Learning" is a good option.
> 5 votes

# Answer
While I agree with the other answers, as I myself and looking to become a student of modern AI, I think Mathematical knowledge is of paramount importance.

Take this YouTube lecture series from Stanford University for example. If you can get through the first 6 lectures and understand the mathematical concepts and notation that is presented to explain how and why algorithms like Logistic Regression, Bayesian, and Neural Network algorithms like SVM (Support Vector Machines) can be used to solve problems in a computer's knowledge gathering process, then you are ready to begin serious research - in my opinion.

If you find that you are lacking the fundamentals, then Courses like what are list below may be a good place to start:

1. Computer Science 1 and 2,
2. Data Structures,
3. Analysis of Algorithms,
4. 3 Calculus courses,
5. Discrete Math,
6. Linear Algebra,
7. Probability and Statistics,

Some may suggest Ordinary Differential Equations or an Analysis course - but this may be over kill. Though if serious research is your goal, then I recommend the over kill approach. Another interesting book recommended to me was "Superintelligence" by Nick Bostrom if you are just curious.

I also think so courses in Psychology, basic Neuroscience, Biology (How cells and micro-organism communicate) possibly even Sociology may not be bad investments of your time. It will help you understand **intelligence** in the larger sense. Genetic algorithms, for example, are modeled off of biological processes concerning how genes are passed down.

In the Sociological sense, how does a crowd think? Is it distributed intelligence or distributed stupidity, or both under certain circumstances? Can this provide guidance for new algorithms in the future? Doubtful, but hopefully you see my point.
> 0 votes

---
Tags: artificial-intelligence
---


title: How to prove with induction

text:
# Question
Title: How to prove with induction
So far I have learned how to write proofs by induction and it went fine until I got this recursive problem, which I'm not quite sure how to begin and how to prove that with induction.

```
            P(2·a,⌊b/2⌋) : b>1 and b is even number
P(a,b):=    P(2·a,⌊b/2⌋)+a : b>1 and b is odd number
            a :b=1

```

to prove is for all a,b ∈ N+ -\> P(a,b)=a·b

Please don't show me the proof but how to deal with this kind of question.

Thank you

# Answer
The first step is the basis step (or base case). For this problem, that is when $b = 1$. We identify that as the base case because $P(a, b)$ is a piece-wise function, and the non-recursive case is the base case. So prove that $P(a,b) = ab$ when $b=1$.

The inductive step will be a proof by cases because there are two recursive cases in the piecewise function: $b$ is even and $b$ is odd. Prove each separately.

The induction hypothesis is that $P(a,b\_0) = ab\_0$. You want to prove that $P(a,b\_0+1)=a(b\_0+1)$.

For the even case, assume $b\_0 \> 1$ and $b\_0$ is even. Then show that $P(a,b\_0+1)=P(2·a,⌊(b\_0+1)/2⌋)=a(b\_0+1)$. Prove this with a substitution based on the induction hypothesis.

After you complete the proof for the even case, do the same for the odd case.
> 0 votes

# Answer
In the recursive definition

$$ P(a,b) = \begin{cases} P(2a,\lfloor b/2 \rfloor) & b \> 1, b \text{ even} \\ P(2a,\lfloor b/2 \rfloor) + a & \text{if } b \> 1, b \text{ odd} \\ a & \text{if } b = 1 \end{cases} $$

the value of $b$ always decreases in a recursive call. Therefore you should prove the property $P(a,b) = a \cdot b$ by induction in $b$. We use the strong induction principle.

*Base case -* $b=1$: $P(a,1) = a$ and $a \cdot 1 = a$.

*Inductive step -* assume for all $k \< n$, prove for $n$:

Suppose $b$ is even. We then have $P(a,b) = P(2a,\lfloor b/2 \rfloor)$. Since $b$ is even, we have $\lfloor b/2 \rfloor = b/2$. Since $\lfloor b/2 \rfloor \< b$, we have by induction hypothesis that $P(2a,\lfloor b/2 \rfloor) = 2a \cdot \lfloor b/2 \rfloor = 2a \cdot b/2 = a \cdot b$.

Suppose $b$ is odd. Since $b$ is odd, we have $\lfloor b/2 \rfloor = (b-1)/2$. We now have $P(a,b) = P(2a,\lfloor b/2 \rfloor) + a = 2a \cdot (b-1)/2 +a = a(b-1) + a = a (b-1 + 1) = ab$.
> 0 votes

---
Tags: discrete-mathematics, induction, mathematical-analysis
---