# Question
Title: Is there a name/algorithm for this problem related to set cover and CSP?
Our college would like to determine if a transcript contains classes that satisfy every general education requirement. What makes this nontrivial is that while a single class may in theory satisfy multiple graduation requirements (e.g., writing, quantitative literacy, and art), each class may only count for up to two graduation requirements for a single student. We wish to be able to determine the mapping of courses (within a given transcript) to graduation requirements that satisfies the most graduation requirements in order to see if a student can graduate, and, if not, what graduation requirements are unmet. I've tried writing this up semi-formally:

Given:

* A set of graduation requirements $\cal G$.
* A set of classes $\cal C$ offered at the college.
* A map ${\cal M: C} \rightarrow 2^\cal G$ indicating which classes fulfill which requirements. A given class can fulfill anywhere from 0 to $|\cal G|$ requirements.
* A set of classes $\cal T$ (for transcript) $\subseteq \cal C$.

Determine:

* A set $\cal S$ of $(c, g)$ pairs, where $c \in \cal T, g \in \cal M(c)$ that maximizes coverage of $\cal G$ but contains no more than 2 pairs with the same $c$.

Is there a name and known algorithm to solve this problem?

# Answer
> 3 votes
This can be reduced to maximum bipartite matching.

Each left-side vertex represents a course. Each right-side vertex represents a requirement. Add an edge $c \to g$ if course $c$ satisfies requirement $g$. To deal with the fact that each course is allowed to be used satisfy at most 2 requirements (per course), we'll have two vertices for each course. In other words, we'll make two copies of each course, so the number of vertices on the left side is twice the number of courses.

Then, look for a maximum matching in this graph. The matching will tell you which requirements are covered and by which courses. You can use any standard algorithm for finding a maximum matching in a bipartite graph: a network flow based algorithm, or Hopcroft-Karp, or any other such algorithm.

# Answer
> 3 votes
Just to be sure, I assume that $\mathcal{G}^\* = 2^\mathcal{G}$, i.e. that $\mathcal{G}^\*$ is the power set of $\mathcal{G}$.

Alright, we can use the following flow network $(V,E,\text{cap})$: let $V = \\{s\\} \uplus \mathcal{T} \uplus \mathcal{G} \uplus \\{t\\}$. Now let $E = \\{(s, c) : c \in \mathcal{T}\\} \uplus \\{(g,t) : g \in \mathcal{G}\\} \uplus \\{(c,g) : c\in \mathcal{T} \wedge g \in \mathcal{G} \wedge g \in \mathcal{M}(c)\\}$. Finally, we need capacity constraints:

\begin{align}\text{cap}(s,c) &= \min\\{|\mathcal{M}(c)|,2\\} \qquad &\text{(every class covers at most 2 requirements)}\\ \text{cap}(g,t) &= 1\\ \text{cap}(c,g) &= 1 \end{align}

Now we run maxflow to find an $s-t-$flow and we are done; while there may be fractional maximum flows, finding an integral one is easily done via an augmenting path algorithm (since all capacities are integral).

---

The problem reminds me of maximum matching, but I can't reduce it to matching off the cuff. Maybe some generalization, not sure.

---
Tags: algorithms, graphs, bipartite-matching
---


title: Maximize ratio of sums

text:
# Question
Title: Maximize ratio of sums
I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a\_{ij}$ for all $i$ in the set $\\{1,2\\}$ and for all $j$ in the set $\\{1,\ldots,n\\}$.

I would like to select a subset $S$ of the columns that maximizes the ratio $$\left(\sum\_{j\in S}a\_{1j}\right) / \left(\sum\_{j\in S}a\_{2j}\right)\\,.$$

Can this be done efficiently? Is this a known problem?

For example, if

$$A=\begin{pmatrix} 1 & 2 \\ 2 & 3\end{pmatrix},$$

then the best thing to do is to choose the second column. Because, (i) if I choose column $1$ I will get $1$ as the sum of the first row and $2$ as the sum of the second row, (ii) if I choose column $2$ I will get $2$ as the sum of the first row and $3$ as the sum of the second row and (iii) if I choose column $1$ and column $2$ I will get $3$ as the sum of the first row and $5$ as the sum of the second row.

# Answer
There's a linear-time algorithm for this problem. Find the index $j$ that maximizes the ratio $r\_j = a\_{1j} / a\_{2j}$. This $r\_j$ is the maximum possible value of the ratio of sums.

Proof: The ratio of sums can be made $\ge c$ if and only if there exists a set $S$ such that $\sum\_{j \in S} a\_{1j} - c a\_{2j} \ge 0$. That's possible iff there exists $j$ such that $a\_{1j} - c a\_{2j} \ge 0$, i.e., such that $a\_{1j}/a\_{2j} \ge c$.

As a tip for how you could discover this on your own: play with some examples. If you try many examples and work out by hand the optimal solution, you might happen to notice the pattern (that the best ratio for the sums matches the largest ratio of columns), and that would give you a hypothesis that you could then try to prove.
> 5 votes

---
Tags: reference-request, optimization, search-problem
---


# Question
Title: How to solve for p in Akra-Bazzi method for analyzing time complexity?
Every single online resource I've looked up on Akra-Bazzi method appears to skip over the same step: They say you have to solve for $p$ without explaining how. If you look up the various PDFs and webpages online, they all basically say "Here's the equation. Solve for $p$. It equals (whatever). Moving on now to the integral..." without explaining how they solved the equation.

If I had to figure it out I could use a binary search but I imagine there is a more mathematical way to get an exact answer.

It is not at all obvious to me how you're supposed to solve for p.

That is:

$$ a\_1 b\_1^p + a\_2 b\_2^p + a\_3 b\_3^p + \dots + a\_k b\_k^p = 1, $$

Where all $a\_i$ terms are positive and all $b\_i$ terms are fractional ($0 \< b\_i \< 1$).

How can you solve for $p$ by hand?

# Answer
> 3 votes
You don't solve for $p$ by hand. You use a computer to get a numerical solution. In general, there is no reason to expect that $p$ have some nice form.

Since the left-hand side of the equation is monotone decreasing, there is at most one solution. Furthermore, when $p \to -\infty$ the left-hand side tends to $\infty$, whereas when $p \to \infty$ it tends to $0$. This shows that a solution does exist. The computer can find it using standard root-finding methods.

This kind of situation is encountered in many other places in computer sciences. Here are two examples:

