# Question
Title: Minimum number of scenarios to run to fully test a page
I run a testing application that, using Selenium, runs testing "scenarios" each of which visits a bunch of pages on a website. Each page is modeled by a Java file that contains locators, each of which are used to locate certain elements on the page maybe to verify that they exist or, beyond that, that they work as intended. Some elements may always show up, and some may only show up depending on the scenario you are running. Let's say the page we would like to test in question is the "login" page, and we are talking about all the scenarios that visit that page.

Bear in mind, some scenarios may visit the login page, but only a small subset of those scenarios are actually intended to test the login page.

Let's say each page is modeled by a Java source file that contains a bunch of locators intended to locate elements on that page.

Each scenario is intended to test a different overall functionality on the website, but as far as the login portion of each scenario is concerned, multiple scenarios might be totally redundant (only one of these redundant scenarios need to be run to achieve the exact same level of interaction). Let's say one set of redundant scenarios only minimally enters a username/password and then clicks the log in button. So our Java page always has the exact same sets of locators locating the same elements and not locating any elements for those redundant scenarios.

Let's say 100 of your scenarios visit the login page. Let's also say you ran all 100 scenarios to fully interact with that page, but only 10 of them needed to be run to achieve the same thing, that is, only 10 needed to be run to fully test the page.

Let's say each locator in the Java file modelling the login page is marked with the scenarios where it successfully located an element on the page. Each locator could have anywhere from 1 to 100 scenarios tagged to it.

Having already run the 100 scenarios, how do you go about knowing what those 10 scenarios are for future benefit? What sort of algorithm would achieve this? Thanks!

# Answer
> 1 votes
I would approach this a little differently.

Suppose you want to test a particular piece of functionality, e.g. logging in.

You first need to navigate to the login page, which may succeed or fail. Failure doesn't mean your test is failing; it means a *precondition* of your test, namely, being able to navigate to the login page, is failing. That's not what you're testing in this test.

Once you've arrived on the login page, you can attempt to log in, which may succeed or fail. This is the test you want to perform. If your test is correct, the results will correctly indicate whether logging in worked or not.

This is true in general: tests may generally have *preconditions* that aren't part of the test, but that can be tested themselves.

I think what you're trying to say is that many different paths may cause the precondition (in this case: the login page being reached) to be fulfilled, and testing those paths really should be separated from running the test that that precondition is a precondition for. We want to test those paths separately, and once we think they are reliable, use *any* of them to fulfill the precondition for the present test.

This can be formulated differently by saying: we'll assume that using the application will put us into certain consecutive *states*, and what we want to do is test each *transition* between states. Certain sequences of actions will (if they go well) bring us into a certain state, suitable as a starting point for performing the test we want to perform. The test will then perform another action, that is supposed to bring us into a certain state (the transition), and from the test we will be able to determine whether that state has actually been reached (whether the transition happened that is supposed to happen).

We can express this by modeling the behavior of the application as a state machine that contains the states the application can be in and the state transitions we want to test.

However, we also need to take input and output into account. Sometimes, state transitions depend on user input. For instance, supplying a correct combination of username and password produces the state of being logged in; supplying an incorrect combination produces the state of not being logged in. Furthermore, the output we see (the webpage being produced) may not correspond to a specific state, it may also depend on which transition was taken to arrive into that state. For instance, when a login attempt fails, we will see an error message, but the resulting state is one of not being logged in, not one of being shown an error message.

Therefore, it's a good idea to introduce input and output into the model, which turns our model into an I/O automaton.

So the idea is to specify the application's behavior using an I/O automaton, then to write tests to test each of its transitions. Given those tests, you can automatically generate a complete test suite to test the whole system, using various strategies. I even know a piece of software designed to do this: JTorX.

We'll need to add parametrization. For instance, when logged in, we're logged in as a specific user. The user we're logged in as is a parameter to the state of being logged in. We may need to check whether we're logged in by checking whether certain attributes of that user appear in certain positions on the page. So being able to parametrize the model by user may be important.

Furthermore, I'd factor the state machine into a Petri net or similar. For instance, being logged in is not really a state; it is an *attribute* of a state. Typically, being logged in we can do everything we can do when not logged in (except logging in), plus a couple of things we need to be logged in for. This can be modeled using Petri nets or some derivative (some sort of colored Petri net).

This approach will provide structure and meaning to your endeavor. Your 100 test scenarios will be paths in your I/O automaton transition graph. Your 10 paths are those of the 100 that lead from the initial state to the state in which you need to be in order to start the test at hand. The whole thing will be incomparably more understandable and concise than just specifying a zillion test scenarios and trying to group them afterwards.

Too bad Selenium, TestNG, or anything else I've worked with don't support this approach directly. If I were still working in test automation, I might have written something that does by now. The JTorX software is dead, as far as I know, but it may still be usable, or alternatives may be out there that use the same approach.

# Answer
> 0 votes
I think I may have the answer. I have tested it, but still not 100% confident it completely holds water in all situations, but so far I can't find any leaks and it seems to run decently fast. If it works, is it optimal?

1. Get the union of all the scenario IDs into a collection of unique ID strings (e.g. HashSet). Let's call this listing "union".
2. Create a copy of "union" called "result".
3. Cycle through each locator's listing of scenarios that successfully located something with that locator. Let's call each listing "myDetectedScenarios".
4. Try to remove, one at a time, each of the scenario IDs from "result", and try to remove that same ID as well as from all of the "myDetectedScenarios" listings. If removing it from any one of these listings causes it to be empty, then DON'T remove from anywhere. Otherwise, remove it from "result" and any listings using it.
5. The remaining scenario IDs in "result" will be the scenario IDs that can be minimally run to fully test the page.

---
Tags: algorithms
---


# Question
Title: Are regular and context free languages closed against making them prefix-free?
For a language L we define:

$\qquad A(L) = \\{ x \in L \mid \text{ no proper prefix of x is in L} \\} $

Are regular / context free languages closed under this operation ?

For regular languages I thought about taking the DFA that accepts the language L and create a new NFA by making all accepting states sinks (so the only way of being accepted by the automata is that when reading the last letter we reach an accepting state for the first time).

Can't we make the same thing with a pushdown automata for context free languages ?

Edit (as Raphael pointed out, the example below is wrong):

But here is a strange language that I think implies the opposite:
$L = \\{ 0^{i}1^{j}2^{n} \mid i \le n \ \text{ or }\ j \le n \\} $
$A(L) = \\{ 0^{i}1^{j}2^{n} \mid n = \min(i,j) \\} $

$L$ is context free but $A(L)$ isn't. Obviously, at least one of the things I wrote above is wrong. Anyone have any clue what is going on here ?

# Answer
> 7 votes
> Can't we make the same thing with a pushdown automata for context free languages ?

No. Your construction needs to start with a deterministic automaton, and PDAs cannot be determinized.

# Answer
> 7 votes
$\newcommand{\Pref}{\operatorname{Pref}}$With $\Pref(x)$ the set of all prefixes of $x$ (note that $x \in \Pref(x)$), I assume you intended to define

