# Question
Title: Minimize number of DFS searches in a graph
I got a weird homework question about graph.

A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed however the helicopter won't know beforehand. Once the the helicopter lands on a house u, they can drive to any neighboring house v if the road (u,v) is not destroyed. The rescue team would only know if a road (u,v) is destroyed or not after they arrive at either u or v. They also don't know the number of safe roads in advance. Design a strategy to minimize the number of **helicopter landings**, also the plan needs to have less than 2n trips along the safe roads.

My thinking is to do a DFS search on a random unvisted node. After the DFS is done, if there are still unvisited nodes, then do another DFS search from a random unvisited node again. Repeat this until all the nodes are visited. However, I don't know how to prove that this minimize the number of searches. Can anyone help me? Thanks!

# Answer
> 1 votes
Your approach is pretty good.

---

Instead of the word "search", I would prefer "traversal" or "tour".

Here is your strategy/algorithm in slightly different terms.

1. Choose a random unvisited house $h$ to land the helicopter.
2. The rescue team visits all houses connected to $h$ according to a depth-first traversal by driving along safe roads.
3. If there is another unvisited house, which must not be connected to any visited house by a path of safe roads, go back to step 1. Otherwise, stop.

Does the strategy above minimize the number of helicopter landings? Well, for each landing, all houses that can be visited are connected by paths of safe roads. So the number of landings must be at least the number of connected components. The strategy above makes one helicopter landing per one connected component.

---

The next issue is to make sure that a depth-first traversal of a set of $k$ connected houses will make no more than $2k-1$ trips, where a trip means reaching a house from another house by a single safe road.

Here is how we would perform the traversal recursively starting from one random landing at house $h$.

Input: a house $h$.
Output: a series of houses to be passed starting at $h$.
Procedure depth\_first\_traversal ($h$):
$\quad$output $h$
$\quad$marked $h$ as visited
$\quad$for each unvisited house $i$ connected to $h$ by a safe road:
$\quad$$\quad$call procedure depth\_first\_traversal ($i$)
$\quad$output $h$

The depth\_first\_traversal($h$) above will output each node exactly twice, once when it has just been visited and once when all houses connected to it by a safe road have been visited. The number of trips made is one less than the number of the houses passed, i.e., $2k-1$.

# Answer
> 1 votes
Your problem has two clauses:

A) Given a set $V$ of houses, decide on the set of existing edges $\\{(u,v)\\}$ with a minimal amount of queries (=helicopter landings), when a single query $Q(v)$ reveals all the edges $(v,u)$.

B) Given a graph $G=(V,E)$, find a path that visits all vertices, that traverses at most $2n$ edges.

---

The connectivity problem A has a trivial solution of $O(n)$, which under the model you describe can be easily bounded below by an adversary argument, showing it is also optimal.

Consider the following adversary:

* Choose arbitrary $v\_k$ that was not queried before.
* Given query $Q(v\_i)$:
    + If $i$ has been asked before, answer accordingly
    + If $i$ is new and $i \neq k$ answer that $v\_i$ is only connected to $v\_k$
    + If $i$ is new and $i = k$ answer that $v\_i$ is connected all previous vertices connected to $v\_k$ through previous phase, **and** to a new vertex $v\_j$. Set $v\_k \leftarrow v\_j$

It is clear any query connects **at most** $1$ vertex (beside the very first), so regardless of the order of queries an algorithm makes, it must make **at least** $n-1$ queries to reveal the set of edges, and the connectivity status of the graph.

It follows the naive algorithm of asking all vertices for neighboring edges is also optimal.

---

The traversal problem is simple; find a spanning tree of $G$ (denoted by $T$), after its been revealed by your helicopter. To visits all vertices, do an euler-tour on $T$. Since $T$ has $n-1$ (or less, if it's a spanning forest and $G$ is not connected) edges and an euler tour visits each edge twice, you visits all vertices at the maximal cost of $2n-2$ edges.

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


# Question
Title: Prove disprove an existence of mapping reduction between 2 sets
I am currently studying mapping reduction in computational theory and finding it hard to grasp the concept fully.

For reference, consider the following given WHILE-Prog sets:

A = { (p.d) | p doesn't halt on input d } = Complementary HALT set. B = { p | p halts on exactly one input (the input is unknown) }

Is A \< B. meaning, is there a mapping reduction from A to B?

---

Can someone suggest a hint?

knowing that A belongs to coRE did not help much. B doesn't seem to belong to either RE nor coRE.

# Answer
One basic idea is to observe that $B$ looks harder than $A$ since

* we need to run a given Turing machine on one given input in order to find whether the pair is in $A$ but
* we may need to run a given Turing machine on infinity many inputs in order to find whether it is in $B$.

That observation should motivate us to find a reduction from $A$ to $B$.

---

Suppose $(p,d)\in A$. Construct a machine that behaves as the following.

Upon an input string $s$, it checks whether $s$ is $d\sigma$, where $\sigma$ stand for a fixed letter in the alphabet.

* If yes, it halts.
* If no, it checks whether $s$ is $d$.
    + If no, it loops forever.
    + If yes, it simulate $p$ on $d$.

It should be routine to verify the construction above is indeed a reduction from $A$ to $B$.
> 0 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Maximize number of museums visited in a day
Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day.

Suppose that no time is needed in order to travel from one museum to another. Tourist cannot, of course, be in two different museums at the same time.

For example, if given:

```
+-------------+-------+--------+-------------------+
|   Museum    | Opens | Closes | Duration of visit |
+-------------+-------+--------+-------------------+
| Louvre      | 08:00 | 16:00  | 01:00             |
| Hermitage   | 08:00 | 15:00  | 01:00             |
| Uffizi      | 09:00 | 18:00  | 04:40             |
| Rijksmuseum | 10:00 | 21:00  | 02:20             |
| Vatican     | 08:00 | 15:00  | 05:30             |
+-------------+-------+--------+-------------------+

```

One itinerary maximizing number of museums visited would be:

```
Vatican 08:00 - 13:30
Hermitage 13:30 - 14:30
Louvre 14:30 - 15:30
Rijksmuseum 15:30 - 17:50
    ---> Total No. of museums visited: 4

```

Also, this itinerary would also be valid:

```
Uffizi 09:00 - 13:40
Hermitage 13:40 - 14:40
Louvre 14:40 - 15:40
Rijksmuseum 15:40 - 17:40
    ---> Total No. of museums visited: 4

```

There is no preference over different itineraries having the same number of museums!

## *Things I have tried:*

# **Greedy algorithm**

For the sake of simplicity, let us consider the following table:

```
+-----------+-------+--------+-------------------+
|  Museum   | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Louvre    | 08:00 | 10:00  | 02:00             |
| Hermitage | 08:00 | 11:00  | 01:00             |
| Uffizi    | 08:00 | 11:00  | 03:00             |
+-----------+-------+--------+-------------------+

```

Based on Interval scheduling, I tried first sorting this list by earliest museum visit finishing times (i.e. by *time museum opens* \+ *duration of visit* sum):

```
+-----------+-------+--------+-------------------+
|  Museum   | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Hermitage | 08:00 | 11:00  | 01:00             |
| Louvre    | 08:00 | 10:00  | 02:00             |
| Uffizi    | 08:00 | 11:00  | 03:00             |
+-----------+-------+--------+-------------------+

```

and then "greedily selecting" the next visit, which gives only:

```
Hermitage 08:00 - 09:00

```

while the optimal itinerary would be:

```
Louvre 08:00 - 10:00
Hermitage 10:00 - 11:00

```

I have also tried sorting the list using different combinations of criteria (opening/closing time, shortest/longest time needed to visit, etc.) to no avail, thus concluding that the greedy algorithm approach is probably not suitable.

---

# **Dynamic programming**

Given that we have to "place the maximum number of visits" in "a container of fixed length", i.e. a 24-hour day, it seemed to me that this problem is a variation of the Knapsack problem.

I have tried solving for an optimal itinerary for some $k$ museum visits, where $0\leq k\leq$ no. of museums, but failed to see the correspondence of $k+1$-th solution to $k$-th solution.

\[EDIT: Added examples of what might not work\] Suppose that we go hour-by-hour from the latest closing time up to the earliest opening time. (Here, the choice of *time step* as one hour is for the sake of simplicity and would work only if times where given as integer number of hours, as in the following example.) Considering the following table:

```
+-----------+-------+--------+-------------------+
|  Museum   | Opens | Closes | Duration of visit |
+-----------+-------+--------+-------------------+
| Hermitage | 08:00 | 11:00  | 01:00             |
| Louvre    | 09:00 | 11:00  | 02:00             |
+-----------+-------+--------+-------------------+

```

At 10:00 o'clock, the tourist can visit:

```
Hermitage 10:00 - 11:00

```

At 09:00 o'clock:

```
Hermitage 10:00 - 11:00

```

At 08:00 o'clock, still the same:

```
Hermitage 10:00 - 11:00

```

i.e. *Louvre* never appeared because *Hermitage* occupied its 'time slot' even though the tourist could have gone to *Hermitage* at 08:00, like so:

```
Hermitage 08:00 - 09:00
Louvre 09:00 - 11:00

```

---

Is this problem, then, solvable only by backtracking or similarly brute-force approach? If so, how?

# Answer
The problem is strongly $NP$-complete by reduction from 3-Partition.

Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each having sum $M$. Note that we can assume that no four integers have sum $\leq M$.

Suppose a day is $3M+n-1$ units of time long. We want to visit $n-1$ museums $m\_1,\ldots,m\_{n-1}$ for $1$ unit of time each, and the $i^\textrm{th}$ museum is open from time unit $i\times(M+1)-1$ to time unit $i\times(M+1)$. I.e., there are $n$ museums that can only be visited at one very specific time of day, and they partition the day into $n$ slots of length $M$ each.

For each integer in the 3-Partition instance we now create a museum to visit that can be visited any time during the day, and takes a number of time units equal to the original integer.

Clearly a solutions visiting all museums in a single day corresponds to a solution for the $3$-Partition instance and vice-versa.

This implies that it is unlikely that an algorithm significantly better than brute-force exists. One possible approach would be to use Held-Karp style dynamic programming, similar to solving TSP. One would, for all subsets $S$ of museums and any time of day $T$, compute the maximum number of museums from $S$ that can be visited before time $T$ (i.e., the last visit must be completed before time $T$). This can be evaluated recursively by picking one museum to visit last, and then removing that museum from $S$ and decreasing $T$ and solving the resulting subproblem. This results in an algorithm with running time exponential in the number of museums.
> 3 votes

# Answer
I agree with you that dynamic programming is the best choice. However, I wouldn't recurse over the number of museums, but over the time of day.

In particular: at 11:00pm, what plan gives you the greatest number of museums? Your only option is to go home and see zero.

Now, at 10:00pm, what plan gives you the greatest number of museums? There are only two options here: visit the Hermitage for one hour (so your score is 1 + max\_score(11:00pm)) or wait for one hour (so your score is 0 + max\_score(11:00pm)).

Continue in this manner, with a nice dynamic-programming memoization table to keep the time complexity low, until you hit the start of the day (the earliest opening time). And voilà!

EDIT: If you need finer granularity than an hour, you can make your times more precise: in your first example, for instance, ten-minute increments will work nicely.
> 1 votes

---
Tags: optimization, dynamic-programming, greedy-algorithms, backtracking
---


title: Variant of stCON

text:
# Question
Title: Variant of stCON
Consider the following variation on stCON desicion problem:

> Given a directed graph G, decide whether for every two different vertices $s$ and $t$, there is a directed path between $s$ and $t$.

Intuitively, it seems like this problem is indentical to the clique desicion problem, for a clique of size $n$. But does it also belong to NL?

# Answer
This answer assumes that you want to check whether for every two vertices $s \neq t$ there is a directed path from $s$ to $t$. If this is the case, we say that the graph is *strongly connected*.

The idea is to use NL=coNL. In order to check that a directed graph is *not* strongly connected, we guess two vertices $s$ and $t$, and nondeterministically verify (using the algorithm underlying NL=coNL) that $t$ is not reachable from $s$. This shows that your problem is in coNL. Since NL=coNL, it is also in NL.

In fact, your problem is NL-complete, by a simple reduction from stCON; see notes of Matulef.
> 2 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: Substitution for Landau's O notation formula
I found the following description when I was reading a paper on computational complexity theory.

> This can be done ... in time 2*n*･poly(log*s*,*n*)+2*O*(log*s*)*c*. For *s*≤2*n**o*(1), the runtime is 2*n*･poly(*n*).

I know this means substituting *s*≤2*n**o*(1) for 2*n*･poly(log*s*,*n*)+2*O*(log*s*)*c* results in 2*n*･poly(*n*), but I don't know how this is done. So please tell me the calculation process.

# Answer
> 1 votes
First let us notice that $\log s = n^{o(1)} = o(n)$, and so $\mathit{poly}(\log s, n) = \mathit{poly}(n)$. This shows that the first summand is $2^n \mathit{poly}(n)$.

Next, since $\log s = n^{o(1)}$, also $O(\log s) = n^{o(1)}$ (since constants are $n^{o(1)}$) and $O(\log s)^c = n^{o(1)}$ (since a constant multiple of $o(1)$ is also $o(1)$), hence the second summand is $2^{n^{o(1)}} = o(2^n)$. So the first summand is more significant.

---
Tags: complexity-theory, landau-notation
---


title: Programs to circuit conversion

text:
# Question
Title: Programs to circuit conversion
Suppose we have an algorithm for a decision problem with $n$ bit inputs that runs in $DTIME\[f(n)\]$ is there ways to convert to circuits of $O(f(n))$ size with AND, OR and NOT gates?

How about when we go from circuits to programs?

# Answer
> 2 votes
The Cook–Levin theorem shows how to construct a circuit of size $f(n)^{O(1)}$. I'm not sure what's the best exponent.

The opposite direction is impossible, since circuits of size 1 can compute the following language: $$ \\{ w : \text{the $|w|$th Turing machine halts on the empty input} \\}. $$ More generally, circuits of size 1 can compute any language in which the answer depends only on the length of the input.

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


# Question
Title: Can all regular tree types be expressed as $\mu$ types?
In "Types and Programming Languages", Pierce gives a translation from recursive types ($\mu$ types) to types expressed as regular trees: possibly infinite trees, but with finitely many distinct subtrees.

I'm wondering, is the converse true? Can every regular tree type be expressed using the $\mu$ fixpoint notation? It seems obvious that this can be done if you have mutually recursive types: you have a type for each subtree of the regular tree type. But can it be done with singly recursive types?

# Answer
You can reduce mutual recursion to a single recursion, see Bekic's Theorem, see e.g. Section 10.1 of Winskel's (1), where Bekic is worked out for programs rather than types. Note however that the details depend on the exact nature of the formal system in question. See A. Bauer's answer in (2) for the case of types.

---

1. G. Winskel, *The Formal Semantics of Programming Languages*.
2. CSTheory Stackexchange, *Can Isorecursive types capture mutually recursive data types?*
> 7 votes

---
Tags: programming-languages, lambda-calculus, type-theory, types-and-programming-languages, tree-automata
---


# Question
Title: Universal Turing machine and virtualization technology
I was wondering if virtualization technologies (VmWare, virtual box) are possible thanks to the theoretical existence, translated into practice, of the concept of universal turing machine or if the two are simply a coincidence. As far as I'm concerned they seem to me to be closely linked but I could be wrong.

# Answer
Yes and no. Essentially because of the existence of universal Turing machines, you *could* write a VMWare-like system that used software to simulate the CPU. In reality, though, that would be unbearably slow, so it's not how these products actually work. Instead, they run the code directly on the CPU, in a carefully controlled and hardware-supported environment.
> 2 votes

---
Tags: turing-machines
---


# Question
Title: What is the specific name for basic data types?
What is the specific name for data types such as integer, string, real (the basic ones)?

# Answer
They are called **primitive data types**.

(This is a pretty basic find in Wikipedia's article on data types.)
> 3 votes

---
Tags: terminology, abstract-data-types
---


title: Scheduling algorithms and quantum time

text:
# Question
Title: Scheduling algorithms and quantum time
I would like to know what impacts does a scheduling algorithm, let's say Round Robin or FIFO, have on an Operating System. I understand that a scheduling algorithm has the processes run in burst then switch between one another. But what does this mean for an OS. All I can figure out is that the OS has to keep track of which process is running, see if it has done/completed its operation, choose/switch to another process and run it for a given time. Am I missing the obvious here? It does not really seam to me that a scheduling algorithm really affect the OS per se but the CPU hardware.

# Answer
It seems that the missing piece here is that the switching does not only occur when a process completes. The switch will occur when either 1) the process completes, or 2) when the process explicitly yields its remaining run time slice (whatever it has not used of its time quantum), or 3) when the OS pre-emptively interrupts the process due to that process having been running for all of its assigned time quantum.

