# Question
Title: Valid actions of Reductions to NP-Completeness
To my understanding, as long as we can find some polytime function $f$ such that $\forall x:x \in A \Longleftrightarrow f(x) \in B, x\notin A \Longleftrightarrow f(x) \notin B$, it follows that if $A$ is NP-complete and B is in NP, then B is also in NP-complete.

My question is about what sort of 'things' we can do to obtain reductions from NP-completeness. That is, I want to know if $f$ is allowed to do anything so long as it is still done in polytime and satisfies the above property? If not, then what sort of limitations are there?

# Answer
> 1 votes
Your understanding is correct.

The only restriction is the one you mention: the reduction must work in polynomial time. That is, there must be some algorithm and some polynomial function $t(n)$ (e.g. $t(n)=n^5+n^3+42$) such that, on all inputs $x$ of length $n$, the algorithm outputs $f(x)$ and the time it takes the algorithm to do that is less than or equal to $t(n)$.

To answer concretely what "things" you may do, I can't! Anything you can think of that takes polynomial time: perfect matching, integer multiplication, some variants of linear programming... graph isomorphism? Counting the number of solutions to the traveling salesman problem? If you can do it in polynomial time, then yes!

To read some posts on this site about NP Completeness, click here to search for posts about that topic.

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


# Question
Title: Decision version of the traveling salesman problem and NP-hardness
Wikipedia says:

> The problem has been shown to be NP-hard

and

> the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete.

How can the "non-decision problem" version be NP-hard? Doesn't this class contain decision problems, by definition? Is this some sort of abuse of notation? Are they just being overly flexible with the definition of NP-hard?

# Answer
> 2 votes
When we say that an optimization problem is NP-hard, what we mean is that its decision version is NP-hard. In this particular case, according to Wikipedia more is true: the function version (finding an optimal solution) is complete for $\mathsf{FP}^\mathsf{NP}$.

# Answer
> 0 votes
No, it is not the abuse of notation.

First of all, very formally $NP$ contains only decision problems, while $NP$-hard contain problems to which all problems in $NP$ can be reduced. So, if you have an optimization problem for which the decision version is $NP$-complete, it automatically becomes $NP$-hard (but not complete). Vice versa, for hard optimization problem the decision version becomes complete.

Note, that search vs decision versions of a problem are not always equivalent in terms of hardness. They are for an optimization search or $NP$-complete problems though.

Also, I expect some comments about stuff above from people who might have seen different definitions. I warn that different books allow different level if strictness of their definitions.

---
Tags: complexity-theory, decision-problem, complexity-classes, traveling-salesman
---


# Question
Title: Can every single regular expression be translated into deterministic finite automata?
Can every regex be translated into a DFA? Or only a subset of regular expressions?

If so, what is an example of a regular expression that cannot be translated into a DFA?

# Answer
> 3 votes
Every regular expression using only \*,+,| (but not, say, backreferences) can be converted into a DFA. This is shown in textbooks on formal languages. Modern regular expressions, as used in actual programming languages, are more powerful than classical ones, and in particular they can recognize non-regular languages, such as the language of squares $w^2$, which is recognized by `(.*)\1`.

# Answer
> 3 votes
A regular expression can only describe a regular language, but it can describe all regular languages. The same is valid for DFA: They can only describe regular languages, but they can describe all regular languages.

So if a regular expression can describe a language, that language is regular, and can be described by a DFA. You can construct such DFA by using Thompson or Glushkov construction (among others) to construct an NFA, and then convert it to a DFA.

If a language is produced by a DFA, it is regular, and can be described by a regular expression. To construct a regular expression from a DFA, have a look at this question.

Note: Outside of theory, people often confuse regular expressions with languages designed for programming, for example PCREs. While they are named "Perl Compatible *regular expressions*", they are much more powerful than regular expressions or DFA. They can in fact decide some NP-complete problems.

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


# Question
Title: Can the set of all $2^{24}$ colors be expressed as a ternary linear code?
> Consider the usual RGB color palette, for which each color (red, green, blue) has $256$ distinct intensities. Can the set of all $2^{24}$ colors be expressed as a ternary linear code? If so, give a basis. If not, explain why not.

I'm confused on how to solve this because I've only worked with binary linear codes. Can somebody please walk me through it?

# Answer
Hint: The number of codewords in a ternary linear code is a power of 3.

That's my best guess for the answer that the setter expects. However, the truth is you can certainly use a ternary linear code to represent all colors, you will just have a little redundancy.
> 1 votes

---
Tags: information-theory
---


# Question
Title: Infinite Intersection/Union of regular languages
Hello I'm having trouble understanding how an intersection/union of regular languages can be regular and in other case non-regular.

Can someone please give me some good examples?

# Answer
> 9 votes
For every word $w$, there's a language $\\{ w\\}$, which is regular, and $\Sigma^\* \setminus \\{ w\\}$, which is also regular.

But, we can express every language (regular or not) $L$ as an infinite union: $L = \bigcup\_{w \in L} \\{ w \\}$, which is an infinite union of regular languages.

For intersection, you do the opposite:

$L = \bigcap\_{w \not \in L} (\Sigma^\* \setminus \\{w \\})$.

So, we know that there are regular languages, and non-regular languages, and they can all be expressed as infinite unions or intersections of regular languages.

# Answer
> 0 votes
Every regular language can be described as a DFA. So assume you have a DFA that represents language one, and a DFA that represents language two. Now construct a third DFA that represents the union of the first two DFA. Construct another DFA that represents the intersection of the first two DFA.

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


# Question
Title: Can we build a Finite Determinist Automaton from any Nondeterminist Finite Automaton?
Is it possible to create a Determinist Finite Automaton that is equivalent to a Nondeterminist Finite Automaton, whatever that NFA is ?

Is there an algorithm to create such a DFA if we have a NFA ?

# Answer
> 5 votes
Yes that is called the subset construction.

# Answer
> 0 votes
As the other posters have mentioned, yes! NFAs and DFAs are equivalent, and there is a deterministic algorithm to convert any NFA to a DFA. Likewise any DFA is an NFA without any reduction.

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


# Question
Title: What are the uses of multi-dimensional arrays?
While studying arrays a question came to my mind. If only 1D and 2D arrays can be used, then why multi-dimensional arrays exist? Is there any use of multi-dimensional arrays?

# Answer
> 5 votes
One could just as easily ask "what are the uses of multidimensional spaces?" After all, with space-filling curves, all we really need is one dimension.

But a single dimension, even if it's sufficient, does not always yield useful models. For example, a 2-dimensional euclidean line would be non-continuous when mapped to a space-filling curve.

It's the same with multi-dimensional arrays -- they're used not because they're inherently necessary, but because they're a useful model.

For example, let's take a look at how one might model a movie.

* A movie is nothing more than a time-varying sequence of images -- i.e., an array of images.
* Each image is a two-dimensional array, with each element of the array representing a color.
* A color has three components:
    + Red
    + Green
    + Blue

So a movie can be modeled as a multidimensional array.

# Answer
> 0 votes
An array is nothing else than a named association from integers (in a range) to another data item, usually optimized to have a cost O(1) for the retrieve data operation. Using your words "only 1D arrays exist".

The usual expressions: `a[1]`, `a(1)`, or even the unusual `a.1` are sugar of `a.get(1)` (`get(a,1)` in some not oo languages, `get a 1` in others, etc).

If the data item returned is itself an array, we could talk about a bidimensional array. Thus, bidimensional expressions `a[4,2]`, `a(4,2)`, `a[4][2]` are `a.get(4).get(2)`. Three dimensional ones are `a.get(2).get(4).get(7)`, and so on.

About the example you request, assume you have a big library, with several floors, rooms in each floor, bookstore in each floor, shelfs in each bookstore and slots in each shelf. All they are numbered (floor 1, room 3, bookstore 4, shelf 1, slot 7). You can retrieve data for one specific book as: `mylibrary.get(1).get(3).get(4).get(1).get(7)`, that some languages will write as `mylibrary[1,3,4,1,7]`, `mylibrary[1][3][4][1][7]`, ... .

# Answer
> 0 votes
A person can easily reason about n-dimensional vectors in code. A 2-D vector is simply a vector of vectors. A 3-D vector is a vector of vector of vectors and so on and so on. You can construct a 1-D vector to behave like an N-dimensional vector however, but this is typically more difficult to reason about.

General code for a 3-D vector:

for i to N for j to N for k to N dosomething(vec\[i,j, k\])

You can have more for loops and this will traverse every element in your N-dimensional vector

---
Tags: data-structures, arrays
---


# Question
Title: Choosing the optimal radix/number-of-buckets when sorting n-bit integers using radix sort
This is a popular question:

> What is the most efficient (in time complexity) way to sort 1 million 32-bit integers?

Most answers seem to agree that one of the best ways would be to use radix sort since the number of bits in those numbers is assumed to be constant. This is also a very common thought exercise when CS students are first learning non-comparison based sorts. However, what I haven't seen described in detail (or at least clearly) is how to optimally choose the radix (or number of buckets) for the algorithm.

In this observed answer, the selection of the radix/number of buckets was done empirically and it turned out to be $2^8$ for 1 million 32-bit integers. I'm wondering if there is a better way to choose that number? In "Introduction to Algorithms" (p.198-199) it explains Radix's run-time should be $\Theta(d(n+k))$ (d=digits/passes, n=number of items, k=possible values). It then goes further and says that given n b-bit numbers, and any positive integer $r \leq b$, radix-sort sorts the number in $\Theta((b/r)(n+2^r))$ time. It then says:

> If $b \geq \lfloor \lg(n) \rfloor$, choosing $r = \lfloor \lg(n) \rfloor$ gives the best time to within a constant factor.

But, if we choose $r = \lg(10^6) =20$, which is not $8$ as the observed answer suggests.

This tells me that I'm very likely misinterpreting the "choosing of $r$" approach the book is suggesting and missing something (very likely) or the observed answer didn't choose the optimal value.

Could anyone clear this up for me?

# Answer
> 1 votes
Minimizing run time is a very different question from minimizing operation counts. Sorting large data sets tends to be memory bound, so the goal of optimization is not to reduce the number of operations, but to try and do make efficient use of memory — for example,

* do as much work as possible in L1 cache
* use bandwidth to main memory efficiently by writing full cache lines
* avoid overflowing the TLB by too much

Increasing the number of buckets works against all three points; it does no good to complete a radix sort in two passes if each pass takes three times as long as each pass of a four pass implementation!

