# Question
Title: What are the state-of-the-art algorithms for pathfinding on a continuous map of the Earth?
Suppose I have got a solar-powered autonomous surface vessel somewhere in the fjords of Norway, supplied with a fairly recent set of maps, a GPS receiver, and no means of downlinking detailed commands from me. This vessel has to reach, say, the island of Hainan at the earliest possible moment.

* What are the **deterministic** algorithms for finding a maritime route on a globe?
* What is their time and memory complexity?
* Can I, for instance, use A\* after transforming the map of the globe into a diagram with connected polygons (i.e. Delaunay triangulation on a sphere/ellipsoid) and what are other feasible approaches?

Answers should ideally provide references to papers with discussion of the above-mentioned questions.

As pointed out by *Rob Lang*, the algorithms must fit the usual criteria: in the absence of time constraints, lead to the shortest path between any two points on Earth's oceans and seas, or indicate pathfinding failure otherwise.

There are interesting sub-topics here (trading pre-computation time/storage for online computations, providing slightly suboptimal routes before a deadline kicks in etc.), but these are ancillary to the main issue.

# Answer
The deterministic requirement isn't all that constraining. That just implies your vehicle is certain of the state it's in. That being said, you'll probably want to plan paths in a way that allows you to avoid obstacles. The best way I've seen this done is with sampling-based planners. Steven LaValle wrote the central academic resource on this topic: Planning Algorithms.

The RRT\* algorithm is among the planners he describes. This algorithm generates the state space tree with random samples and a few heuristics to ensure feasibility (e.g. obstacle avoidance) and optimality. Details on RRT\* can be found in LaValle's book, or at Sertac Karaman's website. The asymptotic time and memory characteristics are described as O(nlogn) to process, and O(n) for queries. The algorithm is linear, O(n), in space complexity too.
> 7 votes

# Answer
For your further consideration, potential fields are an interesting, low-cost choice for pathfinding. You would place a strong charge at the destination, and eventually the agent would arrive at the charge. A more technical article by the International Foundation for Autonomous Agents and Multiagent Systems provides more insights.

Vector fields are also a very cheap solution, but more often used for multi-agent pathfinding. Vector fields are very good however for open areas. None of the above methods guarantee the shortest path however, sacrificing optimal pathing for better dynamic response.

Combined approaches are also strong, such as using A\* beforehand to generate waypoints and using vector fields to go to each waypoint. This will probably give much more optimal behavior on a macro scale.

Keep these in mind in case you acquire a swimming robot army.
> 4 votes

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


# Question
Title: Basic action for every data structure O(1)
My lecturer for Algorithms said that most of the data structures I will encounter in the algorithms course I am taking have a basic action which is of O(1).

Ex: Binary heap.

Basic action is:

> 1. Compare 2 childen.
> 2. Compare the "winner" with his parent.
> 3. Replace when needed.
> 4. Do 1-3 with the "winner", until and including the root.

How is O(1) even possible?

# Answer
> 5 votes
What was meant is that every data structure is designed to do something *really well*, e.g:

* For an array, lookup by index is O(1)
* For a linked list, insertion at the head is O(1)
* For a heap, finding the smallest element is O(1)

... and so on. This doesn't mean that the operation that is O(1) for one data structure wouldn't have much worse complexity for some other data structure.

# Answer
> 1 votes
**After EDIT in Question:**

The operations in step 1, 2 and 3, you mentioned, are actually `O(1)`.

By `O(1)` it is not meant that it is going to take 1 step only but it means that whatever time it is taking is CONSTANT. That constant can be small or large, but as you increase number of nodes in your tree, these *basic operations* are not going to take more time. Be it on a tree with 3 nodes or 200 nodes, one of these operation is going to take the same amount of time each time.

For an example, take operation 1 `Compare 2 children`. It is always going to take same number of comparison(here 1).

But if you say the sequence of step 1, 2, 3, 4 in order, as an algorithm. Then it is not `O(1)` and instead `O(log n)` with n being the number of nodes in the tree. Reason being, the operation 1-3 are done from a bottom pair of two nodes, propagating to top root node. So, in worst case it will traverse equal to height of the tree which is `log n`.

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


# Question
Title: Given 2 regular languages and their DFA's, how to construct the DFA of the union?
Suppose $L1, L2$ are both regular languages and $A1, A2$ are their corresponding DFA's. How can I construct a new DFA for the regular language $L1 \cup L2$?

# Answer
> 4 votes
Let's denote the sets of states in $A\_1$ and $A\_2$ by $Q\_1$ and $Q\_2$, respectively. Furthermore, let's denote by $F\_1$ and $F\_2$ the accepting states of these machines, $q\_0'$ and $q\_0''$ the start states of these machines, and $\delta\_1$ and $\delta\_2$ the transition functions of these machines.