* The approximation ratio of the Goemans–Williamson algorithm is $$ \min\_{0 \leq \theta \leq \pi} \frac{2}{\pi} \frac{\theta}{1-\cos\theta} \approx 0.878, $$ which doesn't have a closed form. Surprisingly, assuming the *unique games conjecture*, this approximation ratio is the best that polynomial time algorithms can achieve in the worst case.
* Running times of fast matrix multiplication algorithms are of the form $O(n^\rho)$ where $\rho$ is in simple cases the solution of an equation similar to the one you describe, and in other cases the solution of a much more complicated optimization problem. Again, there is no closed form for $\rho$ in most cases (other than Strassen's algorithm, perhaps).

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: Difference between heuristic-based searching and optimal path searching
I'm currently studying for an AI computer-science course. One thing is difficult for me to grasp and somewhat vaguely explained in my course-material:

I understand that with search-methods like e.g. beam search, hill-climbing... you can search based on a certain knowledge about the problem which can tell you in each state an approximation off how close you are to finding the solution. Currently I've reached a chapter about Optimal Search algorithms. An important algorithm in that chapter is Uniform Cost which is based on the lowest accumulated "travel-cost", with as desired consequence that the algorithm will reach a solution in a branch with the lowest accumulated travel cost. Now, I don't understand that travel cost and how it differs from a normal heuristic value. Can someone explain the difference and how it effects finding a solution?

# Answer
> 2 votes
Uniform Cost Search (UCS) does not have a heuristic value and doesn't rely on a heuristic function. I suspect you're getting it confused with some other algorithm (e.g., A\*). In Uniform Cost Search, there's no heuristic: we know exactly what the distance from the starting point was, and we use that to determine which nodes to expand.

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


# Question
Title: What restrictions apply to query and target vector encoding on fast-forward neural networks?
I'm currently studying fast-forward multi-layer neural networks with back propagation, in the book I see that all query and target vectors are binary-encoded, this makes me believe that this is the only allowed encoding, yet all other neurons in the hidden layers and output layer can take on any real value between 0 and 1.

Now I am creating my own neural network and I want to classify an image by using the RGB values of every pixel as input neurons in some way.

So now my question is, as the title states, what restrictions apply to the encoding pattern used for query and target vectors?

# Answer
> 2 votes
The inputs are not restricted to be 0 or 1. They can be arbitrary real numbers. In practice we often normalize or standardize the inputs so that they are in the range $\[-1,+1\]$ (or most of the input values are in that range), but even that is not required, and even then, they can be any real number in that range.

The outputs are also real numbers, and they can be any real number: not limited to 0 or 1, and not limited to a particular range. (In some applications we interpret the outputs using the softmax function -- i.e., we postprocess the outputs of the neural network using another function -- which rescales them to get one likelihood value per output that's in the range $\[0,1\]$, but this is not mandatory and will depend on the specific application setting.)

# Answer
> 2 votes
Using highly variable data for training neural networks (NN) model may induce "overrating". So for practical reasons normalizing (or standardizing) the inputs in NNs can make training faster and reduce the chances of getting stuck in local optima. That the reason for normalizing data. A good choice for inputs is range \[-1:1\]. Another possibility is to scale the inputs to have mean 0 and a variance of 1.

Target normalization depends on the activation function used. For tanh is range \[-1:1\], for sigmoid function, for example, is \[0:1\], and the range arises from the nature of the function (output range). This is valid for continous data in input and output. An "advantage" of range \[0:1\] (sigmoid) is that output of ANN can be interpreted as a posterior probability.

Really, normalization for targets must be in the range \[-0.9:0.9\] or \[0.1:0.9\] (depending of the activation function used) to avoid the asympthotic parts of the function, regions where resolution is smaller.

For clasification problems as yours, output is discrete and not continous. You are two possibilites for your system:

1. example: 5 classes. Output is 1 unit with value continuous between 0 and 5 (normalized in the appropriate range as discussed above). Class is defined by the range where output is located (first class for target between 0 and 1, second class for target between 1 and 2, a so on, obviously in the normalized version);
2. example: 5 classes. 5 neurons target with discrete value 0 or 1. You train the net assigning 1 to correct class for each example and 0 for the other 4 neurons. Practice demonstrates that this option is better.

My suggestion: input normalized in the range \[-1:1\] (continuous variables given RGB values between 0 and 255, I think); output composed by n neurons (in the same number of your target categories for classifier), where only one unit target for each trainig example is assigned to 1 (all other to 0).

I hope I undestanded correctly your question.

---
Tags: machine-learning, neural-networks
---


# Question
Title: Shortest path in a known room for a Roomba
I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search can do this, but I was left wondering if you could minimize the backtracking.

I looked into how it's actually done for Roomba and from what I read on Robotics stack exchange, it doesn't use a deterministic algorithm that guarantees shortest distance, because it doesn't know the room layout and obstacles ahead of time.

But what if we did know the full layout of the room at the start? Is there a way to use a map to generate a path through the room with minimum backtracking? In this example, the map is an undirected graph without weights (or every joining edge distance is 1), and it likely contains cycles.

The problem sounds similar to travelling salesman and Hamiltonian paths, but I don't think it maps to them exactly. Travelling salesman and Hamiltonian paths have the requirement that vertices are only visited once. In the Roomba example, we don't care if it vacuums the same spot twice, we just want it to thoroughly vacuum the whole room (don't miss anywhere) as fast as possible.

# Answer
> -2 votes
the classic A\* algorithm was invented in 1968 and is used for the purpose of shortest path-finding by robots, and it is provably optimum in a limited sense (eg given an unchanging layout and other constraints). there are many other pathfinding algorithm variants, basically "smart graph traversal" algorithms, eg focused on the online problem with changing constraints, see eg "how do state of the art pathfinding algorithms differ", cstheory.

here is some information on the roomba algorithm which is somewhat proprietary based on an interview with one of the designers (the interview seems no longer available). it is somewhat random and apparently uses a locally optimizing algorithm aka "greedy".

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


# Question
Title: Isn't polynomial identity testing over arithmetic *expressions* trivial?
Polynomial identity testing is the standard example of a problem known to be in **co-RP** but not known to be in **P**. Over arithmetic *circuits*, it does indeed seem hard, since the degree of the polynomial can be made exponentially large by repeated squaring. This question addresses the issue of how to work around this and keep the problem in randomized polynomial time.

On the other hand, when the problem is initially presented (e.g. here), it is often illustrated over arithmetic *expressions* containing only constants, variables, addition, and multiplication. Such polynomials have total degree at most polynomial in the length of the input expression, and for any such polynomial the size of the output value is polynomial in the size of the input values. But since a polynomial of degree $d$ has at most $d$ roots, isn't this trivial? Just evaluate the polynomial over the rationals at *any* $d + 1$ distinct points and check whether the result is zero at each point. This should take only polynomial time. Is this correct? If so, why are arithmetic expressions without shared subexpressions often used as examples, when sharing is essential to the difficulty of the problem?

# Answer
That isn't known to be trivial.

The polynomial $x \cdot y$  has infinitely many roots. (When either variable is zero, the other variable won't affect the polynomial's value.)
> 6 votes

# Answer
For a *univariate* polynomial $p(x)$, yes, it's that easy.

For a *multivariate* polynomial $p(x\_1,x\_2,\dots,x\_k)$, no, no such algorithm works.

In particular, when you write "a polynomial of degree $d$ has at most $d$ roots", that is true for univariate polynomials $p(x)$, but it is not true in general for multivariate polynomials. Ricky Demer gives a simple example: $p(x,y) = xy$ is of degree two, but has infinitely many roots.
> 7 votes

# Answer
heres a more general/ abstract way to understand the significance/ hardness of polynomial identity testing in CS. one reason polynomial identity testing is under intense study right now because it has long been known to be closely linked to boolean circuit complexity. imagine taking two arbitrary boolean circuits and then converting them (ie basically setting up a 1-1 mapping) to multivariate polynomials. this is not so hard. basically one uses values of 0/1 to represent false/ true and the constructions are set up in old papers. then the roots of the polynomial correspond to T/F variable assignments that satisfy the formulas/ circuits.

after this setup, PIT is basically nearly the same problem as determining if two binary circuits are equivalent. there are also other (newer) deep proofs that say its nearly equivalent in complexity to factoring polynomials.\[\] so one ends up with a result like the following: if one can solve PIT "quickly" it means that two large circuits can be compared for equivalence "quickly" which is unlikely. so a rough way to understand the problem is that its nearly equivalent to nontrivial problems in boolean circuit theory.
> -1 votes

---
Tags: randomized-algorithms, polynomial-time, circuits
---


# Question
Title: Finding cache block transfer time in a 3 level memory system
Following question was asked in one of entrance exams for a graduation programme. Please help me try to solve it :

> A computer system has an L1 cache, an L2 cache, and a main memory unity connected as shown below. The block size in L1 cache is 4 words. The block size in L2 cache is 16 words. The memory access times are 2 nanoseconds, 20 nanoseconds and 200 nanoseconds for L1 cache, L2 cache and main memory unit respectively.
>
> 1. When there is a miss in L1 cache and a hit in L2 cache, a block is transferred from L2 cache to L1 cache. What is the time taken for this transfer?
>
> (A) 2 nanoseconds (B) 20 nanoseconds (C) 22 nanoseconds (D) 88 nanoseconds
>
> 2. When there is a miss in both L1 cache and L2 cache, first a block is transferred from main memory to L2 cache, and then a block is transferred from L2 cache to L1 cache. What is the total time taken for these transfers?
>
> (A) 222 nanoseconds (B) 888 nanoseconds (C) 902 nanoseconds (D) 968 nanoseconds

First thing that came to my mind was, how to calculate the transfer time using the given access time. During a miss, a block of data is moved from main memory to cache. Then CPU will access it. So, wouldn't be access time \> transfer time ?

Then I thought, lets assume access time = transfer time & do the calculation.

Now first question. The question already states there is a miss in L1, so I will not consider L1 access time. Since there is a miss in L1 & hit in L2, a entire block from L2 has to be moved to L1. L2 block size is 16 words, but data bus size is 4 words.

So we have to move 4 words * 4 times.

To transfer 4 word it takes 20 ns. To transfer 4 words, its 80ns. Isn't it the time transferred from L2 to L1 ? The question does not say anything about accessing L1 after moving the data. But 80ns is not in the option !

Similar case with second question also.

Time to move main memory to L2 = 4 words * 4 times = 4 * 200 = 800ns

Time to move L2 to L1 = 80ns \[earlier calculation\]

So total time taken is 880ns. Which is again not in the option.

Either I am doing a very big mistake or options are wrong or question isn't framed correctly. If I am doing anything wrong, please give me some hint & I will try to work on this exercise again.

# Answer
> 3 votes
In order to find that any cache does *not* contain the value at the requested address you have to access it.

> That means you have to add up the access times of all contributing levels.

Some of the options seem to suggest one might think that whole blocks from, say, L2 cache are transferred upwards to L1 cache; as far as I know, that is not what happens: transfer volume is determined by the block size of the requesting level.

# Answer
> 6 votes
I guess you got the access time wrong. Access time means time to locate a data on a memory. So, whoever accesses the memory (be it CPU or some other device) it will be the same.

Coming to first question here. A block is transferred from L2 to L1. And L1 block size being 4 words and data bandwidth being 4 bytes, it requires 1 L2 access (for read) and 1 L1 access (for store). So, time = 20+2 = 22 ns.

For the second question, L2 block size being 16 words and bandwidth between memory and L2 being 4 words, we require 4 memory access (for read) and 4 L2 access (for store). Now, we need to send the requested block to L1 which would require 1 more L2 access (for read) and 1 L1 access (for store). So, total time

= 4 * (200 + 20) + (20 + 2)

= 880 + 22

= 902 ns

# Answer
> 0 votes
answer for 1 question :

to transfer the block from l2 to l1 , generally it takes 20+2 ns to transfer 4 words : here why only words means we have a databus with capacity 4 words, so due to miss l1 and hit l2 , we have to transfer a block of l2 which contains 16 words.. so here we have to access the l2 an l1 4 times. so 4(20+2)..

similarly answer for the 2 question :

main memory to l2 and l2 to l1 so 4(200+20) + 4(20+2)

---
Tags: computer-architecture, cpu-cache, memory-access
---


# Question
Title: Different characterization of $\Delta_2^P$
$\Delta\_2^P =P^{NP}$, is the set of all languages decidable by a polynomial Turing machine with access to a SAT oracle. I came across a definition of $\Delta\_2^P$ as the set of all languages $L$ such that there exists $L\_1\in NP, L\_2\in coNP$ where $L=L\_1\cap L\_2$.

I'm trying to prove that a language in $P^{NP}$ can be expressed by such intersection. Let $L$ be some language in $P^{NP}$, $x\in L$ if $M$ (the machine with access to a SAT oracle) accepts $x$ using some transcript $w$ (the answer of the oracle to the queries raised by $M$). I need to make sure $w$ is a valid transcript (i.e. doesn't lie by giving no answers for satisfiable formulas or yes answers for unsatisfiable formulas). I tried somehow encoding this condition in an intersection of a language in $NP$ with a language in $coNP$, but didn't succeed. Can you give a description of $L\in P^{NP}$ using such intersection?

# Answer
> 4 votes
That set is BH2, and BH is a subset of PNP.    If  BH ⊆ BH2  "then the polynomial hierarchy collapses to" BH3(2), where BH3(2) is the 2nd "level of the Boolean hierarchy over $\Sigma\_2^P$."

(So, to answer your question:  No, I can't give such a description.)

---
Tags: complexity-theory
---


# Question
Title: Step by step method for generating Regular Expressions for languages
I was wondering if there was a method that can be used to generate a Regular Expression for a language. Take the Language $L$ as an example where:

$L= \\{w \in \\{0, 1\\}^{\ast} \mid \text{length of } w \text{ is a multiple of } 2 \text{ or } 3\\}.$

Can you show the step by step method to make the `RE` for this language? Cheers

# Answer
> 0 votes
**Hint:** Let's denote $w\_{\text{two}}$ words with length that is a multiple of $2$

and $w\_{\text{three}}$ words with length that is a multiple of $3$

So think about:

$$|w\_{\text{three}}|\bigg|\_{3}\cup|w\_{\text{two}}|\bigg|\_{2}$$

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


# Question
Title: Terminology needed for the computational solution to the Rubik's Cube
I apologize if this question is out of the guidelines of this forum. If it is please let me know and I will abstain from requesting definitions and terminology.

Hello! I am currently writing a program to find the shortest path solution in a randomised Rubik's Cube. There is a certain language/search based methodology that has caught my attention, and which I would like to apply to the solution, but I am unaware of what kind of terminology I should be looking up.

THE METHODOLOGY:

The methodology is one where different languages are developed to satisfy different aspects of the cubes solution. For instance, we might find a language/grammar which appropriately describes/generates all transformations which move one block of the cube to some position we want it to be. We may then find another language which satisfies the movement of another block to some position we want it to be. The language which satisfies both of these languages is the one which generates transformations which will move BOTH blocks to where they are supposed to be.

WHAT I WOULD LIKE TO LEARN MORE ABOUT:

It is in this sense that I am interested in learning more about how languages can be tested against each other in order to CONSTRAIN the otherwise unweildly "search tree" that would be required to be derived and searched in order to find the solution.

At the same time I would like to build a symbolic vocabulary which would allow me to compare the different pertinent variables (runtime, memory size, etc.) of different tree search constraint methodologies, particularly language based methods (as I have poorly defined them).

I am also particularly interested in the methodologies that can be used to detect patterns in the strings which are satisfying two seperate languages so that a third language which satisfies both can be developed.

Also, I would like to learn more about how we can show that one language is mutually exclusive to another language.

I am particularly interested in terminology so that I might do research on the Internet, however I would also greatly appreciate any book recommendations. Thank You!

# Answer
> 3 votes
Kociemba wrote very nice algorithm, which is the fastest working algorithm returning optimal or almost optimal solution very efficiently.

If you want to derive your own system, try in steps:
0) invent notation for the cube, do not try to optimize it.
1) try BFS or something like A\* (this one will be harder, with heuristics).
2) try some kind of memoization, and state precomputation.
3) if something is not efficient step back to 0 and change type of notation.

