title: DFS & BFS Spanning Trees

text:
# Question
Title: DFS & BFS Spanning Trees
I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one.

**DFS:**

My understanding that to the construct this DFS where each next is the cheapest one, the resultant spanning tree would be:

> {(a,c), (c,h), (h,g), (g,f), (f,b), (b,k), (k, j), (j,i), (i, l), (l,m), (m,e), (e,d)}

**BFS:**

My understanding that to the construct this BFS where each next is the cheapest one, the resultant spanning tree would be:

> Queue: a c d b e f h g k m i j k

Is my understanding of spanning trees correct when the next edge to be traversed should be the cheapest one? Is this a MCST?

# Answer
> 0 votes
You can construct a DFS spanning tree or a BFS spanning tree in many ways. You could require the next edge to be traversed should be the cheapest one available, if that helps in any way or if you just like to do that. As long as you are using DFS or BFS, you will end up with a spanning tree.

However, if you do want to always traverse using next cheapest edge among all possible choices, "Queue: a c d b e f h g k m i j k" for BFS should be "Queue: a c d b e f h g k m i j l", which is I assume a typo.

"Is this a MCST?" No, none of the two is a minimum cost spanning tree, which is more commonly called minimum spanning tree (MST). The DFS spanning tree, {(a,c), (c,h), (h,g), (g,f), (f,b), (b,k), (k, j), (j,i), (i, l), (l,m), (m,e), (e,d)} could have less cost if (g,f) is replaced by (c,f). The BFS spanning tree, {(a,c), (a,d), (a,b), (a,e), (c,f), (c,h), (b,g), (b,k), (e,m), (h,j), (k,l)} could have less cost if (b,g) is replaced by (h,g). As you can see, there is no guarantee that a MST can be obtained if you use a DFS or BFS.

In fact, for this particular graph, no matter how you conduct BFS or DFS, you will not end up with a MST.

---
Tags: graph-traversal, minimum-spanning-tree, spanning-trees
---


title: Why is superscalar processor SISD?

text:
# Question
Title: Why is superscalar processor SISD?
From Wiki - Superscalar processor:

> (Line 1): superscalar processor is a CPU that implements a form of parallelism called instruction-level parallelism within a single processor. In contrast to a scalar processor that can execute at most one single instruction per clock cycle, a superscalar processor can execute more than one instruction during a clock cycle **\*by simultaneously dispatching multiple instructions\*** to different execution units on the processor.

> (Line 8): In Flynn's taxonomy, a single-core superscalar processor is classified as an **\*SISD\*** processor (Single Instruction stream, Single Data stream)

I understand ILP, which means two instructions executed at the same time. My problem is that: If one doesn't fetch two instructions simultaneously, how can it dispatch multiple instructions to different execution units...? Or I misunderstand the meaning of instruction stream, which it's single stream but one can fetch two instructions at the same time, why sounds so counter-intuitive?

---

From Wiki - SISD:

> (Line1): In computing, SISD (single instruction stream, single data stream) is a computer architecture in which a single uni-core processor, executes **\*a single instruction stream\***, to operate on data stored in a single memory.

# Answer
There is a single instruction stream. Modern processors just manage to pick up multiple instructions from the instruction stream simultaneously.

For something like a POWER processor, where each instruction is always four bytes in size, that is quite easy. Instructions are loaded into cache lines, and if a cache line holds 8 or 16 instructions, it is quite easy to read four instructions at the same time.

For an x86 processor, it is more difficult because instructions have different sizes. Still, it is possible (with a lot of effort) to read several consecutive simple instructions simultaneously.
> 3 votes

---
Tags: computer-architecture
---


# Question
Title: Is there a software algorithm that can generate a non-deterministic chaos pattern?
Is there a software algorithm can generate a **non-deterministic** pattern or sequence? In Chaos theory, simple processes can create *deterministic* patterns, and psudo-random number generators can generate deterministic numbers with the same seed. Is there a software algorithm that can create completely non-deterministic patterns or sequences? Does it require hardware such as a quantum random number generator?

# Answer
No deterministic algorithm can generate a non-deterministic output.

A non-deterministic algorithm (e.g., a NDFA) could, but they exist only in theory, not in practice.