# Answer
> 0 votes
The derivative of (b/r)(n+2^r) = (b (2^r (r ln(2) - 1) - n))/r^2. A minimum occurs when the derivative == 0, which occurs when 2^r (r ln(2) - 1) - n = 0. For n == 2^20 (about 1 million), r ~= 16.606232 results in O() ~= 2212837. Some example values and O():

```
 r   O
18   2330169
17   2220514
16   2228224
15   2306867
12   2807125

```

So r = 16 would be the best actual number based on the formula. However since L1 cache is typically 32 KB, the optimal values for r are less. On my system (Intel 2600K 3.4 ghz), for n = 2^20, then 4 fields of 8, 8, 8, 8 (r = 8) is fastest. At around n = 2^24 3 fields of 10, 11, 11 (r = 10.67) is fastest. At around n = 2^26, 2 fields of 16, 16 (r = 16) is fastest. There's not a lot of difference though, less than 10%.

---
Tags: algorithms, sorting, efficiency
---


title: Applications of Four Color Theorem

text:
# Question
Title: Applications of Four Color Theorem
I tried finding real life applications for the Four Color Theorem (except for coloring maps) but couldn't find anything useful and well illustrated. For example I found this:

> Graph coloring problems are widely applicable to the problem of scheduling.
>
> Consider a university, where you are trying to schedule times for all of the final exams. Some students are taking more than one class, so you want to make sure they don't have two exams scheduled at the same time. However, you want your exam writing period to be as short as possible, to run as many exams concurrently as you can.
>
> You can represent this as a graph coloring problem: construct a graph in which each class is a vertex, and there is an edge between vertices any time a two classes contain the same student. Your colors will represent different exam timeslots. The minimum number with which you can color that graph is the smallest number of timeslots you need to write all your exams.
>
> source: jmite on cs.se.

However, I don't really get how it works! Also if you could give more examples related with graph theory and four color theorem

# Answer
> 1 votes
Explanation of the graph coloring problem stated above:

So each vertex represents a class. Each edge represents a timing conflict between two classes. Suppose there was a graph with 4 vertices and a single edge between two. This would require only 2 colors, which translates to two time slots. Draw this graph. Write out a few scenarios of class schedules and draw their corresponding graphs to get a better idea. Answer the question on whether or not these graphs are planar. If so, what does that mean w.r.t. the four color theorem?

# Answer
> 0 votes
Anytime graph coloring is applicable, the four color theorem has an opportunity to shine. All you have to do is limit yourself to the type of graph used in this theorem. This could be a possible argument you could make.

---
Tags: graphs
---


# Question
Title: Linear time algorithm for least positive integer missing from array
> Design a linear time algorithm for finding the least positive integer missing from an unsorted array. Changes in the array are allowed.
>
> For example, for the array -10,-1,2,3,6,30, the answer is 1.

I thought about finding the maximum and minimum numbers in the array (this is $\Theta(n)$), then a loop from the minimum number to the maximum number, and in every iteration, check if the current number is in the array, but this will take $\Theta(n^2)$.

# Answer
You could do radix sort with counting sort if your input matches the criteria for these algorithms (this is O(n) ). Another way would be creating a vector of bool the size of the input. Initialize all elements to false. Once you encounter a positive integer, set the index of this positive integer to true if it is within the bounds of the vector size. Once this is done you can traverse this vector and the first false value you find is the least positive integer missing.
> 2 votes

# Answer
Hint (if extra memory is allowed): It is enough to determine which of the elements $1,\ldots,n$ are in the input array. Using an auxiliary array, you can accomplish this in $O(n)$.
> 4 votes

# Answer
Try to rearrange the array so that it starts with the numbers 1 to n, as far as possible, that is a \[i\] = i + 1 for 0 ≤ i \< n. To do this: Loop for 0 ≤ i \< n. As long as 1 ≤ a \[i\] ≤ n and a \[a \[i\] - 1\] != a \[i\] exchange a \[i\] and a \[a \[i\] - 1\].

This works in O (n) because you loop through n values, and you store at most n values into their right place.

Then you just check which is the first i such that a \[i\] ≠ i+1, and i+1 is the first missing number. If none are found missing, then n+1 is the first missing number.
> 1 votes

---
Tags: algorithms
---


title: NaN simple precision IEEE 754

text:
# Question
Title: NaN simple precision IEEE 754
How many words exist in the format of the simple precision IEEE 754 standard to represent the NaN value?

# Answer
> 1 votes
From this link you should be able to come up with a general solution: https://en.m.wikipedia.org/wiki/IEEE\_754-1985

Why should it be general? Because it could work for both 32 and 64 bit numbers. The sign is X, the exponent is Y, the fraction is anything but all P's.

You just need to fill in X, Y, P (which is found on the wikipedia page) and come up with a general formula. This is a combinatorics problem. How many ways can you construct a binary string of size N that is not all zeros?

---
Tags: floating-point
---


title: Converting recursive algorithm to DP

text:
# Question
Title: Converting recursive algorithm to DP
As a follow-up to this question , I've found a recursive algorithm that solves the given problem, but it runs too slow to pass all given tests.

```
int solve(int i, int crane1_pos, int crane2_pos, int dist)
{

    if(i == n)
    {
        return dist;
    }

    int dist1 = dist + get_dist(crane1_pos, t[i].first);
    int dist2 = dist + get_dist(crane2_pos, t[i].first);

    return min(solve(i + 1, t[i].second, crane2_pos, dist1), solve(i + 1, crane1_pos, t[i].second, dist2));

}

```

Where, get\_dist is a function that looks like this:

```
int get_dist(int crn_pos, int fin_pos)
{
    if(crn_pos == -1)
        return 0;

    return abs(crn_pos - fin_pos);
}

```

$t$ in this particular situation is a vector of `pair<int, int>`, $n$ is the size of this vector and the initial call of the function is `solve(0, -1, -1, 0)`.

I'm pretty sure this could be further improved by using DP, but upon doing some research on this issue, I found that I'm unable to transform this recurrence into some form of dynamic programming. I've derived the recurrence trees for several examples and I can't find the overlapping subproblems and a way to use memoization.

So I guess my question is, how do you turn this recurrence into DP?

# Answer
Didn't look at your code, but in general there are two important points that distinguish recursion from dynamic programming.

First recursion is top-down (starting with the big instances, by decomposing them into smaller instances and combining the answers) while DP is bottom-up (first solving the small cases, and combining them into larger ones).

The second important point is the table that contains the solutions to instances with certain parameters. This is to avoid computing certain cases more than once (as recursion tends to do).

So DP is upside down recursion in general. But one can also start with recursion and a lookup table that tests whether a certain subproblem was already solved.
> 4 votes

# Answer
In general for dynamic programming finding the recurrence is the most difficult part. You already have that!

Now you need to use something called memoization. You need to not do work that you've already done. So you'll need to create a matrix that your subproblems will fit into. Now, you need to have an if statement that checks if you've calculated a specific instance of this recurrence or not.

To more easily understand this, think about a recurrence for the Fibonacci sequence. The recurrence without memoization is exponential while using memoization it's linear!

To learn dynamic programming I used mitopencourseware videos on YouTube. Eric Demaine is a great teacher.
> 1 votes

---
Tags: algorithms, dynamic-programming, recursion
---


# Question
Title: Proof NP-Complete for Single machine Job Scheduling Problem specific version
**Problem**: given a set of n tasks with execution time Ti, due date Di, and a profit Vi (given only if is enden before due date), is there a task schedule that returns a total profit greater or equal than k knowing that tasks must be executed one at a time?

I am asked to proof that this problem is NP-Complete, can anyone help?

Thanks.

# Answer
Since this problem is very approachable, you could first try to think about a greedy solution to show this is in the class P, and thus *probably* not in NP-complete. Once you have done this you could think about a polytime reduction to a problem known to be in NP-complete. Consult Karp's original 21 problems to get a feel for the type of problems you can use to find this reduction. Once you have done this come back with more specific questions :)
> 1 votes

---
Tags: np-complete, np, scheduling
---


# Question
Title: Where in memory are global variables stored?
I would like to know where in memory the global variables are stored. Thanks for your help.

# Answer
> 1 votes
This really just depends on the compiler you're using and the architecture you're targeting. For instance, I could make a compiler which assigns global variables to general purpose registers in bank 2 of a PIC16f887a microcontroller. It's arbitrary. This is a bad question.

---
Tags: memory-management
---


# Question
Title: Can a finite automaton have more than one regular expression?
A finite automaton is a generator for a regular language, and a regular expression represents a regular language. A language can be represented in many forms of regular expressions. So can a finite automaton have more than one regular expression?

# Answer
There are multiple ways of writing the same expression, then I guess yes, it can be represented by many expressions.

For example, look at this DFA (with the initial state being final)

```
-->(a)________
    ^         |
    |         |
    |         V
    '--------(b)

```

the regular expression for it can take infinite forms, such as

$(ab)^\*\\;$ or $\\;(ab)^\*(ab)^\*\\;$ or $\\;(ab)^\*(ab)^\*(ab)^\*\\;$ ...

If you consider different forms of the same expression, then it can be represented by lots of regexs, otherwise is just 1.
> 6 votes

# Answer
Every regular expression is equivalent to infinitely many other regular expressions. Indeed, the regular expression $r$ is completely equivalent to the regular expressions $r+r,r+r+r,\ldots$, for example.
> 2 votes

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


# Question
Title: Binary Search Tree Stability Data Structure
> After constructing a binary search tree, you can read off the key values in ascending order by performing an in-order traversal.
>
> Will the resulting sorted order be stable?
> If so, how would the tree have to be coded to ensure this?
> If it is not possible, why not?"

Just a review question I came across. From what I understand,

Stability ensures that if A and B share the same Key, if A comes before B originally, A comes before B after sorting as well.

Ascending order = Bottom up

Inorder = Left - Root - Right

if we have a BST that looks as such;

----5,a

--3,c 4,b

-1,d

and we insert a 1,e into the tree. We can get that 1,e on the left or right child of 1,d.

We want to return 1,d first then 1,e so that stability is retained.

How do we change the code for the BST to do this? My suggestion was to make a linked list that returns the head of duplicate values whenever duplicates are encountered. However I'm not sure this is entirely the best method here.

# Answer
You can ensure that the inorder is stable by modifying the insertion routine (if necessary) so that when it compares an element $x\_1$ already in the tree to the new element $x\_2$, if $x\_1 = x\_2$ then it answers that $x\_1 \< x\_2$.

Caveat: I'm not sure that this works for self-balancing trees.
> 1 votes

---
Tags: trees, binary-trees, graph-traversal, binary-search-trees
---


title: Can randomization be proven?