$\qquad A(L) = \\{ x \in L \mid (\Pref(x) \setminus \\{x\\}) \cap L = \emptyset$.

Now, note that

$\qquad A(L) = L \setminus ( L \cdot \Sigma^+ )$

and we immediately get that

$\qquad L \in \mathrm{REG} \implies A(L) \in \mathrm{REG}$

because regular languages are closed against concatenation and difference.

An automaton construction similar to yours works, too. Instead of making all final states sinks you have to reroute all edges leaving final states to (non-accepting) sinks, though. And you need to use deterministic automata, as otherwise only *some* accepting paths for non-prefix-free words may be cut short.

Towards an answer for context-free languages, we make two observations.

* $\mathrm{CFL}$ is not closed against difference¹.
* The Dyck language provides a non-trivial example, i.e. the size of both

$\qquad A(\mathrm{Dyck} \setminus \\{\varepsilon\\}) = \\{(^n )^n \mid n \geq 1\\}$

and its complement w.r.t. $\mathrm{Dyck}$ is infinite².

So we might guess that $\mathrm{CFL}$ is not closed against $A$ and start looking for a counter example. And indeed we find

$\qquad L = \\{ a^n b^n \mid n \geq 1 \\} \cup \\{ a^m b^n c^n \mid m, n \geq 1 \\} \in \mathrm{CFL}$

for which

$\qquad A(L) = \\{ a^n b^n \mid n \geq 1 \\} \cup \\{ a^m b^n c^n \mid m \> n \geq 1 \\}$.

We can show that $A(L) \notin \mathrm{CFL}$ with Ogden's lemma.

> Use $a^{2p} b^{p+1} c^{p+1}$ and mark all $b$. This ensures that $b$ have to be pumped, but not both $a$ *and* $c$ can be pumped; therefore pumping destroys (at least one of) the "conditions" $\\#\_a \> \\#\_b$ or $\\#\_b = \\#\_c$.

---

1. That does not prove anything!
2. Showing that either $A(L)$ or $L \setminus A(L)$ is always finite would be one way to prove closure.

# Answer
> -1 votes
Here is a proof that context-free languages in general, not only regular ones, are not closed against making them prefix-free.

Bare with me, as I will try to make it as formal as possible.

---

We will demonstrate that:

> **Theorem 1.** $NOPREFIX(L)$ are the $u\in L$ such that no proper prefix of $u$ is in $L$. Context-free languages are not closed under $NOPREFIX$.

First off, we will use the following three lemmas:

> **Lemma 1.1.** If $L\_1$ and $L\_2$ are context-free languages, then the *concatenation* of both languages, $L\_1.L\_2$, and the *union* of both languages, $L\_1 \cup L\_2$, are both context-free.

**Proof.** Let $G\_i$ be the context-free grammar that generates $L\_i$, with starting variable $S\_i$, for $i \in \\{1,2\\}$.

Then, a grammar that generates $L\_1.L\_2$ can be obtained by combining the productions of both grammars (distinguishing the variables) and adding the production: $$S \rightarrow S\_1S\_2$$

which is context-free, therefore being the language context-free.

Finally, a grammar that generates $L\_1 \cup L\_2$ is done with the same fashion: $$ S \rightarrow S\_1,\\;S\rightarrow S\_2 $$

which is also context-free, therefore also being the language context-free.

> **Lemma 1.2.** The language $L$, defined as: $$L=\\{a^ib^ic^i \\;:\\; i \geq 0\\}$$ is not context free. However, its complementary language, $\overline{L}$, is.

**Proof.** The proof that $L$ is not context-free can be easily done using the **pumping lemma for context-free languages**.

However, to prove that $\overline{L}$ is context-free, we must note that $\overline{L} = \overline{L\_1} \cup L\_2$, where:

$$L\_1\\;\text{is the language generated by the regular expression}\\;a\text{\*}b\text{\*}c\text{\*}$$ $$L\_2 = \\{a^ib^jc^k\\;:\\;i\neq j \\;\vee\\;j\neq k\\}$$

$\overline{L}$ is context-free, as it is the union of two context-free languages, using *lemma 1.1*: $\overline{L\_1}$ is regular for being the complementary of a regular language, therefore being context-free; $L\_2$ is context-free for being the union of two context-free languages (the one that verifies condition $i\neq j$ and the one that verifies condition $j \neq k$).

> **Lemma 1.3.** The language $\hat{L}\_i$, defined as: $$\hat{L}\_i=\\{a^jb^jc^j\\\\$^i \\;:\\; j \geq 0\\}$$ is not context free for any $i \geq 0$.

**Proof.** Note that $$\hat{L}\_i=\\{a^jb^jc^j: j \geq 0\\}.\\{\\\\$^i\\}$$ is the concatenation of two context-free languages, $\hat{L}\_i = \hat{L}^a.\hat{L}\_i^b$, where $$\hat{L}^a = \\{a^ib^ic^i \\;:\\; i \geq 0\\}$$ $$\hat{L}\_i^b = \\{\\\\$^i\\}$$

By *lemma 1.2*, $\hat{L}^a$ is context-free, and $\hat{L}\_i^b$ is regular, as it is finite and only has one word, therefore context-free. Using *lemma 1.1*, the concatenation of context-free languages is context-free, therefore being $\hat{L}\_i$ context-free for every $i \geq 0$. Note that the case $i=0$ is exactly *lemma 1.2*.

---

Now we can prove *theorem 1*.

**Proof.** The main idea behind the proof is to find a language that is context free, whose complement is not context-free. A perfect candidate is $\overline{L} = \overline{\\{a^ib^ic^i \\;:\\; i \geq 0\\}}$, although for this proof we can use any $L\_0$ that verifies that is context-free, but whose complementary doesn't, eveng when concatenating a finite amount of symbols that are not in the language's alphabet. We'll note $L\_0 = \overline{L}$. Our language is part of the alphabet $A = \\{a,b,c\\}$, $L\_0 \subseteq A\text{\*}$.

Now we'll use the following language: $$L=L\_0.\\{\\\\$\\} \cup A\text{\*}.\\{\\\\$\\\\$\\}$$

Where $\\\\$$ is a character such that $\\\\$ \notin A$. Clearly, $L$ is a context-free language, as it is formed as concatenations and unions of context-free languages (according to *lemma 1.1*): $A\text{\*}$ is regular, therefore context-free, and every finite language is regular, therefore $\\{\\\\$\\\\$\\}$ is regular, and also context-free; on the other hand, $L\_0.\\{\\\\$\\}$ is also context-free because of the same reason.

We will see $NOPREFIX(L)$ is not context-free.

Basically, we have to see that $u\\\\$\\\\$$ has no prefixes in $L$ if and only if $u \notin L\_0$. Indeed, if it were $u \in L\_0$, then we would have $u\\\\$ \in L$, because $u\\\\$ \in L\_0.\\{\\\\$\\}$. On the other hand, if $u\notin L\_0$, $u\\\\$\\\\$$ has no proper prefixes in $L\_0$: it is enough to see that $u\\\\$ \notin L\_0$ because the only words that end in just a single $\\\\$$ are from $L\_0.\\{\\\\$\\}$ (and $u \notin L\_0$); of course, $u$ neither any other of its prefixes will be in $L\_0$ because they do not end in $\\\\$$.

Therefore, we conclude that $NOPREFIX(L)$ is not context-free, as $NOPREFIX(L)=\\{u.\\{\\\\$\\\\$\\}:u\notin L\_0\\}=\overline{L\_0}.\\{\\\\$\\\\$\\}$ which is not context-free, using *lemma 1.3*.

---

Hope you found it helpful. This was one of the problems from my computing models exam in University of Granada, Spain. Have a great day you all!

---
Tags: formal-languages, regular-languages, context-free, closure-properties
---


# Question
Title: What do the ∀ and ∃ symbols mean in the Axiom of Choice?
On the Wikipedia page for the Axiom of Choice the following statement is given:

$(\forall x^\sigma)(\exists y^\tau)R(x,y)\rightarrow(\exists f^{\sigma \rightarrow \tau})(\forall x^\sigma)R(x, f(x))$

Most of it seems fairly straightforward, except for the meanings of the symbols that look like 180 degree rotated 'E' and 'A'

# Answer
> 13 votes
The symbols are quantifiers. They bind a new variable name to the symbolic logic statements. ∃ reads as there exists. ∀ reads for all so the first part of the statement would be read as:

> forall x (of type ), there exists a y (of type ) such that ...

# Answer
> 15 votes
$\forall$ reads as "for all", and $\exists$ reads as "there exists". So, in english we have

$$\text{"if }\underbrace{\text{for all $x$}}\_{\forall x^\sigma}\text{ }\underbrace{\text{exists a $y$}}\_{\exists y^\tau}\text{ with $R(x,y)$, }\underbrace{\text{then}}\_\to\text{ }\underbrace{\text{there is a function $f$}}\_{\exists f^{\sigma\to\tau}}\text{ so that }\underbrace{\text{for all $x$}}\_{\forall x^\sigma}\text{ holds $R(x,f(x))$".}$$

I skipped over the $\sigma$ and $\tau$ superscripts, as they indicate types and are not of primary importance here.

---
Tags: type-theory
---


# Question
Title: Need help with previous "Automata / Theory Of Computation" exam question
I passed by this question in a previous exam while studying for the "Automata / Theory Of Computation" and I am struggling to find answer. I would appreciate it if someone can help me with it:

This is the question:

a)On the basis of what was covered in class, draw the Venn diagram representing the following sets:

1.REXP: the set of the language given by all regular expressions

2.DFSA: the set of all languages recognized by deterministic FSAs

3.NFSA: the set of all languages recognized by non-deterministic FSAs

4.CFG: the set of all languages generated by context free grammars

5.PDA: the set of all languages recognized by PDAs

# Answer
> 1 votes
The relevant set-theoritic relations are $$ \mathsf{REXP} = \mathsf{DFSA} = \mathsf{NFSA} \subsetneq \mathsf{CFG} = \mathsf{PDA}. $$ The corresponding Venn diagram consists of two circles, one inside the other.

---
Tags: automata, finite-automata, context-free
---


title: Assignment problem or something else?

text:
# Question
Title: Assignment problem or something else?
My primary goal with this question is to identify the type of problem I have so I know what solution to pursue. I think it's either an instance of the assignment problem or the fair item allocation problem, though I can also envision a solution that involves a variation on the stable marriage problem.

The question:

Is there an existing definition of the assignment problem where the solution is not to get as many people as possible their #1 option, but to get the group as a whole the highest preference level of assignments? In other words, the important thing is not that "as many agents as possible get their highest preference." An agent will sacrifice a higher preference for a slightly lower one if it means that another agent will move up to a higher preference.

Example: Alice **would not** swap her 1st preference for her 8th so that Bob can get from his 7th to his 6th. But Alice **would** swap her 1st for her 3rd if it means Bob gets from his 8th to his 4th.

Obviously, there's a lot of subjectivity in what constitutes acceptable tradeoffs, but I'm thinking about ways to define and account for that.

If I visualize it as ships in a harbor, the ideal solution is one where it's a calm day, no movement on the water. Everybody is at the same level--hopefully at high tide. :) Solutions that are more stormy, where some or a lot of ships are up while others are down, are less desirable, even if the average level among them is high.

I think the term for what I'm *not* looking for is rank-maximal allocation. I can't find the term for the solution I do want. But this may just be a gap in my understanding.

More context:

I'm coming to these as a layman, so I'm lost in some of the formal notation and theory, though the concepts are generally clear enough. This is very much a "down the rabbit hole" situation for me. My wife has an event at work where she has to assign groups to projects. She usually does it by hand, and she asked me if there's a program to do it. I said, "There must be." Now that I know how much I don't know, I'm looking for a nudge in the right direction. :)

Here's my scenario: 8 groups, 8 projects. Each group can have one project, each project one group. Each group submits an ordinal preference for which project they would like to have (1 for the most preferred, 8 for the least). The goal is to find the best combination of assignments for the groups as a whole.

To give a simple hypothetical example. The following two scenarios are available.

Scenario A:

* Alice gets 1st choice
* Bob gets 1st choice
* Charlie gets 3rd choice

Scenario B:

* Alice gets 2nd choice
* Bob gets 2nd choice
* Charlie gets 2nd choice

All of the agents will agree that Scenario B is preferable. No one gets their 1st choice, but no one has to accept their 3rd.

The assignment problem is a good fit except, as I understand it, the solutions all value giving as many agents as possible their #1 choice, or finding the "lowest cost" solution. So solutions to the assignment problem would find Scenario A above to be the better solution. In my scenario, the best solution may not include *anyone* getting their 1st choice. All agents would gladly trade their first choice for their second or third if it means another agent gets to move up from a low preference to a higher preference.

This Q&A made me look at the stable marriage problem, but the issue I run into there is that the projects have no preferences. So I thought, well, maybe I can do SMP with indifference, where one side is completely indifferent. But my gut tells me that's the same thing as the assignment problem. I need the suitors to care about each other's outcomes almost as much as their own.

My next stop was the fair item allocation problem. I think this might be closer to what I'm looking for, but I struggled to understand all the different fairness criteria. It felt more complex than the problem I'm trying to solve, though I may be underestimating my problem.

I'm tempted to use this Hungarian Algorithm solver. My gut is that it would be highly likely to produce an acceptable solution. My problem is that I can't stop thinking about whether or not there's a more optimal solution.

I think with my level of knowledge here, my trying to cook up hypotheticals might just be more confusing. But I'll try to reemphasize the standard the ideal solution would meet, barring everyone getting their 1st choice:

* gap between "best" (most preferred) and "worst" (least preferred) assignment is as close to 0 as possible
* maximum number of assignment possible are "highly preferred" (say in the 1-4 range)
* it is acceptable to grow the gap to increase highly preferred assignments up to a point -- we can thin the cluster to shift its preference value higher, but we don't want to drop anyone too far.

The solution I'm thinking of now would be something like this: use the Hungarian Algorithm to get the rank-maximal allocation, then implement some kind of a swap meet where each agent considers his neighbor to see if a trade would result in a better overall outcome. I don't want to go too far down that path if I'd be ignoring a better solution. Or if the Hungarian algorithm *is* the solution and it's just a matter of getting over my own mental blocks. :)

Which type of problem do I actually have? Other than that I can't stop thinking about this?

# Answer
# General remarks

You don't seem clear yet on what it is you're trying to optimize. As such, this question is not well-posed and not solvable. The first step in such situations is for you to figure out an objective function that measures how happy you are with a given solution. That formalizes the specification of what you want. Until you can do that, it's not reasonable to expect a computer to find what you want when you're not even sure what exactly you want. Only once you have such a characterization of what you're seeking does it make sense to ask for an algorithm to solve it.

There are several things you might be trying to optimize. I'll answer for two of them.

# Maximizing the total happiness

Suppose we imagine that there is some amount of happiness that occurs if you match a group to a project, and we want to find an assignment that maximizes the sum of happinesses.