Why should you not optimize your notation?
Because a few bytes overhead is nothing in compare to smooth transitions between states.

Honestly, pure BFS will do the job, but without any help or reductions it will be very slow. You can make encoding relative to color and put your reference point (one corner or the cross), it will decrease hashing time.
To check your approach just take several thousands of permuted cubes, count turns per cube and time it took per cube to solve.
If you are interested in AI, solving cube is doable, but guaranteed least moves will take some time.

There is Rubik Group but language induced solvers in contrary to graph or group solvers are not common, so there might be some hidden treasure there. Look at Kociemba algorithm, he does not use Rubik Cube group per se, but changes it so he has smaller number of instances.

# Answer
> 2 votes
It sounds like you want to compute the intersection of two languages. Depending upon what kind of languages you are looking at and how they're represented, you might look into the "product construction" and closure properties for your class of languages.

For instance, for regular languages, there is a standard method for computing the intersection of two regular languages (expressed as automata) using what's known as "the product construction". On the other hand, computing the intersection of two context-free languages is undecidable in the general case.

You mention search trees and efficiently incorporating multiple constraints into the search process. It seems possible that the formalizations of "languages" from automata theory might not be useful to you, and that thinking of this as languages might not be a useful perspective in the end. For instance, you might be more interested in work from the artificial intelligence field (e.g., A\* and other search algorithms).

# Answer
> 2 votes
have not heard of use of abstract languages to model the rubiks cube. however, there is a huge amount of group theory intrinsically associated with it, and there are natural ways to represent group theory using languages (and automata). as for using the theory to *solve* the cube, there are many standard algorithms and it would be difficult for newcomers to invent them.

here is a very thorough introductory reference on group theory in the rubiks cube aimed at gifted high school students. the 2nd paper has much of the theory with an eye toward an algorithmic solution where group operations are modelled as "macros". the 3rd ref compares basic cube algorithms performance.

---
Tags: formal-languages, terminology, modelling, domain-specific-languages
---


# Question
Title: Sum to a certain value of a group of integers
Take a group filled with an arbitrary number of random integers. Is there any way of finding out whether it is possible for the sum of the integers can equal a certain number, with the condition that any of the integers can (but do not have to) be multiplied by 0 or -1?

The only possible solution I could think of was to have the algorithm test all possible sums with each integer multiplied by 0 or -1, but this seems to be extremely inefficient, especially with larger groups of integers.

Example:

> 2 40 6 7 6 2 can sum to 30 (\[0\*2\] \[40\] \[-1\*6\] \[0\*7\] \[-1\*6\] \[2\])

# Answer
> 2 votes
This is basically the subset sum problem, which is well-studied. In particular, there is no efficient algorithm for solving all instances of this problem.

There's a small twist in your version of the problem: you allow multiplying numbers by -1. However, your problem can still be reduced to the subset problem, by simply appending the negation of all numbers in your list to the list; then you have an instance of the subset sum problem. For instance, if your list is 2 40 6 7 6 2, you ask whether a subset of 2 40 6 7 6 2 -2 -40 -6 -7 -6 -2 can sum to 30. That's an instance of the subset sum problem.

If the numbers are not too large, you can use the standard dynamic programming algorithm, and it will be pretty efficient. But this fails if the numbers are large.

---
Tags: algorithms, integers
---


# Question
Title: Is there a name for algorithms which detect nearly-similar structures?
I'm interested in how you might detect similarities in tree structures. For example, in these three JSON documents;

```
(a)   { name="foo", length=23 }
(b)   { name="boo", length=99, redundant=true }
(c)   { quux="baz", a=44, b=66, c=99 }

```

it's obvious to the human eye that (a) and (b) are more similar, in content and structure, than (a) and (c). However, I don't know of heuristics I might use to quantify that similarity.

I'm sure such algorithms exist -- they might exist, say, in code that detects similarities in parse trees or abstract syntax trees, to detect duplicate code structures -- but I've no idea how to search for more information because I don't know what to look for.

Is there a name for this kind of algorithm, where you're looking to be able to calculate 'near-ness' between different trees, graphs, or sets?

(*Aside: I've just found out about the Levenshtein Distance so maybe there is a common technique like 'print out your data structures as strings and calculate distances between the printed strings' but I'm very new to the concept.*)

# Answer
The search terms you're probably looking for are "similarity measure", "dissimilarity", "distance function", or "metric"... applied to trees.

---

One approach to your probem is to invent a similarity measure or distance function/metric that can be applied directly to tree. There are some references on that at https://stackoverflow.com/q/21897879/781723. You can also easily envision some recursive algorithms for doing that. For instance, if a tree $T$ has children $T\_1,T\_2$ (i.e., the left and right subtrees of $T$), you could define