The OS is responsible for allowing all the processes that need to get 'OnProc' (on processor) some time to actually be running on a processor. The scheduling algorithm is what determines how "fair" the choice of which process next gets to run on a processor is. Note that technically all of the above really should have the word 'process' replaced with the word 'thread' (of which a single process may have many, and also not all threads necessarily have a process associated with them)

As for what the impact is on the OS - that is a question that needs more definition. I can say that other than the scheduler threads and timers and interrupts, generally all threads are subject to the scheduler so the OS will be impacted by the choice of algorithm.
> 4 votes

# Answer
Round Robin is supposed to provide better response time to the OS. Every job has been given a fair share of the processing time (fixed quantum time).

* It avoids starvation. Since every job has a fixed quantum time, so the LONGER job doesn't hold the CPU too long for itself (unless quantum time given is too long).
* It is used in multitasking and multi-user environment since it has a fast context switch by switching to different PCB through the preempt process.
* It does affect the OS in a way IF quantum time given to every job is too long. Since a job holding a CPU for a long time, it would cause the OS not to be responsive which defeats the purpose of Round Robin. (Too long quantum time sometime would cause Round Robin behaves similarly to FCFS). Imagine the highest job requirement is 10ns and the rest is either 5 or 8. However, quantum time given is 11. That means, this round robin is basically a FCFS.
* IF quantum time given is too short, there would be too many context switching going on and overall jobs wouldn't be completed in time.

So the point is Round Robin is very dependent on the quantum time.
> 2 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?
Let $L\_1, L\_2 \subseteq \Sigma^\*$ be two languages, where $\Sigma$ is some finite Alphabet.

Does $L\_1L\_2 = L\_2L\_1$ imply $L\_1 = L\_2$?

What if $L\_1$ and $L\_2$ are regular languages?

Can you give counterexamples?

# Answer
> 6 votes
No, just take as counter example $L\_1=\epsilon$ and $L\_2$ any other langage different from $L\_1$.

# Answer
> 4 votes
No, counter example: $$ L\_1 = a , L\_2 = a^\* $$

# Answer
> 4 votes
Hint 1. For words $x\_1, x\_2 \in \Sigma^\*$. If $x\_1x\_2=x\_2x\_1$, does this imply that $x\_1=x\_2$?

> Two words commute iff they are powers of a common word. Thus an example would be any pair of languages $L\_1,L\_2\subseteq\\{w\\}^\*$.

Hint 2. What about $\Sigma = \\{a\\}$, a one letter alphabet?

> Any pair of languages over a single letter alphabet will commute, however complicated.

Hint 3. You may actually find a language $I$ such that $L\_1 I = IL\_1 = L\_1$ for every language $L\_1$.

> The language $I=\\{\varepsilon\\}$ is your pal.

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


# Question
Title: Show that the following language is undecidable
$\\{ M \mid M \text{ is a machine that runs in }100n^3 + 300\text{ time }\\}$

I am currently stuck with this one. I thought of reducing *HALT* to *M* as the reduction seems legitimate to me: if the first is undecidable then building an instance of the first problem starting from the second, ie asking if a machine M that executes an input n stops after a time $f$$(n)$ is like asking if it stops at all and then **M ⊆ HALT**. However there is something that does not convince me in this demonstration because it seems quite naive and I don't think that this is enough to prove that this language is undecidable. In addition the exercise it is taken from a chapter of a text in which the oracles are introduced, is it possible to prove this language undecidable by means of oracles? I would appreciate your help, thanks.

# Answer
> 4 votes
You haven't defined HALT, so let me assume that it consists of all Turing machines that halt on the empty input. If $M$ halts in time $f(n)$, then in particular it halts on the empty input, and so if $M$ belongs to your language then it also belongs to halt. But the converse doesn't hold, and $L \subseteq HALT$ doesn't imply anything about $L$ (for example, $\emptyset \subseteq HALT$, yet $\emptyset$ is decidable).

In other words, your proof doesn't work. It doesn't prove anything.

Your goal is to show that using an oracle to $L$ (your language), you can decide the halting problem; hence if $L$ were decidable, then so would HALT be, contrary to the known fact that HALT isn't decidable.

In fact, we can show that $L$ is coRE-hard. This means that there is a computable reduction that takes a description of a Turing machine $M$ and outputs a description of another Turing machine $M'$ such that:

1. If $M$ halts on the empty input then $M'$ *doesn't* run in time $f(n) := 100n^3 + 300$.
2. If $M$ doesn't halt on the empty input then $M'$ *does* run in time $f(n)$.

The construction goes as follows. On input of length $n$, $M'$ simulates $M$ on the empty input for $g(n)$ steps, where $g(n)$ is a function to be determined, which tends to infinity. If $M$ halts within $g(n)$ steps, $M'$ goes into an infinite loop, and otherwise $M'$ halts. We choose $g(n)$ so that the simulation runs in time $f(n)$. (Depending on the exact Turing machine model, we might be able to take $g(n) = n$ or so.)

If $M$ doesn't halt then, by construction, $M'$ also halts within $f(n)$ steps. If $M$ does halt, then for large enough $n$, $M'$ will never halt, and in particular won't halt within $f(n)$ steps.

The language $L$ is also coRE: we can enumerate machines not in $L$ by running all machines on all inputs, and outputting the description of a machine once it doesn't stop within $f(n)$ steps on some input of length $n$. This shows that $L$ is coRE-complete.