An algorithm with access to a random number generator can generate a random output, and therefore its output is not deterministic. For instance, in practice by reading from `/dev/urandom` or `CryptGenRandom()`, you can get random bits, which can be used to produce random output, or to seed a pseudorandom number generator. (You don't need a quantum random number generator to get random numbers.)

Chaos theory is pretty much irrelevant here.
> 3 votes

# Answer
D.W's answer is absolutely correct in the strict sense of how it's written. The key words are *"deterministic algorithm"*.

However and this is crucial, your question relates to *"software algorithm"*. We have to assume that software executes on hardware, and this is a computer forum after all. If you make this simple paradigm shift, then the answer becomes yes, there are software algorithms that are non deterministic.

In fact and in the general case, all running software algorithms are entirely non deterministic on the micro scale. The best that can be achieved is to put arbitrary bounds on the duration of processes as done in real time operating systems.

This all stems from the fact that there really is no such thing as digital or binary electronics. All electronics are analogue, even the machine you're using to read this. It takes a finite amount of time for a signal level to rise from a "0" to a "1". It then takes another finite period of time for the signal to pass from one side a circuit to another. Quantum, environmental, temporal and manufacturing parameters all affect the transition time. The notion of digital electronics arises from wanting only two predominant states, whilst trying to minimise the analogue ones.

Then you have to consider that a modern CPU is complicated. It doesn't just plod along running a single program. There is pipelining, parallel and speculative execution and multi level caching. And myriad other things that all interact and make exact microscopic prediction impossible. Language features such as garbage collection further obfuscate execution time.

All these factors mean that it is literally impossible to predict the execution time of a simple FOR/NEXT loop. You can safely predict that it might complete within 10 seconds, but not to picosecond accuracy. Hence chaotic behaviour.

Three examples exploiting this are the HAVEGE random number generator, the CPU Time Jitter Based Non-Physical True Random Number Generator and the chaotic (but pretty) pictures in Is von Neumann's randomness in sin quote no longer applicable?
> -1 votes

---
Tags: randomized-algorithms, nondeterminism
---


# Question
Title: Why do DFAs with a single final state have less power?
I came across this question in a test and I had to answer whether it is true or false.

> DFA with single final state has the same powers as DFA with more than one final state.

I was confused by what definition of "power" have they used. Generally, we always use power as a term to represent the class of languages a machine accepts and to me, it seems that since it is a DFA, regardless of the number of accept states, the power should be the same.

However, the question says that this is false and a DFA with more than one final state is more powerful. Is that true? I've never come across this in any textbook.

# Answer
> I was confused by what definition of "power" have they used. Generally, we always use power as a term to represent the class of languages a machine accepts

There are, equivalent or nonequivalent, definitions of "power" and "has power" in computation theory. Here is one definition of power that is suitable for the current situation.

A (descriptive) power means a set of languages over an alphabet. Given a set of automata $S$, the (descriptive) power of $S$ is $P(S)=\\{L(A)\mid A\in S\\}$, where $L(A)$ is the language accepted by $A$. Given two sets of automata $S\_1$ and $S\_2$, if $P(S\_1)=P(S\_2)$, we say $S\_1$ and $S\_2$ has the same power or $S\_1$ is as powerful as $S\_2$ or $S\_1$ is equivalent to $S\_2$ in power. If $L(S\_1)\subsetneq L\_{S\_2}$, we say $S\_1$ is less powerful than $S\_2$.

For a more rigorous definition, we should define the meaning of "$L$ is the language accepted by $A$". However, since that meaning is clear in the context of DFA and NFA, we will skip it here. Note that we only talk about "power" for a set of automata. When we compare powers, the same alphabet is usually implied.

> Since it is a DFA, regardless of the number of accept states, the power should be the same.

Take a moment to reflect. Are you sure you have seen or proved that claim? I would bet you have not, although there are many popular cases of different automata having the same power, such as NFA and DFA have the same power.

On the other hand, there are many cases where if you restrict some aspect of automata, you will decrease its power, which is of course reasonable. For example, if you restrict the stacks of PDAs to be finite, they become equivalent in power to finite automata. If you restrict (deterministic) PDAs to only have one or two states, you will get various powers depending on how PDAs are defined to accept (here are some result). If you restrict Turing machines to be read-only, they can be considered as two-way finite automata, which have the same power of the usual DFAs.

For an extreme example, if you change DFAs to DFAs with only one state, you will only have two DFAs, one DFA whose start state is not an accept state and one DFA whose start state is also an accept state, whose power is two languages, the empty language and the language of all words over the alphabet.

> DFA with single final state has the same power as DFA with more than one final state.

Final states are also commonly called accept states in the context of DFA or NFA. Fix our alphabet. Let $S\_n$ be the set of all DFA that have $n$ accept states, where $n\ge1$. We will show a more general proposition.

**(Less accept states, less power)**. $S\_n$ is less powerful than $S\_{n+1}$ for all $n$.

Proof. Suppose we have $A\in S\_n$. Let $A'\in S\_{n+1}$ be the same as $A$ except that $A'$ has one extra accept state that is not used by any transition. Since $L(A)=L(A')$, $S\_n$ is at most as powerful as $S\_{n+1}$.

Let $a$ be a symbol in the alphabet. Here is the beautiful example by Hendrik Jan. Let $K=\\{\lambda, a, a^2, \dots, a^n\\}$.

Suppose $K=L(B)$ for some DFA $B$. For the sake of contradiction, suppose both $a^i$ and $a^j$, where $i\<j$, are accepted by state $q$ in $B$. That means, given $j-i$ $a$'s, $q$ is transitioned to itself. So given another $j-i$ $a$'s, $q$ will be transitioned to itself again. And so on. That means, all strings $a^i, a^j, a^{i+2(j-i)}, a^{i+3(j-i)}, \cdots$ are accepted. That contradicts the fact that $B$ only accepts the $n+1$ strings in $K$. So all states of $B$ in which these words are accepted must be different. That is, $B$ must have at least $n+1$ accept states.

I will leave it as an exercise for you to construct a DFA with $n+1$ accept states that accepts $K$. Since $K\not\in P(S\_n)$ but $K\in P(S\_{n+1})$, we have proved "less accept states, less power".

---

Exercise 1. Show that DFAs with $n$ reject states have less power than DFAs with $n+1$ reject states for all $n\ge1$.

Exercise 2. Let $S\_{m,n}$ be the set of DFAs with $m$ accept states and $n$ reject states, $m+n\ge1$. Compare their powers.

Exercise 3. (Provided by Mr. Sigma) Show that NFAs with a single accept state have the same power as all NFAs.

Exercise 4. Show that NFAs with a single accept state and without $\epsilon$-transition have the same power as all NFAs.
> 9 votes

# Answer
Consider the regular language $a^\*\vert b^\*$. The accepting states for $a^\*$ and $b^\*$ must be different, because from the accepting state for $a^\*$ there's no transition with a $b$ to an accepting state, but from the accepting state for $b^\*$ there is one.
> 8 votes

---
Tags: automata, finite-automata, computation-models
---


# Question
Title: First Sets: If $A \to Ad\ |\ c$, what is $First(A)$?
Suppose that we have a grammar with the following rules:

$$S \to Aa\ |\ b\ |\ \varepsilon\\ A \to Ad\ |\ c$$

From looking at it I already know that $First(S) = \\{b, \varepsilon, c\\}$. My question is:

* How to determine $First(A)$?

For instance, by looking at the rule $S \to Aa$ we know that $First(S)$ must include $First(A)$. $First(A)$ already includes $c$ (that's why $c \in First(S)$). but how to handle the rule $A \to Ad$.

Just by applying the algorithm for finding the $First$ set blindly, I will have that $First(A)$ "includes" $First(A)$, which confuses me.

As far as I understand in $A \to Ad\ |\ c$ there is a left recursion. By eliminating it we get the following rules

$A \to cA'\\ A' \to dA'$

Does this mean that $First(A)$ only contains $c$?

Does this mean that I can ignore a rule with left recursion and just look at the other (non-recursive) rules under that variable?

Thanks!

# Answer
The grammar you have presented is left linear grammar. The production $A \rightarrow Ad$ in when transformed into $FM$, $A$ becomes state & an edge with $c$ terminal from $A$ to $A$ (self loop). So its clear for this particular grammar $First(A)$ is $c$.

Moreover, your approach is also correct or primarily correct.
> 1 votes

---
Tags: context-free, formal-grammars, compilers, parsers
---


# Question
Title: In RegExr, why is regex OR in JavaScript sometimes not commutative?
On https://regexr.com/, using the default JavaScript (Browser) engine, the languages $L(a^\*|b^\*)$ and $L(b^\*|a^\*)$ are not the same. The first one matches only $a$'s and the second one $b$'s.

Is this a bug? Or does the site something different than evaluating regular expressions, as I learned them in class?

# Answer
It is not a bug; it is rather the JavaScript RegEx engine tries to match as much of the first of the two expressions combined by the "|" operator as it can. Thus, instead of matching a word like "bbb" with as many "b"s as possible, it matches the pattern `a*` against the empty word (implicitly) at the beginning of "bbb". Granted, the RegExr interface does not highlight this properly, but that is more of a missing feature than a bug.

As mentioned in the comments, you should also be aware the engine tries to find (possibly) strings in the input text which *match* the pattern specified by the regex; the matches are what are highlighted by the RegExr interface. This is a different use of regexes than in formal language theory, in which regexes are used to specify formal languages, and in which an input (word) as a whole either matches the regex or not.

Caveat: If you are trying regexes verbatim from a formal languages class, you may run into trouble when trying to specify the empty word; the character `ε` is *not* interpreted as the empty word but as the Greek lowercase epsilon character instead. This question on SE contains some ways of correctly specifying (only) the empty word.

Warning number 2: If you write `L(a*|b*)` verbatim for your expression there, it is interpreted as a *capital $L$* followed by the pattern `(a*|b*)`, not as the language corresponding to the pattern `(a*|b*)`!
> 2 votes

---
Tags: regular-expressions
---


# Question
Title: Distribute a number of tasks into multiple days (scheduling)
This is about scheduling. I have N tasks of different length and I have to schedule them into M days. Indeed, each day has a max capacity (usually they are the same). Parameters are tight in the sense, that the sum of taks' length is exactly the same as the sum of day's capacity, e.g. tasks of total length 150 must be scheduled into days of total capacity 150.

Resource sharing is not involved, but the ordering of task is important. Idealy, for every j \> i, task Tj must be processed in the same day or later than task Ti. But then, the solution does not exist for the most cases. Thus, as few as possible tasks are allowed to be processed at most one day before a task with smaller index. If there is still no solution, as few as possible tasks are allowed to be processed at most two days before a task with smaller index, and so on.

This seems to me as an NP-hard problem. I have created an algorithm based on Binary Decision Diagrams, which performs an exhaustive search over all schedules but, of course, is quite limited by the size of the problem. I need a comparison with other solutions. Can you, please, suggest me some state-of-the-art approach to solve the given problem.

EDIT: I want to minimize *how much* the solution violates the natural ordering over *how many times* it violates the natural ordering.

# Answer
> 1 votes
Suppose that you have 200 tasks to be scheduled in 100 days. The capacity of each day is 4. Task 1 has capacity 1, task 200 has capacity 3, and tasks 2 to 199 have capacity 2.

In any solution, task 1 and task 200 have to be assigned to the same day. That means that there is a **big** violation of the ordering of the tasks. So even if you could solve your problem effectively, the best solution (which is indeed hard to compute) might still be very bad.

Even worse, *even if we totally disregard the ordering constraint*, there could still be no solution. Consider two days of capacity 7 and four tasks of length 2, 3, 3, 6, respectively. The total length is 14 = 2 $\times$ 7, yet there is no way to separate the tasks into two days of capacity 7. This problem (in which the precedences are not taken into account) is called the Partition problem, so that is one keyword you might want to search for. Unfortunately, checking if a solution to the Partition problem exists is a strongly NP-complete problem whenever you have 3 days or more.

---
Tags: algorithms, scheduling
---


title: About hardware multithreading

text:
# Question
Title: About hardware multithreading
I'm reading Multithreading (computer architecture) - Wiki, aka hardware threading, and I'm trying to understand the second paragraph:

> (p2): Where multiprocessing systems include multiple complete processing units in one or more cores, multithreading aims to increase utilization of **a single core** by using **thread-level parallelism**, as well as instruction-level parallelism.

while the link to **thread-level parallelism** says:

> (Link): **Thread-level parallelism (TLP)** is the parallelism inherent in an application that runs multiple threads at once. This type of parallelism is found largely in applications written for commercial servers such as ...

which is not so useful... So I read **task parallelism** above, since I guess TLP is a subtype of it:

> **Task parallelism** (also known as function parallelism and control parallelism) is a form of parallelization of computer code **across multiple processors** in parallel computing environments. Task parallelism focuses on distributing tasks—concurrently performed by processes or threads—**across different processors**.

Question: If thread-level parallelism is task parallelism, and task parallelism is for parallelization across multiple processors, how *increase utilization **of a single core** by thread-level parallelism* work?

Guessing: I guess for TLP, it should mean across multiple **logical** processors, i.e. hardware threads in the perspective of OS, correct?

---

Another minor issue is that for my first link, Multithreading:

> **In computer architecture, multithreading** is the ability of a central processing unit (CPU) (or a single core in a multi-core processor) to execute multiple processes or threads **concurrently**, supported by the operating system.

And in (p2) it *aim to increase utilization of a single core by using thread-level **parallelism***? What a contradiction.

# Answer
> 1 votes
It may be helpful to show the motivation for this kind of parallelism.

Compared to other components (such as memory access), computation, especially adding/subtraction, is cheap on chips. It takes very little space, relatively, to add another adder - and of course that adder could be used for address calculations as well as for actual arithmetic.

So more ALUs are easy to add. The problem is how to keep them busy. For instance, if you are calculating A+B+C then you need to work out A+B first and then add C to it. Nothing useful can be done with C until you have worked out A+B. So two ALUs don’t help and one is idle.

There is a lot that a CPU can do in terms of sorting out what calculation depends on what data. If a compiler emits code for “add A to B, store in X, add C to D, store in Y, add X to Y” then the chip itself can work out that the first two adds are independent of each other so can be executed simultaneously by two ALUs (but that the third add depends on the results of the first two).

But in many instruction streams there isn’t enough scope for such parallelism, because of the problem of having to wait for results. This is particularly annoying when memory access is involved because memory today is hundreds of times slower than it was in the 1980s, so there are long periods when everything may be idle waiting for memory data to arrive.

The hyper-threading solution is to run two unrelated instruction streams on the same core at the same time. Since they are unrelated, the data for one never depend on a result from the other, and while one is waiting for memory there is a good chance that the other will not be. The main cost is a doubling of the number of registers (one set of registers per instruction stream) but that is silicon area, not long-distance wiring, so it is cheap.

The threads in a core still share the same memory access mechanism, including the cache, so how well all this works does depend on what the instruction streams are doing. If they are both memory-intensive then they will get in each other’s way.

The term “multithreading” is incorrect for this kind of setup because multithreading means any way of accomplishing a goal by means of multiple threads, irrespective of the actual bits of hardware that execute the threads.

---
Tags: computer-architecture, parallel-computing, threads
---


# Question
Title: Counting the number of multiples of number A that perfectly divides the number B
What is the best way of counting the number of multiples of number A that perfectly divides the number B.

This is the sub problem for one of the questions I am solving on codechef. This is the best I could come up with.

```
int func(int A,int B){
    int res = 0;
    int i = 1;
    while(A * i <= B){
        if(!(B %(A * i))){
            res++;
        }
        i++;
    }
    return res;
}

```

However,this is timing out for some of the cases. I am told that this can solved in O(sqrt(n)). Any help would be appreciated.

# Answer
> 4 votes
Start by checking whether $A$ divides $B$. If it doesn't, we're done, the answer is $0$. If it does, let $C = \frac{B}{A}$. The numbers you're looking for are all of the form $AM$ where $M$ divides $C$, so all you need is the number of divisors of $C$.

Let $C=p\_0^{c\_0}...p\_n^{c\_n}$ be the prime decomposition of $C$. The number of dividers of $C$ is then $\prod\limits\_{i}(c\_i+1)$, so the problem boils down to the prime decomposition of $C$, which can indeed be done in $O(\sqrt{C})$:

```
residue = C
divider = 2
number_of_prime_dividers = 0
factors = empty array
while((residue >= divider) and (divider <= sqrt(C))
{
    if(divider divides residue)
    {
        number_of_prime_dividers = number_of_prime_dividers +1
        factors[number_of_prime_dividers] = 0
    }
    while( divider divides residue )
    {
        residue = residue / divider
        factors[number_of_prime_dividers] = factors[number_of_prime_dividers] + 1
    }
    divider = divider + 1
}
if(residue != 1)
{
    number_of_prime_dividers = number_of_prime_dividers +1
    factors[number_of_prime_dividers] = 1
}

```

This algorithm works because by construction, every time `divider`divides `residue`, then it means that `divider`is prime (if `divider` is composite then all the factors of `divider` are strictly smaller than `divider` and thus have already been removed from `residue`). Once we reach `sqrt(C)`, if `residue != 1` we know that `residue` is prime, which concludes the decomposition.

---
Tags: algorithms, coding-theory, mathematical-programming
---


# Question
Title: Reducing Independent Set to a problem to prove that it is NP complete
Given:

* A set of available customers $c\_1, c\_2, \dots, c\_n$.
* A set of available foods $f\_1, f\_2, \dots, f\_m$.
* Each customer will choose a subset of the available food.

Problem:

* Find the maximum number of customers that can be chosen, such that no two customers share the same food.

Question:

* How to reduce the independent set problem to this problem, in order to prove that this is an NP-Complete problem ?

# Answer
> 1 votes
Hint: try to reduce each vertex to a customer and each edge to an available food.

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


# Question
Title: LET REC recursive expression static typing rule
I'm taking a programming languages course and had a question regarding the typing rules for a recursive `let rec` expression in a static typing system.

To be more specific, we're using the textbook *Essentials of Programming Languages (3e) - Friedman & Wand*.

To give some rough background, here's how the author describes the typing rule for a normal `let` binding expression:

To briefly describe it for anybody unfamiliar with the notation, `type-of` is a function used to evaluate the type of the given expression.

According to the typing rule, we evaluate `exp1` first, which would give us type $t\_1$. Then we extend our current environment so $var$ is mapped to $t\_1$. Using this new environment, we evaluate the $body$ of the expression which gives us our final type.

Here's a typical `let` binding example in the OCaml programming language:

```
let func (x) = x + 1 in (func 3);; (* Outputs -: int=4 *)

let func = fun (x -> x + 1) in (func 3);;
(* Equivalent but better aligned with given typing rule. *)

```

Here's how a `let-rec` recursive binding's typing rule is defined:

The main problem that I'm having is how to understand the order of evaluation. According to the typing rule, it seems as though we're extending the environment first with $var$ and $p$, but where are we getting the types to map them to from?

# Answer
It seems you discovered the difference between a set of typing rules and an algorithm for type inference.

Typing rules only define a relation among 1) a type environment, 2) a term, and 3) a type. Their purpose is only to precisely define a mathematical relation $\Gamma \vdash t: \tau$.