text:
# Question
Title: Can randomization be proven?
There exists a collection `c` where `c = {1, 2, 3}` and a randomization of `c`, `d` where `d = {1, 3, 2}`. `d` was obtained by a function `f` where `f` is an undefined randomization function.

Can `c` be obtained again (i.e. `d = c`) by randomizing

1. `d` or
2. `d` initially and then each randomized collection resulting from `d`

using `f`? If so, can it be proven?

# Answer
If *f* is a random permutation, then you can apply it to d and eventually get the ordering of C.
> 0 votes

---
Tags: randomness, permutations, lists
---


# Question
Title: How to find indexes of numbers that has many occurrences?
Disclaimer: This is a simplified part of a question from my homework, addressing the point that I didn't figure out.

> let A be a 1-indexed sorted array of $n$ elements.
>
> There are at most 3 numbers that has at least $\lfloor n/4 \rfloor+1$ occurrences.
>
> Find three indexes that will surely "hit" all such numbers. Explain why it's certain.

Because this is a sorted array, all such numbers will be stacked together, so each "number group" have a limited freedom to travel around the array.

It feels like going symmetrically for $n/4$, $n/2$ and $3n/4$ would be a wise guess, but I'm not sure how to prove it, and furthermore $n$ might not be a multiplicity of 4, so we have to round up or down the indexes.

How can I tackle such question?

# Answer
Let's assume for simplicity that $n$ is divisible by $4$. Aiming for a contradiction, suppose that there is some popular number (a number is popular if it appears at least $n/4+1$ times) which does not appear at any of the positions $n/4,n/2,3n/4$. Denote this popular number by $x$.

> Can $x$ appear before position $n/4$? between positions $n/4$ and $n/2$? between positions $n/2$ and $3n/4$? after position $3n/4$?

If the answer to all of these questions is *no*, then we have reached a contradiction, and the only way out is that $x$ appears in one of the positions $n/4,n/2,3n/4$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Is it possible to eliminate the unit rules in this?
```
S -> aA | bC | CC | a | b | C
A -> B
B -> S
C -> A | S

```

It looks like its going to loop so it would be endless replacing the unit rule....

# Answer
You could remove A,B,C and replace all instances of them in the rule S, with S.
> 0 votes

# Answer
You can always eliminate unit rules. In fact, every context-free grammar can be massaged to one in Chomsky normal form, and there are several algorithms doing that. Their treatment of unit rules is more subtle than what you suggest.
> 1 votes

---
Tags: context-free, chomsky-hierarchy
---


# Question
Title: Why do we need "potential” for amortized analysis?
In the current version as of the Wikipedia article “Potential method”, the amortized cost of each operation is defined as the following $$ T\_{\mathrm{amortized}}(o) = T\_{\mathrm{actual}}(o) + C \cdot (\Phi(S\_{\mathrm{after}}) - \Phi(S\_{\mathrm{before}})), $$

and the total amortized cost is $$ \begin{align\*} T\_{\mathrm{amortized}}(O) &= \sum\_i (T\_{\mathrm{actual}}(o\_i) + C \cdot (\Phi(S\_{i+1}) - \Phi(S\_{i}))) \\ &= T\_{\mathrm{actual}}(O) + C \cdot (\Phi(S\_{\mathrm{final}}) - \Phi(S\_{\mathrm{initial}})). \end{align\*} $$

I understand the formulas and understand $T\_{\mathrm{amortized}}$ is an upper bound on $T\_{\mathrm{actual}}$ if the initial potential is zero. And I think I understand the basic examples like "binary counter", "two stack FIFO", etc. However, I am puzzled this:

> The actual cost is part of the formula.

I might be wrong but it looks like the actual cost is a known quantity. **If we already know the actual cost, why do we need to add the "potential" to get an upper bound**? It looks useless to me. Can anyone help give an example in which such "potential analysis" is useful?

# Answer
As is unfortunately sometimes the case, Wikipedia is doing a terrible job of explaining what amortized analysis actually is.

The idea of amortized analysis is that while operations may have a bad worst case cost, their *average* cost could be much lower. Average cost means different things in different circumstances. In amortized analysis, here is what it means:

> Suppose that you have a data structure supporting operations $O\_1,\ldots,O\_r$. We say that these operations have *amortized cost* $c\_1,\ldots,c\_r$ if the cost of the sequence $O\_{i\_1},\ldots,O\_{i\_n}$ of operations is at most $$ c\_{i\_1} + \cdots + c\_{i\_n}. $$

This definition is a bit simplistic, since sometimes the amortized cost depends on other auxiliary parameters such as the overall number of operations or the number of operations of a specific type.

The *potential method* is one way of carrying out amortized analysis, that is, of proving that the operations in a certain data structure have some amortized cost. Stated differently, if you want to prove that the amortized cost of $O\_1,\ldots,O\_r$ is $c\_1,\ldots,c\_r$, then one of the techniques is the potential method. There are other techniques as well.

How does the potential method work? You define a potential function $\Phi$ on the state of the data structure. The potential function must be always non-negative, and for the initial data structure it must be zero. You then prove that if at state $S\_{\text{before}}$ you execute operation $O\_i$ which leads to state $S\_{\text{after}}$, then the cost $T\_{\text{actual}}$ of the operation satisfies $$ T\_{\text{actual}} \leq c\_i + \Phi(S\_{\text{before}}) - \Phi(S\_{\text{after}}). $$ Given that this holds for all $i$, consider a sequence of operations $O\_{i\_1},\ldots,O\_{i\_n}$, and denote the corresponding states of the data structure by $S\_0,\ldots,S\_n$. The upper bound on $T\_{\text{actual}}$ implies that the total cost of these operations is at most $$ \begin{align\*} \sum\_{t=1}^n \[c\_{i\_t} + \Phi(S\_{t-1}) - \Phi(S\_t)\] &= \sum\_{t=1}^n c\_{i\_t} + \sum\_{t=1}^n \[\Phi(S\_{t-1}) - \Phi(S\_t)\] \\ &= \sum\_{t=1}^n c\_{i\_t} + \Phi(S\_0) - \Phi(S\_n) \\ &= \sum\_{t=1}^n c\_{i\_t} - \Phi(S\_n) \\ &\leq \sum\_{t=1}^n c\_{i\_t}, \end{align\*} $$ which was to be proven.
> 4 votes

---
Tags: algorithms, complexity-theory, amortized-analysis
---


# Question
Title: Is the exact cover problem NP-hard when there is a restriction on the size?
The exact cover problem with restrictions on the size is:

*Input:* Given a set $U=\\{1,2,\ldots,n\\}$ and a collection of $C$ of subsets of $U$.

*Question:* Is there a subcollection $C^\star$ of $C$ such that

* The intersection of any two distinct subsets in $C^\star$ is empty;
* The union of the subsets in $C^\star$ is $U$; and
* The size of any set $S\in C^\star$ is at most $\log\_2 n$, i.e., $|S|\leqslant \log\_2 n$ for all $S\in C^\star$.

Is this problem NP-hard?

# Answer
Yes, it is still NP-hard. In fact, it remains hard even if you replace $\log\_2 n$ with the constant 3. This follows by reduction from 3-dimensional perfect matching.

3-dimensional perfect matching is the following problem:

*Input:* disjoint sets $X,Y,Z$ such that $|X|=|Y|=|Z|$; a set $T \subseteq X \times Y \times Z$

*Question:* does there exist a perfect matching? In other words, does there exist $S \subseteq T$ such that $|S|=|X|$ and the union of elements of $S$ is an exact cover for $X \cup Y \cup Z$?

From this statement of the problem, it is clear that 3-dimensional perfect matching is a special case of your problem: take $U=X \cup Y \cup Z$ and $C = \\{\\{x,y,z\\} : (x,y,z) \in T\\}$.

---

In contrast, if the size of every set is at most 2, then it can be solved in polynomial time, using algorithms for finding a perfect matching in an undirected graph.
> 4 votes

---
Tags: np-hard, set-cover
---


title: "Uniform" Set Cover Approximation?

text:
# Question
Title: "Uniform" Set Cover Approximation?
The (optimization version of) Set Cover problem is the following: given a "universe" set $S$ and a collection of subsets $S\_1, \cdots, S\_m \subseteq S$, we want to find the minimum cardinality set of $k$ elements $\\{i\_1, \cdots, i\_k\\}$ such that $\bigcup\_{i=1}^k S\_{i\_j} = S$.

It is a well-known result in an introductory approximation algorithms class that this problem has no $O(\log n)$-factor approximation unless $P = NP$.

However, I'm interested in a restricted version of the problem: suppose that $|S\_i| = n$ for all $i$ (i.e., all the subsets are exactly the same size). This problem turns out to still be $NP$-complete, but is there a better approximation ratio one can achieve?

I don't know if there is terminology for the problem (I dubbed it "uniform" here), because searching through Google Scholar and the arXiv has not yielded much.

# Answer
> 1 votes
No, one can't achieve a better approximation ratio for your problem. This follows by a simple padding argument.

Let $S\_1^\*,\dots,S\_m^\* \subseteq S^\*$ be an instance of ordinary set cover (where the sizes of the sets are not restricted to be the same). Let $n = |S|$. Define $S^\* = S \cup \\{1,2,\dots,n\\}$ where it is assumed that $1,2,\dots,n$ represent $n$ new symbols not found in $S$. Also define $S\_i = S^\*\_i \cup \\{1,2,\dots,n-|S^\*\_i|\\}$ and $S\_{m+1} = \\{1,2,\dots,n\\}$. Then $S\_1,\dots,S\_m,S\_{m+1} \subseteq S$ form an instance of your uniform set cover problem; by construction, the sets $S\_1,\dots,S\_m$ all have the same size. Moreover, the minimum cardinality cover for the original problem $S^\*$ differs in size from the minimum cardinality cover for the uniform problem $S$ by at most one, since given any solution $\\{i\_1,\dots,i\_k\\}$ for the original problem we obtain a valid solution $\\{i\_1,\dots,i\_k,m\\}$ for the uniform problem, and vice versa, any valid solution for the uniform problem is also a solution for the original problem.

It follows from this reduction that uniform set cover has the same approximation factor as ordinary set cover. Thus, all the standard approximability results for set cover carry over to your problem as well.

---
Tags: reference-request, approximation
---


# Question
Title: algorithm for predicting procces's memory/cpu usage based on other other prior/still running jobs
In a 'pool' with a lot of cpus ,jobs(processes) are running(lots of them) .

Given I have time/resource usage 'samples' from many prior/still running jobs - how would you go about trying to predict the process resource usage ?

Very abstractly , what I think should be done is as follows :

**1**) New job is submitted and start running and I wait for some time to gather resource usage information/samples

