# Question
Title: Path cover with paths of bounded length, in the plane
I have a weighted, undirected, Euclidean complete graph $G$, a special vertex $r$, and an upper bound $b$. I want to find a minimum-cost path cover that covers all vertices of $G$, subject to the restriction that every path must have length at most $b$ and every path must start at the vertex $r$. In other words, I want to minimize the sum of the lengths of the paths, subject to the requirement that the paths cover every vertex at least once and each path starts at $r$ and has bounded length.

Are there any algorithms for this problem that will be effective on medium-size graphs (with, say, at most 200 vertices)? This problem smells likely to be NP-hard; if so, are there exact algorithms that are more efficient than naive exhaustive search or heuristics that are likely to work well in practice?

Recall that the length of a path is the sum of the lengths of the edges it contains. Also, a path cover is a collection of paths such that every vertex belongs to at least one path. A Euclidean complete graph is a graph where each vertex represents a point in the plane, there is an edge between every pair of vertices, and the length of that edge whose length is given by the Euclidean distance between those two points. (It follows that, without loss of generality, we can assume no two paths have any vertex in common other than $r$.)

This question is motivated by Location Selection Algorithm in Solar Engineering.

# Answer
This smells like a problem that might be NP-hard, so you'll probably have to use one of the standard methods for dealing with intractability: e.g., devise a heuristic, or formulate it so you can apply an existing solver.

I suggest that you try formulating it as a mixed integer linear programming (ILP) problem, and if that's too slow, try simulated annealing. I'll sketch both approaches.

### Integer programming

We'll think of our task as selecting a subset of the edges, so that they can be pieced together into paths as required. Introduce a zero-or-one variable for each edge to indicate whether or not it is selected. In other words, for each pair of vertices $i,j$, introduce a zero-or-one variable $x\_{i,j}$, with the intended meaning that $x\_{i,j}=1$ implies the edge $(i,j$) is included.

We'll add a bunch of inequalities that capture the requirement that the selected edges form a bunch of paths of the desired form:

* Each vertex (other than $r$) has exactly one edge out of it: $\sum\_j x\_{i,j} = 1$ for each $i \ne r$.
* Each vertex (other than $r$) has at most one edge into it: $\sum\_i x\_{i,j} \le 1$ for each $j \ne r$.
* $r$ has no edges coming out of it: $x\_{r,j} = 0$ for all $j$.
* For each vertex $i$ introduce a variable $y\_i$ (not restricted to integer values), with the intended meaning that $y\_i$ captures the distance from $r$ to $i$ along the harness that connects the two. We'll require that no harness is longer than the limit: $y\_i \le b$ for all $i$. Also $y\_r = 0$.
* Finally, we'll ensure the consistency of the $x$'s and $y$'s by adding

$$y\_i \ge y\_j + \ell(i,j) - (b + \ell(i,j)) (1-x\_{i,j})$$

for all $i,j$, where $\ell(i,j)$ is the length of the edge $(i,j)$. (Notice how this works: if edge $(i,j)$ is not selected, i.e., $x\_{i,j}=0$, this inequality implies only $y\_i \ge 0$; but if edge $(i,j)$ *is* selected, this inequality ensures that $i$'s distance from $r$ is $j$'s distance from $r$ plus the length of the edge between $i$ and $j$.)

Now ask an ILP solver to minimize the objective function $\sum\_{i,j} \ell(i,j) x\_{i,j} $, subject to these inequalities. The solution will correspond the optimal solution to the original problem.

You'll have to test to see whether existing off-the-shelf ILP solvers (e.g., CPLEX) are able to solve this ILP instance efficiently. You end up with an ILP instance with about $|V|^2$ variables and inequalities. If it takes too long, some solvers will have an option to specify a "timeout", so they give you the best solution they've found so far within the specified time, even if it isn't necessarily the globally optimal solution.

Some minor optimizations are possible. For instance, we can omit any edge $(i,j)$ whose length exceeds $b$ (eliminating the variable $x\_{i,j}$ from the linear program, as it is forced to be zero). Also, for any pair of edges $(i,j),(k,l)$ that "cross" (i.e., their line segments intersect), we know they can't both be simultaneously selected, i.e., we can add the inequality $x\_{i,j}+x\_{k,l}\le 1$. You probably don't want to add all such inequalities, but you could try adding a small number (e.g., for all pairs of short edges). You can also add the inequality $y\_i \ge \ell(r,i)$ for all $i$, in case that helps the solver.

This approach is also fairly flexible: for instance, we can limit the number of paths that are allowed to be used (by adding an inequality to upper-bound $\sum\_i x\_{i,r}$) or make other minor adjustments. You can limit the number of edges allowed in each path by adding variables $z\_i$ that count the number of hops between $i$ and $r$ along the harness connecting the two, and adding the inequality $z\_i \ge z\_j + 1 - K (1-x\_{i,j})$ where $K$ is a suitably large constant (larger than the maximum number of edges per path) and then adding inequalities to upper-bound all of the $z\_i$'s.

### Simulated annealing

Another option is to use some form of local search, such as simulated annealing. The idea is that we start from a candidate solution and at each step try making a small, randomly selected, local change and check whether it is an improvement or not.

Part of the art of simulated annealing is to choose a set of allowable changes; at each step, you'll randomly select from this set to obtain your candidate change. In this case, one reasonable class of "changes" is: Pick a pair of vertices (probably ones that aren't too far apart), and swap which paths they are in. For example, suppose I've selected vertex $b$ and vertex $e$, where the path containing $b$ looks like $\cdots \to a \to b \to c \to \cdots$ and the path containing $e$ looks like $\cdots \to d \to e \to f \to \cdots$. Then after the swap operation you'll end up with the two paths $\cdots \to a \to e \to c \to \cdots$ and $\cdots \to d \to b \to f \to \cdots$. You can then evaluate whether this increased or decreased the objective function. You might want to experiment with the distribution on pairs of vertices (do you try to make nearby vertices more likely to be selected than far-apart ones?).

There may be other operations that would be useful to add and make simulated annealing work better. Selecting an appropriate set of operations and choosing the parameters for simulated annealing is largely an art, and may require some experimentation. It's hard to predict how well this will work without trying it.
> 1 votes

---
Tags: algorithms, graphs, heuristics, weighted-graphs, set-cover
---


# Question
Title: Location Selection Algorithm in Solar Engineering
This is a practical problem in energy generation with heliostats.

We have a number of heliostats basically forming the shape of a doughnut. The facility needs to deploy hubs on those heliostats. One hub can support 12 harnesses (a kind of cable) and one harness can support 16 heliostats; namely, one hub can support 192 heliostats. The cost of deploying a hub and harness per meter are given. In other words, every harness starts from a hub and can connecting at most 16 heliostats. Deployment of a hub results in a cost. Also, the cost of harnesses result from its distance from the hub to the furthest heliostat on this harness. However, there is no distance from heliostats to its connecting harness.

Currently my approach is to use k-means to cluster the whole region and run greedy on distance from harness for each split region, though I do not think this is a good approach.

This is a pattern generated by my algorithm. As you can see, some harness only support 1 or 2 heliostats and result in a waste of harness.

Our job is to optimize the cost. In the end, the algorithm should return locations of hubs, harness topology patterns, and the total cost.

Can anyone enlighten me potential algorithms on this?

(Every point on the image is a heliostat, there are 40981 in total)

----------- Updated 14/12/2016 -----------

More details on the question, thanks D.W's suggestion:

1. Coordinates of heliostats are given. These coordinates correspond to real-world metrics (meters).
2. The placement of hubs are not constrained. However, one harness cannot be longer than 45 meters due to voltage requirement.

----------- Updated 15/12/2016 -----------

1. The classification on "furthest" in "the cost of harnesses result from its distance from the hub to the furthest heliostat on this harness": Furthest is in the sense of "last", not "furthest" in the sense of "having the largest Euclidean distance from the hub"

# Answer
> 2 votes
The problem looks messy, so there probably isn't a clean algorithm to produce a globally optimal solution. Instead, I suggest you use some combination of heuristics to try to find a nearly-optimal solution in a reasonable amount of time, perhaps by iteratively making small incremental improvements.

Any candidate solution is comprised of three elements:

* Location of the hubs.
* Assignment of each heliostat to a hub.
* Routing of the harnesses.

One way to make an incremental improvement is to repeatedly fix two of these three and optimize the other (holding the other two fixed), and rotate through which one you change. You seem to have a reasonable strategy to obtain an initial candidate solution, and you could iterate from there. I'll sketch in more detail each of these three optimizations, which you could rotate through repeatedly until you cannot make any further improvement:

**Harness optimization.** Hold the location of the hubs and the assignment of which hub each heliostat is associated with fixed (to be the same as in the current candidate solution). The goal is optimize the routing of the harness wiring. For candidate algorithms for that, see the other question. My suspicion is that this step is the one where there are the greatest opportunities for improving your solution, and where it's worth devoting the most effort to.

**Hub location optimization.** Hold the heliostat-to-hub assignments and harness routing fixed. Pick a single hub and the heliostats associated with it. Then it's easy to fine-tune the location of the hub to minimize overall cost, under the assumption that you don't change the topology/routing of the harnesses.

In particular, each harness contributes one edge from the hub $r$ to the heliostats $h\_1,h\_2,\dots,h\_{12}$ it is immediately connected to. Now we want to find a location for $r$ that minimizes the sum of distances $d(r,h\_1)+\dots + d(r,h\_{12})$. This is a sum-of-squares problem so it can be solved through standard sum-of-squares optimization, or simply by solving it with gradient descent; since we're in only 2 dimensions I would expect any method to converge rapidly. You can do this separately for each hub.

It would also be possible to try a random perturbation to the location of the hub, re-apply harness optimization, see whether this reduced the overall cost, and if so accept that change to the hub location. This might be more expensive than it is worth.

**Heliostat assignment to hubs.** Hold the location of hubs fixed, and assume we're not going to make radical changes to the harness topology. We can try to fine-tune the assignment of heliostats to hubs in a number of ways.