Once we have such definition, we do not automatically get a type checking algorithm. That is, in general, there is no algorithm described by the rules which, given $\Gamma,t,\tau$, is able to test whether $\Gamma \vdash t: \tau$ holds. (In some cases, such an algorithm could even fail to exist!)

Similarly, we do not automatically obtain a type inference algorithm, which given $\Gamma,t$ is able to find a related $\tau$ (when it exists).

The type checking/type inference algorithm must be devised independently.

Now, it *is* true that in many cases the algorithms can follow the rules quite closely. The rule for non-recursive LET you mention is one nice example, since it is clear how to turn it into an algorithm. For recursive LETs, we are not that lucky.

A typical strategy to type check/infer recursive LETs is to introduce a fresh type variable in the environment, and then perform type checking on the body while generating a set of constraints. For instance, consider this example

```
let-rec f (x: int) = 1 + f(x) in f(0)

```

We discover immediately that `f : int -> ???`. Let's introduce a fresh type variable `R` for the result, and say `f : int -> R`.

We then type check `1 + f(x)` assuming the environment `f: int -> R , x: int`. Here `+` is applied to arguments `1: int` and `f(x): R`. Assuming `+` requires its arguments to be of the same type, this forces the constraint `int = R`. If `+` also returns the same type, we obtain another constraint `int = R` (redundant, in this case).

Finally, we solve the constraints, discovering `R = int`.

Note that in the general case we might be less lucky, since more complex types could be involved.

```
let-rec f(x: int) = (2, fst(f(x-1)))

```

Here, we discover `f: int -> R`, then we see that `R` must be a pair type `R = A*B`, then `A=int` (because of the `2`). Moreover, we get `f(x-1):R` so `fst(f(x-1)): A`, hence `B=A`. We conclude `f: int->(int*int)`.

It is not trivial to generate these constraints, or to solve them (usually through a *unification* algorithm). In the scientific literature we can find several algorithms which perform this, but they are not obvious at first.
> 6 votes

# Answer
Typing rules are not "code". There is no "evaluation order". All the rule is saying is: if we're given *some* $t\_{res}$ and $t\_{var}$ (and $t$ and $tenv$ and ...) such that the first two equations hold, then we can conclude the bottom equation. *How* you come up with the $t\_{res}$ and $t\_{var}$ is out of scope and not specified.

That said, often we *can* read these types of rules as programs, but they are *logic* programs. In this context, the answer to your question is easy: you simply stick logic variables everywhere. Unification will handle the data transfer in whatever direction is needed.
> 4 votes

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


# Question
Title: Shortest distance from multiple points to one point
I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v\_1,v\_2,\dots,v\_r$ be the nodes on a graph with distance $d\_1,d\_2,\dots,d\_r$ to the end node $v$. I want the shortest $d$ to $v$.

# Answer
> 2 votes
This is quite straightforward

* Reverse the direction of each edge.
* Apply single source shortest path algorithm with destination as the source.
* Reverse the direction again. (Optional, only if you want to preserve the originality of graph)

**Time Complexity**\- With graph given as adjacency list, it takes $O(E+V)$ to reverse the directions of each edge. With graph given as adjacency matrix, it takes $\theta(V^2)$. Rest you can apply any single source shortest path algorithm like Dijkshtra.

Note that a graph with reverse edges of original one typically called as **transpose** of the original graph.

# Answer
> 1 votes
Add a new vertex $s$ to your graph and give it an edge to each of $v\_1, \dots, v\_r$. Then use your favourite shortest path algorithm to compute the shortest path from $s$ to $v$. That path has length $1+\min\\{d\_1, \dots, d\_r\\}$.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: FInding the combination with the least number of elements from and array of integers, given an integer sum
I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm which doesn't find the optimal solution, however I'm having problems finding the optimal solution using dynamic programming.

The gready algorithm I've written is:

```
Function min_comb(array, value)
    min = 0
    for i in 1:length(array)
        if array[i] <= value
            min += floor(value / array[i])
            value = value % array[i]
        end
    end
    return min
end

```

which works fine for Example 1 below, but of course not for Example 2.

Example 1: If given an array $A=\[1000,500,100,20,5,1\]$ and a sum $S=1226$, the least number of combinations would be $N=6$ ($1000+100+100+20+5+1$).

Example 2: If given an array $A=\[4,3,1\]$ and a sum $S=6$, the least number of combinations would be $N=2$ ($3+3$).

How should I go about solving this problem?

# Answer
> 1 votes
Let $f(s, i)$ be the minimum number of elements (only the first $i$ elements of the array are considered) required to sum up to $s$, then we have $$f(s,i)=\min\_{0\le j\le s/A\[i\]}\left\\{j+f(s-jA\[i\], i-1)\right\\}.$$

You can use this formula to compute $f(s,i)$ for all $s$ and $i$. With knowing $f$, you can figure out the optimal combination. This is left as an exercise for you.

# Answer
> 0 votes
In general, the problem is very hard. In your special case where every number divides the next higher one, it is trivial. Even in cases like \[5, 2, 1\], You can prove an optimal solution doesn’t contain two 1s (because one 2 is better) or three 2s (because 5+1 is better) or 2+2+1 because 5 is better.

So you examine the numbers to find any such restrictions. Then you use the greedy algorithm which gives a lower bound for the number of integers you need, then do a systematic search.

In your example, you found a solution with six integers using the greedy method. you can take one 1000, but you can’t add another 1000 or 500. You must add 100 since 1000+4\*20 is too small. You must add another 100 since 1100+3\*20 is too small. Then you must add 30, then 5 and don’t have enough numbers. You can’t use two 500s because one 1000 is better. One 500 only lets you reach 900, and no 500 only lets you reach 500. Your solution is optimal.

In your second example the greedy algorithm uses 3 numbers. Starting with a four cannot improve, but 3+3 does.

---
Tags: algorithms, dynamic-programming, arrays, greedy-algorithms
---


# Question
Title: Strongly connected orientations of undirected graphs
I'm trying to prove the following.

> There exists a strongly connected orientation of a connected, undirected graph $G$ if, and only if, $G$ has no bridge.

(An orientation of an undirected graph is a directed graph made by replacing each edge $uv$ with exactly one of the directed edges $(u,v)$ and $(v,u)$; a directed graph is strongly connected if it contains a directed path from $u$ to $v$ for every pair of distinct vertices $u$ and $v$; a bridge is an edge whose deletion disconnects the graph.)

I can prove just one side. Assume that there is no bridge in the graph. So, for vertices $u$ and $v$, we can remove the edge which is between them and still there are(is) some paths(path) in the graph which we can reach $v$ from $u$ (so still the graph is connected). Because there is no bridge in the graph and every pair of vertices are reachable from the other without the edge of between them, we can convert the undirected graph to directed graph.

**how about the other side? how can I prove that?**

Can I say that, because the graph is undirected and it can be converted to a digraph, for each arbitrary pair of vertices $u$ and $v$ there is a path (or maybe some paths) which we can reach $v$ from $u$ and vice versa except the directed path of between them (the edge between them). So we can remove the directed path of between them. So there is no bridge edge in the graph.

# Answer
If $uv$ is a bridge then any orientation of $G$ either includes the edge $u\to v$ and has no path from $v$ to $u$, or vice-versa.

If $G$ has no bridge, then it is $2$-connected. A graph is $2$-connected if, and only if, it can be decomposed as $C\cup P\_1 \cup\dots \cup P\_k$ where $C$ is a cycle and each $P\_i$ is a path (possibly just a single edge) that intersects $C\cup P\_1\cup\dots\cup P\_{i-1}$ at both its endpoints and nowhere else. Now construct your strongly connected orientation from this decomposition.
> 3 votes

---
Tags: graphs
---


# Question
Title: Prove that the number of edges is at least twice the number of vertices
I need to prove that

> In a simple graph $G$, if all the $n$ vertices have a degree of at least $4$, then the number of edges is at least twice the number of vertices.

I already know that $\deg(n) = 2E$.

Then for the question $$\deg(n) \ge 4 = 2E$$

but then I couldn't solve further.

# Answer
> 3 votes
Hint: if you add up the degrees of all the vertices, you've counted each edge twice.

# Answer
> 1 votes
> i already know that deg(n) = 2E then for the question deg(n)\>=4 = 2E

Try to be as precise as possible. What is $E$ here? What is $\deg(n)$? Are you referring to the fact that $$ \sum\_{v \in V} \deg(v) = 2|E|, \tag{1} $$ where $V$ is the set of vertices and $E$ Is the set of edges? (Here $|E|$ means the size of set $E$, that is, the number of edges.)

> but then i couldent solve more

If you are stuck, a good place to start is the above equation (1). There is a $\deg(v)$ in that equation. What do you know about $\deg(v)$? There is also a $|E|$ in that equation -- that's good, because you are trying to show something about the number of edges. You want to relate the number of edges to the number of vertices. So, you should be looking for a way to use what you know about $\deg(v)$ to get something in terms of the number of verticies, $|V|$.

---
Tags: graphs, discrete-mathematics
---


# Question
Title: Maintaining data structure with two operations
I was trying to implement data structure over set of rectangles that can perform two types of operations.