**2**) find a subset of jobs that their 'behave' (up until that point in running time) 'similarly' - how would u do that ? maybe those who are always in a specific margin and also there average distance is closest ?

**3**) choose one job from the subset I found at stage 2, and give prediction of resource usage based upon that job..

Are there known/standard way for my objective ? Would love to hear your ideas,direction etc ..

# Answer
Here are the broad outlines of one general approach:

1. Determine what observable attributes of a job might help you predict the resource usage of the job. You'll have to hypothesize what these might be based on your domain knowledge of the kinds of jobs you run, as well as your knowledge of what attributes of a job can be measured and observed, before the job finishes.
2. Treat that set of observable attributes as the "feature vector" for the job. Each job gets assigned a "feature vector", based on the values of those attributes.
3. Gather training data: gather a data set, from past jobs, where you have measured the attributes of the jobs before they finished running and also measured the actual resource usage of those jobs.
4. Now use some suitable machine learning algorithm to predict the resource usage of new jobs, based on the training set and the attributes of the new job. Select some appropriate supervised learning algorithm. The choice of a specific algorithm will depend on how you expect the resource usage to vary depending on the attributes. (Is it a linear relationship? Smooth curve? Something else?) You might choose linear regression, or CART trees, or something else entirely. There's lots of literature on this -- I'll leave you to study it on your own and get up to speed on standard materials on this subject.

You'll have to work out the details on your own and play with it a bit to see how well it works in your particular setting. I can't tell you whether or not this will work well in the end; that will depend on your particular workload and the types of jobs you are dealing with.
> 1 votes

---
Tags: algorithms, machine-learning
---


title: Inverse Homomorphisms and Kleene star

text:
# Question
Title: Inverse Homomorphisms and Kleene star
The exercise is to prove or give a counterexample to the following proposition with $L \subseteq \Gamma^\*$ regular and $h: \Gamma \to \Sigma^\*$ a homomorphism.

Is there any regular language $L'$ such that $h^{-1}(L^\*) = L'^\*$ ?

I know that it isn't that easy to see, since $h^{-1}(L^\*) \not= h^{-1}(L)^\*$ in general with $L = \\{a\\}$ and $h : \\{a,b\\} \to \\{a\\}^\*$ with $h(a) = a, h(b) = aa$. It is $h^{-1}(L^\*) = \\{a,b\\}^\* \not= \\{a\\}^\* = h^{-1}(L)^\*$.

I still fail to deliver a proper argument to prove it.

# Answer
> 5 votes
Since you solved the first question, let me answer the second one. If you don't mind, I will use $h$ instead of $h'$ for simplicity. Let $L$ be a regular language and let $K = h^{-1}(L^\*)$. Since regular languages are closed under inverses of homorphisms, $K$ is regular. Moreover, if $u, v \in h^{-1}(L^\*)$, then $h(u), h(v) \in L^\*$ and hence $h(uv) = h(u)h(v) \in L^\*$. It follows that $uv \in h^{-1}(L^\*)$ and thus $K = K^\*$. Consequently, $h^{-1}(L^\*) = K^\*$, which answers your question.

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


# Question
Title: Why divide by $b-1$ when computing size of a tree
In one of the lectures I went to, my professor stated that in order to determine the size of a search tree, we use the following formula: $$\frac{b^{d+1}-1}{b-1},$$ whee $b$ is the branching factor and $d$ is the depth of the tree in question. I would like to understand why we divide by $b-1$. I would have thought that the correct solution is $b^{d+1}-1$.

# Answer
> 5 votes
There are $b^i$ nodes at depth $i$, and so the total number of nodes is $$ 1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1}, $$ using the formula for the sum of a geometric progression.

---
Tags: trees, search-trees
---


# Question
Title: If X reduces to a problem in NP, is X in NP?
Let $X$ and $Y$ be problems, and let $X \le\_p Y$. Is it true that \begin{equation} Y \in NP \rightarrow X \in NP\ ? \end{equation}

I do mean $NP$ here, not $NP$-complete or $NP$-hard.

The solution is simple if the reduction from $X$ to $Y$ transforms an instance of $X$ to an instance of $Y$; to verify that a solution to $X$ is correct, we could transform it to an instance of $Y$ and then verify that the transformed instance is a solution to $Y$.

All we know from $X \le\_p Y$, though, is that you can solve $X$ with a polynomial number of solutions to $Y$; we're not guaranteed a simple one-to-one transformation.

I suspect that \begin{equation} Y \in NP \rightarrow X \in NP \end{equation} is true for all $X,Y$ such that $X \le\_p Y$, but I would like confirmation, and I would like to know how to prove it.

# Answer
> 8 votes
The answer depends on what you mean by the notation $\le\_p$.

* If $\le\_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes". It follows from the definition of NP. See What is the definition of P, NP, NP-complete and NP-hard? to learn more.
* Assuming that $\le\_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT. Then $X \le\_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY). We know that SAT is in NP. However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise. While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

---
Tags: complexity-theory
---


# Question
Title: Is complement of diagonal language countable?
I tried to find out how to arrange the complement of diagonal language, but I failed. So I'm about to believe that it's not a countable language. Could you, please, help me?

# Answer
> 9 votes
A language is a set of finite strings over some finite alphabet $\Sigma$. Therefore, *every* language is countable. You can see this by considering $\Sigma = \\{0, \dots, d\\}$ for some $d\in\mathbb{N}$ and now you can associate any string with a natural number written in base $d$. To avoid the problem that, e.g., $0$ and $000$ denote the same number (and I guess $\epsilon$ counts as zero, too), we actually associate the string $x\_1\dots x\_n$ with the number $1x\_1\dots x\_n$. Thus, we have an injection from $\Sigma^\*$ to $\mathbb{N}$, so $\Sigma^\*$ is countable and so are all its subsets.

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


# Question
Title: Binary search algorithm - worst-case complexity
I tried to calculate the worst case of binary search (not binary search tree). My calculations: $$T(n) = T\left(\frac{n}{2}\right) + 1$$ $$T(n) = T\left(\frac{n}{4}\right) + (1+1) = T\left(\frac{n}{8}\right) + (1+1+1) = {\dots} = T\left(\frac{n}{2^{k}}\right)+(1\cdot k) $$ $$T(n)=T(1) + (1\cdot k) = c\_{1} + (1\cdot k) = c\_{1} + log\_{2}n = c\_{1}+\frac{log(n)}{log(2)} $$ Finally the complexity should be $$O(log(n)) $$ Is this a good way to prove the worst case complexity of binary search algorithm? Make I mistakes?

# Answer
> 1 votes
A much better way is to use the master method :), check that out!

# Answer
> 2 votes
That's a way to do it. Sometimes it's easier to go the other way round: What is the size of the largest array where binary search will locate an item or determine it's not there, using k comparisons? And it turns out that the largest array has size $2^k - 1$. And then you reverse this.

Understanding the master method is very useful if you have to pass a test that tests whether you understand the master method. But be prepared to have more practical problem where the only method that works is the "turn on your brain" method. A simple example is the Greatest Common Divisor algorithm.

---
Tags: complexity-theory, recurrence-relation, binary-search
---


# Question
Title: Find out duplicate number between 1 to N numbers
I first saw this question on this website where I was trying on Java puzzles.

Here is the Question:-

```
You are given in an ArrayList, 1 to N Numbers. For Example, 1,2,3,4,5. However, one of
the numbers is repeated twice. That is, in the form 1,2,3,4,2,5. Find the duplicate number
without using loops.

```

I thought that this could be done with 2 For loops, and tried running the program which Worked fine. However, the question specified otherwise. Therefore, I checked the answer, which read as follows :-

```
int highestNumber = numbers.size() - 1;
int total = getSum(numbers);
int duplicate = total - (highestNumber*(highestNumber+1)/2);
return duplicate;

```

Here `numbers` is the List(Java) which contains the elements. The `getSum(List n)`method returns the sum of all the elements in the List.

Then comes this line which I fail to understand. How does `total - (highestNumber*(highestNumber+1)/2);` result in the correct Answer?

**Edit1: As answered below the formula - n(n+1)/2 is derived from Arithmetic Progression. More details are here**

# Answer
Here is the question:

> You are given a list of length $n+1$ which contains the numbers $1,\ldots,n$, one of them appearing twice (and the rest appearing once).
>
> Find the number which appears twice.

The sum of numbers from $1$ to $n$ is $\frac{n(n+1)}{2}$, so if you subtract that from the sum of the list you get the number appearing twice.
> 6 votes

# Answer
The answer is simple, but very unsatisfying - because you don't actually know whether the claim is true or not after you give the answer. For example, if you do the calculation and the result is -3 or n+7, what now? It's fine as a puzzle, but not in computer science or in serious software development.

There is a simple O (n) algorithm, posted to a previous question, that will exchange array elements so that the elements will be ordered 1 to n, followed by the duplicate, *if* that is indeed what the array contained. What it actually does is storing the numbers 1 to n once into their right place, so you can then check easily which numbers are not present at all, and which one are either outside the range 1 to n, or are duplicates.
> 1 votes

---
Tags: algorithms, java, lists, real-numbers
---


title: Machine Learning - Data Pre-Processing

text:
# Question
Title: Machine Learning - Data Pre-Processing
I'm trying to do some non-linear predictions and am going to use a random forest with Sk-learn. However my question has to do with data pre-processing.

I'm planning on using minmaxscaler to normalize the temperature, wind, and humidity data...however I have two other variables class, and month. Class is a category data feature which I'm going to use OneHotEncoder to pre-process. However do I want to normalize or do anything with the month data? (Normalize on scale of 0 to 1? Or leave 1-12?) What might be the best approach?

Thanks!

# Answer
No. You can leave the month as is. It shouldn't matter. For a random forest, there's no value in normalizing it; it won't make the classifier any more or less accurate.

(The same is actually true for temperature, wind, and humidity data, too: there's no harm in normalizing them, but also no benefit, if you're using a random forest classifier.)
> 0 votes

---
Tags: machine-learning
---


# Question
Title: On asymptotic complexity class notation?
Is the class of problems with complexity $O(n^{n^\epsilon})$ at every $\epsilon\>0$ same as class of problems with complexity $O(n^{f(n)})$ at every $f(n)\in\omega(1)$ and hence both classes are equivalent to $\mathsf P$ ($n$ is number of input bits)?