One approach is to pick a heliostat $h$ that is currently assigned to hub $r\_1$ but is relatively close to another heliostat that's wired to a different hub $r\_2$, try swapping which hub it is associated with, and see if this leads to any reduction in cost. To determine whether it leads to a reduction in cost you could re-run harness optimization from scratch in both cases (which might be slow). Or, as a fast heuristic, you could remove $h$ from its current harness, find the nearest heliostat $h'$ that's currently connected to $r\_2$, attach $h$ to $h'$ (splicing it into the harness for $h'$), and see whether this reduces the cost.

Another approach would be to do a more ambitious optimization. Pick a pair of hubs $r\_1,r\_2$ and the set of heliostats currently connected to either of them. Now try to apply joint harness optimization to that set of heliostats and those two hubs simultaneously, simultaneously optimizing the routing of the heliostats and also which hub each heliostat is connected. The methods in that other question can be generalized to solve this problem. When finding the solution we may find that one or two heliostats switch which hub they are connected to. Now repeat this for every pair of adjacent hubs. However, my guess is that heliostat assignment might not yield many gains (compared to the naive method of assigning each heliostat to the hub it is closest to), so it might not be worth implementing these more sophisticated methods for heliostat assignment.

**Overall algorithm.** In summary, we start from some initial solution (e.g., selected using the method described in the question) and then repeatedly rotate through the following three operations:

* Harness optimization: fine-tune the routing of the harnesses.
* Hub location optimization: fine-tune the location of the hubs.
* Heliostat re-assignment: fune-tune the assignment of heliostats to hubs.

There is no guarantee that this will lead to a global optimum, i.e., the absolute lowest cost possible. This could get stuck in a local minimum. There are various methods for dealing with that (e.g., applying random perturbations; re-starting from multiple randomly chosen initial solutions), which you could experiment with as well.

Hopefully this will help you find a solution that is "good enough", or at least, get you started on some methods to try. Good luck!

---
Tags: algorithms, graphs, optimization
---


# Question
Title: Data-flow analysis problem adjust to Ullman-Aho's framework?
I am reading the classical book "Compilers. Principles, techniques and tools" by Aho et alii. On chapter 9.3 they talk about a general framework to solve data-flow analysis problems that use a framework which is monotone and of finite height.

The technique is shown to be useful for live variable and reaching definition analysis and I'm wondering if it is applicable to the following problems:

1. Checking if variables are always initialized.
2. Do range computations (the idea is to apply it on out of bounds array accesses check).
3. Eliminate common subexpressions.

My question is if this same framework can be used for this problem or I need more general frameworks such as the constant propagation framework described in chapter 9.4.

If the answer is yes what are the values of the framework defined as $(D,F,V,\land)$, where D is the direction of the analysis, F the family of transfer functions, V is the semilattice domain and $\land$ the semilattice operator? If the answer is no for some of the problems I don't really need this parameters for the more general framework but the reason why it doesn't work would suffice so that I can find a more general framework.

I ask this just in case somebody already know the answer and I can save me some time so don't worry about being too specific.

# Answer
**Checking initialization:** Yes, you can use this framework. You need only a single boolean for each variable. The lattice is $V\to \\{\bot,\top\\}$, i.e., $2^V$, where $V$ is the set of variables. The height of this lattice is $n+1$ where $n=|V|$ is the number of variables. The transfer functions are monotonic. Consequently, you can use the framework.

**Range computation:** No. The lattice of ranges has infinite height. Consider, e.g., the sequence of ranges $\[0,0\]$, $\[0,1\]$, $\[0,2\]$, $\[0,3\]$, and so on: it never ends. Consequently, you need something more, such as widening operators.

**Common subexpressions:** I don't know of any nice way to express this in that framework (though there could always be something I'm not aware of).
> 3 votes

---
Tags: compilers, lattices, data-flow-analysis
---


# Question
Title: Finding the longest repeating subsequence
Given a string $s$, I would like to find the longest repeating (at least twice) subsequence. That is, I would like to find a string $w$ which is a subsequence (doesn't have to be a contiguous) of $s$ such that $w=w' \cdot w' $. That is, $w$ is a string whose halves appear twice in a row. Note that $w$ is a subsequence of $s$, but not necessarily a substring.

Examples:

For 'ababccabdc' it will be 'abcabc', because 'abc'='abc' and 'abc' appears (at least) twice in 'ababccabdc'.

For 'addbacddabcd' one option is 'dddd' because 'dd' appears twice (I cannot use the same letter several times, but here i have 4 'd's so its ok), but its of lebngth 4. I can find a better one of length 8: 'abcdabcd', because 'abcd' is a substring of 'addbacddabcd' that appears twice.

I'm interested in finding the longest repeating subsequence. This is also called "finding the longest/largest square", but I've read many articles in which a square is defined for a substring and not for a subsequence.

I can easily use a brute force algorithm that will take $O(n^3)$ by iterating on all options for a breakpoint in the string, and then I will have two strings in which I'll be looking for largest/longest common subsequence, but each check will take $O(n^2)$ using a dynamic programming technique, so the entire time will be $O(n^3)$. I found a more efficient algorithm for longest common subsequence which takes $O(\frac{n^2}{\log n})$ , so the running time will be $O(\frac{n^3}{\log n})$.

I am looking for a more efficient algorithm for longest repeating subsequence problem. Perhaps my idea of iterating over all breakpoints wastes too much time, and can be reduced to less iterations. Or perhaps an algorithm with a different attitude can solve this problem.

I've searched in many journals and previous questions, and most of the results I found were about a substring and not about a subsequence.

I've also read that this can be done using suffix trees, but this too was relevant to substrings and I am not sure if such an idea can be extended for subsequence.

I'm looking for a solution that runs in time $O(n^2)$. If there exists one in time $O(n \cdot \log n)$ that will be even better (I am not sure if such exists).

# Answer
Here is a dynamic programming solution.

Suppose that the input string is $x\_1\ldots x\_n$. Create a table $T$ whose rows and columns are indexed by $0,\ldots,n$ (where $n$ is the length of the string), populated by the rule $$ T\[i,j\] = \begin{cases} 0 & \text{if $i = 0$ or $j = 0$}, \\ T\[i-1,j-1\] + 1 & \text{if $x\_i = x\_j$ and $i \neq j$}, \\ \max(T\[i-1,j\],T\[i,j-1\]) & \text{otherwise}. \end{cases} $$ The answer is $T\[n,n\]$.
> -2 votes

---
Tags: algorithms, optimization, dynamic-programming, strings, subsequences
---


# Question
Title: Is there such a thing as an algorithm that runs in asymptotic time?
For example: $O(-e^{-x} +1)$. Basically as the size of the input increases, the time it takes to run converges.

# Answer
> 3 votes
It is not hard to see that $O(-e^{-x} +1) = O(1)$.

---
Tags: algorithms, asymptotics
---


# Question
Title: How is the R-Tree's MBR size determined? Changes to MBR?
The R-Tree creates 'rectangles' to index 2D data. How is their size calculated exactly? What happens to the performance by changing this parameter i.e. the size of this rectangle/MBR? Number of overlaps, area covered change but can this speed up some kind of queries or build a smaller index?

# Answer
> 2 votes
First of all, let us have some background. There are variants of Guttman's r-tree that have different splitting heuristics (e.g. Sellis' r+-tree, which involves inserting an item multiple times into a tree; and Beckmann's r\*-tree, which takes into account area, margin, overlap). Also, there are variants that are more suitable for higher dimensions (e.g. Berchtold's x-tree, which uses split history and supernodes). You can improve any of the above structures using bulk loading, which can guarantee zero overlap between rectangles at the same level.