1. Update operation, add new rectangle with sides parallel to x and y axis and positive coordinates to the set.
2. Query operation, for some rectangle check if there is some rectangle intersecting with this rectangle.

I don't have big knowledge of data structures so I was thinking if you could give me some hints how to start approach this problem.

Thanks in advance.

# Answer
You might want to look into R-trees (described in detail here) or a similar tree data structure for spatial indexing.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Decidability of factoring algebraic equations
Given an *arbitrary* algebraic equation, say for example the likelihood of the bernoulli distribution:

$$\prod\_{i}^{n}\theta^{x\_i}(1-\theta)^{1-x\_i}$$

And some *arbitrary* factorization constraints, say:

$$f(x)g(\theta)e^{\phi(\theta)^{T}u(x)}$$

Can I factor the equation into the form above where f, g, and phi are functions depending only on x, theta, or x respectively? This is something as humans we do all the time. The problem I gave above is an instance of "is this distribution in the exponential family", but of course there are simpler and less puffy versions of this:

Given the equation:

$$f(x,y,z) = x^2 + y^3 - e^{z}$$

Can I factor this into:

$$ f(x)\*g(y)\*h(y,z)$$

This feels undecidable to me. The tree of legal "algebra moves" from the root is infinite. If a program cannot find a solution in n moves, there is no guarantee that the solution is not at n + 1 moves, so I can't think of a halting condition. There doesn't even seem to be a good greedy solution to this, other than human intuition.

Any mathematica wizards out there know how to write a one liner to this?

# Answer
Interesting question. Factorization of functions, including factorization of polynomials is in fact a classical problem throughout history of mathematics.

For the sake of contradiction, assume that $$x^2 + y^3 - e^{z} = f(x)\*g(y)\*h(y,z)$$

For the sake of simplicity, assume that $f, g, h$ are continuously differentiable inside $D$, the place where we are interested.