This can be solved by finding a maximum matching in a bipartite graph. You have one vertex for each group and one vertex for each project, and an edge between a group and a project that describes the utility/reward if that group is assigned to that project. Then, use any standard algorithm for maximum bipartite matching, such as the Hungarian algorithm.

I'd suggest that you don't think of this in terms of ranked preferences (your #1 preferred project, your #2 choice) but rather in terms of ratings (e.g., I'd be 100 units of happiness if I'm assigned this project, 50 units of happiness for that one, etc.). Ratings are more powerful and encode more information than rankings: given ratings, you can infer what the rankings would be if you wanted, but it also contains extra information about how much more I prefer my #1 choice over my #2 choice. This can lead to a better solution. It does require people to provide more information about their preferences, but that additional information might lead to a better solution, so it seems worthwhile.

Maximum bipartite matching is a special case of the assignment problem, so you could also view this as an instance of the assignment problem: you can convert rewards to costs by negating the value (so a utility/reward of $10$ corresponds to a cost of $-10$), then running an algorithm for the assignment problem.

# Maximizing the least-happy group

Alternatively, suppose you measure how happy you are with an assignment overall by how happy is the unhappiest group.

Then this too can be solved by maximum matching. A simple approach is to use binary search: guess a threshold $t$, build a bipartite graph with an edge from a group $g$ to a project $p$ if $g$ would have happiness $\ge t$ if assigned to $p$. (Ignore all other pairs $g,p$ that yield less happiness.) Then check whether there is a perfect matching in this group. If yes, then it is possible to find an assignment that assures all groups have happiness $\ge t$; if not, then it is impossible. Finally, do binary search on $t$ to find the largest $t$ for which such an assignment exists. The running time will be the time to find a perfect matching (e.g., using the Hungarian algorithm), multiplied by a logarithmic factor (for the binary search).

There may be faster algorithms, but this one is conceptually simple to understand.
> 1 votes

---
Tags: assignment-problem
---


title: Is this a deadlock?

text:
# Question
Title: Is this a deadlock?
Consider we have two processes P1 and P2. There are also two semaphores M and N which are initialized to zero. Here's how they execute:

```
+-----------+-----------+
|    P1     |    P2     |
+-----------+-----------+
| wait(M)   | wait(N)   |
| ...       | ...       |
| wait(N)   | wait(M)   |
| ...       | ...       |
| signal(N) | signal(M) |
| signal(M) | signal(N) |
+-----------+-----------+

```

So neither of the process will go through the first statement because the value of both M and N are zero, so they both get blocked.

But if the initialization value for both M and N were 1, then they successfully execute, with no deadlock.

Can this be considered deadlock solely because of the faulty initialization of the semaphore?

# Answer
> 0 votes
Assuming the semaphore only has 1 slot, Yes it can lead to Deadlock

Improper use of semaphores with wait queues can cause deadlock, As a good programming practice, a semaphore should be initialized once at the very beginning of your program and before the threads which use it are created. It is a bad practice to reinitialize semaphores in the middle of program execution.

Deadlock means a group of processes are all waiting for each other for some event.

For example (the following system has the potential for deadlock; see Deadlock.java):

```
Semaphore s=1, q=1

process p0 {
   s.acquire();
   q.acquire();
   ...
   s.release();
   q.release();
}

process p1 {
   q.acquire();
   s.acquire();
   ...
   q.release();
   s.release();
}

```

If p0 executes S.acquire(), then p1 executes Q.acquire(), the processes become deadlocked.

Solution:

```
Semaphore s=1, q=1;

process p0 {
   // order matters a great deal on the waits
   q.acquire();
   s.acquire();
   ...
   // order does not matter that much on the signals
   s.release();
   q.release();
}

process p1 {
   // order matters a great deal on the waits
   q.acquire();
   s.acquire();
   ...
   // order does not matter that much on the signals
   q.release();
   s.release();
}

```

Contrast deadlock with livelock, where a thread continuously attempts an action that fails.

A single semaphore will not deadlock unless it is being misused.

Semaphores Deadlock

# Answer
> 0 votes
It is a *possible* deadlock. There will be an *actual* deadlock if each process manages to execute one “wait” before the other one manages to execute the second “wait”.

That will happen if both processes try to run their code at almost exactly the same time. Since this is very time dependent, that kind of code will deadlock very rarely - which makes that kind of problem very hard to reproduce and therefore very hard to fix.

---
Tags: operating-systems, concurrency, deadlocks
---


# Question
Title: Pseudo code of recursive method of printing all permutations of $n$ given integers
I really don't understand this pseudo code. The function prints all permutations of $n$ given integers, assuming that all numbers are different.

Is there a way to explain this code more easily as I really don't get the purpose of the swapping.

```
PERMUTATE(A, start, end)
   if start == end return A
   else
      PERMUTATE(A,start+1,end)
      for i = start+1 to end
         SWAP(A[i],A[start])
         PERMUTATE(A,start+1,end)
         SWAP(A[start],A[i])

```

# Answer
Your procedure produces all permutations of the input, returning it to its original state at the end.

When the input has length 1, there is nothing to do.

Otherwise, suppose that the input is $a\_1,\ldots,a\_n$. Let us represent all permutations of $a\_1,\ldots,a\_n$ as $\[a\_1,\ldots,a\_n\]$.

Here is what the procedure does:

* Output $a\_1,\[a\_2,a\_3,\ldots,a\_{n-1},a\_n\]$.
* Output $a\_2,\[a\_1,a\_3,\ldots,a\_{n-1},a\_n\]$.
* Output $a\_3,\[a\_2,a\_1,\ldots,a\_{n-1},a\_n\]$.
* ...
* Output $a\_n,\[a\_2,a\_3,\ldots,a\_{n-1},a\_1\]$.

In the first step, the procedure just goes over all permutations of the tail of the list, consisting of all but the first element.

In the second step, it switches $a\_1$ and $a\_2$, goes over all permutations of the tail, and then switches $a\_1$ and $a\_2$ back.

In the third step, it switches $a\_1$ and $a\_3$, goes over all permutations of the tail, and then switches $a\_1$ and $a\_3$ back.

And so on, until in the $n$th step, it switches $a\_1$ and $a\_n$, goes over all permutations of the tail, and then switches $a\_1$ and $a\_n$ back.
> 1 votes

---
Tags: recursion, permutations, pseudocode
---


# Question
Title: Maximum number of similar groups of a given size that can be made from a given array
I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$.

I need to find the maximum number of groups with the exact same contents and of size $A$ that can be made from the elements of $B$. Once an element is used in a group it is exhausted. A group can have more than one element with the same value as long as the element is still available in $B$.

Example:

1. If the input array is $\\{1, 2, 3, 1, 2, 3, 4\\}$, and the group size is $3$ the maximum number of groups that can be made is $2$, which are $\\{1, 2, 3\\}$ and $\\{1, 2, 3\\}$.
2. If the input array is $\\{1, 3, 3, 3, 6, 3, 10\\}$, and the group size is $4$ the maximum number of groups that can be made is $1$, which is $\\{1, 3, 3, 3\\}$.

What I have tried so far, is to frame some equations ( given below ) but after that, I am struggling to come up with an algorithm to solve them.

Let $F\_1$ be the frequency of the element $B\_1$, $F\_2$ be the frequency of the element $B\_2$ and so on till $B\_n$, where $B\_1 \dots B\_n$ are distinct elements from the array $B$.

Now I need to choose $n\_1, n\_2, \dots n\_i$ such that

1. $n\_1 + n\_2 + \dots + n\_i = A$
2. $k\cdot n\_1 \leq F\_1\text{ , } k\cdot n\_2 \leq F\_2\text{ , }\dots \text{ , }k\cdot n\_i \leq F\_i$
3. $k$ is the number of groups and we need to maximize it.

Length of $B$ can be as large as $10^5$ and $A$ can also be as large as $10^5$.

Please help me find a greedy or dynamic approach to the problem.

# Answer
The function $$f:\mathbb{N}\rightarrow\\{0, 1\\}:f(k) = \begin{cases} 1; &\text{if there is a solution of size $k$,}\\ 0; &\text{otherwise} \end{cases} $$ is monoton, since if there is no solution of size $k$ then there is no solution of size $k+1$. That means we can binary search the value of $k$ in the interval $\[1, |B|\]$, and output the greatest $k$ for which there is a solution of size $k$. Thereby, we turned the problem into a decision problem with an $O(\log |B|)$ factor in the running time.

For a fixed value of $k$, a greedy solution suffices. If we have $F\_i$ copies of some element $B\_i$, then each set can contain at most $\left\lfloor\frac{F\_i}{k}\right\rfloor$ of this element. So we have a solution of size $k$ if and only if $$\sum\limits\_{i=1}^{n} \left\lfloor\frac{F\_i}{k}\right\rfloor \geq A.$$

As an exercise, try to prove that the greedy solution is optimal. The running time can be bounded in $O(|B|\log|B|).$
> 1 votes

---
Tags: dynamic-programming, greedy-algorithms, mathematical-analysis, algorithm-design
---


# Question
Title: Search for maximal value smaller than V in an array composed of K linear functions
Sorry for the lack of clarity in the question description.

I have an array composed of length $N$ composed of $K$ linear subarrays. We define a linear subarray as a contiguous subarray of the array $\[l,r\]$ where $A\[i\]-A\[i-1\] = C$, a constant, for all $l\<i\<=r$. (Note: $C$ may be different for different subarrays; the elements of the array are integers.) Please note that the linear subarrays *are not disjoint* (there is one element intersection between any pair of adjacent linear subarrays). For example, \[1,3,5,4,3,2\] has two linear subarrays: \[1,3,5\] and \[5,4,3,2\]. \[1,3,5,1,2,3\] would have three: \[1,3,5\], \[5,1\], \[1,2,3\].

I wish to find multiple queries for the maximal value that is less than a queried value $V$, in $o(K)$ and $o(N)$ time per query, with $o(K^2)$ and $o(N)$ preprocessing. (Assume that the array has already been stored in terms of the *K* linear subarrays, perhaps in terms of the constant *C* and length of each subarray, with the subarrays ordered. Therefore, you are given the array with the starting and ending points of all the linear subarrays, as well as the linear constant *C*, as described before. So, one does not need to derive the linear subarrays in the first place.) Otherwise, a proof (formal or not) that it is not possible to do so would be appreciated.

Of course, a balanced binary search tree (BBST) or simply sorting achieves the purpose, but it requires $O(NlogN)$ preprocessing, which is too much. Checking the largest valid value within each subarray takes $O(K)$ per query, which is again too much. Would it be possible for something to combine both of these, perhaps?

Randomised algorithms are okay as long as they always achieve the correct answer and work fast enough in the average case, though deterministic algorithms are preferred.

Thanks for any and all responses. I was wondering if there was any research in the question, maybe? It does not seem like too obscure a topic, but unfortunately my searching has not been competent enough.

EDIT: A method that seems useful.

Here was my line of thinking after I asked the question; I wonder if this would help somehow. It uses the idea of modulo as well. Initialise `V=0`, and allow each linear subarray to be stored as `L,R`; where `L` is the minimal value of the subarray and `R` is the maximal value. When we are given a query for `V`, we somehow disinclude elements where `L>V` and `R<V` (perhaps by using multiple dimensions?) A supplementary data structure stores the minimal theoretical difference of the element in the array, which is something like `L - V mod c[i]`. So essentially, we now need to be able to run a range add on this data structure, but if the value of any element becomes `<0` or `>=c[i]` it needs to be reset (eg. if an element becomes equal to -1 with c\[i\]=5 it would be reset to 4; if an element becoming equal to 6 with the same c\[i\] would be reset to 1); and also run range minimum queries.

If such a data structure can be made, the problem is solved. The trouble is the modulo, as range add and range minimum query can be easily done with a segment tree and lazy propagation; as well as the disinclusion of certain elements.

# Answer
> 3 votes
It is not possible to guarantee to find the maximal value that is less than a queried value $V$ in $o(K)$ time with preprocessing in $o(N)$ time.

This can be seen easily in the following extreme case. Let $A$ be any array of $N$ integers, which is composed of the following $K=N-1$ linear subarrays.

* the subarray $A\[0\], A\[1\]$ with $C=A\[1\]-A\[0\]$.
* the subarray $A\[1\], A\[2\]$ with $C=A\[2\]-A\[1\]$.
* $\cdots$
* the subarray $A\[N-2\], A\[N-1\]$ with $C=A\[N-1\]-A\[N-2\]$.

With $o(N)$ time preprocessing and $o(K)=o(N)$ time processing, an algorithm will not be able to even read some number in $A$ when $N$ is large enough. (In fact, most of the numbers in $A$.) So, for some queried value $q$, the algorithm will fail to recognize that $q+1$ appears in $A$.

(The explanation above could be made more rigorous, for example, using the formal method of adversary and a well-defined model of computation.)

---

It looks like the more interesting question to ask should be whether there is an algorithm with $o(N\log N)$ preprocessing and $o(K)$ per query. Or whether there is algorithm with $o(N)$ preprocessing and $o(K)$ per query given $K=o(N)$. That sounds like another question, anyway.

---
Tags: algorithms, data-structures, search-algorithms
---


# Question
Title: Need help understanding the tuple relational calculus
We say that a query in a TRC is a statement of the form $\\{T: P(T)\\}$, where $T$ is a tuple variable and $P(T)$ is a formula.

Now my question is, what are the possible tuples $T$ to be tested i.e., what are the types and values for tested tuples.

As far as I know in set theory and in particular in set builder notation the variables should come from another well-defined set.

# Answer
From Wikipedia:

A tuple is of the form $T=(D,R,h)$ where $D$ is the domain, $R$ is a set of relation names, and $h$ is a mapping that associates a column name to each relation in $R$. To represent a tuple, we can see $D$ as the set of keys, and $R$ the table associated with those set of keys, and $h$ the column names of the table.
> 1 votes

---
Tags: databases, relational-calculus, tuple-relational-calculus
---


# Question
Title: Why octal and hexadecimal? Computers use binary and humans decimals
Why do we use other bases which are neither binary (for computers) nor decimals (for humans)?

Computers end up representing them in binary, and humans strongly prefer getting their decimal representation. Why not stick to these two bases?

# Answer
Octal (base-8) and hexadecimal (base-16) numbers are a reasonable compromise between the binary (base-2) system computers use and decimal (base-10) system most humans use.

Computers aren't good at multiple symbols, thus base 2 (where you only have 2 symbols) is suitable for them while longer strings ,numbers with more digits, are less of a problem. Humans are very good with multiple symbols, but aren't that good in remembering longer strings.

Octal and hex use the human advantage that they can work with lots of symbols while it is still easily convertible back and forth between binary, because every hex digit represents 4 binary digits ($16=2^4$) and every octal digit represents 3 ($8=2^3$). I think hex wins over octal because it can easily be used to represent bytes and 16/32/64-bit numbers.
> 19 votes

# Answer
We use them for convenience and brevity.

Hex and Oct are really outstanding compressed representations of binary. Hex in particular is well suited to condensed forms of memory addresses. Every oct digit directly maps to 3 binary bits and every hex digit to 4 binary bits. This is a result of the bases (8 and 16) being powers of 2 ($2^3$ and $2^4$). For example, I can write binary $01101001$ as hex $69$ or if I extend it with a leading zero as oct $151$.

So, say you need a 64 bit memory addresses. You can either look at all 64 binary bits, or get it condensed to 16 hex digits. Often you don't need to compare a few addresses to see if their the same or contiguous. Would you rather look at 64 bits or 16 digits?
> 14 votes

# Answer
Binary numbers in text are a waste of space.

Decimal shows no relation to powers of $2$. Often the fact that a number is, say $5\cdot 2^n-1$, is more important than how much that is.
> 6 votes

# Answer
## Introduction

As already mentioned by other answers, there can be different notations for different purposes and constraints. Notations is actually an encoding as a sequence of characters, and we know from the study of algorithms and data structure that there are many ways we can encode abstract concepts, a list or a set for example, depending on what we want to do with it. In this case it is mostly algorithmic convenience.

When considering representation of numbers, the same applies. Inside the computer, everything is binary at the lowest level, though stranger representations can be used for some applications.

Outside the computer, we use any kind of human understandable representation, depending on human convenience regarding the kind of value represented. Binary representation is often too long and unstructured to be read and written easily, thus making place to hexadecimal or octal. **The choice may often have to do with the way information is structured in a binary word, which is not necessarily intended to represent a number.**

But, **when considering only numerals**, i.e. representation of numbers, it is worth looking at other number representation systems to understand that **major factors are: physiology, habit, and convenience.** Convenience is of course the leading factor creating diversity, as it depends on context of use.

## A wider look

It is surprising that all answers so far consider only decimal and base $2^n$ systems, mostly binary, octal and heaxdecimal.

The body of the question seem in no way restricted to computers, and humans have been and are still using several other numeration systems. Some of them are even used within computers, for example when dealing with long integers (not to mention *non integer numerals*).

A first remark is that when people count in thousands, or millions as a unit, this is still considered decimal, because these are powers of 10. So one might wonder why octal or hexadecimal should not be considered just a variation on binary. One possible reason may be the number of symbols used to represent numbers (though that is disputable issue, as we shall see with other systems).

Then, regarding humans, they using several system in base 5, called **quinary systems**. Actually, most of these system are with two bases, the second one being 2 or 4, alternating with the base five, which makes them equivalent to base 10 (decimal) or base 20 (vigesimal). Guess where that comes from :)