---
Tags: formal-languages, undecidability, halting-problem, oracle-machines
---


title: Graphs of maximum degree three

text:
# Question
Title: Graphs of maximum degree three
I'm learning an algorithm for graphs of maximum degree three.

My question is: should the graph of that type have at least one vertex with degree three.

For example if the maximum degree of some graph is 2, can we say that this graph is maximum degree three.

Thank you

# Answer
> 4 votes
In general it is impossible to tell. When people say that a graph has maximum degree 3, they could mean two different things:

* The maximal degree of a vertex in the graph is 3.
* All vertices in the graph have degree at most 3.

Similarly, a function of degree $d$ sometimes means a function of degree *exactly* $d$, and sometimes a function of degree *at most* $d$. In many contexts, the difference is immaterial. For example, a graph of maximum degree 3 on $n$ vertices has at most $1.5n$ edges – and this holds for both meanings.

If the difference is pertinent, then one would hope that you could tell which meaning is intended from context. For example, if we are trying to understand how large the maximum degree can be under some constraints, then probably we refer to the first meaning; and if we have an inductive argument which removes edges, then we might refer to the second meaning.

# Answer
> 3 votes
Usually when people talk of graphs of maximum degree 3, they mean that the maximum degree is *at most* three. So no, such a graph must not necessarily contain a vertex of degree 3. Sometimes, these graphs are also known as *subcubic*.

If the meaning is different from this, the terminology tends to be different as well. For example, a *cubic graph* is a graph where every vertex has degree (exactly) three, i.e., they are the 3-regular graphs.

---
Tags: graphs
---


title: Divide two strings to form palindrome

text:
# Question
Title: Divide two strings to form palindrome
Given two strings, A and B, of the same length $n$, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.

I've tried bruteforce, and this can be achieved in $O(n^2)$. I'm looking for any kind of optimization that is faster than $O(n^2)$. I'm not familiar with backtracking and DP. So, can anyone throw some light?

# Answer
> 3 votes
***Some notations in Python convention***

* $S\[:i\]$ means the first $i$ letter of string $S$.
* $S\[-i:\]$ means the last $i$ letter of string $S$. ($S\[-0:\]$ is the empty string, which is not Python convention.)
* $S+T$ means the concatenation of $S$ and $T$.

### The problem in clearer terms

Given two strings, $A$ and $B$, of equal length $n$, find whether $A\[:i\]+ B\[-(n-i):\]$ is a palindrome for some $i$.

### Brute force

For each $i$ in $0, 1, \cdots, n$, we can check if $A\[:i\]+ B\[-(n-i):\]$ is a palindrome. This search by brute force runs in $O(n^2)$. Its average time-complexity is $O(n)$ under some reasonable assumptions. It is very easy to implement.

### Algorithm in $O(n)$

Let us take a closer look what happens when we get a palindrome. For example, $$\begin{aligned} A&=ab12321xy\\ B&=\text{\**}5\text{\***}4ba\\ C=A\[\text{:}7\]+B\[-2\text{:}\]&=ab12321ba\quad \text{which is a palindrome.} \end{aligned}$$

Note that 12321 in $C$ is a palindrome that sits in the middle of $C$, which is not surprising since the central part of a palindrome is also a palindrome. Since the lengths of $A$ and $B$ are the same, that 12321 should sit in the middle of $A$ as well.

Note the remaining part after $12321$ has been removed, $abba$ is also a palindrome.

The above indicates the following simple algorithm.

1. Compare the letters at the front of $A$ with the corresponding letters at the behind of $B$ one by one so as to find $i\_0$, the largest $i\le n/2$ such that $A\[:i\]+B\[-i:\]$ is a palindrome.
2. Starting from the center of $A$, expand both ways to find the longest palindrome sitting in the central of $A$. Let $c\_A$ be its length. If $2i\_0 + c\_A\ge n$, return yes.
3. Starting from the center of $B$, expand both ways to find the longest palindrome sitting in the central of $B$. Let $c\_B$ be its length. If $2i\_0 + c\_B\ge n$, return yes.
4. If we have reached here, return no.

### Exercise