(This is my view. Denote $C(n^{n^\epsilon})$ to be class of problems solvable in $O(n^{n^\epsilon})$ at every $\epsilon\>0$ and let $D(n^{f(n)})$ be class of problems solvable in $O(n^{f(n)})$ at every $f(n)$ in $\omega(1)$. Does $\cap\_{f(n)\in\omega(1)}D(n^{f(n)})=\cap\_{\epsilon\>0}C(n^{n^\epsilon})$ hold? $\forall n\in\Bbb N\wedge\forall\delta\>0 \exists\epsilon\>0:n^\epsilon\<1+\delta$ and so $C(n^{n^\epsilon})$ is smaller than $D(n^{f(n)})$ at every $f(n)$ in $\omega(1)$. However for every $\epsilon\>0$ there is an $f(n)\in\omega(1)$ such that $f(n)\<n^\epsilon$ at large enough $n\in\Bbb N$ and so $D(n^{f(n)})$ at any $f(n)$ in $\omega(1)$ is smaller than $C(n^{n^\epsilon})$. We then conclude both $O(n^{n^\epsilon})$ and $O(n^{f(n)})$ at any $f(n)\in\omega(1)$ are morally equal. Since $O(n^{f(n)})$ at any $f(n)\in\omega(1)$ is same as $\mathsf P$ we have the notation.).

# Answer
> 2 votes
The time hierarchy theorem shows that there are problems which can be solved in time $O(n^{\log n})$ but not in time $O(n^{\log\log n})$. These problems can be solved in time $O(n^{n^\epsilon})$ for any $\epsilon \> 0$, but not in polynomial time.

---
Tags: asymptotics, notation
---


# Question
Title: Are there programs that can 'translate' source code between any two languages?
Are there programs that can 'translate' source code between any two languages (assuming the translator has access to the requisite libraries)?

If there are, how do they work (techniques used, knowledge required, etc)? How would they feasibly be constructed?

If they aren't, what are the restrictions preventing their development? Is this an A.I complete problem (natural language translation is listed as one)?