These double-base systems are called bi-quinary or quadri-quinary systems. Pure quinary is rarely used.

Roman numeral may be seen as bi-quinary system (which is an indication on how to do arithmetics with them). Chinese and Japanese abacus use bi-quinary. Quadri-quinary was used by the Mayas.

The reason for using a system are probably many. One good reason is that it was the first local design, and people are now used to it. For example, one might wonder as well why English speaking people are still using an extremely weird numeration system when trying to measure distances. You could argue thet it is a matter of multiple units, not numbering, but that is a very weak remark. Numbers are used mainly to measure things.

Other reasons for keeping a system is convenience in a given context. There may be a trade-off between the number of different symbols, or positions on an abacus, and the number of symbol occurencess required to form sufficiently large numbers. Base 2 works with 2 distinct symbols, but has lots of occurences, which may be inconvenient for a material representation. Vigesimal base 20 would require twenty symbols, and very big multiplication tables that people would not remember. But a bi-quinary or quadri-quinary system is a lot more manageable, especially to build abacus. Pure quinary system would probably be even better, but it goes against physiology based habits and intuition. And it is always nice to be able to use our fingers to count with, when we do not know any better.

But that is not all.

One very old and very common system is the **sexagesimal system** used to measure time and angles (but we know they are related, through Earth rotation). It uses base 60, but does not use 60 symbols as that is far too many. So it relies on another system to represent its synbols (such as the decimal system).

The circle can be divided in 6 parts corresponding to 60 degrees angles, which are the simplest to build with equilateral triangles. Then Each degree is 60 minutes of arc, each divided in 60 seconds.

According to wikipedia

> It originated with the ancient Sumerians in the 3rd millennium BC, it was passed down to the ancient Babylonians, and it is still used —in a modified form —for measuring time, angles, and geographic coordinates.

Considering the origin it was a pretty convenient system, at a time when mathematics were hardly entering infancy. Not only is the 60⁰ angle easy to draw, but 60 has a lot of factors, so that it allowed for dividing in many way with integers, without a remainder.

Physiologically, it can be related to a duodecimal-quinary system, base 12 and 5. Base 12 is convenient as it can be used when counting on finger bones of 4 fingers with the thumb of the same hand. Then the fingers of the other hand give the quinary component. And $12\times 5=60$.

But there are other ways to get to 60, such as the vigesimal-ternary system of Babylonians.

Why do we still use the sexagesimal system. I guess we are just used to it, and we may have too many conflicting issues for a change to be fully justified.

It is interesting to note that there is much interplay between numbering systems and unit systems. But this is to be expected since measure is a major role for numbers. This is noticeable in the opposition between the decimal and binary metrics for memory size.
> 2 votes

# Answer
Computers understand binary numbers and in binary, the weights of the number are in power of 2, therefore the number of digits to represent a number may be large depending on the number.

Say, 64 in decimal can be represented by 7 bits whereas to represent number 5000 we require 13 bits.

Octal and hexadecimal number system are **compact way** of representing a binary number.
> -1 votes

---
Tags: numeral-representations
---


# Question
Title: Why not implement Union-Find structure using root as the direct parent?
I just learned about using UF with union by rank and path compression. A path can be compressed via attaching a node to its root after Find is called on the node. If the goal here is to flatten the tree, why not just implement the tree such that each node is directly attached to its root (instead of its true parent)? That way, maximum compression would be achieved from the start. What is the con of this as long as union by rank is used along with it?

# Answer
> 3 votes
Because then a Union operation would be very slow: when you Union two trees, you would have to reparent all of the nodes in one of the trees.

---
Tags: complexity-theory, union-find
---


# Question
Title: How create DFA with multiple finished states for lexers?
Is possible to create DFA directly from regular expression. But for lexical analyse is needed "joined" DFA with many finish states, for example one state for string, one for integers, one for floats etc. How do such DFA? Maybe convert many DFA's to one or join DFA's to one NFA and next convert it to DFA?

# Answer
> 1 votes
As Rick Decker rightly noted, real-world lexical analysers produce a DFA with multiple final states.

Lexical analysers created via Lex-like generators differ from theoretical DFAs in several respects, and this is only one of them. Another obvious difference is that they don't stop at the end of the input string.

Instead, lexical analyser generators generally work as if they ran all DFAs corresponding to the lexer rules in parallel (in practice using a DFA with multiple end states), and applying the following rules:

1. The DFA that "wins" is the one that proceeded the furthest (often called the "maximal munch" rule).
2. If more than one DFA would accept that maximal-length input, the one that occurred first in the specification file "wins" (the disambiguation rule).