Rectangles used typically are minimum bounding rectangles (MBR's) that may fit your data well (if you are using orthonormal rectangles as with data mining), or may have to be used as approximations (if you are trying to detect intersections between polytopes).

You can find MBR's, which are possibly described using upper-left point and lower-right point, by taking extreme value pairs for each dimension.

Note also that points are degenerate rectangles and that we can form MBR's for collections of MBR's.

For example, if we had $P$ = $\\{(1, 0), (2, 1), (3, 2), (4, 3)\\}$, and right is large $x$ and up is large $y$, an MBR for these points could be $(p\_\text{upper-left}, p\_\text{lower-right})$ = $((1, 3), (4, 0))$.

There have been attempts to quantify how much time a query on an r-tree takes, but intuitively what is happening is that we may spend more than $O(k \cdot \log(n))$ time for $k$ matches, even though depth is $O(\log(n))$, because we could go down many branches without reaching a match. If you are interested, there are certain operations one could perform on an r-tree that take more time but have clean running time asymptotic values if you include a "look-ahead" query at each node we visit. In the end, however, with a regular r-tree and with regular queries, loosening the MBR's leads to diminished performance.

---
Tags: database-theory, databases
---


# Question
Title: All Pairs Shortest Path vs Shortest Path
I do not understand the difference between the All Pairs Shortest Path problem (solved by the Floyd–Warshall algorithm) and the Shortest Path problem (solved by Dijkstra's algorithm).

# Answer
All-pairs shortest paths using Floyd-Warshall leads to determination of a value for all pairs of nodes that describes shortest distance of any path that exists between those two nodes. Note that sometimes, two nodes will have no path between them. Also, the graph that we apply the algorithm to may be directed, so one node may have a distance to a second node, but the reverse is not true. It classically takes $O(|V| ^ 3)$ time.

Dijkstra's algorithm solves the single-source shortest paths problem. It classically takes $O(|E| + |V| \cdot \log(|V|))$ time. Note that for dense graphs, $|E|$ = $O(|V| ^ 2)$, so we could say that Dijkstra's is $O(|V|)$ times faster than Floyd-Warshall.
> 2 votes

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


# Question
Title: Computing all possible partial sum-function of a given set of numbers
Let there be $N$ positive numbers given as $\lambda\_1\geq\dots\geq\lambda\_N$. Now I am interested in the following numbers given as $$\alpha\_i=\exp(\frac{\lambda\_i}{\lambda})$$ for some positive constant $\lambda$. Define the function $\mathcal{S}(..)$ which takes a subset of these numbers (let me call me them as a sequence) and calculate their products. For example$$\mathcal{S}(\alpha\_1,\alpha\_2)=\alpha\_1\alpha\_2$$Also note that $$S(\alpha\_1,\alpha\_2,\alpha\_3)=S(\alpha\_1,\alpha\_2)S(\alpha\_3)$$Also $$\mathcal{S}(\alpha\_1,\alpha\_3,\alpha\_4)={\mathcal{S}(\alpha\_1,\alpha\_2,\alpha\_3,\alpha\_4) \over \mathcal{S}(\alpha\_2)}$$ and so on. For given $K$ and $N$, we have $NC\_K$ possible subsequences of $\alpha\_i$'s. Is there a really efficient way of computing $\mathcal{S}(.)$ for all such sequences.

# Answer
There are ${N \choose K}$ subsequences of length $K$, so outputting $\mathcal{S}(\cdot)$ for all of them will certainly require an output of length at least ${N \choose K}$. Thus, the running time has to be at least ${N \choose K}$. Beware that this is potentially exponential in $N$, depending on the value of $K$, so for some choices of $N,K$ there is no hope for an efficient algorithm to compute all those values.

You can list all those values in approximately ${N \choose K}$ time. Take any algorithm for enumerating all $K$-size subsets of $\\{1,2,\dots,N\\}$; then it is easy to turn it into an algorithm to do what you want, by keeping track of the product associated with each subset. Note that when you add an element to a subset, with a single multiplication you can update the product (compute the product of the new subset, based on the product of the old subset multiplied by the new element that was added).
> 1 votes

---
Tags: algorithms
---


# Question
Title: Use of Activation Units in Facial Expression Understanding
The topic of extracting the Facial Action Coding System (FACS) Action Units (AUs) \[1\] from images and it's translation into emotion prediction \[2\] is pretty well studied, but I'm not clear on how it stacks up against alternative approaches such as Convolutional Neural Networks (CNN). How much does the accuracy of AUs effect the accuracy of emotion detection?

---

1. "Joint Facial Action Unit Detection and Feature Fusion: A Multi-conditional Learning Approach", Eleftheriadis S, Rudovic O, Pantic M. (2016)
2. "Emotion Detection From Facial Expression And Its Use In The Evaluation Of Stress" Suvashis Das (2013)

# Answer
As a preliminary answer, I can't imagine the extraction of AUs affecting their ability to detect emotions, since according to Do Deep Neural Networks Learn Facial Action Units When Doing Expression Recognition?, CNNs trained to extract emotions already correspond to AUs (called FAUs in the paper), as shown in the table below taken from their paper:

Additionally, this is a very basic CNN with only three convolutional layers and grayscaled inputs. Given a larger CNN using Inception-layers and residual connections, more specialisation would probably be seen.

However, this conclusion also makes me feel like I'm dismissing a whole area of research, so it's probably a little hasty.
> 2 votes

---
Tags: algorithms, reference-request, neural-networks, computer-vision, features
---


# Question
Title: How do we know that the reduction is correct?
I'm having a really difficult time understanding the logic behind reduction of the halting problems to other problems in order to prove them undecidable.

Here's my reasoning:

Let's say that we want to find out if the following problem is decidable: given any machine $M$ and a string $y$ find out whether the machine $M$ ever writes an $@$ symbol on the tape.

So, I intuitively think that this is an undecidable problem and I try to reduce the halting problem to our problem.

1. Let's have an arbitrary machine $N$ and a string $x$. If $N\\#x \in HP$ then $N$ halts on input $x$ else if $N\\#x \not\in HP$ then $N$ loops on input $x$ where $HP = \\{ M\\#x\ |\ M\ \text{halts on}\ x\\}$.

Here's my first question: how do we know if $N\\#x$ belongs to $HP$ or not? I thought that we cannot tell and that's the whole idea behind the halting problem.
2. Now we typically construct a machine $M'$ which has $N\\#x$ hardcoded inside and which output doesn't depend on its input. Here's how $M'$ works:

1. Erase the input.
    2. Run $N$ on $x$.
    3. If $N$ halts on $x$ then have $M'$ write $@$ to the tape. Otherwise, if $N$ loops on $x$ then have $M'$ make sure $@$ is not written on the tape.

From what I understand, the proof is over as the behaviour of $M'$ is similar to $HP$ (*I am not sure if this is the correct way to formulate this*) and since the halting problem is undecidable then our problem is undecidable as well.

Here comes my second question: why does it prove anything? It looks like any problem could be treated this way leading us to the conclusion that everything is undecidable as we were able to incorporate the halting problem in our algorithm. How do I know that there is no way to avoid an undecidable problem in my algorithm? I feel like we're showing that *we can use the halting problem to solve my problem* instead of showing that *solving my problem would result in solving the halting problem as well*.

I'm sorry if my explanation is a little bit vague – I've already consulted my professor, read related chapters in Automata and Computability by Kozen and tried to read tutorials and presentations on the Internet but I still cannot understand the logic behind the reduction. I'd be grateful if someone could explain my misunderstanding.

# Answer
Your first question is easy to answer: you are confusing "we know" with "it is the case". It can happen that something is the case but we do not know it. In particular, it is the case that $M\\#x$ halts or it does not halt, but we do not know which. It will rain a year from now or not, but we do not know which.

To answer the second question, let us see what goes wrong if we try to reduce the Halting Problem to a decidable problem. Consider the problem:

> Given a single-tape Turing machine $M$ and input $x$, decide whether $M\\#x$ halts in fewer than $\mathrm{length}(x)$ steps.

Now we need to come up with a reduction, i.e., given any machine $M$ and input $x$, we must produce a machine $M'$ and input $x'$, such that $$\text{$M$ halts on $x$} \iff \text{$M'\\#x'$ halts in fewer than $\mathrm{length}(x')$ steps}$$ Here is an idea: let $x'$ be the pair $(x, 0^k)$ where $0^k$ is a a string of $k$ zeroes, where we are going to determine $k$ later (this trick is know as "padding the input"). The machine $M'$ takes this input $(x, 0^k)$, ignores $0^k$ and just does whatever $M\\#x$ would do. Now, for this reduction to work, we just need $k$ such that $$\text{$M\\#x$ halts} \iff \text{$M'\\#(x,0^k)$ takes fewer than $\mathrm{length}(x,0^k)$ steps of execution}$$ Such a $k$ exists because $M\\#x$ halts if, and only if, $M'\\#(x,0^k)$ halts. So there are two cases:

1. If $M\\#x$ halts then so does $M'\\#(x,0^k)$ in some number of steps, say $m$, and we can take $k = m + 1$.
2. If $M\\#x$ does not halt then we can take any $k$.

There is a small technical issue: the number $m$ should not depend on $k$. We can arrange this in several ways. One possibility is to allow $M'$ to have an extra symbol which it uses as "ignore input from here onwards". In any case, this is not essential for the discussion at hand.

Can you spot the problem? A reduction needs to be *computable*, that is, we need a computable procedure which generates $M'$ and $x'$ from $M$ and $x$. We have not given a procedure for computing $k$, even though such a $k$ exists. Perhaps if we think harder we can come up with the required procedure for computing $k$. Or perhaps it does not exist, and our attempt is not worth anything. We just do not know.

So, this is one way in which an attempt at a reduction may fail. It is in fact typical: if we are allowed to use non-computable reductions, then we can reduce any problem to any other non-trivial problem. I leave it as an exercise. (Here "non-trivial" means that the problem has an instance where the answer is "yes" and an instance where the answer is "no".)
> 1 votes

---
Tags: computability, reductions, undecidability, proof-techniques, halting-problem
---


# Question
Title: What algorithm to find end state probabilities
I need help identifying what algorithm I need to solve a problem. I'm not asking for programming help here, just identifying the algorithm.

Each row of a matrix represents a state. Each element corresponds to the count of how often the current state transitions to another state. Some states are final states and do not transition at all. Some states are not reachable. There is always at least one path to one of the final states.

I need to calculate the probability of reaching all of the reachable final states and the probability for each final state.

---

To make this explicit here is an example of what I'm trying to accomplish.

State matrix: $$ \begin{bmatrix} 0& 1& 0& 0& 0& 1 \\ 4& 0& 3& 2& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \end{bmatrix} $$

* First state is always 0.
* State 1 is non-terminal.
* State 2 has probability of 0.
* State 3 has probability of 3/14.
* State 4 has probability of 2/14 or 1/7.
* State 5 has probability of 9/14.

If this is a stationary distribution, then that's what I need to code to solve the problem. If not is it something else.

# Answer
> 4 votes
Take your matrix, and normalize the rows to sum to 1. Denote the result by $A$; in your example, $$ A = \begin{bmatrix} 0& 1/2& 0& 0& 0& 1/2 \\ 4/9& 0& 1/3& 2/9& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \\ 0& 0& 0& 0& 0& 0 \end{bmatrix} $$ Let $v$ be a row vector with $v\_0 = 1$ and $v\_i = 0$ otherwise. In your example, $$ v = \begin{bmatrix} 1&0&0&0&0&0 \end{bmatrix} $$ Then $vA^t$ gives the probabilities of being in each state after $t$ steps, and so $w := v \sum\_{t=0}^\infty A^t$ gives the expected number of times in each state. Since a final state terminates the process, for each final state $i$, $w\_i$ is in fact the probability of the process ending at $i$. The vector $w$ can be calculated using the formula $$ w = v (I-A)^{-1}. $$ In your case, we get $$ w = \begin{bmatrix} 9/7 & 9/14 & 3/14 & 1/7 & 0 & 9/14 \end{bmatrix} $$ In particular, the probabilities of terminating at the final states $2,3,4,5$ are (respectively) $3/14,1/7,0,9/14$.

Regarding algorithms, we can rephrase the problem as follows: given $v,A$, find the vector $w$ such that $$ w(I-A) = v. $$ This requires solving a system of linear equations, for which there are many algorithms.

---
Tags: algorithms
---


# Question
Title: Running time of greedy scheduling algorithm
Here is an algorithm to output a subset of activities S such that no activities in S overlap and profit(S) is maximum.

Define $p\[i\]$ to be the largest index $j$ such that $a\_j$ does not overlap $a\_i$.

$\\#$ Return maximum possible profit from $a\_1,...,a\_n$

```
def rec_opt(n):
    if n == 0:
        return 0
    else:
        return max(rec_opt(n-1), w_n + rec_opt(p[n]))

```

It doesn't mention what $w\_n$ is in the slide, but I think it is the profit of the activity $a\_n$.

> Consider a set of $n$ activities where there is no overlap at all. Then $T(n) = 2T(n − 1) + c$. This recurrence has an exponential closed-form, $O(2^n)$.

* "return max(rec\_opt(n-1), w\_n + rec\_opt(p\[n\]))": I think this line takes time $2T(n-1)$.
* "if n == 0": this line takes time $c$.

Am I correct?

One more question, how can we get $O(2^n)$ from $T(n) = 2T(n − 1) + c$?

# Answer
> 1 votes
You are asking several questions. I will only answer the second one.

Suppose that $T(n) = 2T(n-1) + c$, and that $T(0) = a$. Define $S(n) = T(n) + c$. Then $S(n) = T(n)+c = 2T(n-1)+2c = 2S(n-1)$, and so $S(n) = 2^nS(0) = 2^n(a+c)$. We conclude that $T(n) = 2^n(a+c)-c = 2^na+(2^n-1)c$.

---
Tags: runtime-analysis, recursion, greedy-algorithms
---


# Question
Title: Dynamic algorithm: what's the difference between memorization and bottom-up algorithm?
Here are two ways to output a subset of activities S such that no activities in S overlap and profit(S) is maximum.

I can't see what's the difference between these two algorithms except the first one use a if statement and the second one use a for loop. They both store result in OPT\[n\] first.

# Answer
> 5 votes
The algorithms are indeed very similar, but there are several differences:

1. **Order of evaluation:** The bottom-up algorithm specifies a particular order of evaluation, which ensures that when `OPT[i]` is due to be computed, all the prerequisites have already been computed. In the memoization algorithm, this is taken care of automatically.
2. **Evaluated entries:** The bottom-up algorithm evaluates all entries of `OPT`, even though only `OPT[n]` is needed. The memoization algorithm only computes the entries that are necessary for computing `OPT[n]`.

Two other differences, which are not encountered in this example:

1. **Indexing:** The bottom-up algorithm stores its entries in a simple array. The memoization algorithm, in more general instances, uses an association array (i.e., dictionary or hash table).
2. **Memory term:** The memoization algorithm remembers all entries which have been computed. A smart bottom-up algorithm could "forget" some of them.

Summarizing, the memoization algorithm is simpler to program. In terms of efficiency, the memoization algorithm has the advantage that only the necessary entries are calculated. In other instances, however, a lot can be saved by implementing a dedicated algorithm, in terms of indexing cost and, especially, memory usage.

---
Tags: dynamic-programming
---


# Question
Title: Converting any computable function into a sequence of additions
Not sure if this question should be here, or on math.se.

That said, let me proceed:

On the Wikipedia page for the Ackermann function, it is mentioned that by passing the inputs of 0, 1 and 2 to the third parameter one could perform the three fundamental operations of addition, multiplication and exponentiation, respectively, on the other two parameters.
That is, addition, multiplication and exponentiation are the three fundamental operations.

But multiplication is merely repeated addition, and exponentiation repeated multiplication. So addition is the fundamental operation?

My question is this:

> Does there exist an algorithm to convert any sequence of (computable) mathematical operations, into another sequence of computable operations involving only addition.

# Answer
I don't quite see the connection between the preamble and the question.

Regarding the three fundamental operations, this is of course an arbitrary selection. On one hand, you could say that the most fundamental operation is the unary successor function $x \mapsto x+1$. On the other hand, you have hyperoperations, some of them occurring naturally in Ramsey theory and combinatorial pseudorandomness.

Regarding your actual question, the answer is plainly no. No finite sequence of addition operations can compute the function $(x,y) \mapsto xy$, for example. Indeed, the output of any given sequence of additions on inputs $x,y$ is $O(x+y)$, which grows too slowly.

This is a special instance of a more general theorem about nested bounded iteration, which states that a function $f(n)$ can be computed using $m$ nested bounded loops iff it is recursive and eventually bounded by $A(n,m)$ (the binary Ackermann function). This is part of the circle of ideas around primitive recursive functions.
> 3 votes

---
Tags: algorithms, computability
---


# Question
Title: How can a probability distribution across classical states be computed for the measurement of a Quantum State represented by a Complex Vector?
Suppose I have a quantum state represented by a Complex vector, arbitrarily:

$\[~-0.538, 0.044 - 0.323i, 0.706, 0.044 + 0.323i~\]$

With each value in that vector corresponding to some classical state:

$\[~ |00\rangle, |01\rangle, |10\rangle, |11\rangle ~\]$

What is the correct mathematical formula to derive a probability distribution across possible classical states that could be observed in measurement from this complex vector?

E.g. how do I find individual real values for $p(|00\rangle)$, $p(|01\rangle)$ etc. in this example?

# Answer
> 2 votes
The quantum state is a vector $v$ of unit norm. The probability of measuring outcome $x$ is $\\|v\_x\\|^2$, the squared magnitude of the corresponding coefficient in the vector. Since $v$ has unit norm, these probabilities add up to $1$.

---
Tags: quantum-computing
---


# Question
Title: Algorithm to detect if word belongs to pushdown automaton
I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that.

My thought at first would be to go through all possible transitions, and check if we didn't match this word in accepting state, but got in problem with (epsilon, epsilon)/V where we can put V into stack without reading anything and getting from stack.

Is there any good algorithm which could work, or is this task impossible?

# Answer
> 4 votes
As adrianN notes in their comment, your task is certainly algorithmically possible. There are algorithms that take a PDA $A$ and outputs a context-free grammar $G$ such that $L(A) = L(G)$, and others (such as CYK) that take a context-free grammar $G$ and a word $x$ and determine whether $x \in L(G)$.

There might be shortcuts, but at least this shows that your problem is decidable. In fact, since both algorithms run in polynomial time, the problem belongs to $\mathsf{P}$.

Judging from the literature, it seems that this chain of reductions is the standard way of solving the *membership problem* for pushdown automata. See for example these notes from Hendrik Jan Hoogeboom and Joost Engelfriet.

---
Tags: algorithms, automata, search-algorithms, pushdown-automata
---


# Question
Title: Algorithm to get maximal selection set of a collection of sets with a binary relation
I have a finite collection of finite sets $\\{A\_i\\}\_{i \in I}$. There is a relation $R$ defined on the elements of those sets (which is not transitive, it is irreflexive, and it is symetric). Suppose we define a *related partial choice* as a set $\\{a\_j\\}\_{j\in J}$ such that:

1. $J\subseteq I$
2. $a\_j \in A\_j, \forall j \in J$
3. $a\_j R a\_{j'} \forall j,j' \in J$

That is, it consists of choosing one element for each of some of the original sets, such that all elements are related to each other.

What I need is an algorithm that a computes a *related partial choice* with maximum cardinality.

An equivalet way of seeing the problem would be as follows. Given the set $\\{A\_i\\}\_{i \in I}$, call a *related selection partial function* ($RSPF$, for short) any partial function $f : I \rightarrow \cup\_{i\in I} A\_i$ such that:

1. $f(i)\in A\_i$ for all $i \in I$ where $f$ is defined.
2. $f(i)Rf(i')$ for all $i,i' \in I$ where f is defined.

If we define $N := max(\\{ \\#Dom(f) : f \in RSPF\\})$. I need an algorithm to efficiently compute an $f$ such that $\\#Dom(f) = N$.

In the algorithm, the $\\{A\_i\\}\_{i \in I}$ sets can be arrays or sets.

Any Ideas?

# Answer
> 2 votes
Your problem generalizes MAX-CLIQUE, and as such its decision version is NP-complete. To see this, given a graph $G=(V,E)$, take $I=V$, $A\_i=V$, and $R=E$.

---
Tags: algorithms, sets, clique, finite-sets
---


title: Modification of Dijkstra's algorithm

text:
# Question
Title: Modification of Dijkstra's algorithm
How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality?

There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough road.
Taking this into account, if there are roads $p1$: the short distance with road quality $3$ and $p2$: the long distance with quality $1$, the longer path $p2$ is chosen due to easier road difficulty.

The quality of the road is more important than the distance. If there are roads of equal quality the shorter one is chosen.

# Answer
You seem to have chosen a strange metric, in that your wheelchair user apparently prefers travelling 1000km over concrete to even 1cm over gravel.

However, in general, the way to proceed is to combine your two metrics into a single metric in such a way that even the best possible score on the secondary metric can't make the algorithm prefer a path that does worse on the primary metric.

So, I'm going to assume that each edge $e$ has a quality $q\_e$ and a length $\ell\_e$. The quality will be a nonnegative integer; the length can be a nonnegative real (or integer – it doesn't matter). Because Dijkstra likes to minimize, I'll take $q=0$ to be the best possible quality (in the question, you take it to be the worst, but this makes no real difference).

Any path between two vertices can't possibly have length more than $L = \sum\_{e\in E} \ell\_e$. This means that, for any path of total length $\ell$, $\ell/(L+1)\<1$. We'll take the weight of the edge $e$ to be $w\_e = q\_e + \ell\_e/(L+1)$, and use these values $w\_e$ to run Disjkstra's algorithm. The point is that if a path has total quality $Q$, then it has total weight $W$ with $Q\leq W\<Q+1$. Therefore, the least-weight path is guaranteed to be one of the best quality paths (smallest $q$-values) and, among those, it's the one of least total length.
> 3 votes

# Answer
Well each edge could contain a pair of natural numbers. While constructing the shortest path you could consider the road quality first, then the distance if there are potential paths with the same road quality. I hope this helps people with wheelchairs navigate more easily!
> 1 votes

# Answer
Instead of considering some of the costs first you can actually define a function $\mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N}$ (or $\mathbb{R}$ if you're using real numbers) that converts a cost tuple $(a,b)$ to a scalar weights, then just apply Dijsktra with the scalar weights.
> 0 votes

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


# Question
Title: Description of lists with functions in LISP
I have been given the following implementation of basic list functions in LISP:

```
nil = (lambda (k) (k ’none ’none))
(cons x y) = (lambda (k) (k x y))
(car l) = (l (lambda (x y) x))
(cdr l) = (l (lambda (x y) y))
(null? l) = (l (lambda (x y) (= x ’none)))

```

As an intent to show that data can be constructed using only pure functions.

I don't understand very well this code. For starters, what's the role of k? Can you show how I can come up with this implementation? Basically, I'm looking for some intuition on how this works and if you can show in some manner how you deduce the implementation.

# Answer
In PL theory, this is known as (a variant of) the Church-encoding of pairs.

The idea is the following: assume for the moment you only have a language with primitive booleans (true, false, if-then-else) and primitive (first-class) functions. Pairs are not primitive, yet they can be encoded as follows.

In place of a pair $(x,y)$ we can consider the following function: $$ p(b) = {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y $$ It is immediate to verify that $p({\sf true}) = x$ and $p({\sf false}) = y$. So this function $p$ indeed encodes the information which lies inside a pair. Projections can then be defined as $$ \pi\_1(p) = p({\sf true}) \qquad \pi\_2(p) = p({\sf false}) $$ while the pair constructor becomes $$ cons(x,y) = \lambda b.\ {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y $$

Now, suppose we no longer have primitive booleans/conditional, but only have functions. We can still obtain something which behaves as a boolean through this encoding: $$ {\sf true} = \lambda x y. x \qquad {\sf false} = \lambda x y. y \qquad $$ and (since now a boolean $b$ is a "binary" function) $$ {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y = b x y $$ It is immediate to verify that $$ {\sf if}\ {\sf true} \ {\sf then}\ x \ {\sf else}\ y = {\sf true} x y = x $$ and the $\sf false$ analogous.

Once you combine both encodings, you get that $$ \begin{array}{l} cons(x,y) \\ = \lambda b.\ {\sf if}\ b \ {\sf then}\ x \ {\sf else}\ y \\ = \lambda b. b x y \\ \end{array} $$ and $$ {\sf car} = \pi\_1 = \lambda p. p {\sf true} = \lambda p. p (\lambda x y. x) $$ and its $\sf cdr$ analogous.

The LISP encoding you have is very similar to this encoding: it only have a few more twists for encoding $\sf nil$ as well, but that's a minor point.

The variable name $k$ which appears there in place of the "boolean" $b$ likely stands for "continuation", which is a key notion in PL theory.
> 6 votes

---
Tags: functional-programming, lists, lisp
---


# Question
Title: recursive algorithm to find the max sum of 2 numbers
I am looking for a recursive algorithm to find the max sum of 2 numbers in an array, and the numbers can't be "neighbours" ( for example $a\[0\]$ and $a\[1\]$ or $a\[4\]$ and $a\[5\]$, in general $a\[i\]$ and $a\[i+1\]$ )

example: for the array 5 8 3 9 20 1 4, the result will be 28.

# Answer
> 5 votes
Pick the four largest numbers in the array, $X \geq Y \geq Z \geq U$, and check for a few cases.

If $X$, $Y$ are not neighbours $\implies$ largest sum is $X + Y$.

Otherwise if $X$, $Z$ are not neighbours $\implies$ largest sum is $X + Z$.

Otherwise ($X$ is between $Y$ and $Z$) $\implies$ largest sum is $\max(Y + Z, X + U)$.

How did I get the solution: Well, the restriction is very mild, so it seemed likely that the largest sum would be found by adding two of the largest numbers. I tried with the three largest numbers, and found that $Y + Z$ could be small compared to $X$ plus the next smaller number, so the largest 4 were needed.

---
Tags: algorithms, arrays
---


# Question
Title: Do cryptographic hash function solve clustering problems with linear probing?
I understand in open addressing hash tables some clustering will always happen just by random chance, even if the input data is perfectly random, leading to some "best possible" lookup performance hit (for an open addressing scheme).

If the hash function is of low quality, and we use linear or quadratic probing, we may observe "primary" and "secondary" clustering effects that make clustering, and therefore lookup performance, worse.

My question is: would using a cryptographic hash function result in linear / quadratic probing having the "best possible" lookup performance, effectively eliminating primary and secondary clustering problems?

# Answer
> 3 votes
Cryptographic hash functions are not better than any hash functions with good distribution and "avalanche effect" (eg xxHash) on this regard.

Do they ensure "best possible" lookup performance? In the way you defined that, yes.

Do they eliminate clustering problems? No, clustering is a probabilistic effect that becomes worse as you insert more entries into your hash table, even if they are perfectly distributed. And this effect is already accounted in formulas of average lookup complexities for linear/quadratic ht algorithm for a given ht load.

---
Tags: cryptography, hash, hash-tables
---


# Question
Title: How to solve for a problem using a primitive function in toc
I have been searching on the internet how to multiply a function but I cannot find any. I have only found solution in adding but not in multiplication.

$add(2,3) = s(s(s(add(2,0)))) $

$add(2,3) = s(s(s(I(2))) $

$add(2,3) = s(s(s(2)) $

$add(2,3) = s(s(3)) $

$add(2,3) = s(4) $

$add(2,3) = 5 $

For example, Using the *multiply primitive function*, how to compute $multiply (5, 3)$.

Does anybody know?

# Answer
> 1 votes
**Hint:**

You probably have: $$add(0, n) = n$$ $$add(m+1, n) = S(add(m,n))$$

Now you know the base case for addition is adding zero. What's the base case for multiplication? Multiplying by zero.

$$mul(0,n) = 0 $$

I will not do the last part,because you must do your own homework, look at your example and the addition definition, the $mul$ function must work like this:

$$mul(3,5) \longrightarrow 5 + 5 + 5 + 0 $$

---
Tags: turing-machines
---


# Question
Title: As a Teacher: Choosing a suitable programming language
*I'm not sure if it's the right place for this question. Sorry if going a bit off-topic.*

Choosing a suitable Language for the first programming course is one of the most important things that every related teacher/lecturer should bear in mind; especially if the students are young or having a limited math knowledge.

I'm currently teaching a group of highly enthusiastic young people (about 16 to 17 years old) with a **medium knowledge of math**. They're attending **High School at 10th grade** class right now. I'm going to start teaching a programming language for the upcoming semester.

They're a group of handpicked students throughout the city with a extraordinary level of creativity and diligence, so i see that **working with a real programming language would not be a hard task for them.** So, choosing simple graphical and drag'n'drop solutions like Turtle Art, Scratch, and Tynker are not considered as options.

There are a few factors that should be checked before making a choice:

* **Simplicity**: Most of them probably have not experienced any kind of real coding action before.
* **Simplicity, Again**: One of the main ideas is teaching *how to think algorithmic*. Having a sophisticated or hardly-syntaxed language will divert them out of the path.
* **Generality**: It's better that the language not be designed for special development cases. Take PHP and MATLAB as examples which are respectively designed for Web Development and Calculation/Modeling.
* **Minimum Objective stuff**: No forced OO programming (like Java). Or at least with the minimum dependency to OO concepts.
* **Platform**: It's important to have Windows as a supported dev environment, as neary all of them are on Windows.
* **Easy to Set-up**: It's better to have a straightforward way of setting up the dev environment.
* **Industry preference**: Not a serious problem. But it should be at least a currently-active language allowing students to reach nearly-real dev experiences.
* **Hardware Portability**: It's important (but not required) that the language be flexible enough to be used on Hardware programming. (I'm not speaking of Hardware Description languages like Verilog and VHDL.) The aim is programming for more simple processor-based hardware like **AVR Microprocessors** or **Raspberry Pi GPIO interface**.

I want to know that

1. is there any other factors that i'm missing?
2. And, what languages do you suggest as choices?

# Answer
> 10 votes
My answer? Python.

Let me explain by tackling all your points.

1. **Simplicity**. Python code reads like English. Seriously, how simple is `print("Hello World!")`
2. **Generality**. Python can be used for web development (via. Flask/Django), data analysis (via. NumPy/Pandas/SciPy), games (via. PyGame), as well as a multitude of other tasks because of the sheer amount of libraries there are.
3. **Minimum Objective stuff**. You can do some OOP in Python but it isn't required.
4. **Platform**. Python2.7 is in pretty much on every Linux distro and there are plenty of YouTube videos on setting it up on Windows/Mac. If anything, you can use the online interpreter that Repl.It offers.
5. **Industry Preference**. Correct me if I'm wrong, but Python has consistently been ranked as one of the most popular languages.

In my experience teaching, it is extremely important to make sure that the syntax is as easy as possible to write and understand. For a new programmer, it can be pretty discouraging when he/she writes code only to see an error message (especially if he/she does not have the skill to read an error message and debug).

Side note, PythonTutor will be really helpful in explaining some major computer science/programming concepts.

# Answer
> 10 votes
**Background**

This question raises its ugly head every 5 or so years at our department. We had Miranda and Pascal ages ago, then we had Haskell, now we have C because thee EE dept decided to send us their students as before but demanded "something practical such as C" and our spineless leadership had nothing better to do than comply.

**Why not any of those recommended above?**

I've taught some of this and seen students come out of it over close to 20 years. The one thing that stood out was that the language hardly matters as long as it allows you to express fundamental concepts of computation with sufficient ease and that if you didn't do the right thing, you'd get good error messages, preferably from the compiler. That's where python fails. Types are important! That's where C fails: types are important and polymorphism is important! (And no, making everything have type void is not a solution. You merely move to python land.) That's where java fails: programs don't fit on slides - there's just too much boiler plate and verbosity.

So personally, I would not go with any of the answers above. I'd go with Haskell. It is beautifully aligned with mathematics. It's more concise than any of the others. You can focus on the essentials of computation. And ghc tends to produce better and faster code than C compilers do for the feeble attempts at optimization I witness every time I let students use C.

**But really..**

Having said that, in my experience the most important thing is though that the teacher actually knows the language better than from just a few online tutes. First languages are just that, first languages. If your students are serious they are going to pick up many more along the way. Focus on concepts rather than syntax.

# Answer
> 7 votes
This question is highly opinionated, in my opinion. There's nothing which can trigger an holy war like "which language is the best for X". Still, I'll bite.

> 1. is there any other factors that i'm missing?

First, I would recommend you read what Dijkstra said about teaching. It's old but still relevant -- possibly much, much more relevant today than it was in the past.

Second, I would also recommend reading a blog post by Joel Spolsky on the same topic.

Third, and less importantly, my very own criteria for a first language would be:

1. Any runtime error must be reported with a clear error message.
2. It should be typed.
3. There's no single programming language that can make you understand all the programming aspects. To become a real programmer, one needs to learn many languages, especially radically different ones.

Point 1 is very, very useful to a beginner. Most languages satisfy that, with the notable exception of C and C++. While I think that C is a must-know language for any programmer (see point 3), I think it's unnecessarily harsh for a beginner. Garbage collection is pretty much a prerequisite for point 1.

Point 2 is the most controversial. While I believe that one should also learn to work in an untyped language (again, point 3), I think starting with types is more beneficial. Even in an untyped environment, programmers often think about which kind of data should be passed to a subroutine. Further, detecting errors earlier than runtime is nice.

Point 2 rules out a lot of languages. Note however that Python is not ruled out: while Python is untyped, there's the wonderful mypy project which allows one to use a typed Python. Further, Perl6 has optional (gradual) typing, so that would still be in. Typescript also adds types to JavaScript. Even if Lisp and Scheme are ruled out, there are many typed functional programming languages to choose from (Ocaml, Haskell, F#, ...).

Point 3 is important as well. One needs to learn a lot of things to be a good programmer. From low level stuff (pointers, C) to the highest level (recursion, closures, parametric polymorphism / generics, ...), different paradigms (imperative, functional, logic, ...). This can't be taught in a single course, of course. As a first course, you should pave the way to the full road.

# Answer
> 1 votes
I would go with the Python answer, but I also like to recommend an alternative: C.

My first programming language was C and at the time learning it I really enjoyed it. The teacher (and some fellow students) would have taken Java as first programming language but it was set to take C. The teacher used to show some Python examples to show benefits of a more modern programming language. Anyway, back to topic:

* **Simplicity** The C syntax is pretty small, but from time to time kind of strange. You are not forced to take the vodoo approach, but you might.
* **Simplicity, Again** As result of the first points, algorithms can be implemented pretty compact and understandable. Think of Fibonacci or more advanced the Knight's Tour.
* **Generality** Using C you might implement what you want. You can also use some subsystems like scripting languages (Lua).
* **Minimum Objective Stuff** C talks for itself here. You have to have some good knowledge of C to implement OO stuff.
* **Platform** Every major platform supports the language, take a compiler of your choice and start coding.
* **Easy to Set-up** C does not need a IDE with plenty of buttons and a fat toolchain. Simply take a make file (or a script) and comile your code with some commands. You can use an IDE (Codeblocks, ...) if you want to.
* **Industry preference** Linux, Windows, ...
* **Hardware Portability** It is working good on AVR microcontrollers or take Arduino, which is also programmable using plain old C.

---

As an alternative, what about developing on an affordable platform like Arduino (there might be better alternatives). You might show them all algorithmic stuff using simple stdout prints or you might put some hardware to work. It might be of benefit if the resulting code does not only print some text (or picture, or gui, or stuff...) but also lets an LED flash or something. In my company there are sometimes pupils courses where they code some stuff on a pretty basic Arduino board and we receive good feedback from attendants.

---

I think you are asking the right questions and I wish you all the best for teaching yours students.

# Answer
> 1 votes
I'd go for Swift, using Swift Playground. You might want to check how many people have either a Mac or an iPad. Among students it's 90% in some places. It's also available online at http://iswift.org/playground , so you need nothing more than a browser. You can use it on your phone if you don't have a computer.

Swift is a modern language, it's a safe language, and it's a language that will get you a job if you master it. (Any new code that Apple writes is written in Swift. )

# Answer
> 0 votes
Edit: Sorry, about that - I misread your point about the platform. I basically thought you said that it only had to run on Windows, but I see now that it is just the majority of your users that are using Windows.

Microsoft has been building support for Linux and Mac and VS Code and Visual Studio for Mac, respectively, and .NET Core so I think this is still a valid answer, albeit perhaps not as strong.

---

I would suggest you look into C#, the .NET framework, and the Visual Studio IDE \- they cover pretty much all of your 7-8 points. (depending on how you count the first two ;D)

* **Simplicity**: The syntax is fairly easy to pick up, and there is a large amount of information on the web for beginner tutorials.
* **Simplicity, Again**: C# is a strongly-typed language, which helps highlight errors before the application even runs. Visual Studio is arguably one of the best IDEs you can get with great syntax highlighting, Intellisense, and debugging support.
* **Generality**: While it may not be the best choice, I've personally used it for a wide variety of applications - from websites and desktop applications to robotic equipment.
* **Minimum Objective stuff**: ***Edit*** Object Oriented Programming is a style of programming focusing on encapsulation, abstraction, inheritance, and polymorphism. C# has features that make writing OO code easier, but it does not require that you use them. You can write a C# program procedurally.
* **Platform**: ***Edit*** The .NET Core is the cross-platform version of the .NET Framework. It works on Mac, Linux, and Windows.
* **Easy to Set-up**: I don't think you can find an easier language and IDE to get setup on Windows. ***Edit*** As for Mac and Linux, I don't have any experience with it, but there are VS Code (Win/Mac/Linux) and Visual Studio for Mac (Mac Only). I would assume these would be relatively easy as well.
* **Industry preference**: C# is definitely a professional language, though you can take a look for yourself by searching for jobs in your area based on whichever languages you are considering. Using Dice, I got roughly equal results for C# (6,548) and Python (6,639) across all of the open job postings, but I don't know if Dice has a bias one way or another, or if there are significant regional differences.
* **Hardware Portability**: Maybe half a point here - I don't think there is a lot of support for programming microcontrollers with C# other than a couple specialty .NET boards like the Netduino, but the Raspberry Pi is supported.

As an added bonus, Microsoft has a program called Imagine (previously DreamSpark) where they give away a lot of free software for teachers and students in high school and college. They also have some contests for the students as well.

# Answer
> -1 votes
Take a look at Lazarus:

http://www.lazarus-ide.org

Lazarus is a programming environment based on Free Pascal Compiler (FPC). It runs very smoothly on Windows, and also available for other major platforms. FPC supports a modernized version of Pascal, which is called Object Pascal.

Object Pascal is a multi-paradigm programming language. You can write code in standard Pascal, then start using OO features when you need it.

Real world applications can be developed using Lazarus/FPC. They are both quite mature, but you can also use Delphi as a commercial alternative.

FPC can cross-compile your programs to devices like Raspberry Pi or Android.

Besides, future of Pascal is bright. Oberon programming language will eventually take over as the most productive way of developing software:

ht tp://www.projectoberon.com

Hopefully, tools to develop in Oberon will mature in time. There is already a cool compiler for Win64 target:

https://github.com/congdm/AyaCompiler

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


# Question
Title: Enumerating the set of polynomial time Turing machines
I was checking this question and wondered how to apply it to the following language to prove it is in $RE$: $$ L = \\{ \langle M \rangle : \exists P \text{ such that } M \text{ halts on every input } w \text{ within } P(|w|) \text{ steps} \\},$$

where $P(x)$ is a polynomial with coefficients $a\_1,\ldots,a\_n \in \mathbb{N}$.

Those are the two approaches I am thinking of so far, in order to build a Turing Machine $M\_L$ which accepts $L$ above:

1. Let $d$ be the degree of the polynomial $P$. For each $d=1,2,3,\ldots$, iterate over all possible $d$ coefficients, and check whether the current $P$ satisfies $L$'s condition above. I think it might work because if there is no such $P$, then the Turing machine $M$ won't stop and this is OK.
2. Here I am taking $P$ to be a constant (i.e. $P(x)=k \in \mathbb{N}$), and then iterate over all $k$ and apply the Turing machine from the question I linked at the beginning, where the language at the question above is in $R$ then there is a Turing machine $M\_k$ which **decides** it, thus, while we get *Rejection* from $M\_k$ for the $k$ values we're iterating on, $M\_L$ does not stop.

I am not sure even where I made a mistake above, since the concept of iterating over all $k \in \mathbb{N}$ does not seems robust.

Does the approach of building a Turing machine work? Since I could not get to a reduction which proves that $L \in RE$.

# Answer
> 3 votes
The halting problem reduces to $\overline{L}$: given a machine $T$, create a new machine that on input $n$ simulates $T$ for $n$ steps, and if $T$ halts then it enters an infinite loop. (I leave you the details.)

Since the halting problem is complete for $\mathsf{RE}$, it cannot be the case that $\overline{L} \in \mathsf{coRE}$, and so it cannot be the case that $L \in \mathsf{RE}$.

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


title: How reducing languages work?

text:
# Question
Title: How reducing languages work?
I am reading Automata Theory book by Hopcroft, Motwani and Ullman 2nd ed. In this book, there are these sentences:

> In general, if we have an algorithm to convert instances of a problem $P\_1$ to instances of a problem $P\_2$ that have the same answer, then we say that $P\_1$ * reduces to \*$P\_2$. We can use this proof to show that $P\_2$ is at least as hard as $P\_1$. Thus, if $P\_1$ is not recursive, then $P\_2$ cannot be recursive. If $P\_2$ is non-RE, then $P\_1$ cannot be RE.

I am quite confused due to last statement above because the book further states the following theorem:

> If there is a reduction from $P\_1$ to $P\_2$, then:
>
> * If $P\_1$ is undecidable then so is $P\_2$.
> * If $P\_1$ is non-RE, then so is $P\_2$.

I dont know whether I should feel that the last statement above contradicts with the last statement in the first paragraph. So whats true?

> If $P\_2$ is non-RE, then $P\_1$ cannot be RE.

Or

> If $P\_1$ is non-RE, then so is $P\_2$.

Or both mean the same and I am unnecessarily thinking that they are contradicting each other unnecessarily? Or the book is wrong?

# Answer
You will reduce $P\_1$ to $P\_2$ if you know something "bad" about $P\_1$, and you want to see if this extends to $P\_2$.

It should read "If $P\_1$ is non-RE, $P\_2$ cannot be RE". If it is in the book, it's a typo.
> 1 votes

---
Tags: automata, undecidability
---


# Question
Title: Lambda calculus lists construction explanation
I have the following notes that introduce how lambda calculus handles lists. They go as follows:

> A list is something we can match on and deconstruct if it is not empty:
>
> ```
> list match{
>  case Nil => M
>  case Cons(x,y) => N(x,y)
> }
>
> ```
>
> A list value is given by how it interacts with two terms M and N

(1) For starters I don't understand at all what is the role of M and N here. Then it continues:

> We define it (a list) as a function that will take such M and N as arguments
>
> $Nil = \lambda mn.m$
>
> $Cons(P,Q) = \lambda mn. n (P,Q)$

(2) Assuming I know how pairs and if constructs work in lambda calculus how can I come up with this expressions myself? I suppose that once this is clear I will be able to understand this sentence:

> Cons is like a pair but takes m as argument, too, to fit along with nil

Can you clarify points (1) and (2)?

**Edit:**

This are some further comments made in my notes that may make easier to understand what the intention of the writer is:

$Nil \ M \ N \implies M$ $Cons(P,Q) \ M \ (\lambda p. p.\_1) \implies \cdots \implies (P,Q).\_1$

# Answer
> 5 votes
There are several ways to define lists in lambda calculus. You can find them here.
Your definition doesn't seem to fit exactly in any of those (please, check that).
Anyway, I'll try to answer to your questions.

Lists (and many data types) can be defined in lambda calculus in terms of the way to *deconstruct* them.

If you are familiared with the fold operation, you know it follows this specification:

$fold\ Nil\ e\ f$ = $e$
$fold\ (Cons\ x\ l)\ e\ f$ = $f\ x\ (fold\ l\ e\ f)$

Many functions over lists can be defined with $fold$. For example, if you want to sum the elements of a list $l$ of integers, you can do:

$sum\ Nil = 0 $
$sum\ (Cons\ x\ l) = +\ x\ (sum\ l) = x + sum\ l$

Or just say:

$sum\ l = fold\ \\, l\ 0\ +$

In this case, you can imagine that the $sum$ functions *replaces* the empty list with $0$ and the cons operator with '+'.

So, if we want to define lists in lambda calculus, a way of doing it is to define each constructor ($Nil, Cons$) to do the work of $fold$.
The fist step is to state that $fold$ is just the identity function ($\lambda x . x$). Then we get the $fold$ specification to be our specification for $Nil$ and $Cons$:

($\lambda x . x$)$\ Nil\ e\ f$ = $e$
($\lambda x . x$)$\ (Cons\ x\ l)\ e\ f$ = $f\ x\ ((\lambda x . x)\ l\ e\ f)$

This is the same as:

$Nil\ e\ f$ = $e$
$(Cons\ x\ l)\ e\ f$ = $f\ x\ (l\ e\ f)$

Rewriting it a bit, we get:

$Nil$ = $\lambda e\ f.e$
$(Cons\ x\ l)$ = $\lambda\ e\ f. f\ x\ (l\ e\ f)$

So, this answers fits in the last form of definition of lists from the wiki (using right fold). But it is important to notice that is not the only way. The way you posted seems to do the same as here, but instead of using the $fold$ operator, using some sort of $destructor$, where:

$destructor\ Nil\ m\ n = m$
$destructor\ (Cons\ x\ l)\ m\ n = n\ x\ l$

---
Tags: lambda-calculus, lists
---


title: NP-completeness of DISCONNECTED-SET

text:
# Question
Title: NP-completeness of DISCONNECTED-SET
I'd like to show that the language DISCONNECTED-SET, defined by $$ \\{\langle G, k\rangle | \text{$G$ is an undirected graph that contains a disconnected set of size $k$}\\},$$ is NP-complete. (A *disconnected set* $S$ is defined as a set of vertices such that for every pair of vertices $u,v \in G$, if there is no edge between $u$ and $v$, then at least one of the vertices is in $S$.)

I'm under the assumption that it could be done by reduction from CLIQUE. I've made the following observations (which I'm unable to utilize, though):

* If we have a graph $G$, then the maximum disconnected set of its complement $G'$ has a size equal to the number of nodes in $G$ that belong to connected components of size at least 2 in $G$.
* If we have isolated nodes in $G$, the sizes of the disconnected sets in $G'$ are unchanged.

May I just ask for a tiny tip that would get me going in the right direction, **not a complete proof**. Thank you.

# Answer
This is just VERTEX-COVER in disguise. The reduction from CLIQUE is also simple – a set is disconnected iff its complement is a clique.
> 2 votes

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


# Question
Title: One element that differs in two arrays. How to find it efficiently?
I am preparing for a coding interview and I can't really figure out the most efficient way to solve this problem.

Let's say we have two arrays consisting of numbers that are unsorted. Array 2 contains a number that Array 1 does not. Both arrays have randomly located numbers, not necessarily in the same order or at the same indices. For example:

Array 1 \[78,11, 143, 84, 77, 1, 26, 35 .... n\]

Array 2 \[11,84, 35, 25, 77, 78, 26, 143 ... **21**... n+1\]

What is the fastest algorithm for finding the number that differs? What is its running time? In this example, the number we would be looking for is 21.

My idea was to run through Array 1 and delete that value from array 2. Iterate until you are finished. This should be around $O(n \log n)$ running time, right?

# Answer
> 31 votes
I see four main ways to solve this problem, with different running times:

* $O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time.
* $O(n \\: log \\: n)$ solution: sort the arrays beforehand; then, perform a linear search to identify the distinct element. In this solution, the running time is dominated by the sorting operation, hence the $O(n \\: log \\: n)$ upper bound.

When you identify a solution to a problem, you should always ask yourself: can I do better? In this case, you can, making a clever use of data structures. Note that all you need to do is to iterate one array and perform repeated lookups in the other array. What data structure allows you to do lookups in (expected) constant time? You guessed right: a **hash table**.

* $O(n)$ solution (expected): iterate the first array and store the elements in a hash table; then, perform a linear scan in the second array, looking up each element in the hash table. Return the element that is not found in the hash table. This linear-time solution works for any type of element that you can pass to a hash function (e.g., it would work similarly for arrays of strings).

If you want upper-bound guarantees and the arrays are strictly composed of integers, the best solution is, probably, the one suggested by Tobi Alafin (even though this solution will not give you the index of the element that differs in the second array):

* $O(n)$ solution (guaranteed): sum up the elements of the first array. Then, sum up the elements of the second array. Finally, perform the substraction. Note that this solution can actually be generalized to any data type whose values can be represented as fixed-length bit strings, thanks to the bitwise XOR operator. This is thoroughly explained in Ilmari Karonen's answer.

Finally, another possibility (under the same assumption of integer arrays) would be to use a linear-time sorting algortihm such as counting sort. This would reduce the running time of the sorting-based solution from $O(n \\: log \\: n)$ to $O(n)$.

# Answer
> 16 votes
The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is:

* *total*, such that for any values $a$ and $b$, $a \oplus b$ is defined and of the same type (or at least of some appropriate supertype of it, for which the operator $\oplus$ is still defined);
* *associative*, such that $a \oplus (b \oplus c) = (a \oplus b) \oplus c$;
* *commutative*, such that $a \oplus b = b \oplus a$; and
* *cancellative*, such that there exists an inverse operator $\ominus$ that satisfies $(a \oplus b) \ominus b = a$. Technically, this inverse operation doesn't even necessarily have to be constant-time, as long as "subtracting" two sums of $n$ elements each doesn't take more than ${\rm O}(n)$ time.

(If the type can only take a finite number of distinct values, these properties are sufficient to make it into an Abelian group; even if not, it will at least be a commutative cancellative semigroup.)

Using such an operation $\oplus$, we can define the "sum" of an array $a = (a\_1, a\_2, \dots, a\_n)$ as $$(\oplus\\, a) = a\_1 \oplus a\_2 \oplus \dotsb \oplus a\_n.$$ Given another array $b = (b\_1, b\_2, \dots, b\_n, b\_{n+1})$ containing all the elements of $a$ plus one extra element $x$, we thus have $(\oplus\\, b) = (\oplus\\, a) \oplus x$, and so we can find this extra element by computing: $$x = (\oplus\\, b) \ominus (\oplus\\, a).$$

For example, if the values in the arrays are integers, then integer addition (or modular addition for finite-length integers types) can be used as the operator $\oplus$, with subtraction as the inverse operation $\ominus$. Alternatively, for *any* data type whose values can be represented as fixed-length bit strings, we can use bitwise XOR as both $\oplus$ and $\ominus$.

More generally, we can even apply the bitwise XOR method to strings of variable length, by padding them up to the same length as necessary, as long as we have some way to reversibly remove the padding at the end.

In some cases, this is trivial. For example, C-style null terminated byte strings implicitly encode their own length, so applying this method for them is trivial: when XORing two strings, pad the shorter one with null bytes to make their length match, and trim any extra trailing nulls from the final result. Note that the intermediate XOR-sum strings *can* contain null bytes, though, so you'll need to store their length explicitly (but you'll only need one or two of them at most).

More generally, one method that would work for arbitrary bit strings would be to apply one-bit padding, where each input bitstring is padded with a single $1$ bit and then with as many $0$ bits as necessary to match the (padded) length of the longest input string. (Of course, this padding does not need to be done explicitly in advance; we can just apply it as needed while computing the XOR sum.) At the end, we simply need to strip any trailing $0$ bits and the final $1$ bit from the result. Alternatively, if we knew that the strings were e.g. at most $2^{32}$ bytes long, we could encode the length of each string as a 32-bit integer and prepend it to the string. Or we could even encode arbitrary string lengths using some prefix code, and prepend those to the strings. Other possible encodings exist as well.

In fact, since *any* data type representable on a computer can, by definition, be represented as a finite-length bit string, this method yields a generic $\Theta(n)$ solution to the problem.

The only potentially tricky part is that, for the cancellation to work, we need to choose a unique canonical bitstring representation for each value, which could be difficult (indeed, potentially even computationally undecidable) if the input values in the two arrays may be given in different equivalent representations. This is not a specific weakness of this method, however; any other method of solving this problem can also be made to fail if the input is allowed to contain values whose equivalence is undecidable.

# Answer
> 15 votes
*I'd post this as a comment on Tobi's answer, but I don't have the reputation yet.*

As an alternative to calculating the sum of each list (especially if they are large lists or contain very large numbers that might overflow your data type when summed) you can use xor instead.

Just calculate the xor-sum (i.e. x\[0\]^x\[1\]^x\[2\]...x\[n\]) of each list and then xor those two values. This will give you the value of the extraneous item (but not the index).

This is still ***O(n)*** and avoids any issues with overflow.

# Answer
> 14 votes
Element = Sum(Array2) - Sum(Array1)

I ***sincerely*** doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps.

If the number of added elements is more than one, this won't work.

My answer has the same run time complexity for best, worst, and average case,

***EDIT***
After some thinking, I think my answer is your solution.

For an array of length $n$, number of primitive operation to find sum = $n-1$ Sum of Array$1 = n-1$ operations. Sum of Array$2 = n+1 -1=n$ operations.

We now have $2n-1$ operations. Sum$2 - $Sum$1 = 1 $ operation.

$2n - 1 + 1 = 2n$ operations.

Worst case complexity of my algorithm: $$\Theta(n)$$

***EDIT:***
Due to some problems with Data types, an XOR sum as suggested by *reffu* will be more apt.

# Answer
> 1 votes
Assuming that array 2 was created by taking array 1 and inserting an element at a random position, or array 1 was created by taking array 2 and deleting a random element.

If all the array element are guaranteed to be distinct, the time is O (ln n). You compare the elements at location n/2. If they are equal, the extra element is from n/2 + 1 to the end of the array, otherwise it is from 0 to n/2. And so on.

If the array elements are not guaranteed to be distinct: You could have n times the number 1 in array 1, and the number 2 inserted anywhere in array 2. In that case you can't know where the number 2 is without looking at all array elements. Therefore O (n).

PS. Since the requirements changed, check your library for what is available. On macOS / iOS, you create an NSCountedSet, add all numbers from array 2, remove all numbers from array 1, and what's left is everything that is in array 2 but not in array 1, without relying on the claim that there is *one* additional item.

# Answer
> -1 votes
var shortest, longest;

Convert shortest to a map for quick referencing and the loop over the longest until the current value is not in the map.

Something like this in javascript:

if (arr1.length \> arr2.length) { shortest = arr2; longest = arr1; } else { shortest = arr1; longest = arr2; }

var map = shortest.reduce(function(obj, value) { obj\[value\] = true; return obj; }, {});

var difference = longest.find(function(value) { return !!!map\[value\]; });

# Answer
> -1 votes
O(N) solution in time complexity O(1) in terms of space complexity

Problem statement: Assuming that array2 contains all the elements of the array1 plus one other element not present in array1.

The solution is : We use xor to find the element which is not present in array1 so steps are: 1. Start from array1 and do xor of all the elements and store them in a variable. 2. Take the array2 and do the xor of all elements with the variable which store the xor of array1. 3. After doing the operation our variable will contain the element which is present only in array2. The above algorithm works because of the following property of xor " a xor a =0" "a xor 0=a" I hope this solves your problem . Also the above suggested solutions are also fine

---
Tags: algorithms, search-algorithms, arrays, efficiency
---


# Question
Title: page fault while executing machine instruction
A process executing machine instruction Y right after machine instruction x.On executing x It causes a page fault. what is the next instruction that is executed immediately on restarting the process. ? assume that instead of page fault the process receives timer interrupt while executing x. what is the next instruction that is executed immediately on restarting the process.

# Answer
You'd need to consult the manuals of the manufacturer of the processor for details like this. Different processors will behave in different ways.

On a modern processor, "executing instruction y after instruction x" usually makes little sense. Instructions are executed simultaneously, out of order, and so on. What the processor and operating system hopefully guarantee that either the total observable behaviour will be as if the page had been present (except for some delay), or the process is killed, or a higher level signal is sent to the process informing it that the page isn't there *and cannot be acquired*.

And I remember that on a 68020 processor a single instruction could create up to 11 (eleven) page faults...
> 0 votes

# Answer
Regarding page fault I found these on the internet at 2 different sources :) \*The process is then restarted at the machine instruction where the memory fault occurred. \*If instructions are idempotent, just restart the faulting instruction (hardware saves instruction address during page fault).

So it seems that it again tries to execute X.
> -1 votes

---
Tags: operating-systems, paging
---


# Question
Title: Where we Use Dynamic Programming and Greedy Algorithm?
Can someone tell me where we use Dynamic/Greedy algorithm and how we trace from the question that it will solved by any one of the above?

Thanks

# Answer
> 2 votes
**Greedy Algorithm**:

> An algorithm that always takes the best immediate, or local, solution while finding an answer. Greedy algorithms find the overall, or globally, optimal solution for **some optimization problems**, but may find less-than-optimal solutions for some instances of other problems. \[1\].

Problems that can be solved by a Greedy Algorithm will have two properties:

1. *Greedy Choice Property*;
2. *Optimal Substructure*.

Essentially, Greedy Algorithms solve combinatorial problems having the properties of matroid.

For more detail you can consult Introduction to Algorithm.

**Dynamic Programming**:

> Solve an optimization problem by caching subproblem solutions (memoization) rather than recomputing them. \[2\]

Dynamic Programming algorithms are often used for optimization because it will examine the previously solved subproblems and will combine their solutions to give the best solution for the given problem.

Now, problems that can be solved by a Dynamic Programming Algorithm will have this necessary condition:

> *Principle of Optimality*: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision. \[3\]

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


# Question
Title: Given the logical address, how to extract the page number?
I am studying Computer Systems. I have th following question and its answer:

> Given the logical address 0xAEF9 (in hexadecimal) with a page size of 256 bytes, what is the page number?
>
> Answer: **0xAE** (I found this answer in the web, but I want to know how can I figure it out myself?

How can I figure out the page number for a given logical address?

# Answer
> 0 votes
Your logical address is made of 16 bits, that means you have a addressable space of $2^{16}$ bits. The page size is typically a power of 2, $2^n$, in this case $2^n = 256 \Rightarrow n = 8$.

The page number is calculated by substracting $n$ from the size of your logical address: $16 - 8 = 8$, so the first 8 bits of the address are your missing page number, that is 0xAE

# Answer
> 0 votes
Logical address includes both page number and the offset within the page.
Your logical address is **16** bit.
Page size as mentioned is **256** = **28**. It means that **8** bit address is necessary to address any word within the page. The least significant **8** bits are used for this purpose (as offset address)
The remaining bits (the most significant **8** bits) are used as page number.
So the fist **8** bits specify the page number. **0xAE** in this case.

# Answer
> 0 votes
Page Number=Logical Address/Page Size

AEF9 converted to decimal-\> 1\*9+16\*15+16^2\*14+16^3\*10 = 44793

44793/256=174

174 in hexa-\> AE

---
Tags: operating-systems, memory-management, paging, virtual-memory
---


title: Is the given grammar LL(2)?

text:
# Question
Title: Is the given grammar LL(2)?
http://dickgrune.com/Books/PTAPG\_1st\_Edition/BookBody.pdf

The book by Grune and Jacobs presents an example of a grammar that is $LL(K + 1)$ but not $LL(K)$

The example is $S -\> a^kb/a^ka$

The grammar of this type is $LL(K + 1)$ but not $LL(K)$.

---

I have an example based on the grammar shown. Is this also $LL(2)$ ?

$S-\> cca/ccb$

Based on the information above, I just want to confirm that is this grammar also $LL(2)$ but not $LL(1)$ ?

# Answer
It is neither LL(2) nor LL(1). Read the Grune and Jacobs argument carefully. What is the k in this example?

If the first two characters of the input are "cc", would you know which production to apply? So how can it be LL(2)?
> 2 votes

# Answer
It is actually $LL(3)$. Try to prove it yourself.
> 2 votes

---
Tags: automata, formal-grammars, compilers, parsers
---


# Question
Title: Algorithm to reconstruct sentence from shuffled string
Given a dictionary of words, and given a string which is an anagram of concatenation of group of words from the dictionary, is there an efficient algorithm to find valid set of words that can form this string ?

```
eg1: dict = [ 'dog', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ]

```

If we join the words in the answer to form the string, we can see that it is an anagram of the input string `s`

```
eg2: dict = [ 'dog', 'act', 'cat', 'cow' ]
s = 'ocdgatcta'
ans = [ 'cat', 'cat', 'dog' ] or [ 'act', 'cat', 'dog' ] or [ 'act', 'act', 'dog' ]

```

In the above case any of the above list is valid as the string formed by them is an anagram of the input string `s`

We can brute force but there seems to be overlapping sub problems. Can this be solved in polynomial time ?

# Answer
> 3 votes
This is NP-hard, so it's very unlikely there's a polynomial-time solution. To see this, notice that any instance of the NP-hard problem Exact Cover can easily be encoded as an instance of your problem in such a way that there is a solution to this encoded instance if and only if there is a solution to the original Exact Cover instance.

---
Tags: algorithms, strings
---


# Question
Title: Using Dijkstra to find shortest path in relation to two weight functions?
I'm given a graph and two weight functions, $w\_1$ and $w\_2$, such that there doesn't exist a negative loop in the graph in $w\_1$ and $w\_2$. I'm also given two vertices, $s$ and $t$, and am asked to find the lightest path from $s$ to $t$ in relation to $w\_1$, out of all the lightest paths from $s$ to $t$ in relation to $w\_2$.

I get that this question begs for me to modify Dijkstra somehow, but I just can't seem to find the intuition to do so. Any guidance would be appreciated!

# Answer
Let $\epsilon\>0$ be an infinitesimal. Define a new weight function $w(v) = w\_2(v) + \epsilon w\_1(v)$, and run Dijkstra with respect to this weight function.

How do you implement infinitesimals? There are two options. The first is to let $\epsilon$ be a small enough number. For example, if $W\_1$ is the maximal $w\_1$-weight and there are $n$ nodes, then $\epsilon \< 1/(nW\_1)$ should be small enough (why?). The other option is to notice that you only have to be able to compare numbers of the form $w\_2 + \epsilon w\_1$. We have $x\_2 + \epsilon x\_1 \leq y\_2 + \epsilon y\_1$ if either $x\_2 \< y\_2$ or $x\_2 = y\_2$ and $x\_1 \leq y\_1$. Using this comparison oracle, you can implement infinitesimals in earnest.
> 1 votes

# Answer
Let $G$ be the relevant graph. Run $\text{Bellman-Ford}(G, s, w\_2)$ and for every $v ∈ V$: $d(v)=δ(s,v)$. Now for every $(u,v) ∈ E$, if $d(v)≠d(u)+w\_2(u,v)$ erase ($u$,$v$) from $G$. You are left with $G'$, the graph with all lightest paths from $s$ according to $w\_2$. Run $\text{Bellman-Ford}(G', s, w\_1)$ to find the lightest path from $s$ to $t$ in relation to $w\_1$, out of all the lightest paths from $s$ to $t$ in relation to $w\_2$.

It is done by $O(|E||V|)$.

Dijkstra could have been an option if we were assuming all weights are non-negative.
> 0 votes

---
Tags: shortest-path, weighted-graphs
---


# Question
Title: What are applications of computational models beyond P?
If I may summarize how I feel about collapse of the polynomial hierarchy:

Are intractable models of computation, including collapse of $\mathbf{PH}$ or $\mathbf{PSPACE}$ above but not down to $\mathbf P$ useful for any reason besides the off chance they might collapse? Obviously "useful" is broad - I would gladly be interested in answers outside of computer science, but I am wondering if their study helps us understand really anything besides them themselves.

I am taking complexity theory and have essentially been wondering this entire semester, if my increasingly fluency in problems of the form $\exists\forall\exists\forall...$

# Answer
> 3 votes
Not all problems that are encountered in an industrial setting are clearly either NP-Complete or else polynomial-time solvable, even with randomness, heuristics and approximation. So if you encounter (a variant of) a problem such as Exact Independent Set, or Succinct Graph Diameter, for example, then you ought to be looking to the complexity classes $\text{DP}$ and $\Sigma\_2^P$. Without the study of these classes, there is no proper placement of these problems, no way to relate them to one another and therefore no way to tackle them coherently, and no way to quantify their hardness. We might look for a way to compactly store and then sell the solutions to NP-Complete problems after we've brute forced them for many inputs. But because of Karp and Lipton, we know that this is impossible, unless the polynomial hierarchy collapses to the second level. In general, these conditional collapses are great for question of the form "Can I...", "No.".

I would love to provide an answer like "We were struggling, but then Immerman and Szelepcsényi proved that $\text{Nondeterministic Logspace}$ was closed under complement, and that really gave a boost to our startup!", being a student myself I don't have any anecdotal evidence, and I would love to hear from someone more seasoned.

So if you are looking for an industrial application of computational complexity theory beyond SAT Solvers, then you may be disappointed. Complexity theory is to computer science a bit like string theory is to physics; it is purely theoretical and its study is not motivated by the urge to solve a particular problem, but rather to understand the nature of computation - how do randomness and nonuniform computation relate to one another? Do all programs with small memory footprints have a fast implementation? - very much like the motivation of theoretical physics is not to design a slightly more efficient engine, but rather to understand the laws of physics. You are taking a theoretical class, and must not be surprised to learn about theoretical results. There are coding classes where you come from; if you prefer those, take those.

If I take the liberty of venturing into speculation, then you may know that right now we do not even know how to rule out ridiculous scenarios in which $\text{BPP}=\text{NEXP}$. Of course everyone believes that the result will be $\text{BPP}\subsetneq\text{NEXP}$, but a proof of this fact cannot come without major advances in our understanding of computation, and, staying with the metaphor of physics, where major advances in our understanding of fundamental physics invariably spurs major progress in unexpected areas, I feel confident in saying that these results, when they come, will spur major progress across all fields of computing.

---
Tags: complexity-theory
---


# Question
Title: Algorithm for finding largest subset with equal number of even and odd elements
> A sequence of positive integers $a\_1, ..., a\_n$ is given. Compute the length of the largest continuous subsequence such that the number of even integers is equal to the number of odd integers in the subsequence.

I have thought that we could take all those integers mod 2 and store those in an array, then take two pointers $i=0,j=n-1$ and somehow sweep the table until #(even) = #(odd) is found in the subsequence inside, so that $j-i+1$ would be the optimal length. But I don't know how exactly to choose which of the two pointers to increase/decrease each time, so that I get an $O(n)$ algorithm.

Is my algorithm on the track, or can't it be used here? What algorithm do I need to apply and how can I think of its idea? (It would be preferable if this problem could be solved without using special data structures, such as AVL, segment, suffix trees, etc.)

# Answer
Here's an easy linear time solution which uses $O(n)$ space. You could probably bring this down to $O(1)$ space using the techniques you mentioned.

First compute $$ D\_i = \\# \text{even integers among $a\_1,\ldots,a\_i$} - \\# \text{odd integers among $a\_1,\ldots,a\_i$}. $$ You can do this in $O(n)$.

Second, for each $\Delta \in \\{-n,\ldots,n\\}$, compute $a\_\Delta = \min \\{ i : D\_i = \Delta \\}$ and $b\_\Delta = \max \\{ i : D\_i = \Delta \\}$ (possibly these are undefined). You can do this in $O(n)$.

Finally, compute $\max\_\Delta b\_\Delta - a\_\Delta$ for all $\Delta$ for which these indices exist. This also takes $O(n)$.
> 0 votes

---
Tags: algorithms
---