Now treating $y$ and $z$ as constant, take partial derivative with respect to $x$. (Aha, you might say, why didn't I think of that?!)

$$2x = f'(x)\*g(y)\*h(y,z)$$

Since $2x$ is not constant, $f'(x)$ cannot be constant 0. Shrinking $D$ if necessary to make sure $f'(x)$ is never 0, we have $$2x/f'(x) = g(y)\*h(y,z)$$ That means, both $2x/f'(x)$ and $g(y)\*h(y,z)$ are constant functions since the former is constant w.r.t. to $y$ and $z$ and the latter is constant w.r.t. to $x$. So we will have $$ -e^z=\frac{\partial(x^2+y^3-e^z)}{\partial z} = \frac{\partial(f(x)\*g(y)\*h(y,z)}{\partial z}=\frac{\partial(f(x)\*\text{(some constant)})}{\partial z}=0$$ which cannot be true.

The above reasoning should give you a pretty good idea that particular factorization cannot hold nicely because of too many independences between the variables in the factorization. In fact, we can show that no such $f,g,h$ exist without assuming continuity of any of $f, g, h$, as long as it is required that equality holds for a small 3D space. Note that 2D space will not be enough since we can have, letting $x=0$, $$0 + y^3-e^z=1\*1\*(y^3-e^z)$$

It will require some work to formulate the more general questions of decidability of function factorizations clearly enough so that it might be able to have a clear answer. It looks like if many dependencies are required, then the set of problems is probably decidable. If you are interested enough, you could try formulating those problems and raising new questions.

For related result on polynomials, we can search for "decidability of polynomial factorization".
> 3 votes

---
Tags: computability, undecidability, polynomials, factoring, algebra
---


# Question
Title: How to calculate the minimum number of groups, by grouping groups with capacity together?
I need to group cars (and their passengers) with other cars, and I don't know how to approach this problem.

If I have, for example, 3 cars. Car A with 7 seats and 2 passengers (3/7 because of the driver). Car B, 2/2. Car C, 1/3. The most wasteful clustering would be \[A, B, C\]. But car C has room to pick up the driver and passenger of B, but no room for A, leaving us with \[A, C\]. Obviously, the best cluster would be one with only A because it has room to pick-up the other 2 cars. Now, this is a simple and small example, but how can I search for the minimum number of cars in samples with an arbitrary number of cars and passengers?

I tried to approach this problem in 3 different ways, but all fell short.

1. I thought about a maximum flow problem (image 1). But the maximum flow problem deals with capacities in edges of a graph. This specific problem has limitations on capacities of nodes/cars (not in its edges).

Maybe there's an adaptation of this method that I can use, but I couldn't think of any that would give me the list of groups that minimize the number of cars.

2. I also thought about the longest path problem (image 2). Every edge of my graph would be weighted by the number of people (driver + passenger) that would be picked-up if traversing to that node. And I could adapt the algorithm to decreased the capacity of the origin node accordingly with each node visited and stop that iteration if the max capacity was reached.

But to my understanding, I need to calculate the longest *simple* path (and not repeat any nodes) and that requires an acyclic graph. Given the context of my problem, most of the times there would be no way to turn my graph acyclic given that all the nodes would be strongly connected.

3. Lastly, I considered creating a list of trees (image 3). Where each root would be the origin car, and each child node would be a car that the root could pick-up. For each level of depth the available seats of the root would decrease until no more combinations existed. Then I would group trees' levels together and try to achieve the best combination and minimum of cars.

But at what level do I start. Does starting at the tree with the greatest depth and then grouping with other trees guarantee the minimum number of cars? Or is there a counterexample where grouping trees in their respective mid levels achieve better clustering? Do I just need to try every possible combination? That seems like an exhausting comparison and awfully inefficient.

I may be overlooking some characteristics of my problem, or maybe I'm just not comprehending the solutions I described. Is there a known solution to my problem, or maybe an adaptation I could implement? Any help or guidance is appreciated.

Thank you.

---

Edit:

u/gnasher729 mentioned the Bin packing problem in the answers which is indeed very similar to my problem.

Bin packing is calculated with bins of the same size. Given the context of my problem, my bins (cars) have different capacities.

With u/gnasher729 suggestions, the adaptation I came up with was:

1. Sort cars by remaining capacity first. Items weights are the size of the different groups of passengers.
2. Run the bin packing algorithm with bins of capacity equal to that of the car with more available seats.
3. Of the bin allocations produced by the algorithm, choose the bin with more items in it (meaning more groups of passengers were able to fit inside).
4. Remove the grouped cars (the bin + the items) from the sorted list and from the unplaced items.
5. Re-run the bin packing algorithm with the next emptiest car and with the remaining passenger groups.
6. Repeat until no more packing is possible.

It seems like it'll be an intense computation when given a large enough number of cars. If I have 20 cars with unknown passengers and unknown seats, and if I group 2/3 of those cars together with each iteration of the bin packing algorithm, then it'll be costly.

Is my adaptation wrong? Can i optimize it further?

# Answer
> 2 votes
The problem is NP-complete, because in the special case that all cars have the same capacity, it is just the bin-packing problem.

If car A has a higher capacity than car B, and you get an optimal solution (smallest number of cars) containing B but not A, then you can swap cars A and B, you won't need more cars, and because A has more empty capacity, you *may* fit the passengers from another car. So *which* cars you use in an optimal solution is obvious. You use cars sorted by capacity in decending order. So no matter what the numbers of passengers are, you would use the car with 7 seats, then the car with 3 seats, then the one with 2 seats. I assume you have groups of passengers you want to keep together, otherwise it is trivial.

You should be able to adapt any bin-packing algorithm to your situation. I can't see graphs being useful in any way.

---
Tags: graphs, trees, network-flow, clustering, group-theory
---


# Question
Title: Turing machine with semi infinite tape - Prove by construction
I'm studying constrained Turing Machines.

There's a theorem that proves that both infinite and semi-infinite tape TM have the same computational power. The theorem that proves this by emulating a TM1 with infinite tape with a multi-track tape TM2, where one track emulates the right part of the TM1 tape and the other track emulates the left part TM1 tape.

Could I emulate the infinite tape machine the following way:

* Let the alphabet of TM1 be `{0,1}`
* Construct a TM2 machine with semifinite tape to right with alfabet `{0,1} U {#}`
* Let `w = 011101`
* When execution starts, the tape looks like `|011101BBB...`
* The first step of TM2 should be to call a subrutine TM2 that shifts `w` on the tape `N` times to the right and puts `#` in the first position of the tape, so: `|#BB...011101BBB...`
* If during execution the control unit reads the `#` symbol, then call again the shifting subrutine.

I know this is not a formal prove, just an idea. I also know that this is not efficient nor an elegant construction but, could it work?

# Answer
> 1 votes
You are right. It is possible to shift the contents of the tape when needed.

The two track solution enlarges the alphabet $\Sigma$ to at least an alphabet $\Sigma\times \Sigma$ to store two symbols on each tape cell. That is quadratic. Your solution perhaps is more efficient in the number of symbols, since we merely have to move them into a new position.

A third proof might be to store the left and right cells of the tape (from an imaginary "middle") in the even and odd cells. That means the simulation would usually fins the next cell in two steps rather than one.

It is not always clear how to measure elegance of proofs :) sometimes a solution comes from a certain intuition, making it appealing.

---
Tags: turing-machines, proof-techniques
---


# Question
Title: Context sensitive language is context free
Problem of determining whether a context sensitive language is context free is undecidable.

How to prove it

# Answer
This can be done in a similar way to the proof that it is undecidable whether the language of a context-free grammar is regular. A general statement of such undecidability properties is Greibach's theorem observed by Sheila Greibach in 1968.

> Let $C$ be a family of languages effectively closed under union and concatenation with regular sets, and for which equality to $\Sigma^\*$ is undecidable (for sufficiently large $\Sigma$). Let $P$ be a proper subset of $C$, which contains all regular languages, and is closed under single letter quotient. Then membership of $P$ is undecidable for $C$.

So, we have to check whether the context-sensitive and context-free languages meet the criteria of Greibach for $C$ and $P$.
> 0 votes

---
Tags: undecidability, context-sensitive
---


title: What is Least-Constraining-Value?

text:
# Question
Title: What is Least-Constraining-Value?
In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are:

* Minimum-remaining-values (how many values are still valid for this variable)
* Degree heuristic (how many other variables are affected by this variable)
* Least-constraining-value (what value will leave the most other values for other variables)

The first two are pretty obvious and simple to implement. First choose the variable that has the least values left in its domain, and if there are ties, choose the one that affects the most other variables. This way if a parent step in the solver picked a bad assignment, you are likely to find out sooner and thereby save time if you choose the variable with the least values left that affects the most other things.

Those are simple, clearly defined, and easy to implement.

Least-constraining-value is not clearly defined, anywhere I looked. *Artificial Intelligence: A Modern Approach* (Russel & Norvig) just says:

> It prefers the value that rules out the fewest choices for the neighboring variables in the constraint graph.

Searching for "least-constraining-value" only turned up a lot of university slide shows based on this textbook, with no further information on how this would be done algorithmically.

The only example given for this heuristic is a case where one choice of value eliminates all choices for a neighboring variable, and the other does not. The problem with this example is that it this is a trivial case, which would be eliminated immediately when the potential assignment is checked for consistency with the problem's constraints. So in all the examples I could find, the least-constraining-value heuristic didn't actually benefit the solver performance in any way, except for a small negative effect from adding a redundant check.

The only other thing I can think of would be to test the possible assignments of the neighboring variables for each assignment, and count the number of possible assignments of the neighbors that exist for each possible assignment of this variable, then order the values for this variable based on the number of neighbor assignments available if that value is chosen. However, I don't see how this would offer an improvement over a random order, since this requires both testing numerous variable combinations and sorting based on the results from counting.

Can anyone give a more useful description of least-constraining-value, and explain how that version of least-constraining-value would actually yield an improvement?

# Answer
see this link:

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

It first picks variable "O" and then tests "O" with all of it's legal values "i" to see the number of reductions on "O"'s neighbors "N". It adds all of them. and picks an "i" that causes less reductions:

```
   sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
   For i from 0 to 9:
     plug "o=i" into the constraint formulas
     For each neighbor "N" of "o" in the constraint graph:
       sums[i] += the number of values remaining for "N"

```

It picks "i" so that:

```
sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}

```

I hope This can help you find your answer!
> 3 votes

# Answer
I think that the main thing here is that these heuristics are applied depending on the task for which the solver is written. And if there is a possibility that if the selected value of a variable does not leave a single value in the domain of another variable (let's say that we have heavily-constrained problem with only one solution), then the solution will come to a standstill. And a random search can go along the right path leading to a decision and the wrong one. And if it goes wrong, you will have to do backtracking (see conflict-directed backjumping), and it takes computational time. But the algorithm using LCV heuristics is more likely to go along a more correct path and no returns are required. But if there is underconstrained problem I think it will be much like random search. But I admit that my opinion may not be absolutely correct and this is only my understanding of the problem, since I do not have much experience with CSP.
> 1 votes

---
Tags: artificial-intelligence, constraint-satisfaction
---


# Question
Title: What are some concrete examples of what typed lambda constants are?
I was reading the following and found the following paragraph that I didn't understand:

> Let us also consider a set Σ of typed λ -constants, that is, pairs σ : t, where t is some type. Like for type assignments, we assume that Σ does not contain constants with multiple types and let Σ(σ) denote the type t such that σ : t ∈ Σ.

can I have some **concrete** examples of what lambda-constants are?

# Answer
> 1 votes
With the simply-typed lambda calculus, constants are typically basic datatypes. For example, here is a way to encode booleans in this presentation's notation: $$ \Sigma\_B = \\{ \mathrm{false} : \mathsf{bool}, \mathrm{true} : \mathsf{bool} \\} \cup \bigcup\_{T:\mathit{Type}} \big\\{ \mathrm{if}\_T : \mathsf{bool} \rightarrow T \rightarrow T \rightarrow T \big\\} $$ Note that we can't have a single “if” function: there needs to be one per type. To have a single “if” function that works with multiple types, you'd need to switch from the simply-typed lambda calculus to a typed lambda calculus with polymorphism. In the simply-typed lambda calculus, you have separate functions $\mathrm{if}\_{\mathsf{bool}}$, $\mathrm{if}\_{\mathsf{bool}\rightarrow\mathsf{bool}}$, etc.

The intended execution rules for these constants are $$ \begin{align} \mathrm{if}\_T \\: \mathrm{true} \\: M \\: N &\longrightarrow M \\ \mathrm{if}\_T \\: \mathrm{false} \\: M \\: N &\longrightarrow N \\ \end{align} $$ But the choice of reduction rules doesn't affect the type theory. (We normally do want them to preserve types, i.e. the subject reduction property.)

For the type $\mathsf{bool}$, the constants $\mathrm{true}$ and $\mathrm{false}$ are known as *constructors*: they're ways to build new values of this type. The constants $\mathrm{if}\_T$ are *destructors*: they're ways to take a value of this type and analyze it. Intuitively speaking, whenever a type is a ”data type”, it's defined by its constructors and destructors. An example of a kind of type that isn't a data type is function types, but even there you can think of lambda abstraction as a constructor for function types and application as a destructor. Constructors and destructors are a computational notion, not directly related to typing. (They do get related once you start viewing computation as a way to simplify typing proofs.)

Here's a second example with an encoding of signed integers ($\mathbb{Z}$). Note that this is just one possible encoding, a simple one from the typing perspective. $$ \Sigma\_N = \\{ \mathrm{0} : \mathsf{int}, \mathrm{S} : \mathsf{int} \rightarrow \mathsf{int}, \mathrm{P} : \mathsf{int} \rightarrow \mathsf{int} \\} $$ This particular signature defines three constructors: $\mathrm{0}$ (zero), $\mathrm{S}$ (successor) and $\mathrm{P}$ (predecessor). You may want to combine booleans and integers. For typing purposes you can just put them together, but for computational purposes it's useful to add a way to destruct an integer, e.g. by adding a comparison function. Here I've made the comparison function piggyback on booleans so that it doesn't need to be polymorphic. $$ \Sigma\_{BN} = \Sigma\_B \cup \Sigma{N} \cup \\{\mathrm{le} : \mathsf{int} \rightarrow \mathsf{int} \rightarrow \mathsf{bool} \\} $$

---
Tags: lambda-calculus
---


# Question
Title: What changes need to be made to a Turing machine to make them equivalent to a PDA, a DFA?
I believe in order to make a Turing machine have the same power as a DFA (by power I mean all languages which a DFA can decided so can the Turing machine) we just don't allow any use of backtracking or rewriting, that is you can only move right and read the string in the order it is presented.

To simulate a PDA however I am not sure what restrictions we could apply. I was thinking allowing backtracking but no rewriting on the tape may make a Turing machine with equivalent power to a PDA but I am not sure if that is a correct statement or how I would prove the equivalence of the two.

# Answer
The basic idea is simple. Just make a Turing machine behave like a DFA or PDA. There are multiple ways.

How to make Turing machines have the same power as DFAs?

* Here is a straightforward way as said in the question. We will not allow them to write on the tape. We will only allow them to read the input in one direction. In that way, they literally become DFAs.
* In fact, we do not have to regulate how they read the input. We can simply use read-only Turing machines, which are equivalent to DFAs in power.

How to make Turing machines have the same power as PDAs?

* Let us consider Turing machines with two tapes. One read-only tape with the input, which can only be read sequentially. Another tape that will be treated as a stack. Now you can see they are literally PDAs.
* Suppose we are interested in simulating each PDA individually. The existence of such a TM is proven here.

There are many type of PDAs, such as deterministic or nondeterministic, accepting by final states or empty stack, even various generalized version. It should not be too difficult to see how they can be simulated by Turing machines.

"Allowing backtracking but no rewriting on the tape may make a Turing machine with equivalent power to a PDA." No, it does not. As mentioned above, read-only Turing machines are equivalent to DFAs in power. Here is the explanation from Wikipedia. The proof involves building a table which lists the result of backtracking with the control in any given state; at the start of the computation, this is simply the result of trying to move past the left endmarker in that state. On each rightward move, the table can be updated using the old table values and the character that was in the previous cell. Since the original head-control had some fixed number of states, and there is a fixed number of states in the tape alphabet, the table has fixed size, and can therefore be computed by another finite state machine. This machine, however, will never need to backtrack, and hence is a DFA.
> 0 votes

---
Tags: turing-machines, automata, pushdown-automata
---


# Question
Title: How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal?
How does the language $L=\\{a^nb^mc^nd^m \mid n \geq1, m\geq1\\}$ abstract the problem of checking that the number of formal parameters in the declaration of a procedure agrees with the number of actual parameters in a use of the procedure?

I simply didn't get what each of the variables $a,b,c,d,n$ and $m$ will represent? Seems $1^{st}$ pair $(n,m)$ is for formal parameters and later for actual. But I didn't get why there are $a$ and $b$? Couldn't only single variable be ample?

# Answer
> 2 votes
The language

$$L=\\{a^nb^mc^nd^m \mid n \geq1, m\geq1\\}$$

abstracts agreement of parameter and argument count for the case where there are exactly two *procedures*, one with $n$ parameters, declared with $a^n$ and used with $c^n$, and the other one with $m$ parameters, declared with $b^m$ and used with $d^m$. Each procedure is called exactly once and the calls are interleaved with the declarations. The interleaving makes it impossible for a context-free grammar to specify agreement.

One might be tempted to generalize to more uses of each procedure:

$$L'=\\{a^nb^m\omega \mid n \geq1, m\geq1, \omega \in \\{c^n,d^m\\}^\*\\}$$

or more procedures (I'm not going to try writing that one out), but it just serves to make everything more complicated to no purpose.

The simple example is easily proven to not be context free, and the simplification can be justified by observing that context-free languages are closed under substitution which is a very powerful and useful proof technique. (The fact that declarations and uses can be reduced to repetition of a simple symbol is also justified by substitution. A starting point for Algol-style languages might be to remove all the parameters/arguments from a declaration/call, leaving only the commas and parentheses. For S-expressions it's even simpler.)

So the abstraction provides a simple proof (as well as some intuitive basis) for why parameter/argument agreement cannot be incorporated into a context-free grammar.

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


# Question
Title: What's the time complexity bound for the Knapsack with real weights?
Let's start with the formalism:
Let $W$ be the total weight of our bag, $1,...,n$ be our elements, $w\_1,...,w\_n$ their corresponding weights, and $v\_1,...,v\_n$ their corresponding values.

As is known, the knapsack problem for integer weights can be solved by dynamic programming (or equivalently, using recursion + memoization), with time complexity of $\mathcal O(nW)$, where $W$ is the total weight our bag can hold, and $n$ is the number of items.

However, for real numbered weights, the algorithm fails (just imagine a billion items with weight $\<1$, and $W=1$). We probably can round them in a clever way and then scale them up to be integers again, but that'd blow the size of the problem up in an inacceptable way.

Another approach would be to use recursion instead of dynamic programming, because the idea behind the algorithm still works out - either the $n$'th item is in the optimal solution, or not.

However, even with memoization, we can easily choose our weights in a way so that all sums $$\sum\_{ \begin{align} i&\in M\\ M&\subseteq \\{1,..,n\\} \end{align}} w\_i$$

are distinct, leaving us with $2^n$ weight-sums to memoize.

Is there any optimal algorithm that manages to keep the time complexity pseudopolynomial?

# Answer
> 1 votes
If you have n random real numbers, then you have 2^n possible real sums. If your knapsack has size S, you would expect 2k different sums in an interval $S-k\cdot 2^{-n}, S+k\cdot 2^{-n}\]$, in other words calculating sums with a precision of $k\cdot 2^{-n}$ isn't enough to give the optimal sum.

With random integers, you can find an optimal sum because of the $2^n$ possible sums, there will be gazillions getting the same result. You wouldn't be able to list *all* choices that fill the knapsack exactly because there are to many of them, but you can find *one*.

You can most likely solve the problem "find items that fit in the knapsack, and have a total size at most eps less than the optimal size".

# Answer
> 0 votes
I don't know if you read the book

> Algorithm Design - Jon Kleinberg, Eva Tardos

you can read this(at Extension: The Knapsack Problem pag 271) :

> Using this recurrence, we can write down a completely analogous dynamic programming algorithm, and this implies the following fact

Thats help to maintain the pseudopolinomial time in $\Theta(nW)$ time.

You have other resource about knapsack - approximation in the book, that maybe can help you.

I hope that help.

---
Tags: knapsack-problems
---


# Question
Title: Sorted unsigned integer intervals tree structure
The goal is to store **sorted unsigned integer intervals** that can overlap only in the boundaries, e.g., `|0–10|10–50|100–110|110–200|`. This structure will be created by some **insert operations** (the order matters) in the start and than **queried** by a lot of queries. The query is specified by **interval** and the result is all intervals from structure that has at least a partial overlap.

There is no need to delete inserted data (delete operation), but the new inserted interval can overwrite the existing ones. Please consider the following example.

1. `|0–10|10–50|100–110|110–200|`
2. insert: 40–70
3. `|0–10|10–40|40–70|100–110|110–200|`
4. insert: 105–115
5. `|0–10|10–40|40–70|100–105|105–115|115–200|`

What structure do you recommend?

# Answer
> 0 votes
Interval trees seem like a natural candidate. The Wikipedia page has links to implementations in various languages. You can overwrite an existing interval by querying its endpoints, then removing the resulting intervals on the left and right, and then adding back the truncated intervals together with the new one.

# Answer
> 0 votes
As Mr. Sigma suggest you, you need to use a B+ tree structure. time to insert new value is $\Theta(th)=\Theta(t\log \_{t}n)$

Check this one for implementation

https://www.geeksforgeeks.org/b-tree-set-1-insert-2/

---
Tags: intervals
---


# Question
Title: What is the average search complexity of perfect hashing?
The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?

# Answer
> 6 votes
Yes, but in complexity theory, $≤O(1)$ only means $O(1)$ i.e. constant time.

# Answer
> 1 votes
Given any set $X \subseteq \mathbb{R}$, you have

$\qquad \displaystyle \min X\ \leq\ \frac{1}{|X|}\sum\_{x \in X} x\ \leq\ \max X$.

Therefore, average runtime is always bounded above by worst-case runtime. Denoting an asymptotic upper bound by "$\leq O(f)$" is abuse of notation, but will be understood.

To be more precise, you should say: upper bounds of worst-case runtime are upper bounds on average-case runtime, that is

$\qquad \displaystyle T\_{\text{wc}} \in O(f) \ \implies\ T\_{\text{ac}} \in O(f)$.

The reverse does not hold, that is *lower* bounds on the worst-case runtime do not carry over:

$\qquad \displaystyle T\_{\text{wc}} \in \Omega(f) \quad\not\hspace{-.75em}\implies\ T\_{\text{ac}} \in \Omega(f)$;

a well-known example for this is Quicksort. Of course, bounds can be transfered from average-case to worst-case in the opposite way.

You have to be careful, however, if the worst-case upper bound is an *amortised* one. Then, a certain sequence of operations is assumed, whereas average-case bounds assume a certain input distribution (often uniform). The two are not necessarily comparable, so amortised upper bounds do not necessarily bound the average case.

# Answer
> 1 votes
In algorithm complexity analysis theory, O(1) means the algorithm computes the answer independently of the number of elements -- for the particular case of a perfect hash algorithm, the "number of elements" is relative to the possible keys it may be presented to.

However, such algorithms still have a complexity in regard to the length of the key present. So, the worst case will happen for the bigger key -- but will still be O(1) in regard to the number of possible keys. Conversely, the best case will happen for the smaller key, but will still be O(1).

So, both worst and best cases will have O(1) complexity, even if their computation time is (slightly) different.

---
Tags: complexity-theory, time-complexity, asymptotics, hash-tables
---


title: Finding small-length RSA private key

text:
# Question
Title: Finding small-length RSA private key
I was wondering if there is an algorithm to derive $p$ and $q$ or is it simply trial and error?

> Consider the following RSA crypto-system with public key $(437,13)$. Since the numbers are so small, it is possible to break the crypto-system and determine the private key. What is the value of the two primes $p,\\,q$ with $n=p\times q$ used in the key generation.
>
> Hint: You may ignore the value $13$ in your computations.

The answer is $23$ and $19$ but I was wondering if there is an algorithm for it?

Thanks!

# Answer
> 2 votes
Of course there’s an algorithm for it. Trial division is an algorithm, a very straightforward one.

# Answer
> 0 votes
Divide the odd target number by 3, 5, 7, and 11 to see if they are factors.

Then beginning with the number 11, increment with the values of 2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10 as continuing and repeating .

Finally, divide the odd target number by each incremented number to see if one of them is a factor. Continue dividing by the incremented numbers up to the square root of the target number if no factors are previously found.

One note, I found the increments that produce a sequence of odd numbers with multiples of 3, 5, and 7 removed just by working logically with a sequence of odd numbers. However, the increments can also be determined using Wheel Factorization formulas. But I think it is faster to increment with 48 hard-coded array values than to compute.

---
Tags: cryptography, encryption
---


# Question
Title: Does any parser ever parse non deterministic unambiguous context free grammar?
I have been informed parser parses unambiguous context free grammars of $DCFL$.

I was wondering if there could be a parser which could make a parsing table for unambiguous grammars of $NCFL$?

Note: This has been discussed here briefly in comments.

# Answer
> 2 votes
There are a number of general parsing algorithms (Earley, GLR, GLL, etc.) which can handle arbitrary context free grammars, even ambiguous grammars. (For ambiguous grammars, an entire parse forest is produced, usually as a spaghetti-like graph structure, because grammars can produce an infinite number of parses, or an exponential number if null cycles are removed.)

What these parsers cannot do is parse any grammar in time linear to the length of the input. It could take up to cubic time, although GLR parsers can parse unambiguous grammars in quadratic time even if the grammar is non-deterministic. (In practice, GLR parsers tend to be close to linear time for typical applications, because the grammars are "mostly" deterministic and unambiguous.)

---
Tags: compilers
---


# Question
Title: Reducing optimization problem to its decision version
There are two problems that need to be solved. Both problems use a compatibility matrix $C$, where $C\[a, b\]$ is how compatible students $a$ and $b$ are.

(1) Given an $n \times n$ compatibility matrix $C$ for $n$ students, and $r$ rooms with sizes $s\_1, s\_2, \dots, s\_r$, where $n$ is the sum of room sizes, and a target $A$; determine if there is some assignment of the students to the rooms with average compatibility value at least $A$.

(2) Given an $n \times n$ compatibility matrix $C$ for $n$ students, and $r$ rooms with sizes $s\_1, s\_2, \dots, s\_r$, where $n$ is the sum of room sizes; find an optimal assignment of the students to the rooms.

These two problems seem to be hard to solve efficiently. Not surprisingly, your manager asks you to write programs to solve the two problems. As usual you have no idea how to write such programs. For both problems, you find an efficient program on the Internet that solves that problem. Unfortunately your budget will only allow you to buy one such program.

15. Assume that you have a program that solves the second problem in time $\Theta(n^j)$, for $j ≥ 1$. Can you use it to solve the first problem in polynomial time? If so, how, and how fast is your algorithm?
16. Assume that you have a program that solves the first problem in time $\Theta(n^k)$, for $k ≥ 1$. Can you use it to solve the second problem in polynomial time? If so, how, and how fast is your algorithm

I understand how to do problem 15, but for problem 16, I have no idea.

# Answer
> 2 votes
Use binary search on the target $A$, finding the maximal value for which an assignment of average compatibility $A$ exists.

I'll let you work out the resulting multiplicative overhead (which depends on the magnitude of the numbers involved).

---
Tags: algorithms, reductions
---


# Question
Title: Mathematical modelling on Christofides algorithm
Does a mathematical modelling on Christofides algorithm exist, is it even possible to create one?

# Answer
> 0 votes
The mathematical model relevant for understanding Christofides' algorithm is not the algorithm itself but rather the problem it is trying to solving – the traveling salesman problem. This is a model for optimization problems which occur in practice.

Christofides' algorithm itself could also perhaps be considered a model, if it is supposed to represent the way that humans (or animals, or nature) solve the traveling salesman problem. But in fact, it doesn't – it was designed as an efficient algorithm for computers.

---
Tags: traveling-salesman
---


# Question
Title: Graph theory: determining maximum number of edges
Based on the question below, can someone please explain to me the reasoning behind why the maximum number of edge is 5/2|V|? I don't find the particular reasoning in the solution to be that helpful for why the maximum number is 5/2|V|.

# Answer
The following identity is well-known: $$ 2|E| = \sum\_{v \in V} d(v). $$ In words, if we sum all degrees in a graph, we get twice the number of edges. To see this, divide each edge $(x,y)$ into two halves: the $x$-half and the $y$-half. We think of the $x$-half as a half-edge labeled $x$. The left-hand side counts the number of half-edges. On the right-hand side, $d(v)$ counts the number of half-edges labeled $v$, and so in total, the right-hand side also counts the number of half-edges.

If the graph has maximum degree $\Delta$ (in your case, $\Delta = 5$) then $$ 2|E| = \sum\_{v \in V} d(v) \leq \sum\_{v \in V} \Delta = \Delta |V|, $$ and so $|E| \leq (\Delta/2) |V|$; there is equality if the graph is $\Delta$-regular (all degrees are exactly $\Delta$).
> 1 votes

---
Tags: graphs
---


# Question
Title: Smallest possible sorting network for given permutation
I need to build a sorting (comparator) network using comparators for a specific permutation on a set $x\_1, \dots, x\_n$. The solution should not be a general sorting network that sorts every permutation. I should build the smallest possible sorting network for the given permutation (the depth of the network should be $O(\log n)$).

I am really unsure about how to approach this problem. I thought I might go through the permutation and if the number is in the correct spot then leave it, if not then place a comparator with this number as input and the number that should be here as the second input. But I don't think that the depth of such network would be $O(\log n)$. So how would I go about building the needed network?

# Answer
For concreteness, let us assume that $x\_1,\ldots,x\_n$ are numbers between $1$ and $n$, and that a comparison puts the smaller number at the smaller index.

Consider first the case in which $n$ is even. We divide $x\_1,\ldots,x\_n$ into two halves: $x\_1,\ldots,x\_{n/2}$ and $x\_{n/2+1},\ldots,x\_n$. Let us call a number *misplaced* if it is in the wrong half: that is, a number in the first half is misplaced if it is in $\\{n/2+1,\ldots,n\\}$, and a number in the second half is misplaced if it is in $\\{1,\ldots,n/2\\}$. Note that the first half contains as many misplaced numbers as the second half (why?). Using one round of parallel comparisons, you can exchange the locations of the misplaced numbers, and guarantee that $\\{x\_1,\ldots,x\_{n/2}\\} = \\{1,\ldots,n/2\\}$, and similarly $\\{x\_{n/2+1},\ldots,x\_n\\} = \\{n/2+1,\ldots,n\\}$. Now recursively sort each half, in parallel.

When $n\>1$ is odd, we use the same strategy, dividing the array into two unequal halves, say the first half larger than the second by one element.

As an illustration, suppose that we are given the array $$3,4,2,6,1,5$$ We switch $1$ and $4$ to obtain $$3,1,2,6,4,5$$ Now we recursively sort $3,1,2$ and $6,4,5$.

In order to sort $3,1,2$, we first exchange $1$ and $3$ to obtain $1,3,2$, and then sort the two halves $1$ and $3,2$ in parallel, which means to exchange $2$ and $3$.

Sorting $6,4,5$ is completely analogous.
> 1 votes

# Answer
Well instead, here is a testing of a logic for a "sorting network" as columns left-to-right:

3 2 2 2 1

2 3 3 1 2

4 4 1 3 3

1 1 4 4 4

or

3 2 2 1

2 3 1 2

4 1 3 3

1 4 4 4

or

3 3 2 2 1

2 2 3 1 2

4 1 1 3 3

1 4 4 4 4

and

3 3 2 2 2 1 1

5 2 3 3 1 2 2

2 5 5 1 3 3 3

1 1 1 5 5 5 4

4 4 4 4 4 4 5

or

3 3 2 2 1

5 2 3 1 2

2 5 1 3 3

1 1 5 4 4

4 4 4 5 5

or

3 3 2 2 1

5 2 3 1 2

2 1 1 3 3

1 4 4 4 4

4 5 5 5 5

The idea being that the intermediate sorts must have purpose. So this edited post, and suggestion of a structure, is now more like a question because it says "or" between sets of examples.
> 0 votes

---
Tags: algorithms, sorting
---


# Question
Title: How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?
Like in the title the following equation:

1. $F(n)=F(n-1)+F(n-2)+f(n)$, with $F(0)=0, F(1)=1$
2. $f(n)=f(n-1)+f(n-2)$, with $f(0)=0, f(1)=1$

I don't know how to solve this. The $f(n)$ is basically just $F(n)$, but then I have $$F(n)=F(n-1)+F(n-2)+F(n) \Rightarrow F(n-1)+F(n-2)=0$$ and I cannot go anywhere from this.

# Answer
$f(n)$ is the well-known Fibonacci sequence.

Let $\alpha=\frac{1+\sqrt5}2$ be the golden ratio and $\phi=\frac{1-\sqrt5}2$. It is shown here that $$f(n)=(\alpha^n-\phi^{n})/\sqrt5$$

---

Gnasher729 conjectured that $F(n) \approx 0.72 * n * f(n)$. Following that clue, we can find the following identity holds for all cases we tested by trial and error. $$F(n)= nf(n) - (n-2)f(n-2) + (n-4)f(n-4) - (n-6)f(n-6) + \cdots$$ where the sequence of summands goes on as long as the summand makes sense.

---

How to prove that long formula? We can observe it implies for $n\ge2$, $$ F(n) = nf(n) - F(n-2).$$

Let us prove that simple recurrence relation of $F(n)$ by induction on $n$.

The base cases when $n=2$ and when $n=3$ is easy since f(2)=1, f(3)=2, F(2)=1+0+1=2 and F(3)=2+1+2=5.

Suppose it is true for $n\le k$, where $k\ge3$. $$\begin{aligned} F(k+1) =& F(k) + F(k-1) + f(k+1)\\ =& (kf(k) - F(k-2)) + ((k-1)f(k-1) - F(k-3)) + f(k+1)\\ =& k(f(k)+f(k-1))-f(k-1) - (F(k-2)+F(k-3)) + f(k+1)\\ =& kf(k+1)-f(k-1) - (F(k-1)-f(k-1)) + f(k+1)\\ =& (k+1)f(k+1)- F(k-1)\\ \end{aligned}$$

Now that we have proved that simple recurrence relation of $F(n)$, it is immediate to prove that long formula, which can also be stated succinctly as

$$F(n)=\sum\_{0\le i\lt n, i\text{ even}}(-1)^{i/2}f(n-i)$$

---

Interested readers may enjoy the following exercises, roughly in the order of increasing difficulty.

Exercise 1. Given the above formulas for $f(n)$ and $F(n)$, show that $F(n)=\Theta(n\alpha^n)$.

Exercise 2. Given the above formulas for $f(n)$ and $F(n)$, show that $$\lim\_{n\to\infty}\frac{F(n)}{n\alpha^n}= \frac1{1+\alpha^{-2}}\approx 0.7236$$

Exercise 3. Find a close formula for $F(n)$.
> 1 votes

---
Tags: recurrence-relation, recursion, discrete-mathematics
---


# Question
Title: Amortizing or batching circuit evaluation for many different inputs?
Suppose that I have a boolean function of size $k$ with $n$ inputs. I would expect to be able to evaluate it on all possible inputs in time $O(k\*2^n)$ simply by calculating all the intermediate values for every possible input. Is it possible to do this faster in general, for example in time $(k+2^n)$?

In the special case of linear functions I would expect to be able to do this by going from point to point in gray code order, so that only one bit changes each time, or by calculating tables of size $1,2,4,8,\dots,2^n$ for the functions produced by holding the last $n-i$ bits at zero, using each table to calculate the next one. Are there generalizations of this for general boolean circuits, or are there proofs that no such generalizations are possible?

I have a slightly off-the-wall motivation for this. I am interested in the simulation hypothesis. One reason for running a large number of simulations would be to investigate the result of running the same scenario for all possible inputs.
I would be interested to learn that there was, or was not, a significantly more efficient approach which would achieve the same ends, especially as such a more efficient approach would not have a direct link between any particular set of simulated histories and any particular act of the program, as the increased efficiency of the program would be mean that it could not be the case that every possible history could be mapped to its own set of program activity.

Edit - batch calculation as described above is more powerful when the batch step is used inside a recursive call, as then you don't need to go through all 2^n answers at once. For #P-complete problems, each recursive call returns the number of solutions found within some range of values. For NP-complete problems, each recursive call returns whether a solution is found in some range of values.

Each recursive call uses the batch mechanism to compute the answers for 2^k different problems. This corresponds to k bits of the n bits available. So the lowest level of the recursion just looks at 2^k different results to see whether they are solutions or not, but the highest level looks at 2^k results which are each e.g. the number of solutions found within 2^(n-k) evaluations, each with the k top bits of n set to a different value. Here I assume that the language used to express our function f() is sufficiently flexible that level i+1 can treat level i as just a function f() to consider at 2^k points, even though this f() amounts to a transformation of the original f() producing a function which counts the number of solutions in a particular range or says whether this number is non-zero.

If the cost of level i+1 of the recursion is X\_i+1 = b + a\*X\_i then for a!=1 we get X\_i = a^i + b/(1 - a) and for a=1 we get X\_i = ib (with variations depending on what X\_0 is). Remember that the number of possible solutions examined at each level is 2^(ik) so for small a compared to 2^k this is a large speedup, and for the case of a=1 we would find that P=NP and even P=#P.

(I remain interested in answers that would firm this up or extend this)

# Answer
> 1 votes
Some further thoughts, at least for the case when batch generation is done by feeding a gray code or other simply generated sequence into a circuit with internal memory.

For an ordinary combinatorial logic circuit without memory, we can bound the size of a circuit needed to evaluate a general function on n bits in two ways: by providing a general construction with known size, or by observing that 2^2^n different functions require 2^2^n different circuits, so the size of the largest circuit encountered cannot be so small that there are less than 2^2^n different circuits of up to that size. Knuth Vol 4A section 7.1.2 Theorem L shows that these bounds are in fact very close together, and require a circuit of size O(2^n/n) for a general function on n bits. So combinatorial logic circuits without memory do not waste much complexity by having many different circuits computing the same function.

If we stick to the design of a gray code generator feeding a circuit with internal memory, the only source of variation is the choice of the circuit, which now includes memory elements. The description of such a circuit needs a few more bits per item to offer the possibility of memory elements, but this is just a constant factor. By the requirement that to be able to compute any of 2^2^n different functions we must provide 2^2^n different circuits, and by the observation that ordinary combinatorial logic circuits do not have staggering inefficiencies, I think we find that introducing internal memory into an otherwise pedestrian design will not allow all possible functions to be calculated using only circuits of size significantly smaller than their best combinatorial logic implementation.

(but if P=NP our simulator has other options, such as Valiant Approximate Counting, which allow them to estimate the fraction of input states leading to a particular outcome in a simulation, without actually simulating all possibilities).

I remain interested in any comments, pointers, or whatever, about anything that bears on this.

---
Tags: algorithms, complexity-theory, circuits
---


# Question
Title: Why do many developers continue to rely on pseudo-random number generators?
Although hardware based “true” random number generators are available, software-based pseudo-random number generators still remain the predominant method for generating random numbers in use today. Why do developers continue to rely on pseudo-random number generators?

# Answer
> 3 votes
Pseudo-random number generators and "true" random number generators serve different purposes, though there are some areas where they can overlap.

Pseudo-random number generators are useful when you need a large sequence of bits that appear to be uniformly distributed (or sometimes distributed other ways) that can be deterministically generated. "Unpredictability" is usually unimportant in these applications. In fact, it's often useful to use quasi-random number generators which are even more predictable. Being deterministic is often a valuable, if not critical, benefit. It means that you can easily repeat a specific sequence which is good for debugging and replication among other things. For example, if I want to replicate a database query that involves (pseudo-)"random" numbers, I can just ship a seed to the replicas and they can replay the transaction rather than requiring that I ship the entire sequence of numbers generated. It's also nice that pseudo-random number generators don't require any special hardware or anything at all beyond the ability to compute.

"True" random number generators are used when you need unpredictability, usually in an adversarial (and particularly security) context. You need some "secret" that you know that no one else knows even if they know everything about how you think and could predict anything you could do if they knew what you were observing.1 Producing entropy is time-consuming though. Most of the time, if a large number of "random" bits are needed, a source of entropy will be stretched using cryptographic pseudo-random number generators. Even doing this, hardware instructions take on the order of hundreds of cycles and are usually slower than optimized (non-cryptographic) pseudo-random number generators. If you don't need bits that are unpredictable by an adversary, there is usually little reason to use "true" random numbers.

1 Bits of "true randomness" are powerful things. Being able to "flip a coin" provides solutions to problems that are otherwise unsolvable.

---
Tags: pseudo-random-generators
---


# Question
Title: In the shor's quantum circuit, what is the transformation of the modular operating gates?
I know different parts of this circuit, just I have a problem with that part that I circled in picture. I want to know the function of that part. If you have useful information about it, please share it with me. Thank you so much.

# Answer
It's a modular multiplication gate. It permutes the states such that, for all $k$ below $N$, state $|k\rangle$ becomes state $|k \cdot c \pmod{N}\rangle$ where $N$ is the number being factored and $c = b^{2^{2n-1}} \pmod{N}$ is a classically computed constant and $b$ is the base value chosen randomly at the start of the algorithm.
> 2 votes

---
Tags: algorithms, quantum-computing
---


# Question
Title: Clarify the steps: what happened in this mathematical modelling of TSP?
Source: http://examples.gurobi.com/traveling-salesman-problem

I don't get this part: (look at the source)

> $$\sum\_{i,j\in\\{1,2,3\\},i\neq j} x\_{ij}=3\>2=|\\{1,2,3\\}|-1$$

I get that $x\_{ij}$ is equal to 3, but why the "\> 2" ?

And what is the deal with subtracting 1 from a set? How do you even do that?

How come $|\\{1,2,3\\}|-1 = 3 \> 2$ ?!?

Okay so: $$|\\{1,2,3\\}|-1 = 2$$

So how is he allowed to write: $$|\\{1,2,3\\}|-1 = 3 \> 2$$

?

That is basically the same as writing: (which is incorrect right?) $$2 = 3 \> 2$$

I don't get this part at all, please elaborate on what happened in as simple language as possible. My level is high school final math level.

# Answer
The point of these constraints is eliminating subtours, which the source explains quite clearly. So for every subset $S$ of the nodes, such as $\\{1,2,3\\}$, they add a constraint which says $\Sigma\_{i,j \in S, i \neq j} x\_{ij} \leq |S| - 1$. So when this constraint is satisfied, there is no way to form a cycle on the vertices in $S$.

Now, if this constraint was *not* satisfied (i.e., the number of edges was at least $|S|$), then a cycle could be formed like they show in their figures. For example, on $\\{1,2,3\\}$, you can form a triangle (which is a cycle) if you use 3 edges.

Particularly regarding your confusion, note that they have written $|S|-1$ (and not $S-1$). Here, $|S|$ refers to the size of the set $S$ (also known as the cardinality of $S$), so $|\\{1,2,3\\}| = 3$. Further, notice that they don't write $2 = 3 \> 2$, but instead $3 \> 2 = 3 - 1$. If it's clearer, you can also assume the constraint just says $3 \> |\\{1,2,3\\}| - 1$.
> 2 votes

# Answer
You seem to have misunderstood pretty much every part of the statement

$$\sum\_{i,j\in\\{1,2,3\\},i\neq j} x\_{ij}=3\>2=|\\{1,2,3\\}|-1\\,.$$

> I get that $x\_{ij}$ is equal to 3,

No, the sum of all values $x\_{ij}$ where $i$ and $j$ are distinct values from $\\{1,2,3\\}$ is equal to $3$.

> but why the "\> 2" ?

Because three is bigger than two.

> And what is the deal with subtracting 1 from a set? How do you even do that?

No, it's subtracting one from the *cardinality* of the set. Notice the $|\dots|$.

> How come $|\\{1,2,3\\}|-1 = 3 \> 2$ ?!?

It isn't. When we write something like $A=B\>C=D$, it means that $A=B$, $B\>C$ and $C=D$. You can't just re-order the terms and expect the statement to remain true, just as you can't reorder $3\>2$ as $2\<3$ and expect it to remain true.

So, the statement as a whole means:

* The sum of the values $x\_{ij}$ is equal to $3$.
* Also, $3\>2$.
* Also, $2=|\\{1,2,3\\}|-1$.

> So how is he allowed to write: $$|\\{1,2,3\\}|-1 = 3 \> 2\\,?$$

He isn't and he doesn't.
> 3 votes

---
Tags: traveling-salesman, notation
---


# Question
Title: How to minimize the average distance between pumps and cities?
There are `n` cities \[1, 2, 3, .... n\] and `k` available pumps. These pumps can be installed in `k` cities. The cities are all in a straight line.

How do I need to install these so that the *average distance between the cities and the nearest pumps* is minimized?

What I am thinking is that dividing is this:

Suppose there are 6 cities `[C1, C2, C3, C4, C5, C6]` and 3 pumps `[P1, P2, P3]`.

I divide the array of cities equally -\> `[C1, C2] , [C2, C3] ..` and then each block gets one pump.

Then again break that `[C1,C2]` and let `C2` have the pump. Same way `C4` and `C6`.

So basically recursively calling and assigning the city a pump. Is this the right way to approach this problem?

# Answer
> 1 votes
Minimizing the *average* distance is equivalent to minimizing the *sum* of the distances, so let me work with that formulation of the problem.

Hint #1: When $k = 1$, the pump should be located at the *median* of the positions of the cities.

Hint #2: When $k \> 1$, you can use a dynamic programming approach. Let $f(i, j)$ be the optimal cost of serving cities $1,...,i$ with $j$ pumps. Your goal is to compute $f(n, k)$. Now observe that $$ f(n,k) = \min\_{i=1,...,n} \left( \sum\_{i': i \< i' \le n} d(\text{city}\_{i'}, \text{pump}\_k) + f(i,k-1) \right), $$ because if the rightmost pump (pump number $k$) serves cities $i+1$ through $n$, then the total cost is the sum of distances of those cities to pump $k$, plus the optimal cost of serving cities $1$ through $i$ with $k-1$ pumps. Here $\text{pump}\_k$ is the position at the median of cities $i+1,...,n$.

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


title: Sorting in a Priority Queue

text:
# Question
Title: Sorting in a Priority Queue
Does a priority queue `Queue<K,V>` always sort its elements based on the value of each element or its key?

I know than the priority in the queue is based on the key, and that the element with the highest priority has the minimal key (Correct me if I am wrong) But I am not sure about wether the pq sorts based on value.

# Answer
> 1 votes
The definition of a priority queue is that elements will be dequeued in order of priority. The definition says nothing about the order of items of equal priority so an implementer can do anything, within reason, and still be justified in calling the resulting structure a priority queue.

# Answer
> 0 votes
Think about something like this:

```
 [(1,item1),(2,item2),(2,item3)]

    add (10,item4):

    [(1,item1),(2,item2),(2,item3),(4,item4)]

    dequeue
    [(2,item2),(2,item3),(4,item4)]

    add (1,item5)

    [(1,item5),(2,item2),(2,item3),(4,item4)]

```

The value would have nothing to do , the elements will be stored depending on its queue. (that was my final reasoning)

---
Tags: algorithms, data-structures, sorting, priority-queues
---


# Question
Title: Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$
The language was $L =\\{a^n b^{n+1} : n\geq0 \\}$.

This is my attempt:
I believed $L$ can also be expressed as:
$L =\\{a^n b^{n}b : n\geq0 \\}$
This implies that the number of $b$'s is always greater than the number of $a$'s. Thus, the complement is $L' =\\{w: w\in\\{a,b\\}^\*: n\_a(w)\>n\_b(w)\\}$ or $L' =\\{w: w\in\\{a,b\\}^\*: n\_a(w)\geq n\_b(w)\\}$.

# Answer
> 1 votes
Once we've fixed the alphabet, the complement is simply the set of all strings over that alphabet that don't have the form $a^nb^{n+1}$. Presumably, here, the alphabet is $\\{a,b\\}$. Again, once the alphabet is fixed, there is only one complement. You've given two and it's unclear whether you mean "I'm not sure which of these answers is right" or "It's the set of all strings that are either like this or like that."

In fact, neither of your two answers is correct. The complement also includes the string $abbb$, even though it has more $b$s than $a$s.

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


# Question
Title: How to traverse a graph in reverse with dfs
So I'm watching Stanford's algorithm lectures and I'm on Kosaraju's algorithm. In the lecture, the algorthm was given in 3 steps: calculate the graph with all arcs reversed, run dfs on reversed graph, run dfs on original graph. Then an optimization was given, which was to instead of using the naive implementation of remaking the entire graph with the arcs reversed, you can instead run dfs on the original graph but going backwards along the arc instead of forward, which simulates running dfs on the reversed graph.

The lecturer made it seems so simple to do this and gave no further explanation. I'm completely stumped on how you can achieve this. Can someone give me some help or point me in the right direction?

# Answer
> 1 votes
Just take the code for DFS and, every time it says "If there is an edge from $x$ to $y$", replace that with "If there is an edge from $y$ to $x$."

# Answer
> 0 votes
> You can instead run dfs on the original graph but going backwards along the arc instead of forward, which simulates running dfs on the reversed graph.

This depends entirely on how you're storing your graph.

Let's say you use an adjacency matrix $M$ where $M\[x, y\] = 0$ means no edge between the nodes $x$ and $y$ and $M\[x, y\] = n$ means an edge from $x$ to $y$ with weight $n$ (use 1 instead of $n$ if you don't have weights along your edges)

Let's say during the DFS on the reverse graph, you're at a node $a$ and you have to look at $a$'s neighbors (along reversed edges). To check if $b$ is a neighbor of $a$, you can simply check if $M\[b, a\]$ is nonzero.

---
Tags: algorithms, graph-traversal
---


title: Optimality of A* search

text:
# Question
Title: Optimality of A* search
I use the A\* search algorithm to to search for the shortest path from S to G.
The evaluation function is $f(n) = g(n) + h(n)$.

Since node A and B have the same estimated total cost, I choose to go node A.Then, the $f(n)$ of B is 8, C is 7, G is 10. After expanding C, $f(n)$ of G is 7. Therefore, the path is S-A-C-G with total cost 7.

However, there is a lower cost path S-B-G with $f(n) = 6$. Is the path S-A-C-G still optimal or I did the search in the wrong way?

# Answer
The A\* algorithm requires that its heuristic function $h(n)$ is **admissible** for all $n$, meaning that it should never overestimate the (unknown) true cost from a node to the goal. This assumption appears to be violated in your example for nodes $S$, $A$, and $B$. Only for $n = C$ and $n = G$ is the heuristic function $h(n)$ admissible, but it should be for **all** nodes.

This is why the algorithm seems to be resulting in suboptimal paths for you.

A good example of an admissible heuristic function in 2D environments is often the Euclidean distance (straight-line distance). Unless you start involving strange things such as teleportation, this heuristic is always admissible (you can never get anywhere faster than by following a straight line). Although in your drawing, it seems like this wouldn't work. It doesn't look like your drawing was drawn "correctly". Some short paths seem to have higher costs than longer paths (visually).
> 1 votes

---
Tags: search-algorithms, artificial-intelligence
---