The disambiguation rule is used, for example, to distinguish keywords (e.g. `if`, `else`, `while`) from identifiers. Ignoring underscores for the moment, an identifier is (typically) any lexeme that starts with an alphabetic character followed zero or more alphanumeric characters, *but isn't a keyword*. You could create a regular expression which matches this, but it's much easier to specify keywords before identifiers and let the lexical analyser generator do the disambiguation for you.

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


# Question
Title: What is the time complexity of FC_MRV algorithm?
I am studying CSP and read the papers on it.I wanted to know the time complexity of Forward checking with Minium Remaining Value algorithm.

# Answer
The worst case complexity of FC-MRV is $O(n^2 d^2)$ where $n$ is the number of variables and $d$ is the number of domain size.
> 0 votes

---
Tags: time-complexity, constraint-satisfaction, constraint-programming
---


title: Why is n log n dominated by n log^2 n?

text:
# Question
Title: Why is n log n dominated by n log^2 n?
Does the rule of $n ^ a$ dominate $n ^ b$ if $a \> b$ apply here as well?

My understanding is that $n \log n$ will be dominated by $n \log ^2 n$ because of $\log$ being raised to the power of $2$.

# Answer
**little-oh proof**

An equivalent but more straightforward question would be why $\lg n$ is *dominated by* $\lg^2 n$, that is why $\lg n \in o(\lg^2 n)$.

Then based on the definition of little-oh we need to show that for any choice of constant $ c \> 0 $, we can find a constant $ n\_0 $ such that the inequality $ \lg n \< c \lg^2n $ holds for all $ n \> n\_0 $.

We prove that if we pick $ n\_0 = \sqrt\[c\]{b} $ where $ b $ is the base of $ \lg $, then the definition above holds.

If $ n\_0 = \sqrt\[c\]{b} $ then we have $ n \> \sqrt\[c\]{b} $ or $ n \> b^{\frac{1}{c}} $. Now since $\lg n$ with a base $ b \> 1 $ is an increasing function, then $ \lg n \> \lg b^\frac{1}{c} $ or $ \lg n \> \frac{1}{c} $. If we multiply both sides by $ c \> 0 $, we have $ c \lg n \> 1 $. Now we can multiply both sides by $ \lg n \> 0$ (*Note that for $ \lg n \> 0 $ to be true, we must have $ n\_0 \geqslant 1 $ which leads to $ \sqrt\[c\]{b} \geqslant 1 $ or $ b^\frac{1}{c} \geqslant 1$ which results in $ \lg b^{\frac{1}{c}} \geqslant \lg 1 $ or $ \frac{1}{c} \geqslant 0 $ or $ c \> 0 $; which is already guaranteed.*) to have $$ c \lg^2 n \> \lg n . $$ This is what we needed to show.

---

**Big-Oh proof sketch**

A slightly different but related question could be why $\lg n$ is *bounded above* by $\lg^2 n$, that is why $\lg n \in O(\lg^2 n)$.

The answer is that since $\lg n \> 1$ for $n$ larger than the base of $\lg$, then if we raise $\lg n$ to any power greater than $1$ (including power of $2$), it will be larger than $\lg n$ itself.

(*We could rather argue that since we proved that $ \lg n \in o( \lg^2 n) $, it follows from $ o(f) \subset O(f) $ that $ \lg n \in O( \lg^2 n) $.*)

---

**Note**

So yes, the rule of $n^a \> n^b$ if $a \> b $ and $ n \> 1 $ does apply here. Note that this rule is equivalent to the statement that any exponential function with a base greater than $1$ is an *increasing function*.
> 3 votes

# Answer
Assume $O(n \log n) = O(n \log ^2 n)$. This implies that for any function $f(n) \in O(n \log ^2 n)$, there exist a positive constant $k$ and a constant $n'$ such that $f(n) \< k (n \log n)$ for all $n \geq n'$.

Take $f(n) = n \log ^2 n$. Clearly $f(n) \in O(n \log ^2 n)$.

So we have that there exists a value for $k$ and $n\_0$ such that $n \log ^2 n \< k (n \log n)$ for all $n \geq n'$.

Noting that $n \log ^2 n = n \log n \log n$, we arrive at a contradiction: whatever constant value we choose for $k$, there exists a value $n'$ such that $\log n \> k$ for all $n \geq n'$.

---

In simpler terms, were $O(n \log n)$ to be the same as $O(n \log ^2 n)$, it would mean that $n \log ^2 n$ does not grow faster than some constant factor of $n \log n$. But this is obviously not correct as $n \log ^2 n$ grows at a rate of $\log n$ times $n \log n$ (and $\log n$ grows faster than a constant).
> 1 votes

---
Tags: big-o-notation
---


title: Longest-Path Layering algorithm

text:
# Question
Title: Longest-Path Layering algorithm
**NOTES**:

1. there are a myriad of graph data structures, I use a spin-off of a directed adjacency hash.
2. the code provide in this post is `python3` on the premise that it lends itself to readability.
3. this post was *not* posted to SE code review as:

a. there are not sufficient tags for graphs (just graphs and graphics)

b. the underlying issue is one concerning the algorithm, not the implementation (I think).
4. this post uses the tag as it deals with finding the `longest-path` \- although that is not necessarily the aim of the algorithm or this question.

---

This question deals with implementing the longest-path layering algorithm outlined in Chapter 13 of the Handbook of Graph Drawing and Visualization edited by Dr. Robert Tamassia and penned by Healy and Nikolov. It, and its explanation, can be found on pages 420-1 of the linked PDF. As I am seeking *your* help, I am writing the algorithm as they provide there, here:

# The Longest-Path Algorithm(G)

**Requires:** DAG G=(V,E)

$ U \leftarrow \phi $

$ Z \leftarrow \phi $

$ currentLayer \leftarrow 1 $

**while** $ U \neq V $ **do**

$\quad$Select vertex $ v \in V \backslash U $ with $N^+\_G(v)\subseteq Z$

$\quad$**if** $ v $ has been selected **then**

$\quad$ $\quad$ Assign $v$ to the layer with a number $ currentLayer $

$\quad$$\quad$$ U \leftarrow U \cup \\{v\\} $

$\quad$**endif**

$\quad$**if** no vertex has been selected **then**

$\quad$$\quad$$ currentLayer \leftarrow currentLayer+1 $

$\quad$$\quad$$ Z \leftarrow Z \cup U $

$\quad$**endif**

**end while**

Some things to *note* about this (and many) graph drawing algorithms. They often have stringent assumptions that need to be upheld. In this case, we *assume* that our graph is a directed acyclic graph (DAG) - not too big of a deal, but this should be kept in mind (see Tarjan's method for making acyclic graphs).

The implementation looks almost verbatim to the pseudo-code (a perk of python).

```
def longest_path_layering(vertex_set):
    """
    See page 420-1 of Chapter 13: Hierarchical Graph Drawing by Healy and Nikolov.
    Modified to switch layering (e.g. layer 0 is up top instead of at the bottom)
    U = vertices assigned to any layer
    Z = all vertices assigned to a layer above the current
    V = Vertex Set
    v is selected from v in V \ U
    """
    U = set()
    Z = set()
    V = set(vertex_set.keys())

    current_layer = 0 # layer 0 is 'top most'
    while U != V:

        choices = set(filter(lambda v: set(vertex_set[v]['p']).issubset(Z), V - U))

        if choices:
            selected = choices.pop()
            vertex_set[selected]['layer'] = current_layer
            U.add(selected)

        else:
            current_layer += 1
            Z = Z.union(U)

        if current_layer > len(V):
            # This algorithm will NEVER produce a graph with more layers than vertices.
            # So this is sensible for debugging
            break

    return current_layer + 1

```

In my experience, this has worked very well for me (using the aforementioned Tarjan method based on finding strongly connected components (SCC) to remove cycles via the feedback arc set (FAS)).

Until... this graph:

```
V = list(range(0, 24+1))
E = [[0, 1],
 [1, 2],
 [1, 5],
 [1, 14],
 [1, 19],
 [1, 21],
 [5, 3],
 [5, 20],
 [8, 9],
 [8, 10],
 [9, 0],
 [10, 0],
 [12, 15],
 [13, 1],
 [14, 12],
 [15, 16],
 [15, 17],
 [15, 18],
 [16, 0],
 [17, 0],
 [18, 0],
 [19, 20],
 [21, 20],
 [22, 13],
 [22, 23],
 [22, 24],
 [23, 0],
 [24, 0]]
VS = {v: {'s': set(), 'p': set()} for v in V} # s is short for successors (i.e. v --> s) and p for predecessors (p --> s)
for s, t in E: # for source target
    VS[t]['p'].add(s) # target <-- source
    VS[s]['s'].add(t) # source --> target

```

This graph has already been per-processed to be acyclic. I am fairly confident that my implementation to remove cycles is correct and functioning. If this graph is cyclic, I do not see it at the moment.

If we run the layering algorithm:

```
longest_path_layering(VS)
# returns 27, showing that we hit our sensible break to prevent the endless while loop

```

and then print out only the vertices that were layered:

```
for v in sorted([v for v in VS if 'layer' in VS[v]], key=lambda v: VS[v]['layer']):
    if 'layer' in VS[v]:
        print(v, VS[v]['p'], VS[v]['s'], VS[v]['layer'])

```

we get

```
vertex    predecessors    successors   layer
# layer 0
4 set() set() 0
6 set() set() 0
7 set() set() 0
8 set() {9, 10} 0
11 set() set() 0
22 set() {24, 13, 23} 0

# layer 1
9 {8} {0} 1
10 {8} {0} 1
13 {22} {1} 1
23 {22} {0} 1
24 {22} {0} 1

```

If this does not explain why the algorithm fails, then perhaps the following code might:

```
layer_1 = [8, 9, 10, 13, 23, 24]
for v in [v for v in VS if VS[v]['p'] in layer_1 or VS[v]['s'] in layer_1]:
    print(v, VS[v]['p'], VS[v]['s'])
# prints nothing

```

i.e. there are no vertices connected to layer 1 that are not already in layer 0. So it seems that the issue is that this algorithm has another requirement. The components of the graph must have a connection - albeit an acyclic one.

My question is thus what is the most sensible error handling for this scenario. Should I pick an un-assinged vertex with the minimal number of predecessors? This seems reasonable as the algorithm starts with a random root of the graph. However, given that we now have chosen one, it feels that it matters which vertex we choose. Also, should $currentLayer$ be reset to 0?

# Answer
> 0 votes
It looks like three vertices `n6`, `n7` and `n11` are orphans never included in any edges, also more importantly, the edges described creates a cyclic graph. Longest-Path Algorithm assumes an acyclic graph. There are preprocesses to make a cyclic graph acyclic using algorithms such as greedy cycle removal.

---
Tags: graphs, graph-traversal, graph-drawing
---


# Question
Title: How many segments a process can have in operating system employing Segmentation for memory management
**Some facts about "Segmented Paging"**

1) Each process has one segment table.
2) There is one-page table per segment.

**Fact about "Paged segmentation"**

3) Contains page table of segment table.

**Now consider following problem**