We can use the Cartesian-product-machine construction to define an automaton $A\_3$ which accepts $L(A\_1) \cup L(A\_2)$ as follows. First, let $Q\_3 = Q\_1 \times Q\_2$ be the set of states. Now, define $F\_3 = \\{(q\_1, q\_2) \in Q\_3 \mid q\_1 \in F\_1 \vee q\_2 \in F\_2\\}$. Let $q\_0'''$ be the start state and define $\delta\_3((q\_1, q\_2), \sigma) = (\delta\_1(q\_1, \sigma), \delta\_2(q\_2, \sigma))$.

Consider the functioning of such a machine. By virtue of its being in some state $(q\_1, q\_2) \in Q\_3$, we know by construction that $A\_1$ would have be in state $q\_1$ after seeing the same input, and we know $A\_2$ would be in stare $q\_2$ after seeing the same input. $A\_3$ will accept if either $q\_1$ was accepting in $A\_1$ or $q\_2$ was accepting in $A\_2$, because of how we defined $F\_3$.

Intuitively, this works by demonstrating that we can model two DFAs executing in lockstep using the DFA formalism itself; two DFAs executing in lockstep is equivalent to the DFA constructed above. We have chosen to accept a string if either of the machines accepts, but as you can see, we could define a DFA for any of the standard binary set operations: union, intersection, difference, symmetric difference, etc.

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


# Question
Title: Proving $\log (N)$ mistake bound is "tight" for a learner when learning thresholds
I'm studying the online learning model and the Halving algorithm.

We've seen the threshold problem:

The domain is $X=\left\\{ 1,2,...,N-1\right\\} $, the label set is $Y=\\{-1,1\\}$ and the hypotheses class is $H=\left\\{ h\_{\theta}(x)=sign(x-\theta):\theta\in\left\\{ \frac{1}{2},1+\frac{1}{2},...,(N-1)+\frac{1}{2}\right\\} \right\\} $

I'll denote the number of mistakes the learner $A$ does on the environment $E$ by $M(A,E) = \left|\left\\{ i:\hat{y\_{i}}=A\_{\mbox{pred}}(x\_{i})\neq y\_{i}\right\\} \right|$ where $E=\left\\{ (x\_{i},y\_{i})\right\\} \_{i=1}^{n}$

For any environment $E$, the mistake bound for Halving is $M$(Halving,$E$)$\leq\left\lfloor \log N\right\rfloor $

Now I must prove that this bound is "tight", i.e., for any learning algorithm $A$ there exists a realizable environment $E$ such that $M(A,E)\geq \left\lfloor \log N\right\rfloor$

My try - I came to the conclusion that finding the correct $h^{\*} \in H$ is pretty similar in this case to finding a value in a sorted array. Since we'll need at least $\left\lfloor \log N\right\rfloor $ comparisons, an algorithm $A$ which can find $h^{\*}$ and make less than $\left\lfloor \log N\right\rfloor$ mistakes "*can find a value in a sorted array in less than $\left\lfloor \log N\right\rfloor$ comparisons for any given array, which is a contradiction.*"

The sentence in quotes is my intuition, but I'm having trouble proving it formally.

Is this the right way to go?

Many thanks.

# Answer
I am assuming the learning model described in Wikipedia. The environment will maintain a set of hypothesis forming an interval $S = \[h\_\alpha,h\_\beta\]$ consistent with its current answers, and will ensure that the first $\log N$ answers by the algorithm are wrong. In the beginning, $S = H$. At each step, the environment presents the middle point of the interval (we're identifying hypotheses with points in the domain in a natural way). Depending on the learner's answer, the interval $S$ is halved so that the learner is wrong. This process can go on for $\log N$ steps, in each of which the learner is mistaken, so that in total the learner makes at least $\log N$ mistakes.
> 4 votes

---
Tags: machine-learning
---


# Question
Title: Advantage of the Monte Carlo method over a regular periodic sampling
I am unclear on when to use the Monte Carlo random sampling method for algorithm design. The classic example that I keep seeing is using random points within some bounding rectangle to determine the area of some irregular figure. Wouldn't a regular periodic sampling provide more repeatable results for this application then using the Monte Carlo (random sampling) method?

# Answer
If you use a fixed seed then Monte Carlo is also repeatable. Monte Carlo sampling has the advantage that the expected number of points inside your figure is proportional to the area, which is not necessarily the case for a grid — you can come up with a contrived figure in which the grid is off by a lot, whereas random points are impossible to "fool" this way.
> 4 votes

---
Tags: algorithms, randomized-algorithms, monte-carlo
---


# Question
Title: How are programming paradigms classified?
When I started to learn about imperative programming and declarative programming it raised many doubts, like, how are structured, modular and object-oriented programming classified: declarative or imperative?

# Answer
> 4 votes
Do not be too obsessed with it. It is often only buzzwords covering a fuzzy trend (from structured to object oriented) towards better organization of programs, with somewhat different realizations in different languages. It can appear in any programming paradigm, whether imperative or declarative. They are intended to improve readability of programs, good programming practice, maintainability, code reuse in various guises, independence of program parts, information hiding.

What is a lot more important is to understand the specific techniques that can be used, their costs and benefits, the constraints they create and the freedom they provide. The more interesting techniques are based on formal mathematical analysis.

It involves a variety of more precisely definable concepts, such as environments, scoping and binding of variables, typing systems, modularity and interfacing, parameterization of code and modules, exception handling ...

I would think you will be better off concentrating on these identified technical issues than on more popular but fuzzier concept.

---
Tags: programming-languages, object-oriented, programming-paradigms
---


# Question
Title: A scoring approach to computer opponents that needs balancing
This question is about an approach to computer opponents that I have created and are either currently being used, or are planned to be used, in several computer games.

### Background

Last year, when trying to improve a computer opponent for a game called "Minesweeper Flags" *(short description: A turn-based multiplayer version of Minesweeper where you have to **take** more mines than your opponent)*, I strongly changed the way my algorithms worked. Instead of using an approach like if-else-if-else, I am using a set of "scorers" with specified weights to determine what the best move is.

You might think that for a game like Minesweeper Flags, it's only about making moves that gives you the highest probability of taking a mine, but it's not that simple. Which move the computer will make usually depends on several features for that specific move in the current game state. Examples of features:

* What's the probability of this move scoring a mine?
* What's the probability of revealing anything to my opponent here?

### Description of the system

The system basically works like this:

1. "Pre-scorers": Some pre-analysis is done for the current game state (in terms of Minesweeper Flags, this is usually: Calculating all the probabilities)
2. "Scorers": A set of ordinary scorers are asked to determine the score for each possible move, each scorer applies scores according to it's own criteria. The scorers can check the results of the pre-analysis that was made.
3. The scores calculated in the above step is summed together and is set to be the score for a move.
4. The moves are sorted according to their score and ranked so that all moves with the same score gets the same rank.
5. "Post-scorers": The result of the above can be sent to "Post-scorers" that have the possibility to modify the scores of any fields in any way they want, according to the post-scorer's own rules.

When combining a bunch of pre-scorers, scorers (with their weights) and post-scorers, it's becomes what I call a **score configuration**.

### Example result

This is an example of scores having been applied to Minesweeper Flags. This is the map that was scored:

And this is the output of an actual score configuration. It is showing the rank of the possible moves, where 1 is the best rank and has been highlighted in white:

Thanks to having written highly flexible code, this approach to AIs can be inserted into other games as well.

### Advantages and disadvantages

Below are some advantages and disadvantages of this system that I can think of myself

**Advantages**

* It's very easy to create a whole lot of different configurations for AIs.
* It is possible to use with Genetic Algorithms: Each scorer has an associated weight, the weight can become the gene.
* Using some tools, it is possible to check why a specific move was made and which scorers were mainly responsible for that move
* Using tools, it is possible to create a map of the overall score/rank of possible moves (like the screenshot above)
* By applying scores to the way the human plays, it is possible to create an "#AI\_Mirror" which tries to make moves that it thinks the human would make

**Disadvantages**

* It can be extremely difficult to adjust a score configuration "correctly", to make the AI play as good as possible.

### Questions

* Is the system I have built here widely known in the AI world? What would it be called in real AI terms?
* Does this approach make sense or is there a different approach that you would recommend?
* What ways are there that could make the process of tweaking a score configuration easier?

Regarding the last question, I am aware of the possibility of using genetic algorithms, I am also mildly aware of SARSA (and I do think my scorers resembles that site's description of features with weights, but from my understanding that's not exactly what I have created here). I think that a problem with SARSA is that you don't know the reward until the game is over, the best move is often a move which doesn't give a reward (a mine) at all. Your current chances of winning depends on both the current score (how many mines you and your opponent have taken) and what the current map looks like.

---

<sub> This question was originally posted on a now defunct Artificial Intelligence site. </sub>
<sub> The (Java) code used for this approach has now been posted at Code Review. </sub>

# Answer
> 7 votes
At a stretch it is an expert system (such as fuzzy logic). As you are not running an algorithm to perform feedback onto the decision parameters based on the output, it's not really learning. However, performing feedback is not the only indicator whether an alogirthm is AI. One could argue that if it acts in a way that appears intelligent, that's all that matters - especially when the game is played by a human opponent.

The kind of algorithm you've specified is really a parameterised equation, the kind you'll find in insurance calculations. After each move, the input space changes but the algorithm needs no memory of the previous state, so it treats each move as a new, separate board.

**Using Genetic Algorithms**

There are two clear options for genetic algorithms:

* Use the parameters for the genome (as you suggested). You will optimise the rules that you have but you're still left with an expert system.
* Use Learning Classifier System (LCS) to choose the rules for you. An LCS is a type of Genetic Algorithm where you encode the rules as well as the parameters. They take longer to converge, and are sensitive to the fitness function. I think the resulting manner of play might be more interesting for it.

**Simulated Annealing**

Another way to solve the problem is to use Simulated Annealing (SA). Your problem is a bounded input space and you can analytically write a function that finds the best square to pick in any given scenario. Using Simulated Annealing will find a global optimum for your parameters.

**On making it too good**

I know you want the algorithm to be the best it can be but don't forget that a human is playing against it. There is a tactically perfect way to play these sorts of deterministic games and if the AI player takes it, it would only purely luck that meant that the player wins.

# Answer
> 0 votes
Yes, the technique of assigning scores based on certain aspects of the position is standard in writing AIs to play games. For example, almost all chess programs work by scoring positions based most significantly on the pieces available, with smaller bonuses based on their positions (e.g., pawns protecting each other). They then try to calculate the best available move by using an adversarial search algorithm such as alpha-beta.

Adversarial search might be difficult here because of the large branching factor -- in any position, the legal moves are to mark or reveal any unknown square. On the other hand, it's possible that you can cut down the branching factor a lot by heuristics. For example, marking or revealing a square you know nothing at all about is very rarely going to be the best move. Conversely, if you know the locations of some unmarked mines, marking one of them will presumably be the best move, most of the time. Maintaining a transposition table would also probably help.

---
Tags: algorithms, artificial-intelligence, computer-games
---


title: Tree : Forest :: Path :?

text:
# Question
Title: Tree : Forest :: Path :?
A forest is a collection of trees.

Is there a similar notion for paths? e.g., a ***_*\__*_*\__*_*** is a collection of paths.

# Answer
> 5 votes
Wikipedia says that a graph all of whose non-trivial components are paths is a **linear forest**. Alternatively, you could call it just a **disjoint union of paths**.

---
Tags: graphs, terminology
---


# Question
Title: Why $R\circ\emptyset$ is not always equal to $\emptyset$
I was going through the text Introduction to Theory of Computation by Michael Sipser. It is written that $R\circ\emptyset$ may not equal to $R$. I thought $R\circ\emptyset=\emptyset$ always. $R$ is any regular expression.

Couldnt find any example that contradicts that

# Answer
Assuming by "$.$" you mean concatention ($\circ$ when made explicit by Sipser) and by $\phi$ you mean $\emptyset$, I'm not sure what the confusion is. Sipser is claiming that sometimes (in almost every case actually), $R\circ\emptyset \neq R$. You are correct in saying that $R\circ\emptyset = \emptyset$, so the only case where $R\circ\emptyset = R$ is when $L(R)=\emptyset$. For any regular expression that generates at least one string (including $\varepsilon$), $L(R) \neq \emptyset$ but $L(R\circ\emptyset) = \emptyset$, so $R\circ\emptyset \neq R$.
> 5 votes

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


title: Is human being a Turing Machine?

text:
# Question
Title: Is human being a Turing Machine?
We may not have a determinate answer to this question. But is there any evidence for or against this question? Or is there any study on it?

# Answer
> 1 votes
"Is a dog an animal?" is different from "Is an animal a dog?".

I read your question as going only in one direction: can a human being be simulated by a Turing machine? It is not about human beings being able to simulate a Turing machine, or "functioning" as one.

Essentially this is an open question, that depends on Chuch-Turing thesis, and on issues in physics regarding the physical limitations to computation that are still open (though some people dispute that, but history shows that some physicists have been known to believe they had nearly all the answers, the rest being expected next Friday). These issues involve for example the nature of time, and the opposition between a continuous and a discrete reality. Democritus (460-370 BCE) still lives.

Some details can be found in the second part of another answer I gave. There is a little bit more to it, but it is a first sketch.

Of course it could be that the answer to the OP's question is positive, even though the more general issue of computability might ultimately show that the Chuch-Turing limit could be overcome (I am not saying it can). But other than AI research, and brain research, that is all we have for now, afaik.

# Answer
> 6 votes
A Turing machine is a tuple consisting of an alphabet, a tape, some transition, etc.

I am not one of those. So no. A human being is not a Turing machine (or at least, I am not).

# Answer
> 4 votes
If you allow me an unbounded stack of paper to store the tape contents, I can obviously simulate a Turing machine, so a human being plus data storage is at least as powerful as a Turing machine. If you don't allow me to use paper, there seems to be a finite upper bound on how much data can be stored in my body, so I probably can't simulate a Turing machine.

As to whether a Turing machine can simulate a person, that's essentially the question of whether strong AIs exist, which is an open problem and a matter of much discussion among philosophers.

---
Tags: turing-machines, artificial-intelligence
---


# Question
Title: Algorithm to determine if an interval is covered by a list of intervals?
Given a list of intervals $\[s\_1, e\_1\], \[s\_2, e\_2\], \ldots$, what's the most efficient way to determine if an interval $\[a, b\]$ can be covered by the intervals in the list?

# Answer
> 2 votes
I don't know if it's the **most** efficient algorithm, but here's my suggestion:

Your problem is somewhat similar to balancing parenthesis: you can put all $s\_i$ and $e\_i$ values on a list and sort it (Lets call this list $V$), but keep the type of each element ($s$ or $e$ element) attached to the value. Then use this list to integrate all the intervals with the following algorithm (uniting overlapping intervals to one interval):

```
create a list of intervals L, Create a stack St
for every element n in the sorted list V (from the smallest to the largest)
{
    if n is an s element and St is empty
    {
         create a new interval I (a pair of numbers)
         assign I.s = n
         push some value to St
    }

    else if n is an s element and St isn't empty
    {
         push some value to St
    }

    else if n is an e element (stack can't be empty here)
    {
         pop a value from St
         if St is empty
         {
               assign I.e = n
               add interval I to the interval list L
         }
   }
}

return L

```

Now you have a list of integrated intervals, and checking if $\[a,b\]$ si covered by one of them is easy: for every interval $I$ in $L$, check if $a \geq I.s$ and $b \leq I.e$ (there are no overlapping intervals in $L$ now, they were integrated in the previous step).

Integrating the intervals to create $L$ takes $O(n)$ computation time and so is checking if $\[a,b\]$ is covered by one of the intervals in $L$, which makes the sorting $V$ the most expensive task here, $O(n\log{n})$.

Hope this helps, though there might be a linear time algorithm for performing this task...

---
Tags: algorithms, intervals
---


# Question
Title: Maximum possible file size in the filesystem
A file system with 300GByte disk uses a file descriptor with 8 direct block address ,1 indirect block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the size of each disk block address is 8 Bytes.What is the maximum possible file size in this filesystem? This is previous year question I could not get the idea and couldn't solve it...plz help

# Answer
> 1 votes
You may find the answers here and here

I should have posted this as comment but I don't have enough reputation points.

---
Tags: operating-systems, filesystems
---


title: Resolving many to many relationships?

text:
# Question
Title: Resolving many to many relationships?
I'm trying to separate a weird relationship. It goes like this:

1. One waiter can serve more than one kind of drink and one kind of drink can be served by more than one waiter.
2. One waiter can wear more than one kind of shirt (eg different uniforms daily, or random uniform assignments, etc), and one kind of shirt can be worn by more than one waiter.

There are two many-to-many relationships here that share the waiters, but can be separately resolved. But because they share the waiters entity, then many kinds of drinks can be served while wearing many kinds of shirts.

The relational model looks like this:

My question is, how do I resolve this? It doesn't look like it lends itself easily to being decomposed into one-to-many relationships.

Edit: I changed the image to fit in better with the description, but the problem that results here is the waiter-drinks and waiter-shirt entities still exist as a result of normalizing the drinks and waiters relationship (that is many-to many) and the waiter and shirt (also many-to-many). The resulting entities then have a many-to-many relationship as waiter-drinks and waiter-shirt.

Where am I wrong?

# Answer
If i rightly assume that you are trying to convert the E-R diagrams to relations (tables), then the procedure to convert a many-to-many relationship into relations is to create one more table, apart from the 2 tables that you will create for the 2 entities (waiter-drinks and waiter-shirt). This new table created for the relationship will have its attributes (columns) as the PKey of the constituting entities. In your case, this table will contain 3 attributes; namely waiter\_number, drink\_number and shirt\_number.

Had you been working on a one-to-one or one-to-many relationship, you would augment one more column to the table on many sides instead of creating another relation.
> 1 votes

---
Tags: databases, relational-algebra
---


# Question
Title: Why is the initial state of Zobrist hashing random?
When generating a board for Zobrist hashing, why are the initial elements random? How can you detect changes to elements later if the initial values are random?

# Answer
> 6 votes
The initial elements are chosen randomly to minimize hash collisions. You can think of the Zobrist hash as a random hash function $h$, mapping board positions to bit vectors of length $N$, chosen from some collection of hash functions. What we are trying to accomplish is this: given *any* choice of positions $p\_1,\ldots,p\_n$ arising in the program, we want that with high probability over the choice of $h$, $h(p\_i) \neq h(p\_j)$.

The Zobrist hash family is 3-wise independent: for any 3 distinct positions $p\_1,p\_2,p\_3$, the hashes $h(p\_1),h(p\_2),h(p\_3)$ are uniformly distributed over all triplets of binary vectors of length $N$. In particular, the probability that $h(p\_i) = h(p\_j)$ is $2^{-N}$ (we actually only need 2-wise independence for this), and so the expected number of collisions is $\binom{n}{2} 2^{-N}$, which is the same as the expected number of collisions for a *completely random* hash function.

The Zobrist hash function has an important advantage over a completely random hash function: it is easy to compute. Moreover, it is easy to update after a move of a single piece on the board. It is this last property which makes it especially attractive for hashing board positions.

By choosing the initial elements at random, we guarantee that whatever the board positions $p\_1,\ldots,p\_n$ are, the probability of collision is small (assuming that the positions are chosen *independently* of the hash function). There could also be some intelligent choice for the initial elements satisfying that, but it is not clear what this choice should be, and how to analyze it. On the other hand, a random choice succeeds with high probability, which is why we choose the Zobrist table randomly.

---
Tags: algorithms, artificial-intelligence, hash
---


# Question
Title: If a set S is infinite and recognizable, is there an infinite subset of S that is decidable?
If a set S is infinite and recognizable, how can I prove that, if any, some subsets K is infinite and decidable? how about infinite and recognizable?

# Answer
The second question is the easier one, we can just pick any string $\varsigma$ in the infinite Turing recognizable language $S$, and let $S' = S\setminus\\{\varsigma\\}$. Then you should be able to construct a TM that recognizes $S'$ from the recognizer $R$ for $S$.

The normal proof for the first question is trickier, relying on two facts:

1. Every Turing recognizable language has an enumerator (a TM that prints out the strings in the language one by one).
2. If a language has a lexicographic enumerator (a TM that enumerates the strings in the language in lexicographic order), then it is decidable.

So you start with $S$, which must have an enumerator $E$ that prints out, one by one, the strings in $S$ in some order, which may include repeats. What you have to do is construct a lexicographic enumerator using $E$ as a subroutine. It doesn't have to print out everything in $S$, just a subset of course, the trick is to ensure that the ones it prints are in lexicographic order. As noted Jeremy West in the comments, we must also ensure that the subset is infinite, this is easy enough, just not to be forgotten.
> 7 votes

---
Tags: computability, turing-machines
---


# Question
Title: Is this language depending on P = NP recursive?
Nobody yet knows if ${\sf P}={\sf NP}$. Let us consider the following language

$$L = \begin{cases} (0+1)^\* & \text{ if ${\sf P}$ = ${\sf NP}$} \\ \emptyset &\text{ otherwise}. \end{cases}$$

A language is said to be recursive if there exists any rule to determine whether a string belong to language or not. We have a rule here, but the rule itself depends upon an unknown equation. So can we say $L$ is recursive?

# Answer
> 7 votes
If **P=NP**, then $L = (0+1)^\*$ which is regular grammar. Hence, it is recursive.

If **P!=NP**, then $L = \phi $ which is also a regular grammar. Hence, recursive.

In both the cases, $L$ will be a recursive language.

*PS I see a lotta GATE problems these days :D*

# Answer
> 3 votes
This appears to be a semantic confusion. You are talking about two languages here, both of which are regular, both are recursive, both can be decided. The question we currently cannot answer is whether the label $L$ applies to the empty language or the language $(0 + 1)^\*$, but that has no bearing at all on whether the label refers to a language that is recursive. Languages aren't labels (like $L$) they are sets of strings.

---
Tags: computability, undecidability, p-vs-np
---


# Question
Title: Is it possible to have 2 languages with different syntax but the same semantics?
I have two questions

Is it possible to have 2 languages with different syntax but the same semantics? If not why not else give an example of 2 languages .

Is it possible to have 2 languages with same syntax but different semantics? If not why not else give an example of 2 languages .

I understand that the syntax is the external visible representation of a program and the semantics is the meaning of a program can some one please help answer these questions thank you.

Sorry if I wasn't clear but I was looking for examples of languages for example for the first question i have C# and VB.NET does that seem appropriate?

# Answer
Sure. I think it may be hard to answer the question using production languages since you are unlikely to find two "real" languages with identical semantics or identical syntax.

Let's consider a simpler example to illustrate the concepts. Take JSON (which I suppose isn't a programming language, per se, but the idea carries over). Now, change it so that instead of separating key-value pairs with colons we use equals signs and instead of separating items with commas we use semi-colons. Now it looks like this:

```
{
  "name" = "Bob";
  "age" = 23;
  "titles" = [ "Mr."; "Dr."; "Sir" ]
}

```

This is clearly semantically the same as the following, syntactically different string:

```
{
  "name" : "Bob",
  "age" : 23,
  "titles" : [ "Mr.", "Dr.", "Sir" ]
}

```

A bit of a simple example, but it should illustrate the point.

As far as the other direction is concerned, that is also true. For example, consider the standard for loop found in many languages:

```
for (int i = 0; i < 10; i++) {
  // do something...
}

```

This loop runs the initialization step once at the beginning, tests the condition *before* each iteration of the body, then runs the update step at the end of each iteration. But I could define a language with the same syntax but where the condition is evaluated at the *end* of the iteration and the update occurs at the beginning. The standard version is semantically the same as:

```
int i = 0;
while (i < 10) {
  // do something
  i++;
}

```

whereas my new definition is equivalent to

```
int i = 0;
do {
  i++;
  // do something
} while (i < 10);

```

which is clearly different.
> 1 votes

---
Tags: programming-languages, semantics
---


title: Execution time of an uneven pipeline

text:
# Question
Title: Execution time of an uneven pipeline
I was trying to solve a question dealing with n instructions in an uneven pipeline with k stages. I came across a generic formula for even pipelines i.e. (k + n - 1) * clock cycle. But I feel this should not work for uneven pipelines as the above formula is based on fact that the 1st instruction takes time = sum(time of k stages) and the 2nd instruction onwards takes time = maximum of stage delays.

A example: A pipeline is designed with 5 stages having execution times respectively as 3ns, 4ns, 2ns and 4ns. How much time will it take to execute 1000 instructions?

# Answer
> 3 votes
The first instruction (I1) will pass through all the stages one by one without any stall and will take $3+4+2+4=13$ cycles.

The second instruction (I2) goes next and it begins at the end of cycle 3. As soon as it finishes the execution of S1, it is ready to go to next stage. But it is occupied by the previous instruction. Hence, I2 needs to stall for 1 cycle (as in yellow). After this stall, it need not to pause for any cycle and finishes at cycle 17.

The same pattern is followed by the coming instructions.

So, the first instruction finishes in 13 cycles. Each of the remaining $n-1$ instructions finishes after 4 cycles taking $(n-1)\*4$ cycles.

You put $n=1000$ and the total number of cycles comes to be $13+999\*4 =4009.$

Hope it helps.

# Answer
> 1 votes
This is a very basic concept of pipeline. There is **no general formula** for execution time of instructions in pipeline **in real life** because there might be dependencies (raw,war, waw ) or there might be branch instructions. Although the question you asked is pretty straight forward. The first instruction needs 13 cycles to complete then each of the rest takes max(3,4,2,4) = 4 cycles to complete. So the time needed is 13 + (1000-1)\*4. Here you are assuming execution of same type of instructions 1000 times and without any data dependency or branch, this does not happen in real life. In real life to solve pipeline problems you have to draw the timing diagram, check for dependencies and branching and apply optimizations. So do not try to develop any formula just clear your concepts.

# Answer
> 0 votes
In case of uneven pipelines like you mentioned in the question, you take the execution time of the largest pipeline and treat the whole pipeline as an even pipeline with that execution time using the formula you mentioned in the question. See this pdf

---
Tags: computer-architecture, cpu-pipelines
---


title: Splay tree with odd number of rotations

text:
# Question
Title: Splay tree with odd number of rotations
When inserting an item into a splay tree, rotations are performed in pairs based on either a zig-zag or zig-zig pattern. When there is an odd number of rotations to be performed, one could either do the extra rotation beginning at the leaf or save the extra rotation and do it at the root. Does it matter?

For example, in the attached image I insert a 4 into a BST, and "splay it" it to the root. On the top of the figure, I first locate the zig-zig pair at the leaf node and perform the zig-zag splay from the bottom leaving a final right rotation at the root. At the bottom of the figure, I first do the odd rotation starting from the leaf, and the then do a zig-zig splay to the root.

Which is correct? Or will both lead to the usual splay-tree performance?

# Answer
> 4 votes
It really does not matter for the analysis. The key lemma for analyzing the splay-tree performance is the *access lemma*. It states that the amortized costs of a **splay(x)** operation is less than $1+3(r(t)-r(x))$, where $t$ is the root of the tree and $r(u):=\lfloor \log (\text{weight of $u$'s subtree}) \rfloor$. The weight of a subtree is the sum of the weights of its nodes. (Weights (positive) will be picked depending on the application of the lemma.) The potential function used is $\Phi(T)=\sum\_{x \text{ node of } T} r(t)$.

The proof of the access lemma looks at the costs of a single zig/zig-zag/zig-zig etc. operation. You get

1. Costs of a zig or zag operations are $1+3(r\_+(u) - r(u))$, where $r\_+$ is the rang after the operation and $u$ is the node rotated upwards.
2. Costs of zig-zig /zig-zag and symmetric operations are $3(r\_+(u) - r(u))$.

If you add these differences up for the operations performed in a single **splay(x)**, you get a telescope sum and what remains is $1+3(r(t)-r(x))$.

If you change the order of the rotations you will get the same sum. The only difference is that now the ''+1'' comes from the first rotation and not from the last rotation. You could even do the zig rotation in the middle. All further (classical) analysis relies on the access lemma.

However, the reason why you perform the single rotation last, is that you do not know if the depth of the node is even or odd in advance.

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


# Question
Title: Issue understanding the reduction of SAT to 3-SAT in poly time
Reading this http://classes.soe.ucsc.edu/cmps102/Spring10/lect/17/SAT-3SAT-and-other-red.pdf, I came to know that reducing a clause $C\_i$ from a $SAT$ instance containing more than 3 literals to a $3-SAT$ instance is done this way,

Suppose $C\_1$ is $\\{x\_1, x\_2, x\_3, x\_4\\}$. It's equivalent representation in 3-literal clauses is,

$C\_{3-SAT} = \\{\\{x\_1, x\_2, y\_1\\},\\{\bar{y\_1}, x\_3,x\_4\\}\\}$

The issue lies here. Assume for $C\_1$, all the literals are $False$ except for $x\_2$. For $C\_{3-SAT}$, the first clause would indeed be $True$, but the boolean value for the second clause depends on the choice of $y\_1$. What if we chose $y\_1 = True$? then, $C\_{3-SAT}$ will be $False$, yet $C\_1$ is $True$, realizing a false reduction.

# Answer
The clauses are not intended to be equivalent, so you shouldn't call it an "equivalent representation in 3-literal clauses."

All the reduction requires is that the original formula has at least one satisfying assignment if, and only if, the new formula does. In this case, we have this property: if the original formula was satisfiable, we can choose at least one assignment to the variables $y\_i$ that makes the new formula true and it doesn't matter that there are also choices for the $y\_i$ that make it false. Conversely, if the original formula was unsatisfiable, no choice of the $y\_i$ will make the new formula true.

Formally, there doesn't even have to be any relationship between the values of the variables in the two assignments. In theory, you could map all satisfiable formulas to "$x$" and all unsatisfiable formulas to "$x\wedge \neg x$". (But we don't know of an efficient way to do that.)
> 8 votes

---
Tags: algorithms, np-complete, satisfiability, 3-sat, boolean-algebra
---


title: How to find all "nearly roots"?

text:
# Question
Title: How to find all "nearly roots"?
Let $G=(V,E)$ a directed graph. We define $v \in V$ to be "nearly root" of there's a path from $v$ to at least $|V|/2$ vertices. How do you find the set of all "nearly roots" in linear time?

What we've tried is to build the strongly connected graph $G\_{scc}$ obtained from $G$ and then to do a topological sort. Now we went backwards and for each $U\in G\_{scc}$ we count how many vertices it can reach by scanning all outgoing edges and summing up all vertices reachable from it's successors. This seems wrong since we may count vertices more than once.

# Answer
The following algorithm will solve your problem

## Strategy

The task is decomposed into 2 subtasks:

1. Derive an annotated DAG from $G$. Contract cycles in $G$ to single nodes while traversing the implied spanning tree of a DFS, creating a graph $G'$,
2. Conduct a BFS on $G'$ with reversed edge orientations, identifying and marking nearly roots.

## Details

1. Perform a DFS on $G$. It's used as a tool to identify and contract cycles while keeping tabs on the number of contracted nodes.
For cycle contraction it suffices to detect backward edges ( mark/unmark nodes when entering a node for the first time / leaving it for the last time ). Each time a backward edge $(w, v)$ has been detected, all nodes on the current DFS path $p = v \stackrel{\*}{\rightarrow} w$ are coalesced into a new node $v'$, edges from nodes on $p$ are retained. These modifications can be done in situ
( $V\_{i} := (V\_{i-1} \ \\{ x \in V\_{i-1} | x \in p \\}) \cup \\{ v' \\}$
, $E\_{i} := (E\_{i-1} \ \\{ (x,y) \in E\_{i-1} | x \in p \\}) \cup \\{ (v',y) \in V\_{i}^2 | y \notin p \\})$
for the $i$-th contraction, starting with $(V\_0, E\_0) := (E, V)$). Mark each node in $V\_{i}$ with an attribute `represents` containing the number of nodes from $V$ it represents (i.e. initialising this attribute with $1$ and adding the cycle length subtracted by $1$ for each contraction). in case of contracted nodes also record the represented nodes by adding it to a stack attribute.
2. The resulting graph $G'$ is cycle-free (in particular: irreflexive). Next perform a BFS on $G'$ *with all edges reversed*. Propagate an attribute `reachable`: $V \rightarrow \mathbb{N}$ along the way which locally computes as $\text{reachable}(v) := (\text{represents}(v) - 1) + \sum\_{w \in pred(v)\subset V'} \text{reachable}(w)$ with `pred` denoting the set of predecessors and `reachable` being initialised to $0$ for all maximal elements in $G'$. for all nodes $v \in G'$ with $\text{reachable}(v) \geq |V|/2$, mark all represented nodes from the original graph $G$ as nearly roots.

## Complexity

1. Complexity of this operation is $O(E)$, as each edge is traversed at max 2 times in the course of the DFS and the contraction while the bookkeeping operations are $O(V)$ in total.
2. Complexity of this operation is $O(E)$, as each edge in $G'$ is traversed once during the BFS and $|E'| \leq |E|$. Updating `reachable` is $O(V')$ while marking the nodes from $G$ as nearly roots costs at most $O(V)$.
> 1 votes

---
Tags: algorithms
---


title: How to write a many-one reduction proof

text:
# Question
Title: How to write a many-one reduction proof
Writing a proof by contradiction is fairly formulaic--first you assume the opposite, then derive a contradiction. I would like to know the steps and conventions for writing a many-one reduction proof. This answer was somewhat helpful, but like other explanations I've heard, it sounds too similar to a proof by contradiction for me to understand the difference.

My specific points of confusion:

* The exact meaning of $A \leq \_{m} B$
* Do we reduce an unknown problem to a known problem, or the opposite
* Does the reduction function transform a known problem into an unknown problem, or the opposite
* How a many-one reduction is different from a proof by contradiction. It seems like a simpler version of the same logic; if so, how is the simplification justified

I am only interested in many-one reductions of language/Turing machine problems (in case the term has meaning in other contexts as well). Any help is appreciated, including links and illustrative examples. Thanks.

# Answer
> 8 votes
A many-one reduction is not a "proof-by-contradiction" per se, it is an application of a theorem. The theorem is:

> Let $L,L'\subseteq \\{0,1\\}^\*$, and $L \leq\_m L'$. Then, it holds that
>
> 1. If $L$ is undecidable, then $L'$ is undecidable.
> 2. if $L'$ is decidable, then $L$ is decidable.

I will omit the proof, there are plenty of resources where you can read up on it. You can view the statement $L \leq\_m L'$ intuitively as "The language $L$ is easier to decide than the language $L'$". And that's what a reduction proof does. You show that one language (the hard, known one, like the halting problem $H\_0$) is easier to decide than a new, unknown language $L$. By showing $H\_0 \leq\_m L$ you've essentially shown (by application of the above theorem) that the halting problem is easier than $L$. Thus, $L$ cannot be decided. So, to answer your questions:

1. $A \leq\_m B$ means that the language $A$ is easier to decide than the language $B$.
2. To show hardness, you reduce "YOUR\_HARD\_LANGUAGE $\leq\_m$ SOME\_NEW\_LANGUAGE". To show computability, you *can* reduce in the other direction, but usually it's simpler to just construct a TM that solves the given problem.
3. A reduction $L \leq\_m L'$ takes an instance $x \in \\{ 0,1\\}^\*$ and does the following with it: If $x \in L$, you make sure that the reduction $f(x) \in L'$. If $x \not \in L$, then the reduction maps $f(x) \not \in L'$. So - if you prove hardness, you transform a known hard problem into the unknown problem.
4. It is a contradiction in the sense of "If I could solve the new problem, then I can solve the hard problem, which cannot be, since it is proven to be hard". This contradiction is hidden in the Theorem above and you just slap it (implicitly) on every reduction you do.

I hope that helped. As I said, my main intuitive approach to reductions is "How could I use a new language $L'$ to solve an old, hard language $L$?".

# Answer
> 1 votes
HdM's answer has already dealt with most of the technical points.

A many-one reduction is not a contradiction and should not be thought of one, even informally. A many-one reduction from problem A to problem B is an efficient translation of instances of problem A into instances of problem B such that "yes" instances are mapped to "yes" instances and "noes" to "noes".

Even when you use many-one reductions to prove **NP**-completeness, you're not using contradiction. All you're saying is that instances of every problem in **NP** can be transformed efficiently into instances of some particular problem. It follows that a deterministic polynomial-time algorithm for that problem would give deterministic polynomial-time algorithms for all problems in **NP**. But, even here, there is no contradiction: we do not know that **P** $\neq$ **NP** so there is nothing to contradict.

---
Tags: turing-machines, reductions
---


title: assertion in first order logic

text:
# Question
Title: assertion in first order logic
Can anybody give me an idea how to write this assertion in in first order logic?

> X has not passed one or more of the prerequisites for A.

Here, X is the name of a person and A is a constant representing a course name.

# Answer
> 4 votes
Expressing properties of elements of the universe in first order logic is mostly achieved through defining appropriate relations. So for this you might like to consider relations like:

* $P(x)$ - $x$ is a person,
* $C(x)$ - $x$ is a course,
* $Pre(x,y)$ - $x$ is a prerequisite of $y$ (note that this doesn't actually say that $x$ and $y$ are courses),
* $Pass(x,y)$ - $x$ has passed course $y$.

(The parentheses are just included for clarity - you may have seen different notation where relations are written without.)

Then the rest is just building the logical formula, which in this case should be fairly obvious.

> $notready(x,a) \equiv P(x) \wedge C(a) \wedge \exists y(C(y) \wedge Pre(y,a) \wedge \neg Pass(x,y)) $

---
Tags: logic
---


# Question
Title: Efficiently calculating the minimum distance for TSP
Is it possible to calculate, efficiently, the minimum tour distance for TSP? That is, the distance without having to provide the actual tour.

If this is not possible (I assume it is not), how tight a lower bound can we efficiently calculate?

# Answer
When we say that TSP is hard to approximate up to a factor $\alpha$, this means that if there was an algorithm for TSP which always outputs a number in $\[OPT,\alpha OPT\]$ then P=NP (here OPT is the length of the minimal tour). The algorithm doesn't have to find a tour of this length.

Even more formally, what these results (probably) show is that there is a many-one reduction $f$ from 3SAT to TSP such that for a 3CNF $\varphi$, if $\varphi$ is satisfiable then the optimal tour of $f(\varphi)$ has length at most $1$, while if $\varphi$ is unsatisfiable then the optimal tour of $f(\varphi)$ has length at least $\alpha$. So if you could tell between these two cases, then P=NP.

See this list of hardness of approximation results for various variants of TSP.
> 4 votes

# Answer
Computing the length of the shortest tour is **NP**-hard: using it, you could solve the decision version of TSP (given the distance matrix and a target $k$, is there a tour of length at most $k$?), which is one of the standard **NP**-complete problems.

Approximation is covered by the Wikipedia article on TSP, which you should have checked before asking here. Essentially, approximation is hard in general but, for metric TSP (the version where the distances obey the triangle inequality), you can get within a factor of 1.5 of the optimal tour.
> 3 votes

# Answer
The question seems only for a lower bound rather than an approximation algorithm, although they are similar. For estimating a lower bound, you can use $TSP\geq \max\\{MST,2\times MM\\}$, where MM is the minimum perfect matching. Indeed this lower bound is used to develop the 3/2-approximation for the metric case but the lower bound works even for non-metric cases.
> 3 votes

---
Tags: traveling-salesman
---


title: GSAT incompleteness example

text:
# Question
Title: GSAT incompleteness example
The GSAT (Greedy Satisfiability) algorithm can be used to find a solution to a search problem encoded in CNF. I'm aware that since GSAT is greedy, it is incomplete (which means there would be cases where a solution might exist, but GSAT cannot find it). From the following link, I learned that this can happen when flipping variables greedily traps us in a cycle such as I → I' → I'' → I.

http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete.html

I've been trying quite hard to come up with an actual instance that can show this, but have not been able to (and could not find examples elsewhere). Any help would be much appreciated. Thanks :)

P.S. I'm not talking about "hard" k-SAT problems in which the ratio of variables to clauses approaches 4.3. I'm just looking for a simple example, possibly involving the least number of variables and/or clauses required.

# Answer
The original paper contains such an example (on page 5): $$ \begin{gather\*} (1 \lor \lnot 2 \lor 3) \land (1 \lor \lnot 3 \lor 4) \land (1 \lor \lnot 4 \lor \lnot 2) \land (1 \lor 5 \lor 2) \land (1 \lor \lnot 5 \lor 2) \land \\ (\lnot 1 \lor \lnot 6 \lor 7) \land (\lnot 1 \lor \lnot 7 \lor 6) \land \dots \land (\lnot 1 \lor \lnot 98 \lor 99) \land (\lnot 1 \lor \lnot 99 \lor 6) \end{gather\*} $$ The first five clauses force $1$ to hold. Indeed, suppose that $\lnot 1$. Clauses 4 and 5 force $2$, and so clauses 1 and 3 force $3 \land \lnot 4$, contradicting 2. The entire formula is satisfiable, for example by the all-true assignment.

If the starting assignment is not satisfiable or very close to satisfiable, then the authors claim that the large number of clauses of the form $(\lnot 1 \lor \cdot \lor \cdot)$ will ensure that $1$ remains false throughout the algorithm. See if you can substantiate this claim.
> 2 votes

---
Tags: algorithms, satisfiability, greedy-algorithms, 3-sat
---


# Question
Title: Why is determining the size of a maximum independent set or a clique in P?
I read that determining the size of the maximum independent set (and also a clique of maximum size) is in P. The versions that find the actual solution are known to be NP-hard.

With respect to finding clique size, you can sort the node degrees, decrement $i$ from $|V|$ to $0$, and each time check if you have $i$ elements of node degree $i$, pick the power set of those $\geq i$ elements and verify the clique. However, picking the power set is exponential, and this algorithm would give you the solution itself. I have a hard time figuring out how you can construct an algorithm that decides the presence of a clique (or independent set) of a certain size in polytime, but doesn't give you the solution.

# Answer
I would be interested to see what you read, but determining the size of the maximum independent set is $NP$-hard (of course clique is equivalent, so I'll just talk about independent set). Recall that the decision problem "Does the graph $G$ contain an indepedent set of size at least $k$?" is $NP$-complete. If we could determine the size of the maximum independent set ($\alpha(G)$) in polynomial time, we could answer this decision problem in polynomial time by taking $G$, getting $\alpha(G)$ from our polynomial time algorithm, then if $k \leq \alpha(G)$, we say $Yes$, if $k \> \alpha(G)$ we say no. Hence a polynomial time algorithm for determining the maximum would immediately give us $P=NP$.

Perhaps you read that determining the size of a *maximal* independent set is poynomial time solvable. A maximal set is just one that cannot be made larger, so we can (typically, and certainly for independent sets) compute these greedily.
> 4 votes

---
Tags: algorithms, complexity-theory, graphs, time-complexity
---


title: Description of “Logistics Domain” in AI

text:
# Question
Title: Description of “Logistics Domain” in AI
While reading some papers in AI (for a project I have to do), I see expressions "blocks world domain" and "logistics domain". I know what blocks world domain is, but I don't know the definition of logistics domain.

Any help would be appreciated.

# Answer
Logistics and Blocksworld are domains that are often used as examples in the field of automated planning and scheduling.

Logistics was used in the first international planning competition IPC98. The description on this site says:

> There are several cities, each containing several locations, some of which are airports. There are also trucks, which can drive within a single city, and airplanes, which can fly between airports. The goal is to get some packages from various locations to various new locations. This domain was created by Bart Selman and Henry Kautz, based on an earlier domain by Manuela Veloso.

It is described in more detail in by McDermott:

D. McDermott, The 1998 AI Planning Systems competition, *AI Magazine* 21 (2), pp. 35-55. 2000. (paper)

A complexity analysis for this domain is in the follwing paper by Helmert:

M. Helmert. Complexity results for standard benchmark domains in planning. *Artificial Intelligence* 143 (2), pp. 219-262. 2003. (paper)
> 1 votes

# Answer
As far as I can see, it refers simply to the field of Logistics.
> 1 votes

---
Tags: terminology, artificial-intelligence
---


# Question
Title: Karnaugh map - assign variables to the inputs?
I drew the map on the right, but what I drew doesn't work for what the question is asking me. I think I did something very wrong, and I don't really understand what this question is asking me. Am i suppose to re arrange the binary inputs somehow?

# Answer
I assume $w,x,y,z$ are inputs to the circuit given. What we need is $$\sum\_{w,x,y,z}(2,3,8,9)$$

Put this in a Karnaugh Map and you will get the simplified equation as $w^\prime x^\prime y + wx^\prime y^\prime$. Now, let $a,b,c,d$ be the inputs to the circuit that you have given. Output of first **OR gate** will be $a+b$. Let it be called $f$. Output of second **OR gate** will be $c+d$. Let it be called $s$. Output of the **XOR gate** is $fs^\prime+sf^\prime$. Substitue the values of $f$ and $s$ in the equation and use the equality $(\alpha+\beta)^\prime=\alpha^\prime \beta^\prime$The output will be $$a^\prime b^\prime\cdot(c+d)+c^\prime d^\prime\cdot(a+b)$$.

Compare this with the equation that we require and we find that $$a=w$$$$b=x$$$$c=x$$$$d=y$$ These are the order in which inputs should be given.

Karnaugh Map that you have drawn is correct assuming that $w,x,y,z$ are inputs to the circuit.
> 0 votes

---
Tags: logic
---


title: Removing Null moves from NFA

text:
# Question
Title: Removing Null moves from NFA
While Learning about removing null moves from NFA , I came across a thought....

To **Remove Epsilon moves** we follow following steps :

1. Find **Closure of all states** which have null moves
2. Mark **these states which have null moves**
3. **Make a revised transition table without epsilon column** and Find all possible transition for those marked states by using their Closures.
4. you will get nfa without null moves/epsilon moves

Where is the issue : Actually, Doubt arises when you think of an nfa like this :

If we try to remove epsilon moves out of it...

Initial transition Table :

Now finding closure for q0, q1 and q3.

**Which is CL(q0) = {q0,q1,q2} CL(q1) = {q1,q2} CL(q3) = {q2,q3} We find a transition table after following above steps which is :**

The question gets quite tricky...

because now this nfa has q1,q2 where there is no way to reach them..

So What do you think we will remove q1 and q2 as they are unreachable or we will draw a nfa with them...

# Answer
> 6 votes
In your construction you correctly computed the closures of the original states and then made the $a$- and $b$-transitions, but you omitted step (3) of the algorithm: compute the closures of the results *again*. For example, from $q\_0$ on input of $a$ the first step is $$ q\_0\stackrel{CL}{\longrightarrow} \\{q\_0, q\_1, q\_2\\} $$ then, on seeing an $a$ we make the transitions, as you did: $$ \\{q\_0, q\_1, q\_2\\}\stackrel{a}{\longrightarrow} \\{\delta(q\_0, a), \delta(q\_1, a), \delta(q\_2, a)\\}=\\{q\_3, q\_4\\} $$ then (here's the step you omitted), *you take the closure again*: $$ \\{q\_3, q\_4\\}\stackrel{CL}{\longrightarrow} \\{q\_2, q\_3, q\_4\\} $$ and thus you'll have the new transition $\delta'(q\_0, a) = \\{q\_2, q\_3, q\_4\\}$.

If you do this for all the state-symbol pairs, you'll find that the transitions of your new NFA are $$\begin{array}{c|cc} & a & b\\ \hline q\_0 & \\{q\_2, q\_3, q\_4\\} & \\{q\_2, q\_3\\} \\ q\_1 & \\{q\_2, q\_3, q\_4\\} & \varnothing \\ q\_2 & \\{q\_4\\} & \varnothing \\ q\_3 & \\{q\_4\\} & \\{q\_5\\} \\ q\_4 & \\{q\_5\\} & \\{q\_2, q\_3\\} \\ q\_5 & \varnothing & \varnothing \\ \end{array}$$ Since $q\_1$ is an unreachable state, it can be eliminated without changing the langauge of the resulting NFA.

# Answer
> 2 votes
**Hint**. There is a path $q\_0 \xrightarrow{\lambda} q\_1 \xrightarrow{a} q\_3 \xrightarrow{\lambda} q\_2$. So you should have a transition $q\_0 \xrightarrow{a} q\_2$ in your revised transition table. \[Forget about this\].

**Update**. Sorry for the confusion, but actually I am not sure to understand your algorithm, but here is one. Let us call *null path* a path labeled by the empty word. For each state $p$, let $$ R(p) = \\{ q \mid \text{there is a null path from $p$ to $q$}\\} $$ Now take as set of initial states the set $$ \bigcup\_{\text{p initial}} R(p) $$ and as set of final states the set $$ \\{p \mid R(p) \cap F \not= \emptyset \\} $$ In your case $q\_0, q\_1, q\_2$ will become initial states. Then for each transition $p \xrightarrow{a} q$, add the transitions $p \xrightarrow{a} r$ for each $r \in R(q)$. Finally remove all the empty transitions. In your case, you will only need to add the transitions $q\_1 \xrightarrow{a} q\_2$ and $q\_0 \xrightarrow{b} q\_2$. This is simpler.

# Answer
> 0 votes
You should change the start state to $CL(q\_0)$ where $q\_0$ is the start state. This makes $q\_1,q\_2$ re-appear in the transition table. Why should you do this? Because, if the start state has null transitions and if you want to remove $\lambda$-transitions, then you have to make these states start states too.

# Answer
> 0 votes
You may try removing $\epsilon$-moves in your NFA from vertex $v\_1$ to vertex $v\_2$ using following steps :

1. Find all the edges starting from $v\_2$.
2. Duplicate all these edges starting from $v\_1$, without changing the edge labels.
3. If $v\_1$ is an initial state, make $v\_2$ also an initial state.
4. If $v\_2$ is a final state, make $v\_1$ also a final state.

If you still want to do it in your way, I will read your procedure.

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


# Question
Title: Doubt in the correctness of decision tree models for constructing a lower bound
If we were to intuitively construct a lower bound for searching an element in a list $A$ containing $n$ integers, it would be in $\Omega(n)$.

But with the decision tree model, the number of leafs is $n$, so we conclude that the lower bound is $\Omega(\log{n})$.

This is the same as finding the maximum element in a list. Intuitively, it is in $\Omega(n)$, but with the decision tree model it is $\Omega(\log{n})$.

Can someone help me understand this discrepancy ?

Thank you in advance.

# Answer
The bound you're describing is that the depth of the decision tree is at least the logarithm of the number of distinct answers. This bound always holds, but is not always tight. In the case of searching an element in a list, it is tight when the list is sorted, and not tight if we don't assume anything on the list. The reason for this discrepancy is that the bound doesn't distinguish between the two cases — it is too general.

I challenge you to come up with another argument showing that the depth of a decision tree for finding an element in a list is at least $n$ (or even $n+1$, depending on how depth is defined).
> 4 votes

---
Tags: algorithms, search-algorithms, decision-problem, trees, lower-bounds
---


title: Is this NP-completeness proof correct?

text:
# Question
Title: Is this NP-completeness proof correct?
I want to prove that a problem $P\_1$ is NP-complete. Let say that I want to do a reduction from SAT problem.

If the instance of problem $P\_1$ depends on $M$ and $N$, can I specify the sturcture of the instance of the SAT problem?

More precisely, can I say that, for example, the instance of SAT problem is composed of $M\times N +1$ clauses and every clause has $M+N$ literals ?

Based on this structure of the instance of SAT problem, I construct an instance of $P\_1$. Is this proof correct?

# Answer
> 2 votes
In your specific case, what other constraints do you have on $M$ and $N$? For example, if it is possible that $M=N=1$, then each of your clauses will have 2 literals, and your SAT problem actually seems to become the 2-SAT problem which is in P.

So if $P\_1$ depends on $M$ and $N$, maybe you should consider an NP-complete SAT variant that somehow takes them into account. In general, if you want to add some additional constraints on SAT (or any other problem you reduce from), make sure the problem still remains NP-complete.

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


# Question
Title: How do you classify properties as Trivial and Non-trivial?
I understand what Rice's theorem states and what Trivial and Non-trivial properties mean. However, when given some property, I am having a hard time seeing if it is Trivial or Non-trivial. Can someone help me understand this better, maybe with some good examples?

# Answer
> 16 votes
A property $P$ is a set of Turing machines. The property is *trivial* if it contains *every* TM, or if it is *empty*.

Essentially, in order to check if a property is trivial, just check if there is a TM that satisfies it and if there is a TM that does not satisfy it. If both kinds exist, then the property is nontrivial. Otherwise it is trivial.

However, deciding this can be difficult...

For example, consider the property $\\{M: L(M)=\emptyset\\}$. This is a non-trivial property, since there are TMs with an empty language, and there are TMs with a nonempty language.

A trickier example is $\\{M: L(M)\in RE\\}$. Initially, this may seem like a nontrivial property. But recall that every TM recognizes its own language. So $L(M)$ is in RE for every $M$. Thus, this property is simply the collection of every TM. So it is trivial.

---
Tags: computability, turing-machines
---


# Question
Title: Relation of Space and Time in Complexity?
I'm looking for some clarification on some concepts/facts I came across while studying for a class.

I was reading the following wikipedia article. The below specific section and statement intrigued me when looking it over.

http://en.wikipedia.org/wiki/Computational\_complexity\_theory#Important\_complexity\_classes "It turns out that PSPACE = NPSPACE and EXPSPACE = NEXPSPACE by Savitch's theorem"

I also read that NTMs can be simulated by DTMs but that the shortest accepting computation of the DTM is exponential with respect to the shortest accepting computation of the target NTM.

**My questions are:**

1.) Are PSPACE and NPSPACE the set of all problems that require at least polynomial space to be solved on Deterministic and Non-deterministic Turing machines respectively?

2.) If so, is the actual size of the polynomial space required dependent on the size of the input?

3.) For P and NP, they are each the sets of problems that require at least polynomial time to be solved on DTMs and NTMs respectively correct?

4.) Is the reason that the shortest accepting computation of a DTM simulating a target NTM is exponential with respect to the shortest accepting computation of an NTM due to the exponential explosion of the number of configurations that an NTM supports as input grows for a given problem?

5.) My last and overarching question is: Are the differences in the set of problems that can be solved in polynomial time on DTMs versus NTMs related to time/space tradeoffs where DTMs can't run some polynomial NTM algorithms in polynomial time because they don't have the same "space" that an NTM has available to it?

I'd also appreciate any reading you can suggest to me on time/space tradeoffs and NTMs versus DTMs.

# Answer
> 5 votes
That's rather a lot of questions for one Stack Exchange post. One or two closely related questions per post is best. But here goes...

> 1.) Are PSPACE and NPSPACE the set of all problems that require at least polynomial space to be solved on Deterministic and Non-deterministic Turing machines respectively?

No. They're the set of all problems that require *at most* polynomial space to be solved on deterministic and nondeterministic Turing machines, respectively.

> 2.) If so, is the actual size of the polynomial space required dependent on the size of the input?

No. For any given machine, the polynomial is fixed. The input to the polynomial is the length of the input. (E.g., if the machine runs in space $3n^2+4$ and the input has length 3, the Turing machine will need at most 31 cells of storage on its work tape.)

> 3.) For P and NP, they are each the sets of problems that require at least polynomial time to be solved on DTMs and NTMs respectively correct?

Again, *at most*.

> 4.) Is the reason that the shortest accepting computation of a DTM simulating a target NTM is exponential with respect to the shortest accepting computation of an NTM due to the exponential explosion of the number of configurations that an NTM supports as input grows for a given problem?

We don't know for sure that there's any loss of efficiency at all when simulating a nondeterministic machine on a deterministic one. But the reason we don't know how to do it with better than exponential slowdown is, as you suggest, that we don't know any better technique than trying all the possible nondeterministic choices, one by one.

> 5.) My last and overarching question is: Are the differences in the set of problems that can be solved in polynomial time on DTMs versus NTMs related to time/space tradeoffs where DTMs can't run some polynomial NTM algorithms in polynomial time because they don't have the same "space" that an NTM has available to it?

Not really. It's because the nondeterministic machine in a sense computes lots of options in parallel and it accepts if any of those parallel options accepts. As I said above, the only way we know how to simulate all of these parallel computations is to do them sequentially, one after another. But there isn't any particular time/space trade-off: if a nondeterministic machine makes some computation in time $t(n)$ and space $s(n)$, a deterministic machine can do the same computation in time $2^O(t(n))$ and space $s(n)+O(t(n))$. The exponential blow-up in time is because a $q$-state nondeterministic machine might make up to $q$ nondeterministic choices (i.e., spawn up to $q$ "parallel threads") at each step of its execution; the smaller increase in space is because of the book-keeping required to keep track of which choices we tried at each step.

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


# Question
Title: Algorithm for detection of overlaping between vectors
I am currently developing a math-physics program and I need to calculate if two vectors overlap one another, the one is vertical and the other is horizontral. Is there any fast algorithm to do this because what I came up so far, has a lot of repeats. Eg lets say we have vector V1((0,1),(2,1)) and a V2((1,0),(1,2)) where the first parenthesis is the coordinates starting and the second coordinates that the vector reaches. I want as a result to take that they overlap at (1,1)

So far the only idea I came up is to ''expand'' each vector to a list of points and then compare the lists e.g for V1 its list would be (0,1) (1,1) (2,1)

# Answer
If you have two line segments and you want to know if they intersect, see https://en.wikipedia.org/wiki/Line\_intersection and https://en.wikipedia.org/wiki/Line\_segment\_intersection.

For next time, I'd expect you to do more research on your own. See especially "computational geometry", e.g., a textbook that covers that area.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Help in geometrically understanding "Linear Decision Trees"
In the words of (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf, section 17.2), "Each $f(x)$ can be interpreted as deﬁning a hyperplane in $R^n$. Thus, tracing a path through the tree computes the intersection of the half-planes deﬁned by the nodes touched by the path."

I fail to visualize how path tracing is done? I would be glad to see it explained through the presentation of the path in a 2-dimensional space.

I do understand that $x\_1,x\_2,...,x\_n$ is a point in the $R^n$ dimensional space. But I don't get how Figure 17.1 in (http://www.cs.utah.edu/~suresh/5962/lectures/17.pdf) helped in proving the lower bounds of Element Uniqueness as $\Omega(n\log n)$. I also don't get the implication of $\\#F$ being connected components; why can't they simply be called solutions?

Unfortunately, reading online resources did not help me much understand the aforementioned concepts.

Thank you in advance.

# Answer
> 2 votes
At each point in the linear decision tree, we branch according to whether $f(x) \> 0$, $f(x) = 0$ or $f(x) \< 0$, where $f$ is some linear functional. That means that the values of $x$ reaching some leaf are exactly those values satisfying some system of linear equations and inequalities $$ \begin{align\*} &f\_1(x) = f\_2(x) = \dots = f\_a(x) = 0, \\ &g\_1(x), g\_2(x), \dots, g\_b(x) \> 0, \\ &h\_1(x), h\_2(x), \dots, h\_c(x) \< 0. \end{align\*} $$ Here $f\_i,g\_i,h\_i$ are conditions encountered along the way. (In fact we can get rid of the $h$s, but this doesn't matter.) Each of these conditions — $f\_i(x) = 0$, $g\_j(x) \> 0$ or $h\_k(0) \< 0$ — is convex, so their intersection is convex. This means that the set of all points getting to that leaf is convex, and in particular, either empty or connected.

In order to get a lower bound for element distinctness (for example), we show that the set $\\{x : \text{all components of $x$ are distinct}\\}$ has many (in fact $n!$) connected components. If we take one vector each from all the connected components, then all these vectors must land at different leaves (why?), so there must be many leaves, hence the tree must be deep.

---
Tags: algorithms, search-trees, lower-bounds
---


# Question
Title: How is ARC consistency un-done after a recursive failure condition?
Taking this as an example:

```
bool SolveSudoku(int grid[N][N])
{
    int row, col;

    // If there is no unassigned location, we are done
    if (!FindUnassignedLocation(grid, row, col))
       return true; // success!

    // consider digits 1 to 9
    for (int num = 1; num <= 9; num++)
    {
        // if looks promising
        if (isSafe(grid, row, col, num))
        {
            // make tentative assignment
            grid[row][col] = num;

            //RUN ARC CONSISTENCY HERE ......?

            // return, if success, yay!
            if (SolveSudoku(grid))
                return true;

            // failure, unmake & try again
            grid[row][col] = UNASSIGNED;

            ////REMOVE ARC CONSISTENCY HERE ......?
        }
    }
    return false; // this triggers backtracking
}

```

Given the backtracking algorithm with CSP's, I would like to add ARC consistency to make it smarter.

For example:

> "When we want to assign the digit 'd' to cell s1, we use assign(cells, s, d). ...but I also want to eliminate this possibility from its peers (like Forward Checking does, tell me something new!). If the elimination causes one (or some) of the peers going down to only one possibility, which we call d2, we want to assign d2 to it, and by doing that, eliminate d2 from all of its peer's peers, and that could make another chain reaction. This chain reaction is simply called constraint propagation: placing a constraint on one cell can cause further constraints to be placed on other cells."

* Can the process of arc propagation end up leading to a solution by itself or even a false solution? What is done in those cases?
* In the likely event the next recursive call on the next variable returns false (no values worked out for that variable), **how do I undo all the changes the arc consistency did?**

# Answer
The obvious answer is: take a snapshot (checkpoint) of your state before applying the arc consistency inferences; recursively explore that option; and then if it is a failure, restore the state back to your snapshot.

Whether this is efficient depends upon the size of the state and the amount of work done during the recursive call. For this particular application (Sudoko), I suspect you don't have much state, so I expect this will be a perfectly reasonable solution.

In more complex situations, you can use more sophisticated data structures that support undo/rollback. For instance, persistent data structures are one way to make rolling back to a prior version faster, in some cases. Partial persistence is enough; you don't need full persistence or confluent persistence. However, for simple cases like this one, the overhead of persistence might outweigh any gain from avoiding copying the state.

If you want us to recommend a more efficient solution than the naive copying approach, you'll need to specify in greater detail what sort of data structures you need for this application (e.g., for storing the set of constraints).
> 2 votes

---
Tags: algorithms, artificial-intelligence, recursion, constraint-programming, backtracking
---


title: What CS Textbooks should I buy?

text:
# Question
Title: What CS Textbooks should I buy?
I am preparing to graduate high school. Although I do not intend to study computer science in college, I feel like it might be useful to familiarize myself with the theoretical CS concepts taught in academia (eg. algorithms, structures, compilers). Can you recommend books that are either frequently used in current CS curricula or equate what one would learn in a CS curriculum?

Right now, I am planning on buying The C Programming Language, The Algorithm Design Manual, Algorithms + Data Structures = Programs, and Compilers: Principles, Techniques, and Tools.

# Answer
For Computer Science, I would recommend you

> Computer Science: An Overview 11th J. G. Brookshear.

If you are more interested, you can attend one of the online courses, you can register for free and finish these courses online with exercises. I recommend you one of these:

* An Introduction to Computer Science from Harvard, more informations you can find here EDX
* Computer Science from Stanford, more info here

Algorithms, you can find relevant online courses following these books on EDX and Coursera as well. Depends on how much time you have and want to spend on these subjecs, and how deep you want to go.

> Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne

or

> Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein
> 8 votes

# Answer
The theoretical "core" of a CS degree would consist of (1) basic data structures and algorithms, (2) formal languages, automata, complexity, computability.

For the first, "CLRS" is the most-used textbook: http://mitpress.mit.edu/books/introduction-algorithms

For the second, Sipser: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/113318779X

On the more "applied" side there is systems, programming languages, and of course experience with coding. Systems includes for instance operating systems and compilers. The dragon book might be a classic but I would guess overkill for what you're looking for. The best way to learn OS or compilers might be to just take a class in it; I'm not sure if there are "canonical" textbooks. For a textbook that hits lots of these basics, though, SICP comes highly recommended and is free online: http://mitpress.mit.edu/sicp/ . If you are interested in learning more programming languages and seeing variety, I would look up "Learn You a Haskell For Great Good" and SICP as mentioned above. For the theoretical side, maybe something like Pierce's "Types and Programming Languages"?

I would *not* spend time and money on language-definition or tutorial books like "The C programming language". I'd learn and practice programming online instead. Sites like topcoder's algorithms contests, SPOJ, and projecteuler provide good practice and you can find tutorials to get you going.

There is also some mathematics background, but you can go far on very little: linear algebra, calculus, hopefully some practice with probability and combinatorics.
> 5 votes

---
Tags: books
---


# Question
Title: What are the justifications and historical reasons regarding the choice between the words 'calculus' and 'algebra'?
The principles of calculus, historically, are differentials and integrals \[1\], while those of algebra are operators and equation solving \[2\]. Contemporary principles are analysis and abstract objects, respectively.

As an example case, why is relational algebra not called a calculus, and why is the π-calculus not called an algebra?

# Answer
> 9 votes
What is in a name? Calculus is called *analysis* in some languages other than English, while the word *calculus* itself means computation.

The name π-calculus was most likely chosen by Milner because it has to do with computation, and is intended to be for parallel computation similar to what $\lambda$-calculus is for classical sequential computation. Computation is actually the original meaning of calculus, referring to pebbles used as counters in ancient time.

The word *algorithm*, as everyone knows, comes from the name *al-Khwarizmi* (the man from Khiva, a city formerly called Khwarezm), given to the 9th century Persian mathematician Abū Ja‘far Muhammad ibn Mūsa. *Algebra* comes from the name of the treatise Hisab al-jabr wa'l muqabala, that he wrote about the resolution of equations.

*Al-Khwarizmi systematized the study of equations (**algebra**), and gave procedural techniques to solve them (**algorithms**), which implies some form of computation (**calculus**). Could this be seen as a kind of Curry-Howard situation, where the mathematics for proving go in hand with the corresponding algorithms to actually compute ?*

Names may be chosen for strange reasons, and their meaning evolves along with the objects they initially denote. The internationalization of sciences also leads to different interpretations of words, as the same word (or its local variant) may have a different meaning in different country (and that is also true is other areas of language, possibly creating some awkward situations).

This issue has already been discussed on math.SE.

---

**Further remarks**

Actually, according to wikipedia, *Analysis* is used in all languages, English included, with the same meaning. English appears to use the word *Calculus* which refers only to elementary concepts of Mathematical Analysis, differential and integral calculus. If you look for the English *Calculus* in wikipedia, you find out that translation is missing for many languages (no equivalent entry in German or French for example), and when an entry is proposed for another language it may corresponds to a different meaning (*Cálculo* in Spanish is for calculation or computation, as it is in some other languages).

However, *Cálculo* in Portuguese has the same meaning as in English and covers the same topics. They actually explain, for Portuguese, the origin of this use of the word, and the explanation is likely to be the same in English. *Calculus* is very simply an abbreviation for "*differential and integral calculus*". And indeed, it corresponds to computations expressed with algorithms, and is, in this sense, close to Algebra.

I was mislead, in understanding the question and writing the first part of my answer, because I took *Calculus* to mean the whole of Mathematical Analysis, as there is no single word in my own language to cover specifically differential and integral calculus. Comments show that I am not the only non-american user to be thus mislead.

Hence there is no linguistic inconsistency. The name *λ-calculus* denotes a formalisation of algorithms and computation, and the use of the word *calculus* is adequate. From it was derived the name *π-calculus* for parallel computations.

Note that initially, *calculus* just means computation (*calculation* has a connotation as pertaining to numbers). When applied to a specific domain, it is qualified so that the domain is explicit (integral calculus, π-calculus, ...). The problem comes from the fact that it has a common use in some languages, including English and Portuguese, where it is domain specific without making the domain explicit, while also retaining its more general use.

---
Tags: terminology
---


# Question
Title: Are there dynamic programming examples that run in exponential time?
Are there dynamic programming examples that run in exponential time? Every example that I've seen so far constructs the top half of a matrix in a bottom-up fashion ($n^2$) from the base case and evaluates $n$ expressions to optimize each entry.

# Answer
A well-known example is the Held-Karp dynamic programming approach to solving the traveling salesman problem (TSP), running in $O(n^22^n)$ time and $O(n2^n)$ space. For more, see these notes.
> 7 votes

# Answer
A good example is the dynamic programming algorithm for (integer) SUBSET-SUM, which works in time $O(nT)$, where $n$ is the number of elements and $T$ is the target. The target could be exponential in its length, so in general this runs in exponential time.
> 5 votes

# Answer
Examples can be created artificially. Take any problem for which polynomial running time is not known and apply Dynamic Programming on it. For example, you can take the problem of finding largest independent set in a graph. You can apply DP on it saying a vertex $v\_0$ can be in the set or not. This gives two cases. Since this problem is not known to be solvable in polynomial time, you cannot reduce exponential number of calls in DP to polynomial number.
> 2 votes

---
Tags: algorithms, runtime-analysis, dynamic-programming
---


# Question
Title: ML Algorithms to discriminate "known" from "unknown" instances
I'm classifying different electrical devices based on features extracted from their electricity consumption into a household-specific model built from around 10 devices. Now I want to detect whether a classified testing instance is coming from a device which has not been present in the training set, i.e. I want to discriminate known from unknown devices.

I'm working with Weka and use the Classifier.distributionForInstance() method to give me the (classifier-specific) probability distribution for those 10 possible classes for each instance.

Now, the problem is that some classifiers (SMO, NaiveBayes, J48 and other trees) most of the time classify a not known device with a high probability of almost 1 to a class, whereas RandomForest (preferably with high amount of trees) and IBk (kNN) perform rather well in giving back lower probabilities of classification/more uncertain results.

The questions I have: Can you think of alternative approaches or any other algorithms/methods? Why is it, that the first stated algorithms strongly decide for one class. I would have expected them to return unclearer results.

thx, regards

# Answer
I would use a two-step pipeline where the first step discriminates between known and unknown and the second step performs the actual classification. This approach has a number of benefits.

1. Separating the two problems allows you to judge the accuracy of each step. You can assess the quality of your known/unknown discrimination independently of your actual classifier and vice versa. This will tell you where you need to focus your efforts.
2. You don't need to worry about your classifier being over confident for examples you aren't actually interested in since presumably you're taking care of this beforehand.
3. The known/unknown discrimination is just the problem of outlier detection. There are lots of ways to approach this and you may be able to find methods designed to work within your specific problem domain. I frequently hear 1-class SVMs (support vector machines) come up in this context, but have never worked with them personally.

If you think about the way decision trees work it is pretty easy to see why a single tree is going to be overconfident. There are lots of different ways to learn decision trees, but in general you can think about them as trying to make the leaves as pure as possible, i.e., we want the leaves to contain instances that all have the same class. Since an unknown example is just going to follow some path down the decision tree, it will end up in a leaf, which by construction, contains little class variability. From this observation it is easy to see why combining many different trees (like in Random Forests) is going to help avoid this problem.

As for why Naive Bayes is being overconfident, I would guess this is due to some combination of one of the class priors $P(y)$ being larger than the others, and/or having most features be unknown for your unknown example (so $P(x\_i|y)$ is approximately the same for all $y$ and most $i$ if you're smoothing the estimates) and a couple show up in one class causing the $\prod\_i P(x\_i|y)$ term to blow up for one $y$ relative to the others. This is just a guess without the data.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: How are Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets related?
I am having an AI exam in two weeks, and I am still figuring out certain concepts and ideas, related to Bayesian Nets, Hidden Markov Chains, Conditional Random Fields and Neural Nets (yes it is all going to be tested and yes we have a text (AI - A Modern Approach), but no, we did not cover everything in class).

I "know" a few things about the mathematical descriptions of all of those, but I know pretty much nothing about their usage or practical applications.

Here are my questions (and I apologize for my naivety):

1. What kind of machine learning algorithm classes do they belong to? Since they all need training, does it mean that they are all supervised learning algorithms?
2. They all have an underlying structure that allows a graph to represent them, where directed edges denote dependencies between states. The probability of being in a state is computed as a conditional probability from ancestors of the state. Does that sound about right?
3. In what kind of situation do you want to use which of the algorithms? Is it possible to some it up, or does it require subtle differentiation and expert-level knowledge?
4. Why do Neural Nets get special treatment? I heard of many classes teaching Neural Nets, but I have heard of no such thing for the other guys.

# Answer
1. No, needing training has nothing to do with unsupervised/supervised. Supervised learners need labels, unsupervised learners do not (they do things like clustering, density estimation, dimensionality reduction). In fact you can use all of them for supervised and unsupervised learning, except maybe CRFs, since an unsupervised CRF would more likely be referred to as a markov random field (MRF) since there is no conditional per se. Someone might argue with me on this last point and I probably wouldn't argue back.
2. No, CRFs have undirected edges. ANNs can have undirected edges also (for example autoencodes with tied weigths). ANNs don't need have a probabilistic interpretation.
3. Sometimes it would be obvious. For example, if I'm doing Image Denoising I'm not going to use an HMM. Other times it will depend on things like what the practitioner has experience with, what works well in this domain, or a myriad of other factors.
4. Out of all the thing on your list ANNs are the only one that need not have a probabilistic interpretation. Furthermore, the techniques used for training ANNs normally are of a different flavor than what is used for other methods. That being said there are lots of classes that will focus on other types of models and likely not discuss ANNs, for example Probabilistic Graphical Models, Generalized Linear Models, etc.
> 5 votes

---
Tags: machine-learning, artificial-intelligence, neural-networks, probabilistic-algorithms, markov-chains
---


# Question
Title: Is there a guaranteed min-cut algorithm for weighted graph or weighted cyclical digraph?
I'm looking for find the min-cut of a fully-connected directed graph (with cycles), or an undirected graph.

Karger's works but is not guaranteed to produce the correct solution. Is there a guaranteed algorithm?

I came across max-flow algorithms. Do these only work if the graph is acyclic?

Thanks.

# Answer
> 3 votes
**Directed graphs:** Use any max-flow algorithm together with the max-flow min-cut theorem. There are any number of algorithms for max-flow in an arbitrary directed graph. This is bog-standard stuff that should be covered in any algorithms textbook. See also minimum cut.

**Undirected graphs:** Use a min-cut algorithm for undirected graphs, e.g., Karger's algorithm or this lecture. I don't know what you mean by "it is not guaranteed to provide a solution"; the probability that it fails to find a solution is exponentially small, e.g., you can make this probability smaller than the chance that a cosmic ray hits your computer, makes it compute the wrong answer, and then you get struck by lightning and die anyway. Tough luck about that lightning, by the way.

Next time do more research before asking.

---
Tags: graphs
---


# Question
Title: Is it possible for an NP problem to be reduced to an EXPTIME problem in polynomial time?
And if so would this grant us any insight into the relations between P, NP, and EXPTIME?

# Answer
> 4 votes
We already know that **NP** is included in **EXPTIME**. So every **NP** problem can not only be reduced to an **EXPTIME** problem: it *is* an **EXPTIME** problem!

# Answer
> 2 votes
Any problem having an EXPTIME algorithm can be reduced to an EXPTIME problem, namely the problem itself (the reduction maps the input to itself). Every problem in NP has an EXPTIME algorithm, so every problem in NP can be reduced to some EXPTIME problem in polynomial time.

---
Tags: complexity-classes
---


title: make Magic Square?

text:
# Question
Title: make Magic Square?
I need to write a function that takes in a 2D list, that is a NEARLY magic square, meaning that if you perform ONE swap, it becomes a magic square. The function would take in this nearly magic square, and would return the magic square after the values have been swapped.

I wrote an "isMagic" function already that loops through the sums of the columns and rows, but am having difficulty reasoning through this MAKEMAGICSQUARE function.

So I know that makeMagic(\[\[4,9,1\],\[3,5,7\],\[8,2,6\]\]) would return \[\[4,9,2\],\[3,5,7\],\[8,1,6\]\].

Also, IMPORTANT REFERENCE http://en.wikipedia.org/wiki/Magic\_square.

# Answer
> 3 votes
Hint: There will be two rows with wrong sums and two columns with wrong sums.

# Answer
> 1 votes
You could try all possibilities for that one swap, and check if the result is a magic square. There are only polynomially many of them.

(Yes, there are faster solutions, but you didn't specify efficiency as a requirement.)

---
Tags: loops
---


# Question
Title: The number of executions of the count statement; how many?
How many times does the statement count in line 5 executes in terms of $n$?

```
1.  count=0;
2.  for (i=1; i<=n; i++) {
3.  for (j=1; j<=n; j*=2) {
4.  for (k=1; k<=j; k++) {
5.        count = count + 1;
6.      }
7.    }
8.  }

```

For the loop in line 3, we can list the numbers for $j$ as, $2^0,2^1,...,2^{\log n}$ Therefore, we can refer to the iterations of the exponents as $r$. Doing so would lead to the summations below for counting the number of executions.

$\sum\_{i=1}^{n}\sum\_{r=0}^{\log n}\sum\_{k=1}^{j}1 =\sum\_{i=1}^{n}\sum\_{r=0}^{\log n}j $

I am stuck here, because $\sum\_{r=0}^{\log n}$ depends on $j$ but I am not sure how to incorporate them.

Thanks in advance.

# Answer
> 4 votes
Hint: Substitute $j = 2^r$, and use the formula for summing a geometric series.

Make sure that you understand why the substitution $j = 2^r$ makes sense.

---
Tags: algorithms, algorithm-analysis, time-complexity, runtime-analysis
---