***EDIT*** Conversion is only expected, when the language has the same expression power, can solve the same kind of problems and the code to be converted **can** be expressed in the destination language. (E.g conversion from a shell script to MATLAB isn't expected).

# Answer
TLDR; this is possible but not practical.

> (assuming the translator has access to the requisite libraries)?

This ends up being the tricky bit, and is part of why things like this don't end up being used in practice.

1. **All compilers are translators.** Translating from one language to another is definitely possible, and this is literally all a compiler is doing. The language that a compiler spits out as output is generally machine code or assembly, but this is just another language, and there are compilers (sometimes called transpilers or transcompilers) which translate between two languages. For example, there's a gamut of compile-to-Javascript languages like PureScript, Elm, ClojureScript, etc.
2. **Translating between any two Turing Complete languages is always possible.** Ignoring things like library calls and FFI and other nasty practical bits that get in the way, that is. If a language is Turing Complete, then you have:

* A translation that converts a Turing Machine to code in this language
    * A translation from this language into a Turing Machine

So to translate from language A to language B, you convert the A code into a Turing Machine, then convert that machine into B code.

Of course, in practice, the practical bits get in the way, and this also requires you having the translations accessible to you. They exist for basically every language, but that doesn't mean someone has taken the time to write them out.
3. **Doing this translation efficiently is hard**. Different language prioritize different things. For example, if you translate from C to Python, you're probably going to have to end up simulating C's memory as a Python dictionary, so that you can do pointer arithmetic. There will be overhead associated with this, because you're now not accessing the bare metal memory instructions.

Different languages have difference performance priorities, so something that one language optimizes (or rather, an implementation of one language optimizes) might be impossible to do quickly in another language. Translating a functional language with proper tail calls will have slowdown if you translate it into a language without proper tail calls.
4. **Doing this translation doesn't make the code readable**. It's easy to get a piece of code in language B that behaves the same as the code from language A. It's hard to make it look like code a human would have written in B, for a number of reasons. A and B might have different abstraction tools, and the computer has no idea what makes code readable. This will be particularly true if you end up using the Turing Machine translation I described earlier.

This raises the question: what's the point of such a translation? If all you get at the end us a block of slow, unreadable code, why not just compile it to machine code and use some kind of FFI or inter-process communication to link the pieces together?

There are some exceptions to this. Sometimes you need things in a certain language (like JavaScript). Sometimes language are similar, and a sensible translation is easy. Sometimes a language is not meant to be run, but to have its code extracted into another language (such as Coq).

But in general, it's not a very practical thing.
> 57 votes

# Answer
There are such programs. For example Lisp-to-Fortran translators, that were widely used at their time. Sole Lisp compilers don't compile Lisp directly but generate C code instead that then is compiled by a regular C compiler. Another example would be Vala that isn't compiled directly but first translated to C++ before the C++ code is compiled. Qt is written in MOC, a language that is translated to C++ in order to compile it (but as MOC is just C++ with a few additional commands one can argue if it really is to be named a "new language") - and before there were C++ compilers there were C++-to-C-translators. And some projects were written in Pascal and then translated to C. Also clang and Java tend to be kind of such a thing as they translate C++ and Java code to some intermediate language that then can be processed further.

What you cannot expect of the output of a language translator is that the result makes any sense for an human reader: The program's task is to write code that results in a program doing the same as the original code (which in my experience might or might not work, depending of which features of the language and which external libraries you were using). But as it doesn't know the purpose this task is done for the rest of the program's meaning might be lost to a big extent.
> 2 votes

# Answer
Not a direct answer, but in there is a tool call ILSpy, which was written for the .Net Framework, and allows you to decompile a .Net assembly into C# or VB.Net.

If your unfamiliar with the nature of .Net, you can write .Net code in many languages but primarily C# or VB.Net. When the compiler compiles the application, it translates the code to an "Intermediate Language" (or IL for short) code. This code is then compiled to .Net binaries.

Since .Net applications are are binaries compiled from the IL code, ILSpy can take the .Net application, reverse it back to IL code and, subsequently, take it one step further and reverse it back to C# or VB.Net.

Using this tool, all you have to do is compile an application, and then you can browse the compiled files as IL, C# or VB.Net code. To be clear, it doesn't matter what language the code was initially written in. So long as the binary is a .Net assembly, it can reverse-engineer the compiled files and output the content as any of these three languages.

I know this isn't exactly a compiler, but it is a tool that offers an end-result similar to what you are looking for and, in fact, I've used this to "translate" VB.Net projects into something a little more familiar to me-- C#.
> 0 votes

# Answer
For your use-case (based on comments), it sounds like SWIG might be useful.

> SWIG is a software development tool that connects programs written in C and C++ with a variety of high-level programming languages. SWIG is used with different types of target languages including common scripting languages such as Javascript, Perl, PHP, Python, Tcl and Ruby. The list of supported languages also includes non-scripting languages such as C#, Common Lisp (CLISP, Allegro CL, CFFI, UFFI), D, Go language, Java including Android, Lua, Modula-3, OCAML, Octave, Scilab and R. Also several interpreted and compiled Scheme implementations (Guile, MzScheme/Racket, Chicken) are supported.
> 0 votes

# Answer
I recall the venerable f2c, which does source-to-source translation from Fortran 77 to C.

It was (sometimes is...) used mainly to translate numerical code from decades ago without having to integrate a fortran compiler to your toolchain.
> 0 votes

# Answer
The piece of theory that tells you that such programs exist, in principle, is called *admissible numberings*. We can prove that there are computable compilers between any two such numberings, and every Turing-complete formalism (or programming language) is, in essence, one.
> 0 votes

---
Tags: computability, programming-languages, compilers
---


# Question
Title: How to convert a decimal number to ASCII representation
The question that was in my lecture notes said

```
    "Encode the decimal number 2370  in ASCII. "

```

and the answer given there is

```
    32 33 37 30 (ASCII code representation)

```

My question is how do we get this? Do we simply add 30 to each digit? I am sorry if this is a very obvious question I do not know the correct way to look up the ASCII table for conversions. Any help would be appreciated.

PS: This is not my homework, my course finished today morning. Just asking out of curiosity.

# Answer
> 0 votes
The ASCII encodings for digits 0 to 9 are 48 to 57 in decimal, or 30 to 39 in hexadecimal.

---
Tags: number-formats
---


# Question
Title: How to find subset of vectors whose sum has certain characteristics
Let's say you have list of $n$ vectors with entries from $\\{0,1,x\\}$ and $x$ is \> $n$:

$$ \begin{align\*} L\_0 &= \[1,0,x\] \\ L\_1 &= \[1,1,1\] \\ L\_2 &= \[1,0,0\] \\ L\_3 &= \[x,1,0\] \\ L\_4 &= \[1,x,0\] \end{align\*} $$

I want to find all combinations of $m$ vectors (subsets of vectors from this list) whose elementwise sum in this combination will have exactly $m$ occurrences of $x$. Is there an algorithm to do this in less than $O(m^n)$ time?

In my example, if $m=2$, the only valid combination is $L\_0 + L\_4 = \[1+1, 0+x, x+0\] = \[2, x, x\]$. If $m=1$, valid answer is \[$L\_0$, $L\_3$, $L\_4$\].

Key is: are there's any way to solve this problem without iterating over all $m^n$ combinations.

This might sound like an interview question, but in fact it is a task that I reduced my problem to.

# Answer
The question has changed. I'll answer the updated question. Here are three candidate algorithms; the first is faster than $O(m^n)$ time, and the second might be faster as well for some parameter values. I will assume that the vectors are from $\mathbb{R}^d$, i.e., $d$-dimensional vectors (in your example $d=3$).

### Try all subsets

There are exactly ${n \choose m}$ subsets of $m$ vectors. You can try each, compute what its sum is, and count how many $x$'s it has. The running time will be $O(nd \cdot {n \choose m})$, and can be optimized to run in time $O(d \cdot {n \choose m})$. Note that ${n \choose m} \le 2^n$ and can be significantly smaller than $m^n$, so if we ignore the dependence on $d$, this is faster than your $O(m^n)$ time to beat.

### Try all target vectors

Alternatively, we can try all possibilities for which $m$ locations (coordinates) in the sum contain a $x$. There are ${d \choose m}$ such possibilities. For each, we will try to find a subset of the input list whose sum has a $x$ in those special locations (coordinates), and no $x$ in any other location (coordinate). We'll temporarily ignore the requirement to have a subset of size exactly $m$.

Note that any valid solution must use only vectors that whose special coordinates all have entries from $\\{0,x\\}$ (in particular, no special coordinate can contain a $1$). (Any vector with a $1$ in any special coordinate can't be included in any valid combination; if it were included, the sum in that coordinate would be either $\ge x+1$ or $\le n$, according to whether we include any other vector with a $x$ in that coordinate or not.)

So, let's focus only on those $m$ coordinates, and ignore (throw away) all the others. In this way each $d$-vector is reduced to a $m$-vector. Then, we look for a subset of the input vectors that sums to the $m$-vector $\[x,x,\dots,x\]$. This is a multi-dimensional subset-sum problem. This particular subset-sum problem has a special form: it turns out to be an instance of the exact cover problem, and can be solved with standard algorithms for exact cover. The running time will be exponential in $m$. So, we'll solve the exact cover problem in $m$ dimensions, and then check each solution to see whether it is a valid solution to the original problem.

We repeat this ${d \choose m}$ times (once for each subset of $m$ coordinates). The running time to solve each instance of the $m$-dimensional exact cover problem is exponential in $m$, and we must solve ${d \choose m}$ of them, so the running time will be something in the vicinity of $O({d \choose m} \cdot 2^m)$.

Alternatively, given a target vector (a set of $m$ special coordinates), we could use integer linear programming to search for a subset of $m$ of the input vectors that sum to $\[x,x,\dots,x\]$ in those $m$ coordinates. This will again take time exponential in $m$, in the worst case, for each target vector, though in practice it might be faster. One nice thing about integer linear programming is that it lets you directly express the constraint that the subset must be of size $m$. Also, it may be fairly easy to implement this approach using an off-the-shelf ILP solver.

This algorithmic approach may be better or worse than the other schemes, depending on the values of $m,d$. If $m$ is very small or very close to $d$, this approach may be an improvement on the others.

### Dynamic programming

There is a dynamic-programming algorithm whose running time is $O(nd \cdot 3^d)$. Basically, we have a table that keeps track of which $d$-dimensional vectors can be expressed as a sum of some subset of the input vectors.

Given an entry of a vector, we'll classify into one of three categories: $0$ (meaning the entry is $0$), $☹$ (meaning the entry is not $0$ and not $x$), and $x$ (meaning the entry is $x$). These have the obvious addition rules, e.g., $☹ + x = ☹$, $☹ + ☹ = ☹$, and so on. Thus, each vector mapped to a template where its entries are classified in this way; a template is a value $t \in \\{0,☹,x\\}^d$. A template stands for one or more vectors.

Now, for each template $t \in \\{0,☹,x\\}^d$, the table keeps track of whether any vector that matches the template $t$ can be reached by summing any subset of the input vectors. This table will have at most $3^d$ entries, since there are at most $3^d$ possible templates. You can fill in the entries of the table using dynamic programming in $O(nd \cdot 3^d)$ time. Finally, we check the table to see whether the template $\[x,x,\dots,x\]$ is expressible as a sum of input vectors. YAs described, this tells you whether any valid combination exists; you can augment this algorithm to keep track of all valid combinations.

This might be workable if $d$ is not too large; otherwise, it will be highly inefficient. It has the benefit of being not too difficult to implement, but it is probably strictly worse than the prior algorithm in asymptotic efficiency.

### Integer linear programming

Finally, it is possible to encode your problem directly as an instance of ILP. I suggest you introduce zero-or-one variables $X\_1,\dots,X\_n$, with the intent that $X\_i=1$ means input vector $v\_i$ is included in the combination. Also, define $w = \sum\_i X\_i v\_i$, and introduce zero-or-one variables $Y\_{j,0},Y\_{j,1},Y\_{j,x},Y\_{j,2x}$ for $j=1,\dots,d$, with intended meaning as follows:

* $Y\_{j,0}=1$ means that $w\_j$ is zero.
* $Y\_{j,1}=1$ means that $w\_j$ is not divisible by $x$.
* $Y\_{j,x}=1$ means that $w\_j$ is $x$.
* $Y\_{j,2x}=1$ means that $w\_j$ is a multiple of $x$ that is strictly larger than $x$ (i.e., $2x$ or $3x$ or ...).

I'll show how to enforce consistency of these variables in a moment using linear inequalities. Once we've done that, all that remains is to require that $X\_1 +\dots + X\_n=m$ (a combination contains exactly $m$ of the input vectors) and $Y\_{1,x}+\dots+Y\_{d,x}=m$ (exactly $m$ of the coordinates sum to $x$) and then test whether the entire system of inequalities is feasible, and if so, report all solutions. That can be done using an off-the-shelf ILP solver.

To enforce the consistency of the $X$'s and $Y$'s, we add the following linear inequalities:

* $Y\_{j,0}+Y\_{j,1}+Y\_{j,x}+Y\_{j,2x}=1$ for each $j$ (exactly one of those four cases must be true).
* $X\_i \le 1-Y\_{j,0}$ for each $i,j$ such that $v\_{i,j}\>0$ (something that sums to zero can't have any nonzero terms in the sum).
* $\sum\_{v\_{i,j}\>0} X\_i \ge 1-Y\_{j,0}$ for each $j$ (if it doesn't sum to zero, at least one of the terms in the sum is nonzero).
* $\sum\_{v\_{i,j}=1} X\_i \ge Y\_{j,1}$ for each $j$ (something that sums to a non-multiple of $x$ must have at least one term that is a $1$).
* $X\_i \le Y\_{j,1}$ for each $i,j$ such that $v\_{i,j}=1$ (if the sum has a term that is a $1$, then it sums to a non-multiple of $x$, since $x\>n$).
* $\sum\_{v\_{i,j}=x} X\_i \ge Y\_{j,x}$ (anything that sums to $x$ must have at least one term that is an $x$).
* $\sum\_{v\_{i,j}=1} X\_i \le 1-Y\_{j,x}$ (anything that sums to $x$ cannot have any terms that are a $1$).
* $\sum\_{v\_{i,j}=x} X\_i \ge 2Y\_{j,2x}$ (anything that sums to a multiple of $x$ larger than $x$ must have at least two terms that are an $x$).
* $\sum\_{v\_{i,j}=1} X\_i \le 1-Y\_{j,2x}$ (anything that sums to a multiple of $x$ larger than $x$ cannot have any terms that are a $1$).

### Hardness

Your problem is NP-hard. Consider the special case of your problem where all entries are in $\\{0,x\\}$ (no input vector contains a $1$), where $m=d$, and where there are at least $m$ copies of the all-zeros vector in the input list. This special case is equivalent to exact cover, which is NP-hard. If a special case of your problem is NP-hard, then your problem is certainly NP-hard. So, we shouldn't expect an efficient algorithm for your problem. See What is the definition of P, NP, NP-complete and NP-hard?, What are common techniques for reducing problems to each other?, and Dealing with intractability: NP-complete problems for some reference material on those subjects, or grab a good algorithms textbook.
> 5 votes

---
Tags: algorithms, combinatorics, linear-algebra
---


# Question
Title: Is Bounded Waiting satisfied for this 2 process Solution?
This is my new post linked with my previous post.

Is bounded waiting satisfied in the 2 Process Solution?

---

The answer in that post was very useful and cleared many concepts, but I just want to apply that answer for this example, that how BW works here .

Especially, I want to know this definition works for this example.

> Define $k$-bounded waiting for a given mutual exclusion algorithm to mean that if $D\_A^j \to D\_B^l$ then $CS\_A^{j} \to CS\_B^{l+k}$.

---

Here, the Question comes

> What can be said bout the Bounded Waiting of this 2 process solution"

**\<------- P1 -------\>**

```
While(True)
{
    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)
}

```

**\<-------- P2 --------\>**

```
While(True)
{
    acquire(lock1)
    acquire(lock2)
        withdraw(from, amount)
        deposit(to, amount)
    release(lock2)
    release(lock1)
}

```

# Answer
In the following, I treat the first two statements `acquire(lock1) acquire(lock2)` as "trying", the middle two statements `withdraw(from, amount) deposit(to, amount)` as the "critical section", and the last two statements `release(lock2) release(lock1)` as "exiting".

This algorithm does not satisfy the bounded waiting property. Consider the following execution: $P\_1$ and $P\_2$ simultaneously execute `acquire(lock1)` and $P\_1$ wins. $P\_1$ acquires `lock2` successfully, enters the critical section, and then exit by releasing locks. Now, $P\_1$ and $P\_2$ contend on `acquire(lock1)` again and $P\_1$ wins again .... In this way, $P\_2$ is actually starved.
> 3 votes

---
Tags: operating-systems, synchronization, deadlocks
---


title: Starvation is possible or not?

text:
# Question
Title: Starvation is possible or not?
let S and Q to be initialized to 1

```
process p0:          process p1:

wait(S);             wait(Q);
wait(Q);             wait(S);

..                    ..
..                    ..
Signal(S);           Signal(Q);
Signal(Q);           Signal(S);

```

I know there is a deadlock , where both the process will be going into the sleep , so what about starvation and bounded waiting?

My approach:

as only p0 can be executed any number of times i think there will be starvation and no bounded waiting.But answer is given that there is **No Starvation**.

# Answer
**The answer is wrong**.

**Deadlock** implies **starvation**, and the given code suffers from deadlock, here's how.

Say `p0` executes `wait(S);` and then p1 executes `wait(Q);`. Now both the `semaphores` `S` and `Q` have `value = 0`.Now `p0` will keep on waiting due to statement `wait(Q);` and `p1` will keep on waiting due to statement `wait(S);`.

Freedom from starvation means that:

> if a thread tries to acquire a lock , it will eventually succeed.

This does not happen here, so the answer is wrong.
> 1 votes

---
Tags: operating-systems, synchronization
---


# Question
Title: Is there any decision problem not in NPH but can be reduced to a NPH problem?
I just have taken an algorithm class exam and there was a T/F problem 'one can show that a problem A is in NPH by giving a polynomial reduction from A to a NPH problem B'. I know the direction of reduction is silly, but no counter examples come to mind right now...

# Answer
> 4 votes
Assuming you're using many-one reductions, $\emptyset$ and $\Sigma^\*$ are not **NP**-hard (exercise: prove this!), but they can be reduced to any **NP**-hard problem. Therefore, the statement, "one can show that a problem $A$ is in NPH by giving a reduction from $A$ to a NPH problem $B$" is false.

# Answer
> 2 votes
This is the statement:

> one can show that a problem A is in NPH by giving a reduction from A to a NPH problem B

There are two cases.

1. If P = NP, then NPH contains *all* (non-trivial decision) problems. Then, the statement is silly.
2. If P ≠ NP, then any problem in P serves as a counter-example; the statement is wrong.

Hence, the statement is not something we should make; I daresay it's wrong.

---

Please check that there was no silly mistake on your or your teacher's part. The statement *is* correct if you replace NPH with NP (and use a fitting type of reduction, which is assumed).

# Answer
> 1 votes
Saying problem B is NP-hard means precisely that *any* problem in NP has a polynomial reduction to B.

Consequently, giving a polynomial reduction from problem A to problem B wouldn't show anything useful (assuming A is in NP) -- we already knew there was one, because we knew B was NP-hard.

So the statement is not true unless all problems in NP are NP-hard (i.e. unless P=NP).

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


# Question
Title: Is packing a bag of presents easier for Rupert than Santa?
Or: Do we need Rupert in order to get presents at all?

Routing issues aside, Santa faces the following problem (many, many times over):

> Given a bag with capacity¹ $C$ and a set of presents $\\{p\_1, \dots, p\_n\\}$, each with size $s\_i$, he wants to make children $\\{c\_1, \dots, c\_k\\}$ happy. He knows from all the wish lists that child $c\_j$ values present $p\_i$ exactly $v\_{i,j} \in \mathbb{Q}\_{\geq 0}$ much.
>
> Which (pairwise disjoint) sets of presents $I\_j \subseteq \[1..n\]$ to pick for each child so that everything fits, i.e.
>
> $\qquad\displaystyle \sum\_{j \in \[1..k\]} \sum\_{i \in I\_j} s\_i \leq C$,
>
> and as much happiness as possible ensues², i.e.
>
> $\qquad\displaystyle \max! \sum\_{j \in \[1..k\]} \sum\_{i \in I\_j} v\_{i,j}$ ?

This is clearly not easier than Bin Packing or Knapsack, so poor Santa may have to spend a long time packing bags³.

Now, as we know, his assistant Rupert does not give as unconditionally. He has knowledge about $V\_j$, the maximum value child $c\_j$ may receive based on behaviour during the year; that is, he adds an additional constraint

> $\qquad\displaystyle \forall j \in \[1..k\].\ \sum\_{i \in I\_j} v\_{i,j} \leq V\_j$.

Does that make the problem of packing bags easier? If not always, then under which conditions?

---

1. If the *c*himney diameter is the limiting factor, a similar framework can be established.
2. Let's not concern ourselves with fairness and other ridiculuous ideas.
3. Hence, only one Christmas per year. Q.E.D.

# Answer
After quickly looking at this question, I believe Rupert's extra knowledge of each child's {behavior, max value present} will not *always* make Santa's job easier. Santa will still need to perform a 0/1 knapsack to fill the bags and a Hungarian algorithm as well to maximize the happiness each capitalist child receives on Christmas morning. A simple case where it would make Santa's job quite simple is if every child Santa was considering didn't publish a paper and instead played video games all year received a zero from Rupert (each child would get coal).
> 1 votes

---
Tags: algorithms, complexity-theory, optimization, packing
---


# Question
Title: How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science?
I am studying formal languages and production bases systems (rule-bases systems) and I am a little confused about why do these two word "production" and "rule" mean the same thing in so many context in Computer Science.

In English Language they do not seem to mean the same thing. I am not a native English speaker but I know that a rule refers to something that one should/should not do when talking about people or something that if repeated for many times will give the same result and we say that it works by some rules (the way it works defined by some protocol/procedures that are the same every time).

Production refers to something completely different... the phase of some physical goods or software that are currently being made/produced. THe act of making something either physical or some piece of art, some writing, some drawing, something that is made with physical or mental capacities of someone. We say that the specific thing is produced.

However in Computer science these words that represent completely different things in English mean the same thing in CS. How did this terms ended up being similar in CS.

Is there some sort of etymological dictionary for computer science. A dictionary that tells us how the terms in computer science ended up to be ?

BTW: Interesting fact: neither production neither rule are tags in this Stack Exchange site.

# Answer
> 23 votes
A grammar has "Production rules:" rules about the new sequences of symbols that you can produce from old sequences. In the cases of context-free grammars, this the old sequence is always a single non-terminal symbol.

Sometimes people abbreviate "production rules" to "productions". Sometimes people abbreviate "production rules" to "rules".

The two are not synonymous: there are plenty of things which are rules but are not productions, and people may call a single use of a rule a production, or the rule itself a production. Generally, the hope is that it's clear from the context what is meant.

# Answer
> 6 votes
One of the foundational articles of formal language theory, *Three models for the description of language* (Noam Chomsky, 1956), describes mathematical mechanisms by which sentences can be *produced* (generated), similar to the way in which humans produce sentences when speaking or writing. The sentences are produced by applying rewriting rules, so these rules are language production rules.

The shorthand name *productions* for production rules arose later and is technically inaccurate (Chomsky uses that term in his article to name what is produced by the rules, not as a term for the rules themselves).

---
Tags: formal-languages, terminology, automata, finite-automata, formal-grammars
---


# Question
Title: For data-path cycles in MIPS, what determines wheter a control signal gets the "don't-care" value?
For example for the sw command in MIPs, the control signal values are

ALUOp1: 0

ALUOp: 0

RegWrite: 0

MemRead: x

MemWrite: 1

Branch: 0

ALUsrc: 1

RegDest: x

MemToReg: x

Why do memRead, RegDest and MemToReg have the values of x? Why not just 0?

# Answer
A control signal controls a single component in the architecture. When the command that is now active is not using the component this control signal controls, the control signal gets the "don't care" value.

The principle is that you don't want to restrict yourself for not using this component (=0 value), because any constraint will create a more complex logic inside the cycle. Instead you are freeing yourself from this choice by assigning the control signal with a "don't care" value, which means you can **minimize the logic in the cycle** and allowing the irrelevant component to work in the background (with no obvious bad consequences).

As you mentioned in your example, while using the sw command, you don't need to read anything from the memory. You could assign MemRead with the value 0, but why overkill it? It's easier to don't care if it reads data from the memory or not (it will read gibberish though), and RegWrite=0 (which in turn controls the writing of what was read from the memory) won't allow the use of this read anyway.
> 2 votes

# Answer
It just shows that the implementation works whether it is a zero or a one. If you were to write an assembler for MIPS ISA for example then you could allow those don't cares to be either zero or one. For the other values however it would matter.
> 1 votes

---
Tags: cpu-pipelines
---


# Question
Title: Shortest walk through a given subset of edges
Given an undirected weighted graph $G = (V, \\{E,F\\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once?

---

I'd like to know if there is a general approach to this problem. However, additional constraint may be added for my specific scenario.

The graph $G\_0 = (V, E)$ initially has only edges that must be crossed, but it's disconnected:

* Each connected component is formed by 2 vertices and 1 edge.
* Each vertex $v$ is the endpoint of exactly one edge $\in E$. This means that any two edges $e\_i, e\_j \in E$ don't have a vertex $v$ in common.
* The cost of each edge $e \in E$ is $0$.
* The number of edges in $E$ is at most 1000, usually between 10 and 100.

Then other edges $f \in F$ are added with to link any two vertices (except the one already linked by $e$), so $G = (V, \\{E,F\\})$.

* The cost of each edge $f \in F$ is $\> 0$

---

**Related questions**

I found a few related questions, but they doesn't seem to help:

**Not working solutions**

I tried a few approaches so far, but I'm unable to make them work properly. E.g.:

* Convert $G$ to its line graph $L$. I can't figure out how to assign a proper weight to edges in $L$
* If I can find a proper way to construct $L$, adding a dummy vertex $s$ on $L$ allows to solve this with TSP. Then I'll know the order of the edges $e$, but not the direction.
* I really don't want to use brute-force. It may become impractical very soon.

**Almost-Working solutions for the specific case**

Since by construction every walk will be of the form: $e\_1, f\_1, e\_2, ... f\_n, e\_n$:

1. Compute the weight of the path for each permutation of edges in $E$. The edge $f$ between two edges $e$ will be the mininmum weight one. Pick up the minimum weight path. This solution is brute-force, so not really practical for a large number of edges in E.
2. Start from an edge $e$. Follow the min-cost edge $f$ starting from the end-vertex in $e$. Repeat until all edges in $E$ are reached. This solution is not guaranteed to find the *shortest* path.

# Answer
> 7 votes
This is NP-hard, so it's very unlikely that a polynomial-time algorithm exists.

Given any instance $G=(V, E)$ of Hamiltonian Path, create a new graph $G'=(V', E')$ in which every vertex $v \in V$ becomes a pair of vertices $v\_+, v\_-$ connected by an edge in $G'$. All of these edges should also be added to $F$. Then for each $(u, v) \in E$, add the corresponding 4 edges $(u\_-, v\_-), (u\_-, v\_+), (u\_+, v\_-), (u\_+, v\_+)$ to $E'$ (but not to $F$). All edges in $E'$ get weight 1.

Now if and only if there is a Hamiltonian Path in $G$, there is a path (and thus also a walk) of length $2|V|-1$ in $G'$ that passes through all the edges in $F$. (Exercise: Prove that if a walk having length $2|V|-1$ and passing through all edges in $F$ exists in $G'$, then $G$ has a Hamiltonian Path; the other direction is easy.) IOW, if your problem could be solved efficiently by some algorithm, then that algorithm could be used as a subroutine to solve Hamiltonian Path efficiently too, and people don't think that's very likely.

# Answer
> 1 votes
If you want a walk from $v$ to $u$, and it has to cross every edge of $F$ once, you can do the next: -Duplicate al the nodes from G |F| times (you put every copy in levels) -A node $v\_{i}$ (node in level i) has and edge to a node $v\_{i+1}$ iff this two had an edge in the original graph and this edge is in F. Then, you want the min walk from $v\_0$ to $u\_{|F|}$. You can use Dijkstra for this. I think this works but I'm not sure.

If this is your original graph, the red edges are the ones I want for my path

Then I say to copy it so you have the next graph

Then you want a path from u\_o to v\_2 since there are the paths that uses two red edges. I added weight 1 to the edges because you don't want to cross it more than once. (If the weight were 0, then the min path can go through this edge many times without cost)

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


# Question
Title: Having trouble in understanding the definition of a clique
My definition says

> A clique is a graph that has an edge connecting every pair of vertices

but as I understand, an edge connects only two vertices. Like $A-B$.

If we want to connect three vertices, we need at least two edges. For example, $A-B-C$.

I don't understand how an edge can connect every pair of vertices.

# Answer
Recalling that a clique is a subset $C$ of vertices of an undirected graph such that the subgraph induced by $C$ is fully connected. That is, every two distinct vertices in $C$ are connected by a **distinct edge** of the graph. This means different edges, not the same.

So, on a clique $C$ containing $k$ vertices $v\_1, v\_2,..,v\_k$, there are $\frac{k(k-1)}2$ edges connecting them, that is the number of possible unordered pairs on $k$ elements.

## Example

As you can see in the previous picture, this is a clique on four vertices $\\{{1,2,3,4}\\}$, so there is a different edge connecting every edge (i.e. $(1,2)$,$(1,3)$,$(1,4)$,$(2,3)$,$(2,4)$,$(3,4)$).

You can count them and see that there are exactly $6 = \frac{4\times 3}{2}$ edges.
> 13 votes

---
Tags: graphs, clique
---


# Question
Title: Is there a general algorithm to fill holes in terms of the Calculus of Constructions?
Suppose that you extend the Calculus of Constructions with "holes" - i.e., incomplete pieces of code that you didn't fill yet. I wonder if there is an algorithm to fill those roles automatically. For example (using Morte's syntax):

### Case A:

```
λ (pred : ?)
-> λ (Nat : *)
-> λ (Succ : Nat -> Nat)
-> λ (Zero : Nat)
-> (Succ (pred Nat Succ Zero))

```

On this situation, a type inference algorithm can identify that `?` can obviously only be `∀ (Nat : *) -> (Nat -> Nat) -> Nat -> Nat`, because `pred` receives `Nat : *`, `Succ : Nat -> Nat`, `Zero : Nat`, and must return `Nat`, because it is the first argument of `Succ`.

### Case B:

```
(Id ? 4)

```

Where 4 is λ-encoded and `Id` is the identity function (i.e., `∀ (t:*) -> λ (x:t) -> x`). On that situation, ´?´ is again clearly `∀ (N:*) -> (N -> N) -> N -> N`, because that is the type of `4`.

### Case C:

```
(Id (Equals Nat 7 (add 3 ?)) (Refl 7))

```

Here,`Equals` and `Refl` are defined in a similar fashion to Idris. `?` can obviously only be `4`, but how do you figure that out? One way would be using the fact that `? : Nat`, and `Nat` is a type which we know how to enumerate, so we can just try all `Nats` til it typechecks. That can be done for any enumerable type.

### Case D:

```
(Id (Equal Nat 10 (MulPair ?)) 10)

```

Here, `?` can only be of type `Pair Nat`; it has only more than one valid answer, though: it can be `(Pair 10 1)`, `(Pair 2 5)`, `(Pair 5 2)` and `(Pair 1 10)`.

### Case E:

```
(Id (Equal Nat 7 (Mul 2 ?)) 7)

```

Here, there is no valid answer, since `7` isn't a multiple of `2`.

---

All those examples made me notice that we can make a general algorithm that identifies some known patterns and gives an answer by handpicking a specific algorithm (type inference, brute-force, and so on), kinda like Wolfram Alpha figures out the right strategy to solve an Integral. But that sounds like an engineering/hardcoded approach. Is there a principled way to solve this problem? Is there any research study/area on it?

# Answer
> 9 votes
There is certainly a lot of research into this problem! It often goes by the name of **elaboration**. It is an undecidable problem in general, as you may have guessed. The "holes" are often called **meta-variables** or **unification variables**.

As I explain a bit in this answer, the problem reduces to **higher order unification**, on which several people have written whole PhD dissertations.

As you note in your examples, some cases are somewhat easy, and can be solved by the application of simple rules, whereas some seem significantly more difficult, and have more of a "theorem proving" feel to them.

A third possible case is a "type class" type problem, where `?` represents some kind of *structure*, such as a group or field structure, as in

```
mul ? 2 3

```

with `mul : forall G:Group, G.carrier -> G.carrier -> G.carrier` or some variant. Here we need to find a `G` such that `G.carrier == nat`.

In general, you want to have 3 different "regimes" for each type of problem, the simple unification, theorem proving, and type class resolution problems respectively.

We explain this a bit in the following paper:

Elaboration in Dependent Type Theory, de Moura, Avigad, Kong & Roux.

You might want to look at the references of that paper for more info.

---

I've you've got a strong stomach, here is the open-source for elaboration in Lean.

Here is a wiki post that describes the *interface* to the elaborator in Idris.

---
Tags: machine-learning, programming-languages, unification
---


# Question
Title: Converting If-else condition to Linear Programming
I have a constraint in a linear programming formulation with two variables: $X \ge Y$

To which I want to apply the following if-else conditions:

```
if Y=1:
    X=1
else:
    X=0

```

Where $X$ and $Y$ are binary.

How can I fit this if-else into linear programming? Do I need to define another variable? It looks as an AND operation, between $X$ and $Y$.

# Answer
> 5 votes
This can be expressed with just the equation $X=Y$. Since $X,Y$ are zero-or-one variables, the only possible assignments that are consistent with your condition are $X=Y=0$ and $X=Y=1$.

See Express boolean logic operations in zero-one integer linear programming (ILP) for many more boolean conditions and how to express them as linear inequalities.

---
Tags: linear-programming, integer-programming
---


# Question
Title: On different characterizations of $\mathsf P$
In here it was clarified that $\cap\_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})\subsetneq\cap\_{\epsilon\>0}\mathcal C(n^{n^\epsilon})$ where $\mathcal C(t(n))$ is the class of problems solvable in $O(t(n))$ time.

My query now is whether there is a function of $g(n,\epsilon)$ that non-trivially depends on $\epsilon$ with $g(n,\epsilon)\<g(n',\epsilon')\implies\epsilon\<\epsilon'\vee n\<n'$ such that $\cap\_{f(n)\in\omega(1)}\mathcal C(n^{f(n)})=\cap\_{\substack{\epsilon\>0}}\mathcal C(n^{g(n,\epsilon)})$ can hold?

That is I seek a different characterization of $\mathsf{P}$.

# Answer
I will consider the following simpler version of your question: is there a function $g(n,\epsilon)$ such that the following are equivalent, for a function $f(n)$:

1. $f$ is bounded.
2. For every $\epsilon \> 0$ there exists $N$ such that for $n \geq N$, $f(n) \leq g(n,\epsilon)$.

Consider first the case in which $g(n,\epsilon\_1)$ eventually exceeds $g(n,\epsilon\_2)$ whenever $\epsilon\_1 \> \epsilon\_2$ (like your example $g(n,\epsilon) = n^\epsilon$). Then the second condition can be rewritten equivalently as

3. For every integer $M$ there exists $N$ such that for $n \geq N$, $f(n) \leq g(n,1/M)$.

Define the function $$ f(n) = \max\_{M \leq n} g(n,1/M). $$

This function satisfies condition (3), and so is bounded, say $f \leq C$. This implies $g(n,1) \leq C$. But then the bounded function $C+1$ doesn't satisfy condition (3) for $M=1$. This contradiction shows that under the stated constraint, no function $g$ fits the bill.

On the other hand, as you mention, $f$ is bounded iff it is eventually dominated by every $\omega(1)$ integer function. Indeed, suppose that $f$ is unbounded. Then for every integer $M$ there exist infinitely many $n$ such that $f(n) \geq M$. In particular, we can find an increasing sequence $n\_1,n\_2,\ldots$ such that $f(n\_M) \geq M$. Define a function $g$ by $g(n) = M-1$ for $n\_{M-1} \< n \leq n\_M$. Then $g = \omega(1)$ but $f$ is not eventually dominated by $g$.

The functions from $\mathbb{N}$ to $\mathbb{N}$ have the cardinality of the continuum, and so they can be put (constructively!) in one-to-one correspondence with the real interval $(0,\infty)$. This immediately gives a function $g(n,\epsilon)$ which does fit your bill, though is not particularly natural.
> 1 votes

---
Tags: complexity-theory, complexity-classes, polynomial-time
---


# Question
Title: Is the language $\{ w \in \{ a, b \}^{*} | |w|_{a} + |w|_{b} = 2^{n} \}$ context sensitive?
Is the language $\\{ w \in \\{ a, b \\}^{\*} : |w|\_{a} + |w|\_{b} = 2^{n} \\}$ context sensitive ?

# Answer
> 2 votes
A language is context-sensitive if and only if it can be recognised by a linearly bounded automaton (LBA). To show that $L$ is context-sensitive it is therefore enough to construct an LBA that recognises it. The idea behind the LBA is to repeatedly scan the input from left to right and mark symbols. In every such pass, mark every other unmarked symbol, starting with the first unmarked aymbol. Use a parity check (which can be recorded in the state of the machine) to check that this is done correctly - alternating between parity $0$ and $1$. If at some point the marking process cannot continue when the machine has parity state $1$, then reject. Else, if the machine is in parity state $0$, accept. The underlying idea behind this is to repeatedly divide the length of the string by $2$ to see if we eventually reach $0$.

# Answer
> -2 votes
If I understand the notation correctly (summing the amount of a's and amount of b's) and checking if it if a power of 2, then I do not believe it is context sensitive.

---
Tags: formal-languages, computability, context-sensitive
---


# Question
Title: Circuit of constant depth that takes three binary numbers and outputs two binaries?
How can I construct -- or better to say what type of circuit can be like this -- a circuit that takes 3 binary numbers (a, b, c) and then calculates two binary numbers (d, e) in a way that `a + b + c = d + e` The circuit should be of constant depth and furthermore, a, b, c, d, and e are as follows;

```
a=a_n−1…a_0
b=b_n−1…b_0
c=c_n−1…c_0

d=d_n…d_0
e=e_n…e_0

```

# Answer
A circuit which would satisfy this requirement is a *carry-save adder*. I'm sure you can find a reference for the gate layout somewhere.
> 2 votes

---
Tags: arithmetic, circuits
---


# Question
Title: Efficient algorithm to find all distances to a specific node in a tree
I wish to calculate the number of nodes within a certain distance of a particular node in a tree such as the one below:

Let's assume I'm looking for all the distances to node 2. What would be the most efficient (in terms of time complexity) method of computing the distances? Can it be done in linear time?

For this instance the output for the above tree would be:

* within one edge length distance: 4
* within two edge length distance: 2
* over two edge lengths away: 0

*What I've done so far:*

A simple brute force-ish solution would be to traverse the tree all the way to node 2 starting from all other nodes and counting the edges. I can make it a bit more efficient by storing the distances for all the nodes that are visited during each traverse and using the value if the node is visited again in a traverse that has originated from another node (for example traverses originating from nodes 1 and 3 in this graph will both result in visiting node 5). Is this the most efficient it can get?

# Answer
> 3 votes
Assuming your edges are not directed (which seems to be the case in case you are dealing with trees), you can calculate the distance by starting a breadth-first search from node 2. Then, you get the number of steps necessary to go from node 2 to each node $n$, which, as the graph is undirected, is the same as the number of steps necessary to go from node $n$ to 2.

If your had a directed graph, you can basically do the same, but you have to traverse edges in the opposite direction. E.g. if you are at node $n\_1$, and have the edges $n\_1 \to n\_2$ and $n\_3 \to n\_1$, you would then process $n\_3$ as a successor, but not $n\_2$.

---
Tags: time-complexity, trees, graph-traversal
---