> In a paged segmented scheme of memory management, the segment table itself must have a page table because. (A) The segment table is often too large to fit in one page.
> (B) Each segment is spread over a number of pages.
> (C) Segment tables point to page tables and not to the physical locations of the segment.
> (D) The processor’s description base register points to a page table

**Given solution is:**

Here option (A) is true , as segment table are sometimes too large to keep in one pages. So, segment table divided into pages. Thus page table for each Segment Table pages are created.

**My Doubt**

I believe a page can contain several hundreds of segment table entries of form

```
  <segment base, limit>

```

I only came across code, data, stack and heap segments. I believe a process can have only these "four" segments. And also, we know each process has a segment table (Fact 1). Then how a segment table can grow so large that it cannot be fitted in a single page?

# Answer
A process can only access 6 segments simultaneously through `CS`, `SS`, `DS`, `ES`, `FS`, and `GS` registers on an x86 and x86-64 machines.

These registers point to an entry in the segment descriptor table that the operating system manages. If OS uses a **multi-segment memory model** then that table can have an arbitrary size thus allowing a process to access a theoretically unlimited number of segments. (Intel 64 and IA-32 Architectures Software Developer’s Manual 3-6 Vol.3)
> 1 votes

# Answer
I referenced Galvin and found this:

> Normally, when a program is compiled, the compiler automatically constructs segments reflecting the input program.
> A C compiler might create separate segments for the following:
>
> 1. The code
> 2. Global variables
> 3. The heap, from which memory is allocated
> 4. The stacks used by each thread
> 5. The standard C library
>
> Libraries that are linked in during compile time might be assigned separate segments. The loader would take all these segments and assign them segment numbers.

This explains how there can be multiple segments per process enough to grow the segment table so large that it cannot be fitted in a single page.

**Further doubt:**

From this, I can understand there can be multiple code segments each one for each referenced library. I was guessing if there can be multiple stack, heap and data segments. If yes, when?
> 0 votes

---
Tags: operating-systems
---


title: Sorting algorithm

text:
# Question
Title: Sorting algorithm
I want to know from this picture which one is bubble sort, insertion sort and selection sort?

My answer is:

1. bubble sort algorithm,
2. insertion sort algorithm,
3. selection sort algorithm.

Is it this right? Is there reference link too to picture which one is the right sort?

# Answer
In my opinion you get it right.

First row: in the second picture, we can see that the lower part are sorted and almost every element has been moved, which we can assume that is a bubble algorithm that moves the lower values to bottom.

Second row: we can observe that along the four pictures the algorithm is starting to sort the left part of the data. This indicate that the algorithm is exploring the data from left to right and insert each explored element in right position on the explored data (insertion sort).

Third row: from the second picture, the algorithm is searching for the lowest value and sort it ( selection sort)
> 2 votes

---
Tags: algorithms, sorting
---


# Question
Title: Directed graph where DFS returns on a node before all its child nodes are visited?
> Give an example of a directed graph in which a depth-ﬁrst search backs up from a vertex $v$ before all the vertices that can be reached from $v$ via one or more edges are discovered.

My professor recently asked this question as a warm up to lecture, but never answered it. I still have not figure how that is possible. Why would it return if it's not complete?

I just can't see a scenario where this would happen.

It would never return, since DFS is (essentially) recursive and it can't return without having hit all base cases.

# Answer
Consider the following graph. If DFS will first go to the second node, it will back up even though the third node is reachable from the second.
> 1 votes

# Answer
I am not sure what does he mean by 'back up from a vertex $v$'. If he just means an encounter of parent node then the case is shown in the pic. $s$ is the starting node in the algorithm. Flow might return to $s$ before going to leaves of $v$ making the edge $(v,s)$ back edge.
> -1 votes

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


# Question
Title: Does infinite length strings lead to uncountable languages?
This answer says:

> We can have uncountable languages only if we allow words of infinite length.

So does that means any (finite / infinite) language or any (finite / infinite) set of languages over any (finite / infinite) alphabet will be uncountable of words have infinite length?

Let me simplify this by asking specifically for the simplest language of infinite length string:

> Does the language of "finite" number of words, each of which can be of "infinite length" and are based on "finite" alphabet is uncountable?

# Answer
A finite language is finite. Every finite set is countable, by definition.

A language of finite-length strings over a finite alphabet may be infinite but is always countable.

A language of infinite-length strings over a finite alphabet *might be* uncountable.
> 3 votes

# Answer
I will answer the question "is there a language which is countable and contains a string of infinite length?"

The answer is yes. Consider the symbols $\\{0, 1\\}$ and the language consisting of strings which do not contain the symbol $1$. The string of infinitely many $0$s and no $1$s is in the language, but there are still countably many strings in the language (match the empty string with the natural number 0, match the string of infinitely many $0$s with the natural number 1, match the string $0$ with 2, the string $00$ with 3, $000$ with 4, and so on.)

Now, given an infinite string over this set of symbols it is only semi-decidable if the string belongs to this language. That is, there is no TM which will tell you if an infinite string contains no $1$s, but a TM can tell you if a string does contain a $1$.

Since your question seems to indicate that you view the cardinality of a set and the decidability of set membership as being related, you may be interested in apartness relations and, more generally, in constructive mathematics: https://en.wikipedia.org/wiki/Apartness\_relation
> 3 votes

# Answer
Take sin x for rational x. We write down the first digit after the decimal point in base 2, the second digit in base 3, third digit in base 4, and so on.

This gives us a countable language of infinite strings over an infinite alphabet.

It has the interesting property that examining any finite number of symbols in an infinite string cannot tell you if it is in the language or not.
> 3 votes

# Answer
Each infinite word containing ${a,b}$ corresponds (one-one) to a real number with digits of $0,1$ if $a\mapsto 0$ and $b\mapsto 1$. For example, $$ abaaabb\cdots\mapsto 0.0100011\cdots $$ So all strings containing ${a,b}$ has the same infinity as all the numbers in $\[0,1\]$. And thus language with two symbols of infinite length of words is uncountable.

The infinity of languages with finite or even countable symbols is the same as the one with two symbols. This is a standard theorem in set theory, i.e. $$2^{\aleph\_0}=N^{\aleph\_0}=\aleph\_0^{\aleph\_0}={\aleph\_1}$$
> 1 votes

---
Tags: formal-languages, turing-machines, automata, uncountability
---


title: Doubt regarding deletion from a B-tree

text:
# Question
Title: Doubt regarding deletion from a B-tree
After deleting an element from a B-tree,I could rearrange the tree in several ways,that would still complies to the rules of B-trees.But,we are supposed to follow a certain set of rules for rearranging the tree after deleting an element.

Why is that ?

# Answer
Because it keeps the B-tree balanced?

In essence, what you are asking is why the algorithm is the way it is. The algorithm we use has been around long enough that if there was a better way to do it, people would have suggested that by now. I believe that the reason why this is the case is that the current algorithm is the simplest way possible to solve the B-tree problem. i.e. there's no useful further reduction of the problem to find.

That said, you have to be consistent but you are free to decide whether you want a tree that for example has either left or right bias but never both.

When deleting you also have a choice in whether to borrow from left or right first, or whether to merge with left or right first. You need to do both but you can attempt either left or right first.

The B-tree algorithm has some ambiguity or arbitrary things about it. Some aspects of it can be done in any number of ways, the end result will be the same. This can be confusing if you are not used to dealing with such arbitrary and/or ambiguous things.
> 1 votes

---
Tags: data-structures, trees, b-tree
---


# Question
Title: Why do min/max operations in van Emde Boas trees run in $\mathcal{O}(1)$?
I have read in the book

> "Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and Stein (Chapter 20)

that *Emde Boas trees* run min/max operations in $\mathcal{O}(1)$ time since the minimum and maximum element are stored as attributes in each tree. I don't understand this very well. Does this mean that the min and max values are already given in the input, because the minimum and maximum must be calculated somewhere?

# Answer
> 5 votes
No. They are not given as an input! They were stored and updated as an attribute of each tree(Beware that the concept of the "attribute" in real-world programming means a "variable" in a programming language. More details depend on the programming language that you have chosen up to now to develop the data structure). The same situation is taking place in the min\[Max\]-heap data structure. You can find the minimum \[maximum\] in a min\[max\]-heap with $O(1)$ operation by keeping update (in insertion time) the mentioned attribute.

# Answer
> 1 votes
To search the min/max or successor/predecessor, we use a recursive algorithm that goes through the sub-trees and does the search. While the recursion happens, we don't calculate the min/max in every iteration. We have an attribute in an object that we get as an parameter to the recursive function that we use to assign the min/max. In every iteration, if there's a new min/max, then we assign the attribute to the new value so that we are always up-to-date with the min/max and when we need them, we can get them from the attribute which is $O(1)$.

```
recursiveFunction(metadataObj, x) {

  if x < metadataObj.min:
    metadataObj.min = x;

  if x > metadata.max:
    metadataObj.max = x;
}

```

---
Tags: van-emde-boas-trees
---


title: solving a problem with induction

text:
# Question
Title: solving a problem with induction
The original question is the following

> prove that $2·\sum\_{i=0}^{n-1} 3^{i} = 3^n-1$ for all n $\geq$ 1

I know that I have to prove by induction and have successfully done the base case, my IH is the following:

Assume $2·\sum\_{i=0}^{n-1} 3^{i} = 3^n-1$ holds for all n $\geq$ 1 to prove $2·\sum\_{i=0}^{n} 3^{i} = 3^{n+1}-1$

then I did this: $2·\sum\_{i=0}^{n} 3^{i} = 2·\sum\_{i=0}^{n-1} 3^{i} +3^n$

then by my IH: $2·\sum\_{i=0}^{n-1} 3^{i} +3^n = 3^n-1+3^n $

after this I struggle to continue, I know I have to find a way to rewrite it to $3^{n+1}-1$ and I know this is equal to $3·3^n-1$ but I don't see how to get from the one to the other. Anyone who can help?

edit: I mistook a 2 for a 3, can anyone help now?

# Answer
> 0 votes
You can add the first pair of paranthesis in the derivation below, so that it becomes clear that the factor $2$ also multiplies the second term, as follows:

$2 \cdot \sum\_{i=0}^n 3^i = 2 \cdot \left(\sum\_{i=0}^{n-1} 3^i + 3^n \right) = 2 \cdot \sum\_{i=1}^{n-1} 3^i + 2 \cdot 3^n = (3^n -1 ) + 2 \cdot 3^n = 3^{n+1}-1.$

# Answer
> 2 votes
$2·\sum\_{i=0}^{n} 3^{i} = 3^n-1 +2\cdot{3^n}=3^{n+1}-1$.

# Answer
> 0 votes
As you can find as the basis of induction, it is not true even for $n = 2$ (Easy to see $2(1+2) = 6 \neq 3^2 - 1 = 8$).

---
Tags: induction
---


title: Max heap and array relation

text:
# Question
Title: Max heap and array relation
This question is about max heap and array

> Suppose there is max heap $h$, with $n$ data items already stored in $h$. An array that is formed by inserting a value larger than all the values in $h$ at the beginning/head of the heap $h$ is assumed to be new array $C$. The array $C$ is a heap (or) not?