Given two strings, $A$ and $B$, devise an $O(n)$ algorithm that determines whether $A\[:i\]+ B\[-(n-i):\]$ is a palindrome for some $i$, $0\le i \le\text{len}(A)$ and $0\le n-i \le\text{len}(B)$. (This exercise should be easy if you know Manacher's algorithm.)

# Answer
> 1 votes
I'm assuming by cutting at a common point you mean that only one cut can be made at the same index in both Strings and the resulting string must be of the same length as the original length of Strings A and B, and that A *must* be the first string and B *must* be the second?

In this case, this algorithm should run in o(n) time. Start from the first character in A and the last character in B and count the number of matching characters until you find a mismatch (If you reach the center of the strings then you have found a palindrome by simply putting together each half of String A and String B).

Now you know that if you cut at either right before the first mismatched character in String A or right after the first mismatched character in B, that each half on the ends of the String formed will match, and therefore if the characters in between form a palindrome, then the whole string will form a palindrome. Therefore you can simply check if either String A or String B, minus the first and last n characters, where n is the number of characters that matched in your initial check, is palindromic. If the answer is no, then a palindrome cannot be formed.

Example:

* String A: ABCORLUXIENSTU
* String B: QLDWXYZZYXWCBA

Up the line, you would compare A to A, then B to B, then C to C, then N to W, finding a mismatch. You would then check each String to see if the internal string without the first and last three characters is palindromic. ORLUXIEN in the first string is not, but WXYZZYXW in the second string is, therefore you can form the palindrome ABCWXYZZYWXCBA by cutting at index 3.

I'm pretty certain this will always find a palindrome if there is one, if there are any cases I'm missing, please let me know.

---
Tags: algorithms, strings
---


# Question
Title: When will SLR(1) parser fail but CLR(1) will not
Dragon book says following about where SLR(1) parser can fail but CLR(1) wont:

> Recall that in the SLR method, state $i$ calls for reduction by $A→α$ if the set of items $I\_i$ contains item $\[A→α.\]$ and a is in $FOLLOW(A)$. In some situations, however, when state i appears on top of the stack, the viable prefix $βα$ on the stack is such that $βA$ cannot be followed by $a$ in any right-sentential form. Thus, the reduction by $A→a$ should be invalid on input $a$.
>
> Let us consider the below grammar and its LR0 items:
>
> $S→L=R | R$
> $L→ \*R | id$
> $R→L$
>
> In state 2 we had item $R→L$., which could correspond to $A→a$ above, and $a$ could be the $=$ sign, which is in $FOLLOW(R)(=FOLLOW(L))$. Thus, the SLR parser calls for reduction by $R→L$ in state 2 with $=$ as the next input (the shift action is also called for, because of item $S→L.=R$ in state 2). However, there is no right-sentential form of the grammar in that begins $R=⋯$.. Thus state 2, which is the state corresponding to viable prefix L only, should not really call for reduction of that $L$ to $R$.

**DOUBTS**

1. I didnt get:

> However, there is no right-sentential form of the grammar in that begins $R=⋯$..

Do the authors mean that there is no productions with its right hand side starting with $R$? If yes, what is the significance of this statement?
2. Are lookaheads (as in case of LR(1) items for CLR(1) and LALR(1) parsers) always subset of FOLLOW of production heads (that is non terminal of the left of production)? If yes, why so? That is which of the FOLLOW of production heads are not lookaheads?

---

# Edit 1: Doubt extended based on rici's answer and comments (deprecated, see Edit 2)

I understood following comment by rici:

> ll you need to do is try a few derivations to see (1). $S→L=R$ cannot derive a sentential firm starting with $R$ and after $S→R$, the only possible next derivation results in $L$.

However, this is specific to this particular grammar. I wanted generalized characteristics of non FOLLOW lookaheads and more importantly "generalized reason of why they happen". So I thought better to try some example and see why particular string is accepted and rejected by hitting and non hitting this particular production $R\rightarrow L$. I prepared canonical collections.

**SLR(1) Canonical Collection**

**CLR(1) Canonical collection**

I2 of SLR involves SR conflict for =. So better look for string containing $, which is also in FOLLOW(R).

```
Stack contents while parsing string *id$ by CLR (Reduced number of stack content means reduce move, increased number of stack content means shift move)
================================================
[0]
[0,*,4] (shift * and transit to state 4)
[0,*,4,id,5] (shift id and transit to state 5)
(5,$)= no shift/reduce move ---> reject string

Stack contents while parsing string *id$ by SLR
================================================
[0]
[0,*,4]
[0,*,4,id,5] (shift id and transit to state 5)
[0,*,4,L]
[0,*,4,L,8]
[0,*,4,R]  (Reduce L to R)
[0,*,4,R,7]
[0,L]   (Reduce *R to L)
[0,L,2] (Transit to state 2)
[0,R]
[0,R,3]
[0,S]
Accept

```

Looking at grammar, I felt CLR also should accept the string, as the parse tree will be:

```
  S
  |
  R
  |
  L
/  \
|   R
|   |
|   L
|   |
*  id

```

Then why CLR rejects the string? Did I make any mistake above?

---

# Edit 2 (Both SLR and CLR will do reduction $R\rightarrow L$ in state 2 with $=$ as the next input) (Deprecated see edit 3, sorry for mistakes)

I made a mistake in above CLR(1) canonical collection. The correct one will be as follows:

As you can see, CLR(1) automata contains $R\rightarrow L.,=/\\$$ in $I\_2$. So, similar to SLR(1), CLR(1) will also do the reduction $R\rightarrow L$ on next input symbol $=$ Right? Or am I doing some mistake again?

---

# Edit 3

There was a mistake in $I\_0$. $I\_0$ should not contain $R\rightarrow .L,=$. After trying out several strings & parsing, I feel I came to know why SLR(1) is weaker than CLR(1), or why & when some FOLLOWS(head of final item) are invalid. I wanted to generalize why and where such FOLLOW occur & wanted to put in precise words to get clear understanding. I need confirmation for following:

> "The idea that the body / right hand side of the production can be reduced to the head of the production whenever the next input symbol is in the FOLLOW of the head, is itself wrong. The FOLLOW set of the head forms the set of terminals. which when appear as next input symbol, the tail "may be" reduced to head, however not at all time. Each FOLLOW symbol is valid next input terminals for reduction only at specific position / state / point in the parse. This fact is ignored by SLR parser and is captured by CLR by having different set of lookaheads for same LR(1) item in different closures. Those different closures are nothing but different points in parse, whereas lookaheads are subset of FOLLOW of head which are valid next input symbols for reduction at that point in the parse."

# Answer
> 4 votes
1. No, the authors meant that there is no right-sentential form of the grammar that starts with `R =`. That is, the `=` in that observation is a literal terminal symbol.

A right-sentential form is a sequence of terminal and/or non-terminal symbols which might appear in a rightmost derivation. So what they are saying is that no rightmost derivation of that grammar contains an intermediate sequence starting with the two symbols `R =`.

That's fairly easy to prove, and if you still don't feel confident about what this statement neans, proving the assertion is probably a useful exercise.
2. The lookahead set for an LR item $A\to \alpha .$ is most certainly a subset of $FOLLOW(A)$, since whatever comes next in a valid input obviously follows the non-terminal $A$, and $FOLLOW(A)$ is defined as the set of terminals which might follow $A$ in some right-sentential form. (The lookahead for the item $A\to \alpha .$ is the set of terminals which might follow this particular $A$ when the parser is in this state.)

But it is not necessarily the case that *every* terminal in $FOLLOW(A)$ is in that lookahead set, and this example is intended to be precisely an illustration of that fact.

---
Tags: automata, compilers, parsers, lr-k
---


# Question
Title: Multiple knapsack problem with equal profit and different weight
I am doing a research about the load balancing problem in 5G system, but I am not sure if my problem is a NP-complete problem.

The problem is:

* given a set of n items and a set of m knapsack
* capacity of knapsacks are equal
* the weight of item j in knapsack i is w\[i\]\[j\],that means weight of a item in each knapsack are different
* each profit of items are equal

I am not trying to put all item in least knapsack like bin packing problem. I saw some similar question answered, but no one is identical to this case. In this case, the goal is to put as more as possible item with m knapsacks. Is the problem a NP-complete problem?

# Answer
> 1 votes
This problem can be shown to be NP-complete via reduction from PARTITION. Simply take $m=2$, the weights of each item to be the same across both knapsacks, and the capacities of each knapsack to be half the total weight across all items.

---
Tags: knapsack-problems
---


# Question
Title: In predicate logic, is the "environment" only needed when free variables are present?
Suppose there exist no free variables in a given predicate logic formula. Is then a model alone sufficient to fully interpret the formula and make inferences? Don't we need an *environment* or variable lookup table (as often mentioned)?

# Answer
> 3 votes
It is not so that the model alone allows you to make inferences and that you don't need an environment at all; it is rather that, if no free variables occur, then you may as well start with an *empty* environment. Quantifiers modify the current environment, so you *do* need one. However, if there are no free variables around, then any of the assignments in the initial environment will not be used, and all variable values will come from the quantifiers anyway. Therefore, by trimming unnecessary assignments in the initial environment, you get an empty one.

# Answer
> 1 votes
The wikipedia article First-order logic calls the "environment" a *variable assignment*. A formula with no free variables is called a *sentence*. A model alone is sufficient to fully interpret a sentence. However, all deduction systems for first order logic that I know need formulas with free variables as intermediary deductions, and hence need the concept of a variable assignment for an interpretation of their inferences.

In general, this seems to be necessary. Some specific first-order theories (like Presburger arithmetic) allow quantifier elimination, but all theories that I know which allow quantifier elimination are decidable. So my guess would be that any deduction system for an undecidable first-order theory will need to work with free variables (or some equivalent concept) and hence will need the concept of a variable assignment (or some equivalent concept) for an interpretation of their inferences.

To see that the issue is related to the deductions mostly and not to interpretation, one can look at alternative semantics like game semantics.

---
Tags: predicate-logic
---


title: When Huffman coding is inefficient?

text:
# Question
Title: When Huffman coding is inefficient?
I have a question regarding the redundancy of Huffman coding. I know that for a general prefix code we have the following inequality:

$$ H(X) \le R \le H(X) + 1 $$

$R$ being the rate (average codeword length) and $H$ is the entropy. Based on this relation, how can we conclude that Huffman coding is very inefficient if entropy of the source is much smaller than 1 bit/symbol?

# Answer
> 1 votes
If $X$ is any non-constant source, then any codeword in any prefix code for $X$ has length at least $1$, and so $R \geq 1$. Therefore if $X$ is a source with very low entropy then there's a large discrepancy between $H(X) \approx 0$ and $R \approx 1$.

As a concrete example, consider a binary source in which the probability of one of the options is $\epsilon$. Then $H(X) = \epsilon \log (1/\epsilon) + O(\epsilon)$ whereas $R = 1$.

---
Tags: entropy, huffman-coding
---


# Question
Title: Reduction from minimum dominating set to the set cover
To solve the min dominating set problem of a graph G, we can reduce it to a set cover problem.

For example to find the MDS of the graph G:

#

We can create an instance of the Set Cover problem by:

1. Introducing the universe U to be equal to all vertices of the graph: U={0, 1, 2, 3, 4}.
2. For every closed neighborhood of a vertex in G, we introduce a subset S:

s= {{0, 1}, {0, 1, 2}, {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 4}}

A minimum set cover solution of the instance (s, U) is similar to a minimum dominating set solution in the graph G.

My first question is how we can prove that this reduction is correct, and will give the correct MDS solution for every graph. In our example, the reduction works well and give the correct result.

My second question is how this reduction is related to the reduction when we deal with NP-complete proof(for example we can prove that the MDS problem is NP-complete by reduction to the vertex cover problem).

Are those reductions related? Thank you

# Answer
> 2 votes
Let $G$ be an instance of dominating set and construct an instance of $(U,\mathcal{S})$ of set cover as you describe. The claim is that $G$ has a dominating set of size $k$ if and only if there is a subfamily $\mathcal{S}' \subseteq \mathcal{S}$ with $k$ members that covers $U$.

In the first direction, which you indicate is clearer, let $D$ be a dominating set of size $k$. Construct $\mathcal{S'}$ by adding into it the set corresponding to the closed neighborhood of every $v \in D$. Clearly, $\mathcal{S}'$ has size $k$ as $D$ has size $k$. Further, by the definition of a dominating set, $\mathcal{S}'$ also covers $U$.

In the second direction, let $\mathcal{S}'$ be a set cover for $U$. Build $D$ such that if the set $S\_v$, the set corresponding to the closed neighborhood of $v$, is in $\mathcal{S}'$, add the vertex $v$ to $D$. Because $\mathcal{S}'$ covers $U$ which by construction corresponds to the vertex set of $G$, we have that $D$ is a dominating set. Moreover, we clearly have that $D$ has size $k$ as $\mathcal{S}'$ has size $k$.

Your second question however is unclear. A reduction "being related to another reduction" is not a formal statement. In an informal sense, you can use similar ideas to establish other reductions between dominating set, set cover and/or vertex cover but you have to work through the details yourself.

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


title: Parity Hamiltonian path problem

text:
# Question
Title: Parity Hamiltonian path problem
Wikipedia says that Hamiltonian path problem is NPC, but Parity Hamiltonian path problem (i.e., is there an odd amount of hamiltonian path) is P. Does a reduction from, e.g., SAT, to HPP, unavoidably duplicate some solutions?

# Answer
As far as we know, there is no polynomial-time algorithm for HPP. Put differently, there is no *known* polynomial-time reduction from any NP-hard problem with the properties that you require to Parity-HPP.

If such a reduction did exist, we could reduce any NP-hard problem A to Parity-HPP (in polynomial time) and then solve A using the polynomial-time algorithm that you claim.
> 1 votes

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


# Question
Title: How does a compiler infer a value's type?
From A Swift Tour — The Swift Programming Language (Swift 5):

```
var myVariable = 42
myVariable = 50
let myConstant = 42

```

> A constant or variable must have the same type as the value you want to assign to it. However, you don’t always have to write the type explicitly. Providing a value when you create a constant or variable lets the compiler infer its type. In the example above, the compiler infers that myVariable is an integer because its initial value is an integer.

How does this work?

# Answer
> 2 votes
You did not provide an explicit type identifier in the left part of the variable declaration & initialization statement. However, by implicitly specifying an initialization value in the right part to have type int, which the compiler can infer from values of 42/50, these statements triggered the procedure of the compiler to handle S-Attributed Grammar.

# Answer
> 2 votes
When the compiler sees the `var <identifier> = <expression>;` construct it can parse the `<expression>` out of which a type will emerge.

That type is then used as the declared variable's type.

It is the same logic for type checking when you do declare the type explicitly or assign to a variable, only with the difference that when the type is already fixed and it doesn't match it emits an compiler error.

---
Tags: compilers, type-inference
---


# Question
Title: R-tree insertion procedure when leaf is full
I am implementing an R-tree with the quadratic splitting method.

However in most articles I have read there a piece of information that is missing or misleading (or the most probably case, I completely misunderstood something).

R-trees are supposed to be balanced, yet you need to find the node that will increase less in area to insert your new object, and split such node if full. However this can clearly lead to having a very unbalanced tree in depth, as that node can always be on a single branch (say, leftmost in a graph-type representation of the tree).

Should the insertion criteria say " find the node that will increase less in area to insert your new object **among those that are not full**, \[...\]" ?

OR can the quadratic splitting method create very unbalanced trees if you are unlucky with new entries? Say if after N insertions all the new insertions are are very localized, e.g. in always fit in the leftmost leaf in the following figure

Or is there something else that I did not understand?

# Answer
Nope, you are wrong!

In your example, if you keep adding nodes to the leftmost entry, the splits propagate upwards. There will be more levels, but as they propagate upwards, the leafs are always in the same level, thus it always makes a balanced tree, as long as you make sure you follow the insertion and splitting rules tightly (e.g. make sure there are always $m$ minimum objects in a node)
> 0 votes

---
Tags: search-trees
---


# Question
Title: Problem Set Solutions/Interrupts & Exceptions/Problem 1
Using Tomasulo’s algorithm, for each instruction in the listed sequence determine when (in which cycle, counting from the start) it issues, begins execution, and writes its result to the CDB. Assume that the result of an instruction can be written in the last cycle of its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that. The execution time of all instructions is two cycles, except for multiplication (which takes 4 cycles) and division (which takes 8 cycles). The processor has one multiply/divide unit and one add/subtract unit. The multiply/divide unit has two reservation stations and the add/subtract unit has four reservation stations. None of the execution units is pipelined – each can only be executing one instruction at a time. If a conflict for the use of an execution unit occurs when selecting which instruction should start to execute, the older instruction (the one that appears earlier in program order) has priority. If a conflict for use of the CBD occurs, the result of the add/subtract unit has priority over the result of the multiply/divide unit. Assume that at start all instructions are already in the instruction queue, but none has yet been issued to any reservation stations. The processor can issue only one instruction per cycle, and there is only one CDB for writing results.

Can someone explain why for Instruction 1 the write happens in cycle 5 ? It is given in the question that MUL takes 4 cycles to execute. So write for I1 should have happened in cycle 6 ?

# Answer
> 1 votes
The question I have met in class before. I cannot add comment so I write here. Notice the note '**Assume that the result of an instruction can be written in the last cycle of its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that.**' which means instead of WR in the 1st cycle after the completion of EXE, it WR in the last cycle of EXE.

E.g. The I1 starts its EXE in 2nd cycle and end in 5th cycle (2, 3, 4, 5). So I1's WR happens in the last cycle of EXE which is 5th cycle.

For the rest of the table you should fill them based on the given notes, kind of the manual of a specific processor. This is not the general case which you will encounter in other scheduler problems. Wish it helps you.

---
Tags: computer-architecture
---


# Question
Title: GOTO statement in programming environments for beginners?
As a student, back in the day, I was exposed to high level programming languages that not only had a GOTO statement, but on which its use was common. I also did my fair share of programming in assembly code, but always had the impression that my understanding of the semantics of subprograms was enormously facilitated by my familiarity will programs constructed without them, in high level imperative languages, even though I never used them (or felt the need) in my life as a programmer, ever since.

In my experience as a teacher, the passage from non-modular to modular programming is always a struggle, and I keep asking myself the following **question**:

*Would the careful and well-supervised reintroduction of the jump command in languages and environments devoted to introductory lessons in programming be of help students with the passage from non-modular to modular programming?*

For clarity: the usage of the GOTO statement I am talking about here is restricted to programming environments used exclusively for teaching **the basics** of programming, while (or where) it is still done using **imperative** (monoparadigm) languages. Informed opinions based on experience and/or indications of research available on the subject (I didn't find anything substantial) are really welcome.

# Answer
This doesn't seem like a good idea. Normally, we teach people using a system with restrictive safety features and only remove those safety features when the learner has demonstrated competence: consider training wheels on a bike, children's safety scissors and so on. You're suggesting that we teach using a "dangerous" system (goto) and then remove the dangerous parts once the learner has demonstrated competence.

Also, I don't see how using goto would help the transition to modular programming. Modular programming doesn't tend to use goto, so it seems you're trying to aid the transition from A to B by introducing something that doesn't help with B. To use a rather melodramatic analogy, it's like proposing to help somebody transition from a tricycle to a bicycle by giving them a pair of scissors to use while riding: it introduces a dangerous habit that doesn't even contribute to the desired goal.
> 2 votes

# Answer
The two most common cases for using goto is to break out of nested loops to a specific level, or when there are multiple paths to common code. Such situations could be avoided in a beginner class, but it's always possible that the subject could come up. Some languages include a "continue to label" to break out of nested loops, but it's essentially a restricted form of goto. Java has reserved "goto", but so far hasn't implemented it.

Imagine how messy the end result would be if trying to remove the goto's used in the optimized bottom up 4 way merge sort (without heap) shown at the end of the linked to answer:

https://stackoverflow.com/questions/34844613/optimized-merge-sort-faster-than-quicksort/34845789#34845789
> 0 votes

---
Tags: programming-languages, education
---


# Question
Title: What are the current state of art approximation algorithm for NP-Hard problems?
I came cross some works try to use deep learning to approximate NP-Hard

https://arxiv.org/pdf/1810.10659.pdf

Though the paper seems to have very good results but based on the citations. I'm quit doubt if it really the state of art approximation for NP-hard problem.

I'm wondering what are some state of art NP-Hard approximation algorithms for each problems ?

# Answer
> 1 votes
First, there are two aspects to separate here: theoretical approximation and practical approximation (i.e., heuristics). With heuristics, such as in the NIPS paper you mention, the goal is roughly to propose some method, take a large **bunch of actual instances** of a problem, benchmark empirically the method, and draw conclusions as to how well we did in terms of approximation.

This is in contrast to (theoretical) approximation algorithms that give a *formal guarantee* on solution quality, on **all possible instances**. For example, the guarantee could be "the solution returned by this algorithm is either optimal or at most three less than the optimal". But as you might know, there is an enormous amount of hard problems that can be wildly different in terms of approximation. Maximum clique or chromatic number, for instance, are very hard to approximate theoretically.

---
Tags: np-complete, np-hard, approximation
---


title: Shortest path with a given condition

text:
# Question
Title: Shortest path with a given condition
The problem says to find the shortest way (the smallest amount of intermediary points), with given source and destination points, such that between two consecutive intermediary points there are two alternative routes. Also, all the connections between the points on the map are given.

I understood that the problem is about a graph with given edges and that i have to find the shortest path between two given nodes, but i didn't understand how to search the right path with the given condition (2 alternative paths between every two intermediary nodes). Is the BFS algorithm applicable in this case? And wich other algorithm could I also use?

Thanks in advance for help!

# Answer
First let's look at the special condition. For each edge $p\_i p\_{i+1}$ in the path $P$ the has to exists an additional path that connects $p\_i$ with $p\_{i+1}$. This criterion is equivalent to: no edge of the path is a bridge edge.

This means that we can determine already before the actual shortest path search, which edges we are allowed to use, and which edges we are not allowed to use.

Therefore you can construct an efficient algorithms as follows:

* compute all bridge edges (e.g. with Tarjan's bridge-finding algorithm)
* remove all bridge edges from the graph
* execute any shortest path algorithm, e.g. BFS, on the remaining graph

Some additional notes, since you wrote that you want to use multiple algorithms. However these approaches will perform a lot worse than the one described above.

* of course you can also determine if an edge $p\_i p\_{i+1}$ is a bridge edge in other ways. E.g. remove the edge from the graph, and check if you can find a path from $p\_i$ to $p\_{i+1}$ with a DFS (backtracking), or with another BFS.
* Also you can use Backtracking itself to find the shortest path at the end.
> 0 votes

# Answer
BFS is for tree traversal just like DFS. For the shortest path algorithms that textbook commonly used are:

* Bellman Ford's Algorithm
* Dijkstra's Algorithm
> -1 votes

---
Tags: shortest-path
---


# Question
Title: General question on choosing an Assembly language based on my goal
So I know assembly is so big and it seems learning assembly is like learning high level programming, you don't need to learn them all, you can learn couple and this will be enough.

The thing is with high-level language it is easier to grasp and implement in your life. But I am having hard time with assembly, I learned ARM at university, but I am not sure which version it was. And, it wasn't practical in real life. Also, it was too primitive. It doesn't even help me read other assemblies. Because when i read other assembly, I am lost seeing too many new commands that I have never seen before.

But I want to learn a language where I can add it to my code or make stand-alone version out of it easily like C++ or C# for Windows, so basically a practical language, also a language with live community and not an abandoned one. i learned some programming languages and they are useless for me like CLIPS, ADA and Prolog.

So what are the useful and practical assembly languages out there to learn for windows. Is FAsm a good start? Also note that I do not know what I want to do with it, I will learn it them when I get good command of it I will decide, I may use it for images, or AI project or anyother use where my path will lead. I already know C++ (i use it for UE4 and AI code implementations), C# (desktop/web) app and java (desktop).

# Answer
There is very, very little need for assembler. For is very rarely need for inline assembly - for example, I have some code somewhere that calculates (a * b) / c for unsigned 64 bit integers where a * b overflows.

And asking "which assembler should I learn" - if you ever need assembler, then that's the one you need to learn. Any other assembler is useless.

The only case where you *really* need to use assembler is at the extreme ends: When you are creating a virtual machine, you need to understand the extremely rarely used instructions to do this safely. If you create codecs, or encryption software, where you have very small amounts of code using up huge amounts of CPU time, that's where you may need assembler. But you don't need to know just assembler. You need to know and understand CPU instructions that have been created exactly for these purposes. You are in a highly specialised area there.
> 1 votes

# Answer
For Linux diehard, I suggest NASM which is both classical (for Linux) and still actively strong.

For ARM programmer, I suggest GNU assembler.
> 0 votes

---
Tags: computer-architecture
---


# Question
Title: Prove or disprove the following proposition $L_1^*∪L_2^*⊆(L_1∪L_2)^*$
$L\_1^\*∪L\_2^\*⊆(L\_1∪L\_2)^\*$

I actually disproved the opposite proposition $\[(L\_1∪L\_2)^\*⊆L\_1^\*∪L\_2^\*\]$ and my intuition tells me that this is actually true... I tried to show that the combinations of words in the right group $\[(L\_1∪L\_2)^\*\]$ obviously contain all the words from the left group $\[L\_1^\*∪L\_2^\*\]$ and it's also very plain to see, but I have no idea how to formalize it.

Any idea how to formally prove it? Thanks.

# Answer
This is true. You only have to prove the following staments:

1. if $A\subseteq B$ then $A^{\*} \subseteq B^{\*}$,
2. If $A\subseteq C$ and $B\subseteq C$ then $A \cup B \subseteq C$.

We know $L\_1 \subseteq L\_1 \cup L\_2$ for 1. we can conclude $L\_1^{\*} \subseteq (L\_1 \cup L\_2)^{\*}$, analogously $L\_2^{\*} \subseteq (L\_1 \cup L\_2)^{\*}$. For 2. we can conclude $L\_1^{\*} \cup L\_2^{\*} \subseteq (L\_1 \cup L\_2)^{\*}$.
> 2 votes

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


# Question
Title: Reduction from Exact Cover to Fixed Exact Cover
I am trying to reduce Exact Cover to Fixed Exact Cover to show that Fixed Exact Cover is NP-Hard.

**Exact Cover**

**Input**

S = {x1, x2, ..., xn} (set)

P = {P1, P2, ..., Pm} (subsets of S)

**Decision problem**: Is there a subset {Pi1,Pi2,...,Piq} of P such that every element of S belongs to exactly one of the Pij:s?

**Fixed Exact Cover**

**Input** S, P from Exact Cover, and an integer **K**

**Decision problem**: Is there a subset {Pi1,Pi2,...,Pik} of P of size K such that every element of S belongs to exactly one of the Pij:s?

Given hint: **K = n + 1**

My initial reaction is to iterate through each element in S, and for each element create a subset for P. However, that will result result in K being one too small. I have tried many things, but I just can't seem to figure it out.

**EDIT**

Sorry I should have added this in the original question: (All the Pij :s are assumed to be distinct.) Furthermore, (we can define an instance (S′,P′,K=n+1) of FSEC. S′ will be S ∪ A and P′ will be F ∪ G where A and G are ”dummy” sets disjoint from S and P and such that the elements of G are subsets of A. If A and G are chosen in a clever way (S,P) will have an exact cover if and only if (S′,P′) has a n+1 size cover)

**Example**

S = {1,2,3,4}

P = {{1}, {2,3}, {2,4}, {4}}

Solution

{{1}, {2,3},{4}} (size 3)

K = 5

S' = {1,2,3,4,5,6,7,8}

P' = {{1}, {2,3}, {2,4}, {4}, {5}, {6},{7},{8}, {5,6},{5,6,7}, {5,6,7,8}}

Solution = {{1}, {2,3}, {4}, {5,6,7}, {8}} (size 5)

# Answer
Add $n$ empty sets, and choose $K = n + 1$. Every solution for the original problem is (without loss of generality) of size between $1$ to $n$, so using the empty sets you can complete it to a solution of size exactly $K$.

If you're determined to have your collection duplicate-free, add $n$ new elements $y\_1,\ldots,y\_n$, and the following sets: $$ \\{y\_1\\},\\{y\_2\\},\ldots,\\{y\_n\\},\\{y\_1,y\_2\\},\\{y\_1,y\_2,y\_3\\},\ldots,\\{y\_1,\ldots,y\_n\\}. $$ There are exact covers of the new elements of any size from $1$ to $n$.
> 5 votes

---
Tags: reductions, np-hard
---


# Question
Title: Finding a regular expression of a language
Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^\*b^\*$, whose length is a multiple of 3.

Obviously $(aaa)^\*(bbb)^\*$ is one of the options, but I just can't formalize more options.

Any help will be appreciated.

# Answer
You have to put your triplets, and use Kleene star: $$(aaa)^\*(bbb)^\*$$

Now, add cases where number of $a$ is not divisible by 3, say aabbbb, as alternative. $$ (aaa)^\*(bbb)^\* + (aaa)^\*aab(bbb)^\* + (aaa)^\*abb(bbb)^\*$$
> 2 votes

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


# Question
Title: Complexity of Merge Sort that splits in a random position
I got a question that I don't fully understand: Given a new algorithm to merge sort (AKA mergesort2) that instead of splitting the list in the middle it splits the list in a random number between $1$ and $n-1$. Also, we know the probability of getting $1$ is $2/n$ and to every other number $1/n$.

I have tried again and again and came up with the regular when doing the "average case" $\Theta \ (n \log n)$ and of the merge sort algorithm and "worst case" $O (n^2)$ but I'm not sure about it.

Pseudo-Code:

```
   MergeSort2(A,p,q)
     if(p=q) then return
     i = random number from (1...q-p)
     MergeSort2(A, p,   p+i-1)
     MergeSort2(A, p+i, q)
     Merge(A, p, p+i-1, q)

```

How I did the calculations of the $O (n^2)$ "worst case" when I split it to $1$ and to $n-1$ every time: (if it's correct)

$$T(n)= T(1)+T(n-1)+O(n)$$

*When $T(1)$ is the single number, $T(n-1)$ is the rest list and $O(n)$ is the merge*

$$\begin{align\*} T(n) &= (T(1)+T(n-2)+O(n)) + T(1)+O(n) & \text{second recursive call}\\ &= (T(n-3)+T(1)+O(n)) +2T(1)+2O(n) & \text{third recursive call}\\ & \vdots\\ T(n) &= T(n-k)+kT(1)+kO(n) & k^{th}\text{ recursive call} \end{align\*}$$

Now we know that $T(1) = O(1)$ as it doesn't do anything.

In order to get to our stop condition, we need the $T(n-k)$ will be $T(1)$.

So to do so we will take $k = n-1$.

Therefore we will get the following:

$$T(n) = T(1)+(n-1)O(1)+(n-1)O(n) \implies T(n) = O(n^2)$$

How do I calculate properly the complexity of the given algorithm?

# Answer
> 1 votes
If you always split on index $n/100$ the complexity is going to be $O(n \log n)$. So in reality most split positions will give you a reasonable complexity.

This means that on average you will get a good split position (half of the splits will be between $n/4$ and $3n/4$, 90% of the splits will be between $n/20$ and $19n/20$). This is why using an random element in quicksort also give good performance except for that one in a billion chance the time it pathologically selects the worst pivot.

# Answer
> 5 votes
For definiteness, let us suppose that the $T(1) = 1$ and that if the split is $k+(n-k)$ then the running time is $T(k) + T(n-k) + n$. The recursion for the worst-case running time is therefore $$ T(n) = \begin{cases} \max\_{1 \leq k \leq n-1} T(k) + T(n-k) + n & \text{if } n \> 1 \\ 1 & \text{if } n = 1. \end{cases} $$

In order to calculate the worst-case complexity, we need both an upper bound and a lower bound. You already gave the lower bound: $$ T(n) \geq T(1) + T(n-1) + n = T(n-1) + n+1. $$ Iterating this easily yields $T(n) = \Omega(n^2)$.

In the other direction, let us prove that $T(n) \leq n^2$ for all $n$. The base case is clear. For the inductive case, $$ T(k) + T(n-k) + n \leq k^2 + (n-k)^2 + n \leq 1 + (n-1)^2 + n = n^2 - n + 2 \leq n^2, $$ since $n \geq 2$. It follows that $T(n) = \Theta(n^2)$.

(In fact, with some more work you should be able to show that $k=1$ *is* indeed (together with $k=n-1$) the worst choice.)

Let us now proceed to the average case running time (i.e., the expected running time), which satisfies the recurrence $$ S(n) = \begin{cases} \frac{1}{n-1}\sum\_{1 \leq k \leq n-1} \[S(k) + S(n-k)\] + n & \text{if } n \> 1 \\ 1 & \text{if } n = 1. \end{cases} $$ We can simplify the inductive case to $$ S(n) = \frac{2}{n-1} \sum\_{1 \leq k \leq n-1} S(k) + n. $$ This implies that for $n \geq 2$, $$ n S(n+1) = 2(S(1) + \cdots + S(n)) + (n+1)n, \\ (n-1) S(n) = 2(S(1) + \cdots + S(n-1)) + n(n-1). $$ Subtracting gives $$ nS(n+1) - (n-1)S(n) = 2S(n) + 2n \Longrightarrow nS(n+1) = (n+1)S(n) + 2n \Longrightarrow \\ \frac{S(n+1)}{n+1} = \frac{S(n)}{n} + \frac{2}{n+1}. $$ This shows that $$ \frac{S(n)}{n} = \frac{2}{n} + \frac{2}{n-1} + \cdots + \frac{2}{2} + \frac{S(1)}{1} = 2H\_n - 1 = \Theta(\log n), $$ and so $S(n) = \Theta(n\log n)$.

---
Tags: complexity-theory, time-complexity, mergesort
---


# Question
Title: Trouble finding what this recurrence solves to
I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$

I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.

# Answer
Hint: can you solve it for $n = 2^k$ where we replace $O(1)$ with constant $c$ and let $f(1) = c$? Then you have:

$$f(2^k) = 2f(2^{k-1}) + c$$

Then the pattern starts $f(1) = c$, $f(2) = 3c$, $f(4) = 7c$, $f(8) = 15c$... any guesses?
> 0 votes

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


# Question
Title: Show that the Language L is not regular (pumping lemma)
$L = \\{cda^nb^n\mid n\in \Bbb N\\} \cup \\{a,b,d\\}^\*$

Assuming $L$ is regular then there exist a pumping length $n$ for $L$. Lets use w = $cda^nb^n$.

Thus $w \in L$ and $|w| = 2n+2$ $\implies$ $|w| \geq n$.

$w$ can be splitted into three pieces $w = xyz$ with the following conditions:

* $|xy| \leq n$
* $|y| \geq 1$

Let be $x = cda^j$ and $y = a^k$ with $ k+j\leq n$ and $ k\geq 1$.

Now choose $i = 2$ so that $xy^iz = xyyz = cda^ja^ka^ka^{n-j-k}b^n = cda^{n+k}b^n$

$w$ has now more $a$'s than $b$'s (considering that $k$ is at least 1) $\implies w \notin L \implies$ $L$ is not regular.

**Is that enough for the proof?**

# Answer
Let me explain the easiest way to show that this language isn't context-free. It it were, then its intersection with $c(a+b+d)^\*$ would also be. This intersection is $cda^nb^n$. If the latter were context-free, then if we applied the homomorphism that erases $c,d$, the resulting language $a^nb^n$ would also be context-free; but we know that $a^nb^n$ isn't context-free.
> 2 votes

---
Tags: pumping-lemma, check-my-answer
---


# Question
Title: First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS
I am trying to state, whether the statement is true: During a DFS/BFS, first time visited nodes form a spanning tree, that has the same number of edges whether you use DFS or BFS. Is it true?

What I tried was to do both DFS and BFS on a couple of graph and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ, that's why I ask here.

Thanks

# Answer
> 0 votes
> What I tried was to do both DFS and BFS on a couple of graphs and the spanning tree I got was the same each time. But perhaps there are some graph, where it would differ.

Indeed, the spanning trees formed by the first-visited nodes might be different from DFS and BFS. For example, try a cycle graph of four vertices. When the spanning tree are different, the number of edges is still the same for both.

You might have noticed that the number of edges is always one less than the number of vertices of the graph, either by concentration or by luck, had you been playing with connected graphs long enough.

In fact, the number of edges in every spanning tree of a connected graph is always one less than the number of vertices in that graph. This comes from the following two facts.

* The number of edges in a tree is one less than the number of vertice of that tree.
* The vertices in a spanning tree of a connected graph are the vertices of that graph.

**Exercise.** What about disconnected graphs?

# Answer
> 0 votes
The trees constructed by BFS and DFS can be different. For example, if G is the triangle graph on vertex set $\\{a,b,c\\}$ and the traversal starts at vertex $a$, the BFS tree has edge set $\\{ab,ac\\}$, while the DFS tree has edge set $\\{ab,bc\\}$.

The BFS tree and the DFS tree both contain the same number of edges: if the traversal starts at vertex $a$ and the connected component of the graph containing vertex $a$ has $k$ vertices, then each of these trees will contain exactly $k-1$ edges.

---
Tags: graphs, spanning-trees
---


# Question
Title: What does a ball of center v and radius r with at most r hops away mean?
I am trying to understand what that sentence means. Intuitively, its obvious a radius ball means in a $ \mathbb{R}^{n}$ with respect to some norm. Its just the following set:

$$ B(v, r) = \\{ x \in \mathbb{R}^n : \\| v - x\\| \leq r\\}$$

i.e. its just all the points that are distance $ \\| v - x\\|^2 $ away from the center with respect to some norm $ \\| \cdot\\|$. However, in graph theory, if we have a graph $G = (V,E)$ I seem to have a much harder time to rigorously understand what this set means. Can someone help me define this set rigorously so that there is no doubt in my mind what it means to have a radius ball with at most radius $r$ in a fixed known graph $G = (V,E)$? In particular this is the sentence I am having a hard time understanding rigorously:

> a ball with center v and radius r is the set of vertices at most r hops away from v

---

For example, if I have a path from v1 to v2 to v3, then it has 3 hops. But if v1 also has v4 as a neighbor and we want a ball radius 3, does it mean that v4 should also be part of the set of radius 3 with center v1?

In fact, is the radius ball defined as follow:

$$ B(v,r) = \\{ x \in V : \exists path(v,x) s.t.| path(v,x)| \leq r \\}$$

or maybe it should be defined with shortest paths $\delta(v, \cdot)$:

$$ B(v,r) = \\{ x \in V : \delta(v,x) \leq r \\}$$

i.e. if you can get to a node from v in less that $r$ hops then its part of the radius ball on the graph.

---

In particular, consider the example. If we have a bounded degree say $d$ and the graph is undirected, if we have the radius be some finite number, do we necessarily have to include everyone's neighbor i.e. consider all the nodes in the degree?

# Answer
An undirected (possibly weighted) graph defines a metric space, in which the distance between two vertices $x$ and $y$ is the length of the shortest path between $x$ and $y$; here the length of the path is the sum of the weights on the edges (weights are assumed to be non-negative), or the number of edges if the graph is unweighted. Given a metric, a ball is defined according to your formula.

If the maximal degree is $d$, the number of vertices in a ball of radius $r$ is at most $1 + d(1+\cdots+(d-1)^{r-1})$, which is what you get for a $d$-regular graph.
> 1 votes

# Answer
$B(v,r)$ can be defined to be the set of vertices of the graph whose distance to $v$ is at most $r$. Thus $B(v,0) = \\{v\\}$, and $B(v,1) = \\{v\\} \cup N(v)$, where $N(v)$ is the set of neighbors of vertex $v$. If $D$ is the diameter of the graph, because every vertex has a distance at most $D$ to $v$, $B(v,D)$ is the entire vertex set $V(G)$ of the graph. We have $B(v,0) \subseteq B(v,1) \subseteq \cdots \subseteq B(v,D)$.

Both the formulae you give for $B(v,r)$ look correct because: there exists an $x-v$ path of length at most $r$ if and only if the length of a shortest $x-v$ path is also at most $r$.
> 0 votes

---
Tags: graphs
---


# Question
Title: Does real linear programming produce bipartite perfect matching using maxflow reduction?
Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram:

We can formulate max flow as an linear programming problem with integer variables in latter.

> 1. If we do not use integer variables does solving for maxflow in linear programming formulation with only real variables still produce valid perfect matching of given graph?
> 2. Is there a formal proof of this?

# Answer
> 3 votes
Let us consider $K\_{2,2}$, the complete bipartite graph with two vertices on either side. A valid max flow sends $1/2$ units of flow across each edge of the bipartite graph. This gives a negative answer to your first question.

On the other hand, the integral flow theorem guarantees that there exists an integral max flow, and such a max flow can be found algorithmically. An integral max flow does correspond to a maximum matching.

# Answer
> 1 votes
Just to respond to the above comment by the OP "why does linear programming for $K\_{2,2}$ fail". Perhaps your confusion is because we need to distinguish between "solving an LP" and "solving an LP using a particular algorithm".

The LP formulation of maxflow (with real variables) has optimal solution (1,0,1,0) (for the edges of the bipartite graph $K\_{2,2}$\- I'm ignoring the remaining edges incident to source and sink), which corresponds to a perfect matching. The optimal solution (0,1,0,1) also corresponds to a perfect matching. Any convex combination of these two vertex points, such as (0.5,0.5,0.5,0.5) or (0.3,0.7,0.3,0.7), is also an optimal solution to the LP and therefore can be obtained if you "solve the LP".

Visualize a polygon in two dimensions whose one side corresponds to the above convex combination of two corner points. The level set of the LP cost function is parallel to this side, and we are optimizing in a direction perpendicular to this side. So "solving the LP" (i.e. without reference to any particular algorithm) can give any point (not necessarily a corner point) from this side.

The latter two solutions are not vertices, and so if you "solve the LP using an algorithm that gives a vertex solution (eg, simplex)", then you are guaranteed a matching. Am I correct?

---
Tags: linear-programming, network-flow, integer-programming, bipartite-matching, bipartite-graph
---


# Question
Title: Regular expression notation clarification
For the alphabet $Σ$={a,b,c}

I was wondering how you would say:

> T that has elements from Σ, so could be T=a, T=bc

I was considering maybe $Σ^\*$ or $Σ^+$ would describe that, but I am not sure what both of them mean.

I guess $Σ^\*$={aa, aaa, ba, abc, ...} and not sure what $Σ^+$ is.

# Answer
Usually, $\Sigma^\*$ denotes the set of all strings of length zero or more over the alphabet $\Sigma$. Thus, $\Sigma^\* = \\{\epsilon, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc, aaa, \ldots\\}$, where $\epsilon$ denotes the empty string.

$\Sigma^+$ is the set of all strings of length $1$ or more over the alphabet $\Sigma$. Thus, $\Sigma^+ := \Sigma^\* - \\{\epsilon\\} = \\{a,b,c,aa,\ldots\\}$.
> 0 votes

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


# Question
Title: Is every edge of a graph included in some spanning tree?
Let's say we have a graph $G$. We pick one edge from it (any edge). Will there always be such a spanning tree that contains that very edge?

I think the answer is yes, because no matter what we do we can always create such a spanning tree so that the very edge we picked is included. Of course, a more formal proof would be needed?

# Answer
> 5 votes
Note that the initial graph $G$ needs to be connected or it has no spanning trees at all. (Though the same argument applied to each component would show that any graph has a spanning forest containing any chosen edge.)

Let $G=(V,E)$ be a connected graph, let $T$ be any spanning subtree and let $e$ be any edgein $E$. We claim that there is a spanning tree that includes $e$. If $e\in T$, we are done. Otherwise, $T+e$ contains a cycle. That cycle necessarily contains at least one edge $e'\neq e$ (actually, it contains at least two). $T+e-e'$ is a spanning tree that contains $e$.

You should prove to yourself that $T+e-e'$ really is a spanning tree.

# Answer
> 0 votes
Adding an edge to a tree causes a unique cycle. You can remove any edge from this cycle (different from the one you added) to get back a tree. This new tree contains the edge that was added.

---
Tags: graphs, spanning-trees
---


title: A query regarding P vs NP

text:
# Question
Title: A query regarding P vs NP
**Problem Statement:** Given a Problem $(A)$ such that: Any proposed solution $(S\_0)$ is guaranteed to be polynomial size w.r.t. $A$. Now, consider a fixed set of $K$ properties $\\{k\_0, k\_1,...k\_c\\}$, where each property is $coNP-Complete$.

For any solution $S\_0$ is considered a valid solution iff: "None of the property in $K$ has a $NO$ instance for $S\_0$".

***Example:*** For some hypothetical problem $(A')$ let the solution $S\_0'$ be a simple graph with $n$ nodes. Let $k\_i$ be the property: "$S\_0'$ does not contain a clique with $n/4$ nodes".

**Query:** Assuming the highly improbable scenario that $P=NP$, it implies $P=NP=co-NP)$. Thus, all the properties in $K$ are $P-Complete$. Does that imply that finding the solution $(S\_0)$ for $(A)$ is in $P$ ? It seems so but still need confirmation.

# Answer
Your problem is essentially a $NP^{coNP}$ problem. If $P=NP$ then the polynomial hierarchy collapses and your problem is in $P$.

If $P=NP=coNP$ then we can check in polynomial time whether a solution $S\_0$ is valid (using a polynomial-time algorithm to check each property, which exists because $coNP=P$). Thus, the problem is in $NP$, and thus, in $P$.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Minimum number of comparisons in comparison-based sorting algorithms
I've seen that every comparison-based sorting algorithm must perform at least $\log\_{2}(n!)=\Omega(nlog(n))$ comparisons on some input (*n* being the size of the input).

Why is the minimum number of comparisons $\log\_{2}(n!)$, and how is the omega-notation bound calculated?

# Answer
> 4 votes
Suppose the input array has $n$ elements. The goal of the sorting algorithm is to compute a permutation of $\\{1,2,\ldots,n\\}$ \- the permutation needed to sort the input. Let $A$ be the set of these $n!$ permutations.

Similar to the "guess my number" game (or the game of 20 questions), each comparison can reduce the search space by a factor of at most $2$. For example, after the first comparison is made, one obtains a partition $A= A\_1 \cup A\_2$, where $A\_1$ is the set of permutations in $A$ that are consistent with the comparison and $A\_2$ are the remaining permutations. The search space for the output is now restricted to $A\_1$. In the worst case, the size of $A\_1$ would be larger than that of $A\_2$, and so each comparison reduces the size of the search space by a factor of at most $2$. After each comparison is made, the search space is restricted further to those permutations which are consistent with all the comparisons made so far.

Hence, the number of comparisons required to reduce the size of the search space from $n!$ to $1$ is at least $\log\_2(n!)$. The product $1 \times 2 \times \cdots n$ is at least the product of the last $(n/2)$ numbers, which is $(n/2)^{n/2}$, and is at most $n^n$. Thus, $\log(n!)$ is sandwiched between $(n/2) \log (n/2)$ and $n \log n$, both of which have the same asymptotic growth rate $\Theta(n \log n)$.

# Answer
> 1 votes
There are `n!` possible orderings for `n` items. Each comparison reveals only 1 bit of information, so to choose one of `n!` orderings you need to perform at least `log2(n!)` comparisons.

`log(n!) < C*n*log(n)` for some C is known from Math, so `log(n!) = O(n*log(n))` by definition of O.

---
Tags: sorting
---


# Question
Title: Online Learning Resources for Discrete Mathematics
Are there any good Discrete mathematics learning web resources with problem sets?

# Answer
I have the perfect place for you, I really enjoyed it myself:

Discrete Mathematics lecture series on infocobuild

Everything I learned is from that site.
> 5 votes

# Answer
There is a whole course being offered by Udacity*, Logic and Discrete Mathematics, which has interactive quizzes and homework assignments.

The course description is as follows:

> This course presents key concepts in discrete mathematics, specifically, elementary propositional logic and elements of enumerative combinatorics, elementary number theory, and graph theory, with partially ordered sets and lattices as a unifying concept.

\*I am not affiliated with them in any way, but I have taken some of their prior courses
> 10 votes

# Answer
Kenneth Rosen's text "Discrete mathematics and its applications" is available on archive.org's opensource collection here. The PDF of the ebook can be downloaded (legally, it looks like).

Rosen's text is a classic for introductory discrete mathematics. Solutions to odd-numbered exercises are in the book.
> 0 votes

---
Tags: reference-request, education, discrete-mathematics
---


title: Uniqueness of minimum spanning tree

text:
# Question
Title: Uniqueness of minimum spanning tree
If G has a unique minimum spanning tree, does that mean the edge weights in G are also unique? if yes why and if no why?

# Answer
> 5 votes
If $G$ is a tree, it has a unique MST whatever its weights are. The weights could be unique, all the same, anything.

# Answer
> 0 votes
The question is: If $G$ has a unique MST, then are the edge weights necessarily distinct?

The answer is no. If $G$ is a tree with all edges having the same weight, then $G$ has a unique MST.

More generally, a minimum weight spanning tree must contain every edge that is a bridge (a bridge is an edge whose removal disconnects the graph). Consider a graph which contains two bridges, both having the same weight, and with the edges in the rest of the graph having distinct weights. Such a graph has a unique MST even though the edge weights are not all distinct because the bridges have the same weight.

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


# Question
Title: Define the time complexity of Kruskal's algorithm as function
I am trying to define the time complexity of Kruskal's algorithm as function dependant on:

* the number of vertices `V`
* the number of edges `E`
* the time complexity of verifying, whether two edges don't form a cycle `Ec(V)`
* the time complexity of connecting two sets of vertices `Vc(V)`

The edges are unsorted and I know the time complexity of sorting edges, which is `Big O(E * log E)`.

I don't really know, how to solve this problem and I would be grateful for any help. Thanks!

# Answer
> 1 votes
After sorting the edges, which takes $O(E \log E)$ time, Kruskal's algorithm adds the next cheapest edge which doesn't cause a cycle. The question is what data structure can be used to check if a given edge causes a cycle.

At any given point during the execution of the algorithm, the set of edges chosen by the algorithm forms a forest. Initially, the forest contains $n$ trees, where $n:=|V|$. If the next cheapest edge is $ab$, and vertices $a$ and $b$ belong to different trees in the forest, then the two trees can be combined into a larger tree.

A data structure for storing the above tree information is to store a parent value for each vertex. Following the parent pointer leads to the root node of the tree. If vertices $a$ and $b$ have different roots, then they belong to different trees. One can merge the two trees by making $b$ the parent of $a$. This allows us to maintain a collection of disjoint sets (each set is the vertex set of a tree), whose union is the vertex set of the graph.

So that the merging of two trees into one tree is done efficiently, the smaller tree can be put under the larger tree (i.e. the one with the smaller rank has its root node point to the other root). This ensures that the trees have small heights, and the path that is followed from a node to find its root has small length. Also, in order to not have to follow the same long sequence of parent pointers in subsequent iterations, one can store the root node's value after it is found. These are the "union-by-rank" and "path compression" heuristics, which efficiently implement Kruskal's algorithm, so that it runs in $O(E \log E) = O(E \log V)$ time.

---
Tags: graphs, graph-traversal, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Connection between max independent set and graph coloring
Is there any connection between the size of the largest independent set in a graph, and the minimum number of colors required to color the graph? I know that we can potentially color all the vertices in the largest independent set in the same color, but we know nothing about the rest of the vertices (besides being a vertex cover). Am I wrong?

# Answer
Let $n$ be the number of vertices of a graph $G$, $\chi(G)$ be its chromatic number, and $\alpha(G)$ be the size of its maximum independent set. Then $$ \alpha(G) \chi(G) \geq n. $$ The reason is that every color class in a legal coloring is an independent set.

The bound can be tight – simple examples are complete graphs ($\alpha(G) = 1$ and $\chi(G) = n$) and empty graphs ($\alpha(G) = n$ and $\chi(G) = 1$). More generally, if $G$ is a union of $m$ many $n/m$-cliques, then $\alpha(G) = m$ while $\chi(G) = n/m$; and if $G$ is a complete $m$-partite graph in which all parts have size $n/m$, then $\alpha(G) = n/m$ and $\chi(G) = m$.

The bound can also be far from tight. A simple example is the union of an independent set of size $n/2$ and a clique of size $n/2$: $\alpha(G) = n/2+1$ and $\chi(G) = n/2$.
> 3 votes

# Answer
Each color class is an independent set, and so has size at most $\alpha(G)$, the maximum size of an independent set. Hence, the number of color classes needed to cover the vertex set $V(G)$ is at least $|V(G)/\alpha(G)$. Thus, the chromatic number is at least $|V(G)/\alpha(G)$.
> 0 votes

---
Tags: graphs, colorings
---


# Question
Title: What is the meaning of 'breadth' in breadth first search?
I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book *Introduction to Algorithms by CLRS*, I read the following reason for this:

> Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.

However, I'm not able to understand the meaning of this statement. I'm confused about this word "frontier" and breadth of that frontier.

So, can someone please answer this question in a way which is easy to understand for a beginner like me?

# Answer
Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the **breadth** of the frontier. DFS will always pop the most recently discovered state off of the stack, thus always iterating over the **deepest** part of the frontier.

Consider the image below. Notice how the DFS goes straight to the deepest parts of the tree whereas BFS iterates over the breadth of each level.

Image here
> 23 votes

# Answer
The quote you gives says "the frontier between discovered and undiscovered vertices". So that's the frontier the author is talking about: the frontier between discovered and undiscovered vertices. You have some vertices that you haven't seen anything at all yet. You also have some vertices for which you've seen everything for. And then you have vertices in between. These are vertices that you've looked at, but you haven't loaded all of their children yet. This is the frontier.

The discusses this further on:

> To keep track of progress BFS colors each vertex white, gray, or black. All vertices start out white and may later become gray and then black. The vertex is discovered the first time it is encountered during the search, at which time it becomes non-white. Gray and black vertices, therefore, have been discovered, but BFS distinguishes between them to ensure that the search proceeds in a BF manner.
> ...
> each vertex is initially white, is grayed when it is discovered in the search, and is blacked when it is finished, that is, when its adjacency list has been examined completely.

So all vertices start out white (undiscovered). When a node is discovered, it's colored gray (frontier). When everything it points to has been discovered, it's colored black (completely discovered). The frontier is the set of points that have been discovered, but have undiscovered children.

Suppose you are looking for something on website. You first go to the main page. Suppose that's labelled "animals". The frontier is currently {"animals"}. You look through the main page and don't see what you are looking for. But you notice that it has links to two more pages, "quadrupeds" and "worms". So you click on the link to "quadrupeds". Now the frontier is {"animals","quadrupeds"}. You look through "quadrupeds" and don't find what you're look for. What do you do next? You can either look for links on "quadrupeds" and follow those, or go back to "animals" and click on the link to "worms". The first is a depth-first search, and the second is a breadth-first search.

"depth" refers to how many links from the root node it takes to get to a node, while "breadth" refers to nodes as the same depth. In the example above, BFS starts at "animals" and first looks at all the nodes of depth one, so it looks at "quadrupeds" and "worms" first. After it has looked at all the depth-1 nodes, its expands the frontier across all of those nodes; that is, it looks at the children of all of the depth-1 nodes before looking at any of the children of depth-2 nodes. So, for instance, if one of the links on the "quadrupeds" page is "primates", it will look at all of the links on the "worms" page before it looks at any of the links on the "primates" page.
> 3 votes

# Answer
Suppose the BFS algorithm is executed starting from vertex $a$. Imagine a wave that is sent out from $a$ (like a water-wave or tsunami). After one time step, the wave would have reached all the neighbors of $a$. After two time steps, the wave would have reached (or "visited") all the vertices which are at distance at most $2$ from $a$. And so on.

At any given time, the frontier of the wave is exactly the vertices that are stored in the queue data structure (these vertices have been visited but not yet explored further).

Thus, the wave initially reaches the entire "breadth" of all vertices which are at distance 1 from $a$. After some time steps, the wave would have covered the entire breadth up to some distance from the starting point $a$.

The set of vertices at distance $k$ from $a$ is called the $k$th layer in the distance partition of the graph with respect to vertex $a$. The vertex set is the disjoint union of these layers $(k \ge 0)$. The $0$th layer is $\\{a\\}$, the first layer is the set of neighbors of $a$, the second layer is the set of vertices whose distance to $a$ is two, and so on. The BFS algorithm visits the vertices of the graph in a particular order - layer by layer. Each layer covers the entire breadth, but the different layers are at different depth.

On the other hand, the DFS algorithm would explore as deep as possible in one direction (i.e. visit $a$'s first neighbor, then its neighbor, then its neighbor, and so on) before returning back to $a$ and visiting the next unexplored neighbor of $a$. This algorithm goes deep first, instead of visiting neighbors breadth-wise.

Thus, DFS and BFS differ in the order in which they visit the vertices.
> 1 votes

---
Tags: graphs, shortest-path, graph-traversal
---


# Question
Title: Is the language of all TMs *not* accepting a given string, Enumerable?
Is the following language in **RE**?
$$L = \\{\langle M\rangle : M\text{ is a TM that does not accept }010\\}$$

I could use Rice's Theorem with the property $P = \\{L : 010\text{ is not in }L\\}$ to show it isn't in **R**, but how do I show it is in **RE**?

# Answer
> 1 votes
The classic technique of dovetailing can be used to show the complement of $L$, $\\{\langle M\rangle : M\text{ is a TM that accept }010\\}$ is recursively enumerable. Check this answer for details.

Since $L$ is not decidable as shown by Rice's theorem, $L$ cannot be recursively enumerable.

---

**Exercise.** Show that $\\{\langle M\rangle : M\text{ is a TM that accept } 010\text{ and }101\\}$ is not in **RE**.

---
Tags: turing-machines, computability, semi-decidability
---


# Question
Title: Is it a tautology or not? According to my truth table its not
If $\bigr((q\leftrightarrow p)\leftrightarrow s\bigl)$ is a tautology and $p\rightarrow s$ is contingent, does it follow that $q\rightarrow s$ is contingent?

Since I can't show $\bigr((q\leftrightarrow p)\leftrightarrow s\bigl)$ is a tautology, I'm unsure how to proceed.

# Answer
The question is not phrased clearly. Perhaps the question can be rephrased as follows: Let $p,q$ and $s$ be propositions whose truth values belong to some subset $A \subseteq \\{T,F\\}^3$. Suppose $A$ is such that $(q \leftrightarrow p) \leftrightarrow s$ evaluates to true for each assignment from $A$ and $p \rightarrow s$ can take both possible truth values over assignments from $A$. Can $q \rightarrow s$ take both possible truth values over assignments from $A$?

But there are many $A$'s which satisfy the given two conditions, and different $A$'s will give different answers- it can be a contingency, or it can be tautology.
> 3 votes

# Answer
Let me start by conjecturing a more complete version of your question:

> Is it true that for any Boolean expressions $q,p,s$, if $(q \leftrightarrow p) \leftrightarrow s$ is a tautology and $p \to s$ is contingent, then necessarily $q \to s$ is contingent?

Equivalently,

> Is it true that for any subset $B$ of truth assignments for $(q,p,s)$, if $(q \leftrightarrow p) \leftrightarrow s$ is a tautology with respect to $B$ (i.e., every truth assignment in $B$ satisfies it) and $p \to s$ is contingent with respect to $B$ (i.e., some truth assignment in $B$ satisfies it, and another one falsifies it), then $q \to s$ is also contingent with respect to $B$?

The answer is negative: it doesn't follow that $q \to s$ is contingent. Suppose that $q = \bot$, $p = \lnot s$, and $s$ is a variable (i.e., its truth value is arbitrary). Then:

* $(q \leftrightarrow p) \leftrightarrow s$ is always true.
* $p \to s$ is true iff $s$ is true.
* $q \to s$ is always true.
> 2 votes

# Answer
$\bigr((q\leftrightarrow p)\leftrightarrow s\bigl)$ is not a tautology since setting $q=true$ $p=true$ and $s=false$ falsifies it. Your hypotheisis is then $false$. Since $false$ implies anything, you can conclude anything you want. However,if you replace $\bigr((q\leftrightarrow p)\leftrightarrow s\bigl)$ by a formula that is indeed a tautology,then you can simply use a truth table to check the conclusion.
> 0 votes

---
Tags: propositional-logic
---


# Question
Title: Why does not valiant's reduction show NP=RP?
Valiant converts $SAT$ formula to a $0/1$ matrix such that $Permanent$ of the matrix is $4^m\\#SAT$.

We know $Permanent$ can be approximated to $1+\epsilon$ factor with probability $1-\frac1\delta$ in time $poly(m|\epsilon|^{-1}\log\frac1\delta)$.

Why does not these two help me tell when number of witnesses to $SAT$ formula is $0$ in randomized polynomial time?

What do I miss?

# Answer
> 2 votes
As you state, Valiant shows how to construct, given a CNF $\varphi$, a polynomial size matrix whose permanent is a (known) multiple of the number of satisfying assignments of $\varphi$. Unfortunately, this matrix is not non-negative.

Given a non-negative matrix, you can determine whether its permanent is zero or not using an algorithm for bipartite perfect matching; and you can efficiently estimate its value. The same doesn't hold for general matrices.

Valiant further shows how to construct, given a CNF $\varphi$, a polynomial size 0/1 matrix, from whose permanent you can deduce the number of satisfying assignments of $\varphi$. However, the formula is not as simple as before, and in particular, neither bipartite perfect matching nor the efficient permanent estimation algorithms can determine whether $\varphi$ is satisfiable or not.

For details of a later version of this last reduction, see Section 5.1 of Ben-Dor and Halevi, Zero-One Permanent is #P-Complete, A Simpler Proof.

---
Tags: complexity-theory, counting
---