$$d(T,T') = d(T\_1,T'\_1) + d(T\_2,T'\_2),$$

with some way to bottom out the recursion at leaves (e.g., if leaves are strings, then use edit distance at the leaves). You could also combine the distances of the child subtrees in some other way, e.g.,

$$d(T,T') = \sqrt{d(T\_1,T'\_1)^2 + d(T\_2,T'\_2)^2}$$

or using any other norm.

Another approach is to identify a set of features that capture aspects of the trees that are important to you. Then, each tree can be mapped to a feature vector, and you can measure similarity between two trees by computing the similarity of the two feature vectors. There are many distance metrics one can use on feature vectors (e.g., L1 norm, L2 norm, etc.)

In some cases, there are sophisticated techniques that can be used to speed up the feature-vector-based approach. See https://en.wikipedia.org/wiki/Tree\_kernel.

Finally, you could also look at techniques like shingling or minhash and try modifying them to apply to trees instead of strings/sets.
> 3 votes

---
Tags: algorithms, heuristics
---


title: String Comparison vs. Hashing

text:
# Question
Title: String Comparison vs. Hashing
I recently learned about the rolling hash data structure, and basically one of its prime uses to searching for a substring within a string. Here are some advantages that I noticed:

* Comparing two strings can be expensive so this should be avoided if possible
* Hashing the strings and comparing the hashes is generally much faster than comparing strings, however rehashing the new substring each time traditionally takes linear time
* A rolling hash is able to rehash the new substring in constant time, making it much quicker and more efficient for this task

I went ahead and implemented a rolling hash in JavaScript and began to analyze the speed between a rolling hash, traditional rehashing, and just comparing the substrings against each other.

In my findings, the larger the substring, the longer it took for the traditional rehashing approach to run (as expected) where the rolling hash ran incredibly fast (as expected). However, comparing the substrings together ran much faster than the rolling hash. How could this be?

For the sake of perspective, let's say the running times for the functions searching through a ~2.4 million character string for a 100 character substring were the following:

* **Rolling Hash** \- 0.691 seconds
* **Traditional Rehashing** \- 71.009 seconds
* **Just comparing the strings (no hashing)** 0.100 seconds

How could the string comparing be so much faster than the rolling hash? Could it just have something to do with the particular language I tested this in? Strings are a primitive type in JavaScript; would this cause string comparisons to run in constant time?

# Answer
> 5 votes
One possible hypothesis:

Javascript is interpreted, which can slow things down.

When you compare two strings, this will invoke a string comparison routine that is coded directly in assembly language or C, and thus string comparison will probably be about as fast as the architecture can possibly compare strings. In contrast, when you hash strings, you have to execute multiple instructions in Javascript, which might incur overhead from an interpreter.

Another possible hypothesis:

Numbers in Javascript are a floating-point type. There is no integer type in Javascript. Your rolling hash probably involves what looks like integer arithmetic. However, under the covers this is probably getting interpreted as operations on double-precision floats, which can be a bit slower. This might also make your hash-based schemes slower. Some Javascript engines might optimize this to integer arithmetic in certain circumstances, but no guarantees about whether any particular Javascript engine will or won't be able to do that in any particular case.

# Answer
> 3 votes
Comparing two strings can be really fast if their initial segments differ. String comparison is usually implemented with a loop over the characters, immediately returning false if any one of them differs and returning true when all characters have been examined.

If the strings being compared differ in one of their first characters, then such a comparison function would run really fast. If your strings were "random" then this very likely explains why the string comparison route was so fast.

To get the string comparison approach to display its worst case, I suggest testing it by searching for

> aaaa \[...\] aaaab

in a string consisting entirely of a's. This will trigger the worst case every time.

# Answer
> 2 votes
Numbers are double in standard, you can do typed array, overhead comes mainly from missuse of functions, closures and types.

Problem is strictly in JS usage - C has one byte char\*, JS uses multibyte.
Optimizing for integers is possible in two scenarios - all operations are truncated or typed arrays are used, otherwise no can do.

Although this is my fav lang, its quirks are heavy...

Also there is one very big problem - modulo operator is defined on doubles, while in the most programming languages it is defined for integers, also sign is expected to be +.
In JS % is defined for double precission - so it is the bottleneck when used with $var$.
Without actually showing the code any guess is valid.

The problem you are suffering is strictly due to implementation, and browser (or node.js or whathever environment you are using) it is not comming from concept, but if you think otherwise, maybe test cases are not reasonable enough.
If you have small amount of strings or they differ on first places - compare is faster as this is built in.

The next step is really looking at your code, as this is not any code review, but JS review - take into account all quirks, types and operations.

Remember that built in sort operate on strings (not doubles), so on the first glance everything should work but it slows somewhere on the type coercion or toString function.
Intermixing strings and numbers is possible, resulting type is not symmetric.

Also take DOM operations in profiling separately - putting your result into DOM context results in repainting and reflow on the whole page.

Try to make local variables and denote $const$ where you can, profile code, if some operation is out of blue too heavy, probable type coercion or prototype chaining kicked in, which is devastating in execution time and makes it impossible to optimize in advance.

If your variables are out of the scope - force them by reference to local variables or rewrite code, try jsperf for similar tasks, try using strict code.

---
Tags: programming-languages, runtime-analysis
---


# Question
Title: Formulating a constraint to exclude a single point from the feasible region of an IP?
Consider a basic integer program such as:

$$\begin{align} \min\_x & \quad c^Tx \\ \text{s.t.} & \quad Ax \leq b \\ &\quad x\_i \in \\{-100,\ldots,100\\} \end{align} $$

where $x \in \mathbb{Z}^n, A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$.

Say that I have a point $y \in \mathbb{Z}^n \cap \[-100,100\]^n$ that I would like to exclude from the feasible region.

I am wondering if there is an elegant way to do this without introducing new variables to the formulation? If there is no way to exclude $y$ from the feasible region without adding new variables to the formulation, then is an approach that allows me to do this by adding the fewest possible variables?

I should add that this question is loosely related to a different question that I posted here a few months ago (though there was no concrete answer given to that one either).

# Answer
You need to add an integer cut of the form: $$ \sum\_i |x\_i - y\_i| \ge 1 $$ where $y\_i$ is your point your want to exclude.

We can rewrite this as: $$ \begin{align} &\sum\_i z\_i \ge 1 \\ &z\_i \le |x\_i - y\_i| \end{align} $$ The last inequality is identical to $z\_i \le \max\\{x\_i-y\_i, -(x\_i-y\_i)\\}$. This again can be implemented using additional binary variables: $$ \begin{align} &z\_i\le x\_i-y\_i+M\_i\delta\_i \\ &z\_i\le -(x\_i-y\_i)+M\_i(1-\delta\_i) \\ &\delta\_i \in \\{0,1\\} \\ &M\_i = U\_i - L\_i = 200 \end{align} $$ There are two special cases we can handle more efficiently. If $y\_i=L\_i=-100$ then we can write $z\_i = x\_i - y\_i$. If $y\_i=U\_i=100$ then we can write $z\_i=-(x\_i-y\_i)$.
> 3 votes

# Answer
Here's one possible approach you could try, though I don't know if it will be optimal. One heuristic is to pick a random vector $d$, and then look for solutions where either $d^T x \< d^T y$ or $d^T x \> d^T y$. In other words, we pick a random vector $d$, and then we solve the two integer programs

* $\min c^T x$ such that $Ax \le b$, $d^T x \< d^T y$ (note that $d^T y$ is a known constant), $|x\_i| \le 100$.
* $\min c^T x$ such that $Ax \le b$, $d^T x \> d^T y$, $|x\_i| \le 100$.

and then check to see whether either has a solution.

For instance, you might choose $d$ randomly from $\\{-1,0,1\\}^n$, or even from $\\{-100,\dots,100\\}^n$.

Warning: This is not a principled solution: it's possible that all other optimal solutions to the integer program just happen to satisfy $d^T x = d^T y$. The idea is that, if you choose $d$ randomly, this is unlikely to hold: it would require that $d^T (x-y)=0$, and for any fixed $x,y$ with $x\ne y$, the probability of that is relatively small. However, this is not an absolute guarantee, and it's certainly possible that you could get unlucky and miss out on optimal solution in this way.

There are some ways to reduce the probability of missing an optimal solution, but you can't reduce it to zero with this approach. The domain from which you choose $d$ affects the probability: the larger the range of possible values for each coordinate of $d$, the smaller the probability will be. Also, if you wished, you could repeat this procedure multiple times to reduce the likelihood of missing out on an optimal solution, but I don't know if that tradeoff will be worth it in a practical application.

---

\[ Equivalently, instead of solving two integer programs, you can solve add a new variable and solve just one integer program. In particular, introduce a new zero-or-one variable $z$ and add the constraints $0 \le z \le 1$, $d^T x \< d^T y + Cz$, $d^T x \> d^T y - C(1-z)$, where $C$ is a very large constant, say $C \> d^T y + 100 ||d||\_1$. This is equivalent to solving those two integer programs, though I don't know that there's any particular advantage to this instead of solving two separate integer programs. \]
> 1 votes

---
Tags: discrete-mathematics, integer-programming
---


# Question
Title: What is the difference between Abstract Data Types and objects?
An answer on Programmers.SE characterizes an essay by Cook (Objects are not ADTs) as saying

> * Objects behave like a characteristic function over the values of a type, rather than as an algebra. Objects use procedural abstraction rather than type abstraction
> * ADTs usually have a unique implementation in a program. When one's language has modules, it's possible to have multiple implementations of an ADT, but they can't usually interoperate.

It seems to me that, in Cook's essay, it just happens to be the case that for the specific example of a set used in Cook's paper, an object can be viewed as a characteristic function. I don't think that objects, in general can be viewed as characteristic functions.

Also, Aldritch's paper The power of interoperability: Why objects are inevitable¹ suggests

> Cook’s definition essentially identifies dynamic dispatch as the most important characteristic of object

agreeing with this and with Alan Kay when he said

> OOP to me means only messaging, local retention and protection and hiding of state-process, and extreme late-binding of all things.

However, these companion lecture slides to Aldritch's paper suggest that Java *classes* are ADTs while Java interfaces are objects -- and indeed using interfaces "objects" can inter-operate (one of the key features of OOP as given by one of the bullet points above).

My questions are

1. Am I correct to say that characteristic functions are not a key feature of objects and that Frank Shearar is mistaken?
2. Are data that talk to each other through Java interfaces examples of objects even though they don't use dynamic dispatch? Why? (My understanding is that dynamic dispatch is more flexible, and that interfaces are a step towards objective-C/smalltalk/erlang style messaging.)
3. Is the idea of dependency inversion principle related to the distinction between ADTs and objects? (See the Wikipedia page or The Talking Objects: A Tale About Message-Oriented Programming) Although I'm new to the concept, I understand that it involves adding interfaces between "layers" of a program (see wikipedia page diagram).
4. Please provide any other examples/clarifications of the distinction between objects and ADTs, if you want.

¹ <sub> This paper (published in 2013) is easy reading and summarizes Cook's 2009 paper with examples in Java. I highly recommend at least skimming it, not to answer this question, but just because it's a good paper. </sub>

# Answer
> 9 votes
Google brought up a similar question with an answer that I think is very good. I've quoted it below.

> There's another distinction lurking here that is explained in the Cook essay I linked.
>
> Objects are not the only way to implement abstraction. Not everything is an object. Objects implement something which some people call procedural data abstraction. Abstract data types implement a different form of abstraction.
>
> A key difference appears when you consider binary methods/functions. With procedural data abstraction (objects), you might write something like this for an Int set interface:
>
> ```
> interface IntSet {
>   void unionWith(IntSet s);
>   ...
> }
>
> ```
>
> Now consider two implementations of IntSet, say one that's backed by lists and one that's backed by a more efficient binary tree structure:
>
> ```
> class ListIntSet implements IntSet {
>   void unionWith(IntSet s){ ... }
> }
> class BSTIntSet implements IntSet {
>   void unionWith(IntSet s){ ... }
> }
>
> ```
>
> Notice that unionWith must take an IntSet argument. Not the more specific type like ListIntSet or BSTIntSet. This means that the BSTIntSet implementation cannot assume that its input is a BSTIntSet and use that fact to give an efficient implementation. (It could use some run time type information to check it and use a more efficient algorithm if it is, but it still could be passed a ListIntSet and have to fall back to a less efficient algorithm).
>
> Compare this to ADTs, where you may write something more like the following in a signature or header file:
>
> ```
> typedef struct IntSetStruct *IntSetType;
> void union(IntSetType s1, IntSetType s2);
>
> ```
>
> We program against this interface. Notably, the type is left abstract. You don't get to know what it is. Then we have a BST implementation then provides a concrete type and operations:
>
> ```
> struct IntSetStruct {
>  int value;
>  struct IntSetStruct* left;
>  struct IntSetStruct* right;
> }
>
> void union(IntSetType s1, IntSetType s2){ ... }
>
> ```
>
> Now union actually knows the concrete representations of both s1 and s2, so it can exploit this for an efficient implementation. We can also write a list backed implementation and choose to link with that instead.
>
> I've written C(ish) syntax, but you should look at e.g. Standard ML for abstract data types done properly (where you can e.g. actually use more than one implementation of an ADT in the same program roughly by qualifying the types: BSTImpl.IntSetStruct and ListImpl.IntSetStruct, say)
>
> The converse of this is that procedural data abstraction (objects) allow you to easily introduce new implementations that work with your old ones. e.g. you can write your own custom LoggingIntSet implementation, and union it with a BSTIntSet. But this is a trade-off: you lose informative types for binary methods! Often you end up having to expose more functionality and implementation details in your interface than you would with an ADT implementation. Now I feel like I'm just retyping the Cook essay, so really, read it!

I would like to add an example to this.

Cook suggests that an example of an abstract data type is a module in C. Indeed, modules in C involve information hiding, since there are public functions that are exported through a header file, and static (private) functions that don't. Additionally, often there are constructors (e.g. list\_new()) and observers (e.g. list\_getListHead()).

A key point of what makes, say, a list module called LIST\_MODULE\_SINGLY\_LINKED an ADT is that the functions of the module (e.g. list\_getListHead()) assume that the data being input has been created by the constructor of LIST\_MODULE\_SINGLY\_LINKED, as opposed to any "equivalent" implementation of a list (e.g LIST\_MODULE\_DYNAMIC\_ARRAY). This means that the functions of LIST\_MODULE\_SINGLY\_LINKED can assume, in their implementation, a particular representation (e.g. a singly linked list).

LIST\_MODULE\_SINGLY\_LINKED cannot inter-operate with LIST\_MODULE\_DYNAMIC\_ARRAY because we can't feed data created, say with the constructor of LIST\_MODULE\_DYNAMIC\_ARRAY, to the observer of LIST\_MODULE\_SINGLY\_LINKED because LIST\_MODULE\_SINGLY\_LINKED assumes a representation for a list (as opposed to an object, which only assumes a behaviour).

This is analogous to a way that two different groups from abstract algebra cannot interoperate (that is, you can't take the product of an element of one group with an element of another group). This is because groups assume the closure property of group (the product of elements in a group must be in the group). However, if we can prove that two different groups are in fact subgroups of another group G, then we can use the product of G to add two elements, one from each of the two groups.

**Comparing the ADTs and objects**

* Cook ties the difference between ADTs and objects partially to the expression problem. Roughly speaking, ADTs are coupled with generic functions that are often implemented in functional programming languages, while objects are coupled with Java "objects" accessed through interfaces. For the purposes of this text, a generic function is a function that takes in some arguments ARGS and a type TYPE (pre-condition); based on TYPE it selects the appropriate function, and evaluates it with ARGS (post-condition). Both generic functions and objects implement polymorphism, but with generic functions, the programmer KNOWS which function will be executed by the generic function without looking at the code of the generic function. With objects on the other hand, the programmer does not know how the object will handle the arguments, unless the programmers looks at the code of the object.
* Usually the expression problem is thought of in terms of "do I have lots of representations?" vs. "do I have lots of functions with few representation". In the first case one should organize code by representation (as is most common, especially in Java). In the second case one should organize code by functions (i.e. having a single generic function handle multiple representations).
* If you organize your code by representation, then, if you want to add extra functionality, you are *forced* to add the functionality to every representation of the object; in this sense adding functionality is not "additive". If you organize your code by functionality, then, if you want to add an extra representation - you are *forced* to add the representation to every object; in this sense adding representations in not "additive".

**Advantage of ADTs over objects**

* Adding functionality is additive
* Possible to leverage knowledge of the representation of an ADT for performance, or to prove that the ADT will guarantee some postcondition given a precondition. This means that programming with ADTs is about doing the right things in the right order (chaining together pre-conditions and post-conditions towards a "goal" post condition).

**Advantages of objects over ADTs**

* Adding representations in additive
* Objects can inter-operate
* It's possible to specify pre/post conditions for an object, and chain these together as is the case with ADTs. In this case, the advantages of objects are that (1) it's easy to change representations without changing the interface and (2) objects can inter-operate. However, this defeats the purpose of OOP in the sense of smalltalk. (see section "Alan Kay's version of OOP)

**Dynamic dispatch is key to OOP**

It should be apparent now that dynamic dispatch (i.e. late binding) is essential for object oriented programming. This is so that it's possible to define procedures in a generic way, that doesn't assume a particular representation. To be concrete - object oriented programming is easy in python, because it's possible to program methods of an object in a way that doesn't assume a particular representation. This is why python doesn't need interfaces like Java.

In Java, classes are ADTs. however, a class accessed through the interface it implements is an object.

**Addendum: Alan Kay's version of OOP**

Alan Kay explicitly referred to objects as "families of algebras", and Cook suggests that an ADT is an algebra. Hence Kay likely meant that an object is a family of ADTs. That is, an object is the collection of all classes that satisfy a Java interface.

However, the picture of objects painted by Cook is far more restrictive than Alan Kay's vision. He wanted objects to behave as computers in a network, or as biological cells. The idea was to apply the principle of least commitment to programming - so that it's easy to change low level layers of an ADT once the high level layers have been built using them. With this picture in mind, Java interfaces are too restrictive because they don't *allow an object to interpret the meaning of a message*, or even ignore it completely.

In summary, the key idea of objects, for Kay - is *not* that they are a family of algebras (as is emphasized by Cook). Rather, the key idea of Kay was to apply a model that worked in the large (computers in a network) to the small (objects in a program).

edit: Another clarification on Kay's version of OOP: The purpose of objects is to move closer to a declarative ideal. We should tell the object what to do - not tell it *how* by micromanaging is state, as is customary with procedural programming and ADTs. More info can be found here, here, here, and here.

edit: I found a very, very good exposition of Alan Kay's definition of OOP here.

# Answer
> 4 votes
If you look at the ADT proponents, they consider an ADT to be what OOP would call a class (internal, private state; a limited set of operations allowed), but no relation between classes (no inheritance, basically) is considered. The point being instead that the same behaviour can be obtained with different implementations. E.g. a set can be implemented as a list, elements in an array or hashtable, or some sort of tree.

# Answer
> 3 votes
I always understood it this way:

1. An ADT is an interface: it is just a collection of methods, their type-signatures, possibly with pre-and-post conditions.
2. A class can *implement* one or more ADTs, by giving actual implementations for the methods specified in the ADT.
3. An object is an *instance* of a class, with its own copy of any non-static variables.

It's possible that in the literature, the distinctions different, but this is the "standard" terminology you will hear in computer science.

For example, in Java, `Collection` is an ADT, `ArrayList` is a class, and you can make an `ArrayList` object with the `new` operator.

As for the statement that ADTs usually only have one implementation, this is often not the case. For example, it's possible you would want to use both tree-based and hashtable-based dictionaries in your program, depending on what you're storing. They would share an ADT, but would use different implementations.

---
Tags: programming-languages, object-oriented, abstract-data-types
---


# Question
Title: Merge two sorted arrays without using additional memory
We have two sorted arrays of integers. Without using additional memory we need to merge these two arrays such that the smallest numbers are in the 1st array and the remaining numbers are in the second array.

For instance, if your two arrays are $A=\[1,3,9,14\]$ and $B=\[2,4,15\]$, the result should be $A=\[1,2,3,4\], B=\[9,14,15\]$. Entries are integers, and you can use only $O(1)$ extra memory for auxiliary variables.

# Answer
> -2 votes
Here, great solution, from: http://www.geeksforgeeks.org/merge-two-sorted-arrays-o1-extra-space/

Below is C++ implementation of above algorithm.

```
// C++ program for implementation of Sieve of Atkin
#include <bits/stdc++.h>
using namespace std;

// Merge ar1[] and ar2[] with O(1) extra space
void merge(int ar1[], int ar2[], int m, int n)
{
    // Iterate through all elements of ar2[] starting from
    // the last element
    for (int i=n-1; i>=0; i--)
    {
        /* Find the smallest element greater than ar2[i]. Move all
           elements one position ahead till the smallest greater
           element is not found */
        int j, last = ar1[m-1];
        for (j=m-1; j >= 0 && ar1[j] > ar2[i]; j--)
            ar1[j+1] = ar1[j];

        // If there was a greater element
        if (j != m-1)
        {
            ar1[j+1] = ar2[i];
            ar2[i] = last;
        }
    }
}

```

---
Tags: algorithms, sorting, arrays, in-place
---


# Question
Title: Undecidable language and Turing Machines
I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about.

> If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine that recognizes the complement of A?

To my understanding this turing machines accept states, are all those that were of the rejection states in the first Turing Machine. Also seeing as the Language is undecidable, this Turing Machine will not halt for strings that are not in the language.

Can someone please tell me if my understanding is correct or not, and if not give me some clarification?

# Answer
> To my understanding this turing machines accept states, are all those that were of the rejection states in the first Turing Machine.

You presume to know something about how the machine for $\overline{A}$ was built; don't, because you can't.

What's more, this construction (flipping accepting states) does not work for TMs that do not always halt, as any one for $A$ *has* to be.

Thus, a semi-decider for $\overline{A}$ has to look differently from what you describe.

---

Regarding the original problem you were given, it is a weird formulation to test your understanding of basic closure properties.

*Hint:* Assume there was a semi-decider for $\overline{A}$. What follows about $A$?
> 1 votes

# Answer
You can conclude that it doesn't exist. If $L$ is recursively emumerable, but not recursive, then $\overline{L}$ is not recursive enumerable, i.e., there is no Turing machine that accepts $\overline{L}$.
> 1 votes

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


# Question
Title: What properties of a programming language make compilation impossible?
Question:

"Certain properties of a programming language may require that the only way to get the code written in it be executed is by interpretation. In other words, compilation to a native machine code of a traditional CPU is not possible. What are these properties?"

Compilers: Principles and Practice by Parag H. Dave and Himanshu B. Dave (May 2, 2012)

The book gives no clue about the answer. I tried to find the answer on Concepts of Programming Languages (SEBESTA), but to no avail. Web searches were of little avail too. Do you have any clue?

# Answer
The distinction between interpreted and compiled code is probably a fiction, as underlined by Raphael's comment:

```
the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

```

The fact is that code is always interpreted, by software, by hardware or a combination of both, and the compiling process cannot tell which it will be.

What you perceive as compilation is a translation process from one language $S$ (for source) to another language $T$ (for target). And, the interpreter for $S$ is usually different from the interpreter for $T$.

The compiled program is translated from one syntactic form $P\_S$ to another syntactic form $P\_T$, such that, given the intended semantics of the languages $S$ and $T$, $P\_S$ and $P\_T$ have the same computational behavior, up to a few things that you are usually trying to change, possibly to optimize, such as complexity or simple efficiency (time, space, surface, energy consumption). I am trying not to talk of functional equivalence, as it would require precise definitions.

Some compilers have been actually used simply to reduce the size of the code, not to "improve" execution. This was the case for language used in the Plato system (though they did not call it compiling).

You may consider your code fully compiled if, after the compiling process, you no longer need the interpreter for $S$. At least, that is the only way I can read your question, *as an engineering rather than theoretical question* (since, theoretically, I can always rebuild the interpreter).

One thing that may raise problem, afaik, is meta-circularity. That is when a program will manipulate syntactic structures in its own source language $S$, creating program fragment that are then intepreted as if they had been part of the original program. Since you can produce arbitrary program fragments in the language $S$ as the result of arbitrary computation manipulating meaningless syntactic fragments, I would guess you can make it nearly impossible (from an engineering point of view) to compile the program into the language $T$, so that it now generate fragments of $T$. Hence the interpreter for $S$ will be needed, or at least the compiler from $S$ to $T$ for on-the-fly compiling of generated fragments in $S$ (see also this document).

But I am not sure how this can be formalized properly (and do not have time right now for it). And *impossible* is a big word for an issue that is not formalized.

# Futher remarks

*Added after 36 hours. You may want to skip this very long sequel.*

The many comments to this question show two views of the problem: a theoretical view that see it as meaningless, and an engineering view that is unfortunately not so easily formalized.

There are many ways to look at interpretation and compilation, and I will try to sketch a few. I will attempt to be as informal as I can manage

## The Tombstone Diagram

One of the early formalization (early 1960s to late 1990) is the T or Tombstone diagrams. These diagrams presented in composable graphical elements the implementation language of the interpreter or compiler, the source language being interpreted or compiled, and the target language in the case of compilers. More elaborate versions can add attributes. These graphic representations can be seen as axioms, inference rules, usable to mechanically derive processor generation from a proof of their existence from the axioms, à la Curry-Howard (though I am not sure that was done in the sixties :).

## Partial evaluation

Another interesting view is the partial evaluation paradigm. I am taking a simple view of programs as a kind of function implementation that computes an answer given some input data. Then an interpreter $I\_S$ for the language $S$ is a program that take a program $p\_S$ written in $S$ and data $d$ for that program, and computes the result according to the semantics of $S$. Partial evaluation is a technique for specializing a program of two arguments $a\_1$ and $a\_2$, when only one argument, say $a\_1$, is known. The intent is to have a faster evaluation when you finally get the second argument $a\_2$. It is especially useful if $a\_2$ changes more often than $a\_1$ as the cost of partial evaluation with $a\_1$ can be amortized on all the computations where only $a\_2$ is changing.

This is a frequent situation in algorithm design (often the topic of the first comment on SE-CS), when some more static part of the data is pre-processed, so that the cost of the pre-processing can be amortized on all applications of the algorithm with more variable parts of the input data.

This is also the very situation of interpreters, as the first argument is the program to be executed, and is usually executed many times with different data (or has subparts executed many times with different data). Hence it become a natural idea to specialize an interpreter for faster evaluation of a given program by partially evaluating it on this program as first argument. This may be seen as a way of compiling the program, and there has been significant research work on compiling by partial evaluation of a interpreter on its first (program) argument.

## The Smn theorem

The nice point about the partial evaluation approach is that it does take its roots in theory (though theory can be a liar), notably in Kleene's Smn theorem. I am trying here to give an intuitive presentation of it, hoping it will not upset pure theoreticians.

Given a Gödel numbering $\varphi$ of recursive functions, you can view $\varphi$ as your hardware, so that given the Gödel number $p$ (read *object code*) of a program $\varphi\_p$ is the function defined by $p$ (i.e. computed by the object code on your hardware).

In its simplest form, the theorem is stated in wikipedia as follows (up to a small change in notation):

> Given a Gödel numbering $\varphi$ of recursive functions, there is a primitive recursive function $\sigma$ of two arguments with the following property: for every Gödel number $q$ of a partial computable function $f$ with two arguments, the expressions $\varphi\_{\sigma(q,x)}(y)$ and $f(x,y)$ are defined for the same combinations of natural numbers $x$ and $y$, and their values are equal for any such combination. In other words, the following extensional equality of functions holds for every $x$: $\\;\\;\varphi\_{\sigma(q,x)} \simeq \lambda y.\varphi\_q(x,y).\\,$

Now, taking $q$ as the interpreter $I\_S$, $x$ as the source code of a program $p\_S$, and $y$ as the data $d$ for that program, we can write: $\\;\\;\varphi\_{\sigma(I\_S,p\_S)} \simeq \lambda d.\varphi\_{I\_S}(p\_S,d).\\,$

$\varphi\_{I\_S}$ may be seen as the execution of the interpreter $I\_S$ on the hardware, i.e., as a black-box ready to interpret programs written in language $S$.

The function $\sigma$ may be seen as a function that specializes the interpreter $I\_S$ for the program $P\_S$, as in partial evaluation. Thus the Gödel number $\sigma(I\_S,p\_S)$ may be seen has object code that is the compiled version of program $p\_S$.

So the function $\\;C\_S = \lambda q\_S.\sigma((I\_S,q\_S)$ may be seen as a function that take as argument the source code of a program $q\_S$ written in language $S$, and return the object code version for that program. So $C\_S$ is what is usually called a compiler.

## Some conclusions

However, as I said: "theory can be a liar", or actually seem to be one. The problem is that we know nothing of the function $\sigma$. There are actually many such functions, and my guess is that the proof of the theorem may use a very simple definition for it, which might be no better, from an engineering point of view, than the solution proposed by Raphael: to simply bundle the source code $q\_S$ with the interpreter $I\_S$. This can always be done, so that we can say: compiling is always possible.

Formalizing a more restrictive notion of what is a compiler would require a more subtle theoretical approach. I do not know what may have been done in that direction. The very real work done on partial evaluation is more realistic from an engineering point of view. And there are of course other techniques for writing compilers, including extraction of programs from the proof of their specification, as developed in the context of type-theory, based on the Curry-Howard isomorphism (but I am getting outside my domain of competence).

My purpose here has been to show that Raphael's remark is not "crazy", but a sane reminder that things are not obvious, and not even simple. Saying that something is *impossible* is a strong statement that does require precise definitions and a proof, if only to have a precise understanding of how and why it is *impossible*. But building a proper formalization to express such a proof may be quite difficult.

This said, even if a specific feature is not compilable, in the sense understood by engineers, standard compiling techniques can always be applied to parts of the programs that do not use such a feature, as is remarked by Gilles' answer.

To follow on Gilles' key remarks that, depending on the language, some thing may be done at compile-time, while other have to be done at run-time, thus requiring specific code, we can see that the concept of compilation is actually ill-defined, and is probably not definable in any satisfactory way. Compilation is only an optimization process, as I tried to show in the *partial evaluation* section, when I compared it with static data preprocessing in some algorithms.

As a complex optimization process, the concept of compilation actually belongs to a continuum. Depending on the characteristic of the language, or of the program, some information may be available statically and allow for better optimization. Others things have to be postponed to run-time. When things get really bad, everything has to be done at run-time at least for some parts of the program, and bundling source-code with the interpreter is all you can do. So this bundling is just the low end of this compiling continuum. Much of the research on compilers is about finding ways to do statically what used to be done dynamically. Compile-time garbage collection seems a good example.

Note that saying that the compilation process should produce machine code is no help. That is precisely what the bundling can do as the interpreter is machine code (well, thing can get a bit more complex with cross-compilation).
> 63 votes

# Answer
The question is not actually about compilation being *impossible*. If a language can be interpreted¹, then it can be compiled in a trivial way, by bundling the interpreter with the source code. The question is asking what language features make this essentially the only way.

An interpreter is a program that takes source code as input and behaves as specified by the semantics of that source code. If an interpreter is necessary, this means that the language includes a way to interpret source code. This feature is called `eval`. If an interpreter is required as part of the language's runtime environment, it means that the language includes `eval`: either `eval` exists as a primitive, or it can be encoded in some way. Languages known as scripting languages usually include an `eval` feature, as do most Lisp dialects.

Just because a language includes `eval` doesn't mean that the bulk of it can't be compiled to native code. For example, there are optimizing Lisp compilers, that generate good native code, and that nonetheless support `eval`; `eval`'ed code may be interpreted, or may be compiled on the fly.

`eval` is the ultimate needs-an-interpreter feature, but there are other features that require something short of an interpreter. Consider some typical phases of a compiler:

1. Parsing
2. Type checking
3. Code generation
4. Linking

`eval` means that all these phases have to be performed at runtime. There are other features that make native compilation difficult. Taking it from the bottom, some languages encourage late linking by providing ways in which functions (methods, procedures, etc.) and variables (objects, references, etc.) can depend on non-local code changes. This makes it difficult (but not impossible) to generate efficient native code: it's easier to keep object references as calls in a virtual machine, and let the VM engine handle the bindings on the fly.

Generally speaking, reflection tends to make languages difficult to compile to native code. An eval primitive is an extreme case of reflection; many languages don't go that far, but nonetheless have a semantics defined in terms of a virtual machine, allowing for example code to retrieve a class by name, inspect its inheritance, list its methods, call a method, etc. Java with JVM and C# with .NET are two famous examples. The most straightforward way to implement these languages is by compiling them to bytecode, but there are nonetheless native compilers (many just-in-time) that compile at least program fragments that don't use advanced reflection facilities.

Type checking determines whether a program is valid. Different languages have different standards for how much analysis is performed at compile time vs run time: a language is known as “statically typed” if it performs many checks before starting to run the code, and “dynamically typed” if it doesn't. Some languages include a dynamic cast feature or unmarshall-and-typecheck feature; these feature require embedding a typechecker in the runtime environment. This is orthogonal to requirements of including a code generator or an interpreter in the runtime environment.

¹ <sub> Exercise: define a language that cannot be interpreted. </sub>
> 17 votes

# Answer
I think the authors are assuming that *compilation* means

* the source program doesn't need to be present at run-time, and
* no compiler or interpreter needs to be present at run-time.

Here are some sample features that would make it problematic if not "impossible" for such a scheme:

1. If you can interrogate the value of a variable at run-time, by referring to the variable by its name (which is a string), then you will need the variable names to be around at run time.
2. If you can call a function/procedure at run-time, by referring to it by its name (which is a string), then you will need the function/procedure names at run-time.
3. If you can construct a piece of program at run-time (as a string), say by running another program, or by reading it from a network connection etc., then you will need either an interpreter or a compiler at run-time to run this piece of program.

Lisp has all three features. So, Lisp systems always have an interpreter loaded at run-time. Languages Java and C# have function names available at run time, and tables to look up what they mean. Probably languages like Basic and Python also have variable names at run time. (I am not 100% sure about that).
> 13 votes

# Answer
it is possible the current replies are "overthinking" the statement/ answers. *possibly* what the authors are referring to is the following phenomenon. many languages have an "eval" like command; eg see javascript eval and its behavior is commonly studied as a special part of CS theory (eg say Lisp). the function of this command is to evaluate the string in the context of the language definition. therefore in effect it has a similarity to a "built in compiler". the compiler cannot know the contents of the string until runtime. therefore compiling the eval result into machine code is not possible at compile time.

other answers point out that the distinction of interpreted vs compiled languages can blur significantly in many cases esp with more modern languages like say Java with a "just in time compiler" aka "Hotspot" (javascript engines eg V8 increasingly use this same technique). "eval-like" functionality is certainly one of them.
> 8 votes

# Answer
LISP is a terrible example, as it was conceived as a sort of higher-level "machine" language as a base for a "real" language. Said "real" language never materialized. LISP machines were built on the idea of doing (much of) LISP in hardware. As a LISP interpreter is just a program, it is in principle possible to implement it in circuitry. Not practical, perhaps; but far from impossible.

Furthermore, there are lots of interpreters programmed in silicon, normally called "CPU". And it is often useful to interpret (not yet existing, not at hand, ...) machine codes. E.g. Linux' x86\_64 was first written and tested on emulators. There were full distributions on hand when the chips came to the market, even just for early adopters/testers. Java is often compiled to JVM code, which is an interpreter which would not be too hard to write in silicon.

Most "interpreted" languages are compiled to an internal form, which is optimized and then interpreted. This is e.g. what Perl and Python do. There are also compilers for meant-to-be interpreted languages, like the Unix shell. It is possible on the other hand to interpret traditionally compiled languages. One somewhat extreme example I saw was an editor which used *interpreted* C as extension language. It's C could run normal, but simple, programs with no issues.

On the other hand, modern CPUs even take the "machine language" input and translate it into lower-level instructions, which are then reordered and optimized (i.e., "compiled") before being handed off for execution.

This whole "compiler" vs "interpreter" distinction is really moot, *somewhere* in the stack there is an ultimate interpreter which takes "code" and executes it "directly". The input from the programmer undergoes transformations along the line, which of those is called "compiling" is just drawing an arbitrary line in the sand.
> 3 votes

# Answer
i would presume the main feature of a programming language that makes a compiler for the language impossible (in a strict sense, see also self-hosting) is the **self-modification** feature. Meaning **the language allows to change the source code during run-time** (sth a compiler generating, fixed and static, object code cannot do). A classic example is Lisp (see also Homoiconicity). Similar functionality is provided using a language construct such as eval, included in many languages (e.g javaScript). Eval actually **calls the interpreter (as a function) at run-time**.

In other words the language can represent its own meta-system (see also Metaprogramming)

**Note** that language reflection, in the sense of querying about meta-data of a certain source code, and possibly modify the meta-data only, (sth like Java's or PHP's reflection mechanism) is **not problematic** for a compiler, since it already has those meta-data at compile time and can make them available to the compiled program, as needed, if needed.

Another feature that makes compilation difficult or not the best option (but not impossible) is the typing scheme used in the language (i.e dynamic typing vs static typing and strong typing vs loose typing). This makes difficult for the compiler to have all the semantics at compile-time, so effectively a part of the compiler (in other words an interpreter) becomes part of the generated code which handles the semantics at **run-time**. This is, in other words, **not compilation but interpretation**.
> 1 votes

# Answer
The reality is that there is a big difference between interpreting some Basic program and executing assembler. And there are areas in-between with P-code / byte-code with or without (just-in-time) compilers. So I will try to summarise some points in the context of this reality.

* If how source code is parsed depends on run-time conditions, writing a compiler may become impossible, or so hard that nobody will bother.
* Code that modifies itself is in the general case impossible to compile.
* A program that uses an eval-like function usually cannot be completely compiled in advance (if you regard the string fed to it as part of the program), although if you're going to run the eval'ed code repeatedly it may still be useful to have your eval-like function invoke the compiler. Some languages provide an API for the compiler to make this easy.
* The ability to refer to things by name doesn't preclude compilation, but you do need tables (as mentioned). Calling functions by name (like IDispatch) requires a lot of plumbing, to the point where I think most people would agree that we're effectively talking about a function call interpreter.
* Weak typing (whatever your definition) makes compilation harder and perhaps the result less efficient, but often not impossible, unless different values trigger different parses. There is a sliding scale here: if the compiler can't deduce the actual type, it will need to emit branches, function calls and such that wouldn't otherwise be there, effectively embedding bits of interpreter in the executable.
> 1 votes

# Answer
I feel the original question is not well formed. The authors of the question may have intended to ask a somewhat different question: What properties of a progamming language facilitate writing a compiler for it?

For example, it's easier to write a compiler for a context-free language than a context-sensitive language. The grammar which defines a language can also have issues that make it challenging to compile, such as ambiguities. Such issues can be resolved but require extra effort. Similarly, languages defined by unrestricted grammars are harder to parse than context-sensitive languages (see Chomsky Hierarchy). To my knowledge most widely used procedural programming languages are close to context-free, but have a few context-sensitive elements, making them relatively easy to compile.
> -1 votes

# Answer
The question has a correct answer so obvious that it's typically overlooked as being trivial. But it does matter in many contexts, and is the primary reason why interpreted languages exist:

Compiling source code into machine code is impossible **if you don't yet have the source code.**

Interpreters add flexibility, and in particular they add the flexibility of running code that wasn't available when the underlying project was compiled.
> -1 votes

---
Tags: programming-languages, compilers, interpreters
---


title: Are all irregular languages infinite?

text:
# Question
Title: Are all irregular languages infinite?
How can I prove whether irregular languages are infinite? I thought about proving it by the definition of regular language but got stuck.

# Answer
An intuitive classification between regular and non-regular languages is based on their recognizers. In case of regular languages, Finite State Automata are enough, while for non-regular languages you need more powerful automata.

A language is regular if you can build a FSA for it. Thus, given that you can always build an FSA for a language with a finite number of strings (via the Prefix Tree Acceptor, for example), than every language with a finite number of strings is regular.

If a language has an infinite number of strings, it can be regular or not, it depends (you could use the pumping lemma or other approaches to demonstrate if the language is not regular: take a look here: How to prove that a language is not regular?); on the other hand, no language with a finite number of strings is non-regular. Hence, non-regular languages are composed of an infinite number of strings.

I hope this can help you.
> 2 votes

# Answer
Here's a proof in more or less complete detail. You want to show that non-regular languages are infinite. In more formal terms, this statement is

> If $L$ is a non-regular language, then $L$ is infinite.

Let's define two predicates, $P=\text{"$L$ is not regular"}$ and $Q=\text{"$L$ is not finite"}$. Then your statement is the same as asserting $P\Rightarrow Q$, and you want to show that this implication is true (for any language L$).

**Fact 1**. The expression $P\Rightarrow Q$ is logically equivalent to $\lnot Q\Rightarrow \lnot P$ (called the *contrapositive*). In other words, if we can prove that $\lnot Q\Rightarrow \lnot P$ is true, then $P\Rightarrow Q$ must also be true.

Using this equivalence, we can show that the highlighted sentence above is true by showing that

> If $L$ is finite, then $L$ is regular.

is true.

To prove this, you can use two facts:

**Fact 2**. If a language consists of a single string, $w$, then it is regular. This is almost immediately obvious: just make a finite automaton that accepts $w$ and nothing else.

**Fact 3**. The union of two regular languages is regular. This is a result that you should have seen.

From these two facts, you can conclude (by induction),

**Fact 4**. Any language consisting of a finite number of strings is regular.

Note that this is exactly the second highlighted statement above, so, since it is logically equivalent to the first statement above, that statement must be true: Every non-regular language is infinite. That completes the proof.
> 1 votes

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


# Question
Title: Why don't nodes carry as many pointers as possible in a skip list?
From this main picture explaining how skip lists work from Wikipedia, we see that some nodes carry different amounts of pointers to other parts of the list:

Wouldn't it make more sense to have every node carry 4 pointers (since this is the height of this specific example)? For instance, node with value `2` would also have pointers to nodes `4`, `6` and `7` and not just to node `3`.

I'm asking because I need a data structure that would allow me to traverse the list as quickly as possible. Having each node carry as many pointers as possible would allow me to carry out lots of parallel requests. Also, each arrow in my implementation is actually a network call, so if I can achieve higher concurrency to retrieve all 10 items would be best.

# Answer
In the usual way, where each node carries $i$ pointers with probability $2^{-i}$, the average node has size $O(1)$, so the total space used by the skip list is $O(n)$. If each node carried pointers at every level, then each node would have $\theta(\log n)$ pointers in it, since that is the expected height of a skip list with $n$ nodes. The total space used would thus be $\theta(n \log n)$.

A skip list of one million nodes would thus be using roughly 10 times as much space.
> 6 votes

# Answer
And how would you like to manage this?
It will resemble a tree, not skip list, and memory overhead will be bigger.
Traversal time will decrease in some cases, but insertion time will increase.
Traversing over all elements will not change, you still check them all.

If you want to make concurent task, why bother with skip list?
Just make ten pointers from root and deal them among the threads.

Skip list gives faster search but lower overhead for insertion. It is amortized time. But going through all items does not benefit from additional pointers.
> 4 votes

---
Tags: data-structures, linked-lists
---


# Question
Title: Best data structure for storing an ordered list, where each item is located on a separate server?
I need a structure that resembles an RSS feed of items, but each item is on a different network machine. Users cannot insert in the middle of the feed but only at its head. Deletions are possible.

The first idea was to implement a basic linked-list where each item of the list is an RSS item. Being on the network, this means that to retrieve the latest 10 feed items, I need to wait sequentially until each node returns from the network (so that I can follow the pointer to the next item in the linked list).

Skip lists make this more concurrent as each node also gives me back pointers to other portions of the list and I can request more items in parallel.

However, I'm looking even further for something that follows more closely my users need: there will be more requests of the latest portion of the feed rather than the older portion. With this requirement in mind, I'd be looking for a structure that can perhaps allow me to achieve higher concurrency closer to the head of the list (where latest feed items are), and less concurrency (with more sequential properties) as users get towards the end of the list.

My thinking is that skip lists achieve the same level of concurrency across the entire list, so perhaps there's something I can use to make it "very concurrent" at the beginning and "less concurrent" at the end rather than "same concurrency" all along.

# Answer
> 2 votes
A standard approach is to have a distributed data structure, and then use a *cache* for efficiency. The cache remembers the results of common queries; if you ask the same query again, and the underlying data structure hasn't changed, then you can return the same remembered answer without needing to re-compute it.

For instance, you might store the items spread across networked machines however you like, as a singly linked list. Then, you'd have a single machine M that is responsible for keeping a cache of the 10 items at the head of the list. Each time you insert a new item to the head of the list, you also need to notify M to let it know to invalidate its cache. (As an optimization, instead of throwing away all cached data, M might be able to update the cached information when it receives a notification -- though this does introduce some additional concurrency challenges.)

Now any attempt to read the first items from the queue goes first to M, which can check whether it has the answer cached, before traversing the linked list through the network.

You'll then need to analyze how strict your consistency requirements are. Do you require that M always return the absolutely correct result? Or can the cache be temporarily inconsistent with the backing data structure for a short period of time? That will affect whether you need to use coordination mechanisms like 2-phase commit or whether you can use simpler, higher-performing mechanisms.

I've described this in a particularly simple form, but you can generalize to (a) other backing data structures (not just a singly linked list), and (b) other caches for other kinds of queries that might be performed (not just the top 10 items from the head of the list).

---
Tags: data-structures, distributed-systems, linked-lists
---


# Question
Title: Logic formula for exactly n unique objects (no more, no less)
I have a question in Logic:

If I am asked to construct a formula, using the '=' predicate, that shows that there are exactly n objects, I need to show that there are no n+1 objects, right?

For example, to show that there are exactly 3 objects, I will show that there are no 4 objects.

Also, I need to show that there exist n objects.

My question is, do I need to show that there is no case where only n-1 objects exist?

For example, to show that there are exactly 3 objects, do I need to show that there is no case in which there are only 2 objects?

If so, is that the correct form to do so? :

---

1) Showing that there is no case of 4 elements:

$ {\lnot}{\exists}x{\exists}y{\exists}z{\exists}w(x{\neq}y{\land}x{\neq}z{\land}x{\neq}w{\land}y{\neq}z{\land}y{\neq}w{\land}z{\neq}w) $

---

2) Showing that there are 3 elements:

$ {\exists}x{\exists}y{\exists}z(x{\neq}y{\land}x{\neq}z{\land}y{\neq}z) $

---

3) Showing that there is no case of only 2 elements:

$ {\lnot}{\exists}x{\exists}y{\lnot}{\exists}z(x{\neq}y{\land}x{\neq}z{\land}y{\neq}z) $

---

And finally, combining the three:

$ (1){\land}(2){\land}(3) $

---

I am really not sure.

Thanks in advance

**EDIT:**

Actually, assuming that I do need to show that there is no case of less than 3 elements (n elements), I would probably need to show that there is no case where there is just one element as well (from 1 until n-1), am I correct?

# Answer
> 4 votes
You need to say that (a) there are at least $n$ elements, and (b) there are at most $n$ elements. To express (a), $$ L\_n := \exists x\_1\dotsc \exists x\_n\\, \left( \bigwedge\_{1\le i \< j \le n} x\_i\ne x\_j \right). $$ To express (b), $$ M\_n := \forall x\_1\dotsc \forall x\_{n+1}\\, \left( \bigvee\_{1\le i \< j \le n+1}x\_i = x\_j\right). $$ So the sentence $L\_n \land M\_n$ holds *iff* there are exactly $n$ elements.

---
Tags: logic, sets, first-order-logic, finite-sets
---


# Question
Title: Does a DFA accept an empty string if $q_0$ is the accept state?
Suppose $q\_0$ is the start state, does this mean that if it's the accept state, then the machine must accept the empty string since it cannot have a transition with the empty string?

# Answer
Yes. This is immediate from the definitions.

A DFA accepts if it's in an accepting state after it's read its input. If the input is the empty string, the DFA makes no transitions so, after reading it's input, it's still in its initial state, $q\_0$. If $q\_0$ is an accepting state, the automaton accepts the empty string.

Note that you write "the accepting state" but an automaton may have multiple accepting states.
> 9 votes

---
Tags: formal-languages, regular-languages, automata, dfa
---


# Question
Title: The language of all base-10 integers that are multiples of 9
If I want to represent all the base 10 integers that are multiples of 9 as a language how do I do so?

Alphabets are finite sets.

# Answer
> 2 votes
You need to check the definitions. An alphabet is a finite set of characters (or "symbols") that are used to write strings; a string is a sequence of characters from some alphabet.

When you write numbers down, you write them as a sequence of symbols. What symbols are those? That's your alphabet.

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


# Question
Title: How to find the shortest path from some vertex in set $S$ to set $S'$
If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That is, we are looking for a shortest path among all $S$-$S'$ paths. We can also assume all edge weights are positive.

Here is how I have approached this problem so far:

I already have the distance matrix information $(d)$ for graph $G$ which was calculated by applying the Floyd-Warshall algorithm in a previous operation.

I then iterate over all vertices in $S$ for each vertex in $S'$ and find the pair $(s\_1,s\_2)$ with the smallest value in matrix $d$.

Dijkstra's algorithm is then used to calculate the shortest path between $s\_1$ and $s\_2$, so connecting vertex sets $S$ and $S'$.

Is there a more efficient way of achieving this same outcome?

# Answer
> 7 votes
If all edge lengths are non-negative, then this can be solved in $O(|E| \lg |V|)$ time using a single invocation of Dijkstra's algorithm.

We're going to modify the graph slightly by adding a new vertex $s$. Also, add an edge of length 0 from $s$ to each vertex in $S$.

Next, run Dijkstra's algorithm, starting from the source vertex $s$. Dijkstra's algorithm will compute for you the distance from $s$ to every other vertex $v$, i.e., it will compute $d(s,v)$ for all $v \in V$. Note that $d(s,v)$ will be exactly the length of the shortest path from some vertex in $S$ to the vertex $v$.

Finally, compute $\min \\{ d(s,v) : v \in S' \\}$. This will be the length of the shortest path from some vertex in $S$ to some vertex in $S'$. That's your answer.

There's no need to run Floyd-Warshall.

If you can have negative edges, then it can be done in $O(|V| \cdot |E|)$ time. Simply replace Dijkstra's algorithm with the Bellman-Ford algorithm.

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


# Question
Title: Difference between virtual memory and job pool
Both virtual memory and job pools store the processes temporarily on disk and bring them to memory at some later stage, so what is the actual difference in between them?

What I guess is that when a process is just created, it first goes to the job pool and then it is sent to the ready queue. Virtual memory is only used when available memory becomes smaller than the required memory for any process (please correct me if I am wrong).

If this is the case then doesn't it decrease performance? What is the need to store processes in job pool first? Why don't we send processes directly to memory?

Also somewhere it was written as “job contains the list of all the jobs in the system and jobs in the memory are a subset of the jobs in the job pool”. So what is meant by “all jobs in the system” here? Does it mean “all NEW jobs”?

# Answer
> 2 votes
> All the jobs that enter the system are kept in the job pool. This pool consists of all processes residing on mass storage awaiting allocated of main memory. (Source)

When a job has to get executed, it needs to be residing in the main memory. But, due to the limitation of size of main memory, only the parts of job which are currently being executed are transferred onto main memory, and the rest reside in virtual memory.

So, in short, jobs which are created are sent to the job pool and are waiting to get their required resources and to get executed.

> Why don't we send processes directly to memory?

**Not always, is the main memory free.** So, the job scheduler comes into the picture.

Because it is the job of the **job scheduler** to pick jobs from the job pool. Because, by default the job scheduler must be using some heuristic to schedule jobs i.e. according to priority or FIFO etc. You cannot break the custom and force it directly to the main memory, as that is the job of the job scheduler. This process, might have a bit of performance overhead, I understand, but things are pretty organised this way (the OS is so designed), and ensures no process starves.

All the jobs in the system mean the jobs in the hard disk and the jobs in the main memory combined. So, jobs in the memory are a subset of the total jobs in the 'system'.

# Answer
> 4 votes
The concept of “job pool” refers to a batch processing system, where jobs are queued to be executed when resources are available. The job pool contains both jobs that are currently executing and jobs that have been scheduled but are not yet being executed. Ancient computers (and some mainframes that are still in operation) worked this way. When a job is executing, it is fully present in memory.

Modern systems don't work that way. Computers that are big enough to run multiple tasks — even many embedded systems — have a memory management unit which translates virtual memory addresses to physical addresses, and the operating system uses that to move each page between memory and disk (this is called swapping or paging). This is an evolution from earlier multiprocessing systems: at first (before the MMU era) processes were swapped as a whole, but nowadays, if there isn't enough memory to fit all currently running processes, the operating system can swap out the parts of processes that aren't currently being used.

Systems designed for large non-interactive computations generally use job management even today. Swapping takes time; if the active processes require more memory than is available to run comfortably, this causes thrashing. To avoid this, job schedulers do use job pools, and arrange to start jobs, and possibly pause them, based on available resources. The system works on top of an operating system based on virtual memory, so once a job is paused it will naturally be swapped out as its pages in RAM are replaced by pages of active jobs.

(Note that job-based management is only marginally relevant to today's computing environment. I wouldn't set much store by a textbook that focuses on that in the 21st century. Virtual memory, on the other hand, is relevant to all but low-end embedded systems.)

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