My answer: is heap because it's bigger than any other element in array

> With $n$ data items already stored in heap $h$, a new array $D$ is created by adding a value $u$ to the heap $h$ that is smaller than any of the $n$ items already stored in heap. If $u$ is added to last element in heap $h$, is array $D$ heap or not?

My answer: it is heap because the smallest one has to be in the leaf

But what is the relation with array? Is there rule to insert node in heap? I know that to insert node to array in heap we insert data as last element of heap and then put it in the root and heapify it.

# Answer
Suppose an array $A$ is a maxheap. Inserting a large element in the first position of $A$ does not necessarily preserve the maxheap property. The maxheap property requires a node's value to be larger than both its children's values, for *each node in the tree*. If the value inserted in the first position is larger than all values in the array, then the maxheap property is preserved at the root node, but might not be preserved at some of the other (lower level) nodes.

We can construct an initial array $A$ such that the nodes in the subtree rooted at the right child of the root have much larger values than the nodes in the subtree rooted at the left child of the root. When a new value is inserted in the first position of the array, the tree changes so that the smaller values in the left subtree become parents of the larger values in the right subtree, causing the maxheap property to be violated. For example, take $A=\[6,3,5,2,1,4\]$, which is a maxheap. Inserting a $7$ in the beginning modifies $A$ to $A=\[7,6,3,5,2,1,4\]$, which is not a maxheap because the node with value $3$ is a parent of the node with value $4$.
> 1 votes

---
Tags: algorithms, heaps, heap-sort
---


# Question
Title: Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output
An irreducible kernel is the term used in Handbook of Theoretical Computer Science (HTCS), Volume A "Algorithms and Complexity" in the chapter on graph algorithms. Given a directed graph $G=(V,E)$, an irreducible kernel is a graph $G'=(V,E')$ where $E'$ is a subset of $E$, and both $G$ and $G'$ have the same reachability (i.e. their transitive closures are the same), and removing any edge from $E'$ would not satisfy this condition, i.e. $E'$ is minimal (although not necessarily the minimum size possible).

A minimum equivalent graph is similar, except it also has the fewest number of edges among all such graphs. Both of these concepts are similar to a transitive reduction, but not the same because a transitive reduction is allowed to have edges that are not in $E$. That said, \[1\] proves that for every DAG, it has a unique irreducible kernel, which is also its unique minimum equivalent graph and its unique transitive reduction, and thus there is no benefit in the transitive reduction to using edges not in the original graph (there is a difference between minimum equivalent graph and transitive reduction for some graphs with cycles, but not for DAGs).

HTCS says that there is an algorithm to calculate an irreducible kernel of a directed acyclic graph in $O(V\*e)$ time, where $V$ is the number of vertices, and $e$ is the number of edges in the irreducible kernel, i.e. the *output* of the algorithm. The reference given for this is the following paper, which I have not been able to find an on line source for yet (links or other sources welcome -- I can ask at a research library soon if nothing turns up).

Noltemeier, H., "Reduction of directed graphs to irreducible kernels", Discussion paper 7505, Lehrstuhl f. Mathematische Verfahrensforschung u. Datenverarbeitung (Operations Research & Data Processing), Univ. Göttingen, Gottingen, 1975.

Does anyone know what this algorithm is? It surprises me a little that it includes the number of edges in the output graph, since that would mean it should run in $O(n^2)$ time given an input graph with $O(n^2)$ edges that represents a total order, e.g. all nodes are assigned integers from 1 up to $n$, and there is an edge from node $i$ to $j$ if $i \< j$. That doesn't seem impossible, mind you, simply surprising.

\[1\] Aho, Garey, and Ullman, "The Transitive Reduction of a Directed Graph", 1972 https://epubs.siam.org/doi/10.1137/0201008

# Answer
> 3 votes
I do not know about their algorithm, but the problem is easy to solve in $\mathcal{O}(V \cdot e)$ time. The idea is to just do a DFS from every node to find vertices that can reach it. Normally this takes $\mathcal{O}(E)$ time, but we can use the irreducible kernel we have already built to do it in $\mathcal{O}(e)$ time.

First note that $e \geq n-1$ if the graph is connected. If it is not, solve the connected components individually.

Start by doing topological sort on the vertices, with vertices with indegree zero first. Loop vertices first-to-last. When at vertex $i$, first mark all vertices as unreachable. Then loop vertices from $i-1$ to $1$. At every vertex $j$, if $j$ is unreachable and has an edge to $i$ in the input graph, add the edge $(j, i)$ to the irreducible kernel and mark $j$ reachable. Then if $j$ is reachable, loop all edges $(t, j)$ in our kernel, and mark $t$ reachable.

The topological sort takes $\mathcal{O}(V + E)$ time, and the DFS takes $\mathcal{O}(E + V \cdot e)$ time, so since $e = \mathcal{\Omega}(V)$, the running time is $\mathcal{O}(V \cdot e)$.

The produced DAG has the same reachability as the original graph, as we use a subset of the original edges, and only skip adding the edge $(j, i)$ if $i$ is reachable from $j$ even without it.

Assume some edge $(j, i)$ can be deleted while maintaining reachability. But by the way we did the DFS, $i$ was not reachable from $j$ without the edge (note that any path between them can only visit vertices between them in the topological order). Hence the produced DAG is indeed irreducible.

---
Tags: algorithms, graphs, dag
---


# Question
Title: How to find the loop invariant in hoare triples
Hey I am new to Hoare triples, and I can't understand on finding the loop invariants in hypothesis. For example this while loop

```
[x>1 & y>1] WHILE x>0 DO x:=x-1; y:=y+2 END [x+y>5].

```

The invariant is \[2x + y \> 5\] but I don't understand on how to find it. A step by step explanation on how to find it will be greatly appreciated.

# Answer
First understand the meaning of the loop invariant. It means a condition which is true in every iteration of the program/algorithm at the begining as well as at the termination of the loop. Your program is something like this.

$$ x \> 1 \text{ and } y \>1 $$

$$\text{ While } x \>0 $$

$$\hspace{4cm}\text{ Do } x:= x - 1, y:=y+2$$

$$\text{ End }$$

$$x + y \> 5$$

$2x+y \>5$ is an invariant as you described. It is visible from the program that both $x$ and $y$ will be greater than $1$ during the first iterataion of the loop. So in the first iteration of while loop $2x+y \> 5$(you can prove it). Notice in each iteration of the while loop the value of the $x$ gets decrease by value $1$ and value of y is getting increase by two so inequality $2x+ y \>5$ will be satisfied. You can prove it. Now come to the termination condition, at this point $x$ will be a negative number and **my claim is value of $y$ is going to be at least** $5$. Thus the invariant $2x+y \> 5$ si true throught the iteration of the while loop.

Example :

Let $x=2$ and $y=2$, then $2 \times 2+2 = 6 \> 5$ is satisfied. Now in the second iteration $x = 1, y=4$ so $1 \times 2+4 \> 5$ satisfied. Now $x = 0, y = 6$, loop terminated, $2 \times 0+6 \> 5$.
> 1 votes

---
Tags: hoare-logic
---


# Question
Title: Compare two complexity functions having the same asymptotic complexity
For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found:

* $A1: T\_{A1}(n)=4n^2 +7log(n^2)$
* $A2: T\_{A2}(n) = 4T(n/2) + log(n)$

Say, technically justifying the answer, which of the two algorithms is preferable for input of size sufficiently large

**Here my solution**

For $A1$ there is no recursion, the predominant term is $4n^2$ so we can say:

Complexity of $A1 = O(n^2)$

For $A2$ we do have recursion, Let's use the Master Theorem:

$a = 4$, $b = 2$ and $f(n) = log(n)$

$$f(n) \< n^{\log\_{b} a}$$ $$log(n) \< n^{\log\_{2} 4}$$ $$log(n) \< n^2$$

Hence, $T\_{A2}(n) = \theta(n^2)$

Here comes my question: Which one is preferable and why ?

I'd say there is no difference since both algorithms have an upper bound of $c\cdot n^2$

# Answer
Although, you cannot find the arbitrary constant c from master theorem, you should check using different size inputs which algorithm is faster, because even though both are upper bounded by c\*n^2, if we have 4\*n^2 and 1/4\*n^2, still 1/4\*n^2 is 16 times faster !!

**A very important point** is that your second algorithm seems to use divide and conquer method. This means that maybe it can be parallelized (in order to use more space but less computing time). For example, assuming an ideal choice of pivots, parallel quicksort sorts an array of size n in O(n log n) work in O(log² n) time using O(n) additional space.
> 0 votes

---
Tags: complexity-theory, time-complexity, computability, master-theorem
---


# Question
Title: Number of states in minimal Non Deterministic Finite Automata
> What will be the number of states in minimal NFA that can be designed to accept the language $L = \left \\{ \epsilon \right \\}$ having a non empty alphabet set?

My friends are saying that this can be done using $1$ state, make the only state start state & final state without any transitions.

But will not this NFA accept every string over the alphabet set?
Because for every input string we are already in accepting state.
So every string will be accepted.
My claim is that at least $2$ states will be required so that we can get away from that default accepting state (start state) on any non empty string and the minimal NFA will be exactly same as the minimal DFA accepting $L$.

Am I correct?

# Answer
> But will not this NFA accept every string over the alphabet set?

It will *not* accept any strings except the empty one. Since there are no transitions, the transition function $\delta(q\_0,a) = \emptyset$ for all symbols $a$ of the input alphabet $\Sigma$, thus the extended transition function $\hat{\delta}(q\_0,s) = \emptyset$ for all *non-empty* strings over $\Sigma$.

The set of accepting states $\\{q\_0\\}$ and $\hat{\delta}(q\_0,s)$ for all non-empty strings $s$ are disjoint, hence the NFA doesn't accept any non-empty strings.

As you already know this NFA accepts the empty string, and we just showed that it accepts *only* the empty string.

*Remark*: if it was a *deterministic* automaton you'd need 2 states to do the same thing. You could "cheat" and not show the 'dead state', but still it would be a 2 state DFA. With NFAs rules are a little bit different, since instead of states you use sets of states and having your NFA in no state at all (the empty set of states) is perfectly normal abstraction.
> 6 votes

# Answer
Your friend is right. FA whether deterministic or non accepts a string only if it can reach to final state while consuming all of string. Its NFA has no transition so you can not consume every non empty string to its end.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: Why is my algorithm version so slow with this input?
Here I'm trying to do a comparison of two simple as possible algorithms, solving the symmetric travelling salesman problem, finding the optimal solution without the support of heuristics. I'm showing (or just referencing) the code of both algorithms only to better specify the implementation details, which could be relevant for the comparison. I've written my F# code to solve Advent of Code Day 18 Part 1. It is a BFS adapted to find the optimal solution for a weighted graph (last version has been edited since the original question was posted here, but, as already said, ignore this sort of details). While it seems to work fine with other simple demo inputs, it stucks forever with the following input.

```
#################
#i.G..c...e..H.p#
########.########
#j.A..b...f..D.o#
########@########
#k.E..a...g..B.n#
########.########
#l.F..d...h..C.m#
#################

```

It represents a list of lowercase char vertices with uppercase constrained predecessors and edges weighted by different dotted distances. So here I'm looking for a comparison based on the time complexity of the algorithms, related to an analysis of the cases where the number of edges increases, at a fixed number of vertices. There is a reference solution in Python which is correct and fast, but I fail to see where is the fundamental difference between the two algorithms, behind the other minor code differences (also because the languages are different).

I've tried with recursion vs a queue, with tree vs grid/map (see my github history) but with no luck until now.

The principal part of the code is described below. It should fall under a breadth first search (BFS) algorithm, whose implementation details are reported below only to complete the theoretical description already given, because the standard BFS has been adapted to multiple targets, weighted edges and a tentative tree pruning.

Here is how I produce the single step, by which I elaborate the solution.

```
1 single step receives as input which is the move index i
2 then it updates the distance of the current solution draft by summing the distance to the vertex i
3 it updates the current position as of vertex i
4 it also updates the list of predecessors by including vertex i
5 it computes the new tree of reachable vertices starting from the `fullGrid` and taking into account the newly updated list of predecessors

```

Notice that this is a constrained version of the TSP where each vertex can have as constraint a list of predecessors.

The `fullGrid` is supposed to contain the matrix of distances and it looks fine to me, in terms of the values it contains when I debug it. The wrapping solver is simply a recursion or queue based version of the BFS. Again, I'm not interested in the programming details but in understanding, at a conceptual level, why the underlying algorithm is not applicable for an apparently tractable input case (of "only" 16 nodes).

```
Start by receiving the graph topology and starting point
    Define a mindistance variable
    and a list of completed solutions, initially empty

    Start looping at the queue of partial solutions
        So a single partial solution is dequeued
        It computes possible vertices based on current predecessors
        Check if nothing remains and adds it to the completed alternatives updating mindistance
        Otherwise loop as in classical BFS
        For all possible moves = reachable vertices

                For each one applies above said single step
                If done updates mindistance and completed alternatives
                Otherwise enqueue such partial solution

    Finally select the min alternative by distance.

```

# Answer
> 0 votes
I've found the conceptual problem. In a BFS kind of search, when optimization is needed because the **length of the queue** grows at critical speed, you have to take track of the **visited** items.

The goal is to **avoid adding another item** to the queue when it is **already present** a **better item** there.

Just some code, only to clarify the concept.

In my case I've added a visited map

```
let mutable visited = Map.empty<char,((char list) * int) list>

```

and I'm enqueuing only better items:

```
if visited.ContainsKey(solutionNext.tree.area)
    && (visited.[solutionNext.tree.area]
        |> List.exists (
            fun (keys, distance) ->
            distance <= solutionNext.tree.distance
            && solutionNext.keys |> List.forall(fun k -> keys |> List.contains k)
        ))
then ()
else
    solution_queue <- enqueue solution_queue solutionNext
    let previous = if visited.ContainsKey(solutionNext.tree.area) then visited.[solutionNext.tree.area] else []
    visited <- Map.add solutionNext.tree.area ((solutionNext.keys, solutionNext.tree.distance) :: previous)  visited

```

and skipping the worst ones

```
while (MyQueue.length solution_queue > 0) do
    let solution = dequeue &solution_queue
    if visited.ContainsKey(solution.tree.area)
        && (visited.[solution.tree.area]
            |> List.exists (
                fun (keys, distance) ->
                distance < solution.tree.distance
                && solution.keys |> List.forall(fun k -> keys |> List.contains k)
            ))
    then () else

```

## Cost function

From a theoretical viewpoint, BFS can guarantee that the *ﬁrst* solution returned will be as *short* as possible, **only if** we can assume that every move has got a cost of 1. You could reduce the above examples to that, but the best fit remains a *graph* where the *cost function* is represeted by edges of *different length*. With **real cost functions** finding the shortest path becomes more involved: this is exactly the case here. Especially because you have to optimize also the *Space complexity* (see previous paragraph), avoiding the worst-case time complexity of $O(b^d)$, with $b$ being the branching factor and $d$ the depth of the ﬁrst solution. You have described a scenario where $d$ is well known at start (the number of the keys in the maze) while the edge case you mention is obtained by a bigger $b$ (number of crossings of the maze)

---
Tags: algorithm-analysis, search-algorithms, shortest-path, graph-traversal
---


title: Generate code from automata

text:
# Question
Title: Generate code from automata
I am trying to figure out the process of generating code (set of instructions, implementation language specifics dont matter at this time) from an automaton.

The description of my intent is vague because although I am an electrical engineer, with extensive coding experience, I have no theoretical CS background and I am struggling to even articulate what I mean. The issue at hand is related to a digital circuit that I am working with. At this point I am not even aware of what I need to start looking into. Another way of describing my intent is, say I got a transition model of a process with the data requirements that are associated with the states. Knowing that, can I generate a program that will implement that model? Is there a field of study that deals with problems like this? Or should I just develop some logic to solve a limited interpretation of the model?

I believe I am using incorrect or misleading terms from a CS standpoint but I will appreciate if I can get some guidance on how to formulate my intent and then try to understand the possible solutions, if any.

Thanks!

# Answer
> 2 votes
A simple way to do it is to just write an interpreter that follows the transition table. I.e., do something like (in C):

```
state = INITIAL;
symbol = get_next();
while(symbol != END) {
   state = table[state][symbol];
   symbol = get_next();
}
if(is_accepting(state))
   /* Accept */

```

Next simpler is to write a rat's nest of gotos, transferring among them according to the symbol at hand (each label in the program corresponds to a state of the automaton).

Writing a decently organized,structured program from an automaton is possible, but far from automatic (and it would take a fair amount of work to check it really is faithful to the automaton).

---
Tags: automata, code-generation
---


title: Optimality of a Greedy Algorithm

text:
# Question
Title: Optimality of a Greedy Algorithm
If you designed a greedy algorithm to obtain an optimal solution and the algorithm can produce different combinations of values but still, any of theses combination is an optimal solution. How you prove it is optimality?

For example you have a set of numbers $\mathcal{M}=\\{1,2,3,4\\}$ and you want to design an algorithm to obtain the minimum number of integers required to obtain a sum 5. In this case, $1,4$ or $2,3$ can produce 5 and both are optimal solutions as the minimum number required is two.

How to prove the optimality of the algorithm ?

I tried by contradiction an assume that there is an optimal solution $P^\*$ and my algorithm doesnot produce an optimal solution $P$ so $P \neq P^\*$. but I donot know how to continue the argument.

# Answer
This is the *change making problem*. For some sets of denominations (e.g. powers of some base $b$, the US coins, or almost all coin systems in the world) the greedy algorithm gives the minimal number of coins. The general case is NP-complete, a practical solution requires dynamic programming (see the liked Wikipedia article). There is a polynomial time algorithm to check if a given set of denominations makes the greedy algorithm optimal or not, see Pearson (1994) "A polynomial-time algorithm for the change-making problem", doi 10.1.1.57.3243.
> 0 votes

# Answer
If a greedy algorithm is not always optimal then a counterexample is sufficient proof of this.

In this case, take $\mathcal{M} = \\{1,2,4,5,6\\}$. Then for a sum of $9$ the greedy algorithm produces $6+2+1$ but this is not optimal because $5+4$ has fewer summands.
> 1 votes

# Answer
Greedy algorithm usually involes a sequence of choices and once a choice is made we can't undo it in the next step. So it is important that they(greedy algorithm) never made a mistake. A local optimum solution means best possible solution.

Let set $S$ be an optimal solution to some problem and our greedy algorithm gives a set $P$. If both $P$ and $S$ are same then are done. Assume that both $P$ and $S$ are different,in this case greedy algorithm will have pick an element in the intermediate step(local solution) which is less optimal which resulted $P$ rather than optimal set $S$. But according to the greedy algorithm we always choose an local optimum solution. Hence the argument is proved by proof by contradiction.
> 0 votes

---
Tags: proof-techniques, correctness-proof, greedy-algorithms
---


title: Clique-problem for planar graph

text:
# Question
Title: Clique-problem for planar graph
I have to show, that the clique problem in planar graphs is in P. I found the answer here here. However I don't get the conclusion

> This follows already from Kuratowski's theorem: a clique is at most of size 4.

I've never heard of that theorem before and the exercise indicates to proof it with the fact, that the class of planar graphs is closed under sub graphs. Thank you for your help!

# Answer
> 2 votes
Regarding the proof of the statement you quoted (to complement Juho's answer):

Let $G$ be a connected planar graph with $V \> 2$ vertices, $E$ edges and $F$ faces. We know from Euler's formula that $V-E+F=2$.

Now let us count the number $q$ of $(e,f)$ pairs where $e$ is an edge and $f$ is a face incident to $e$. Because every edge is incident to at most two faces, $q \leq 2E$. Because every face is incident to at least $3$ edges, $q \geq 3F$. Thus, $3F \leq 2E$. Using this together with Euler's formula we get that $3V = 3E - 3F + 6 = E +6 + (2E - 3F) \geq E+6$. Thus $E \leq 3V-6$.

Now, if some graph had a clique of size $5$, by taking this clique as a subgraph we would have that the complete graph on $5$ vertices $K\_5$ is planar. But this graph has $V=5$ and $E=10$, thus $E \> 3V-6$, which contradicts what we have just shown. Thus, $K\_5$ is not planar and our original graph has no clique of size $5$ or more.

# Answer
> 1 votes
The idea is that in a planar graph, there are no cliques of size 5 or more (see Kuratowski's theorem).

So suppose the problem is "is there a clique of size $k$ in a given planar graph $G$?" Now, if $k \geq 5$, we immediately answer NO. If $k \leq 4$, we can simply check every subset of the vertices of size $k$ (note that there are $\Theta(n^k)$ such subsets). If any one of them induces a $k$-clique, we answer YES. Otherwise, we answer NO. Hence, the problem is in P.

---
Tags: complexity-theory, graphs, clique, planar-graphs
---


# Question
Title: What is the result of a reduction operation called?
Is there a commonly used term for *the result of a reduction operation*?

"reductant" does not quite sound right...

# Answer
In the context of reducing one language to another, I have only ever seen this referred to using phrases such as "the problem being reduced to", "the target of the reduction", etc. I don't think there is a single word for it—certainly not one that would be universally understood.
> 2 votes

---
Tags: terminology, reductions
---


# Question
Title: Is there a naming convention for the left child of a right child (and vice versa)?
That is, the right child of a left child, or the left child of a right child. The best that I can come up with is the "opposing child" but I was wondering if anyone has come across an existing naming convention for this.

# Answer
You can use 'sibling' (or 'brother'/'sister' if you prefer to gender the vertices). It's somewhat commonly used, but you may want to redefine it quickly when using it extensively.

NB: this terminology can be used for non-binary tree, the *sibling* of a vertex is any other vertex with the same parent/father.

While you may want to find a more reliable source, Wikipedia agrees with me at the moment: https://en.m.wikipedia.org/wiki/Tree\_structure
> 1 votes

---
Tags: binary-trees
---