# Question
Title: Minimally satisfying multiple qualitative requirements at once
I am trying to design an algorithm that will generate the full list of ways to minimally satisfy multiple requirements, given information on how the individual requirements are fulfilled.

For example, let's say you can either have (1) or not have (0) four different foods: Apple, Banana, Carrot, Donut.

Requirement 1 says "You must have an Apple and a Banana." (1,1,0,0) satisfies this. So do (1,1,1,0), (1,1,0,1), and (1,1,1,1), but these are not minimal solutions, since you could take away the Carrot and/or Donut and still satisfy it.

Requirement 2 says "You must have three foods." (1,1,1,0), (1,1,0,1), (1,0,1,1), and (0,1,1,1) are all minimal solutions for this. (1,1,1,1) is not minimal.

I already have ways of generating the minimal satisfying solutions above. They aren't optimal but the search space for each individual requirement is small enough that it doesn't matter. Here's where it gets sticky: generating a list of ways to minimally satisfy both at once.

The brute-force approach to minimally satisfying both at once is then easy, as long as no requirement turns from satisfied to unsatisfied by adding a food (i.e. there's no requirement that says "You must not have a Donut"). Simply (first) look at all combinations of successful arrays, one from each requirement, and take the maximum of each element. For example, combine (1,1,0,0) from Requirement 1 with (1,0,1,1) from Requirement 2 to get (1,1,1,1) to satisfy both. Then (second) prune out non-minimal solutions by comparing each array that satisfies all requirements against each other to get the minimal solutions (1,1,0,1) and (1,1,1,0).

But this is very slow! The runtime grows very quickly with the number of requirements, or successful arrays per requirement. And it generates a lot of redundant output before pruning (for example, (1,1,0,0) plus either (1,0,1,1) or (0,1,1,1) both make (1,1,1,1)).

I'm at a bit of a loss as to how to attack this differently so as to avoid searching every combination, and would appreciate any help. I only have minimal theoretical-CS training and feel like there's probably some terminology or analogous known algorithm I'm not aware of.

# Answer
> 0 votes
It depends what you mean by "minimal". You might mean either of the following two:

* you want to minimize the number of foods selected (variables set to true).
* you want a set of foods that's a valid solution, but where any subset of that set is no longer a valid solution.

I'll discuss solution to both variants of the problem.

## Minimizing the size of the set

If you want to minimize the number of foods selected (the number of variables set to true), the problem is NP-hard, so there is not likely to be any algorithm that is both efficient and always provides the optimum answer for all possible instances.

However, don't give up. There are reasonable approaches. Your problem can be formulated as an instance of integer linear programming (ILP), and then you can use an off-the-shelf ILP solver to solve it. ILP solvers have gotten pretty good so they might be adequate.

You have $n$ zero-or-one integer variables $x\_1,\dots,x\_n$, corresponding to the $n$ foods. Each requirement then translates to one (or more) linear inequalities. For instance, the requirement that you must have food #1 and food #2 corresponds to $x\_1=x\_2=1$. The requirement that you must have at least three foods corresponds to $x\_1+x\_2+x\_3+x\_4 \ge 3$. Some kinds of requirements take a bit more work to formulate as linear inequalities; see Express boolean logic operations in zero-one integer linear programming (ILP) for some tools you can use. Then, you want to minimize the objective function $x\_1+x\_2+\dots + x\_n$ subject to those constraints. An ILP solver will do that for you.

Alternatively, you could use an off-the-shelf pseudo-boolean satisfiability solver.

The ILP solver will generate *one* minimal solution. To generate all of them, there are various ways to do that. For instance, if you know there's a solution with 3 variables set to true and no solution with 2 variables set to true, then you can add the requirement $x\_1+x\_2+\dots + x\_n=3$ and enumerate all solutions to the corresponding integer linear program.

## Minimal sets of foods

Alternatively, suppose you want to enumerate all ways to choose a set of foods that is minimal (no proper subset is a valid solution). This requires different methods.

One way is to find a valid solution, then start removing foods until you can no longer remove any more. That will be one minimal solution. To enumerate minimal valid solutions, you can now look for a new solution that is not a superset of any prior minimal solution. This could be very slow. One way to find a valid solution is by using an integer linear program (ILP), as above; you can formulate the constraint that the solution must not be a superset of any prior minimal solution as well.

An alternative approach might be to view this as the problem of converting a Boolean formula to DNF form. I think that each DNF clause corresponds to one minimal subset of foods (of variables that can be set to true). There are various methods for conversion to DNF form; e.g., Quine-McCluskey, the Espresso logic minimizer. I haven't thought about this carefully and I don't know for sure whether this will find all minimal solutions. It appears that in your specific situation, you have a *monotone* Boolean formula; I don't know whether there are better algorithms for converting monotone Boolean formulas to DNF form.

---
Tags: algorithms
---


# Question
Title: Counting permutations whose elements are not exactly their index ± M
I was recently asked this problem in an algorithmic interview and failed to solve it.

> Given two values N and M, you have to count the number of permutations of length N (using numbers from 1 to N) such that the absolute difference between any number in the permutation and its position in the permutation is not equal to M.
>
> Example - If N=3 and M=1 then, 1 2 3 and 3 2 1 are valid permutations but 1 3 2 is invalid as the number 3 is at position 2 and their difference is = M.

I tried NxM Dynamic programming but failed to form a recurrence that doesn't count repetitions.

# Answer
The first thing I would ask when given this question would be

> Do you want a polynomial time algorithm?

and then I'd hope the answer is 'no'. I suspect that this problem is NP-hard, for the following reason:

The natural approach to this problem is to consider the placement of the first number and derive a recursive formula to place the others. This works nicely for the $M=0$ case (i.e. counting the number of derangements), as it doesn't matter on what position you have placed the first number, since there is only one 'illegal' position of every number. In other words, this approach leads to independent subproblems.

For $M\>0$, this is not so simple, as we now can have $2$ illegal positions for some numbers. Which of these positions remain in the subproblem is now relevant to the solution of the subproblem. Only considering the number of 'illegal' positions is not sufficient, as the 'chains' of numbers that share an illegal position are required to determine the structure of the subproblems of that subproblem. So, this approach essentially leads to the following subproblem:

> Given a set $A \subseteq \mathbb{N}$, a set $B \subseteq \mathbb{N}$ both of size at most $N$ and a natural number $M$, count the number of perfect matchings on the bipartite graph $(A,B,E)$, where $(a,b)\in E$ if and only if $|a-b|\neq M$.

This problem looks hard. The only approach to this problem I see is inclusion/exclusion, which will not lead to a polynomial time algorithm.

We can consider approaches that do not rely on the iterative placement of the numbers, but I have no clue how you would do this. (especially during an interview!)

Of course, all this is mere speculation and it is still possible that a clever trick can give a polynomial time solution, but I hope I have made convincing argument that this trick has to be very clever indeed.

Perhaps it is possible to show NP-hardness by reducing this problem to #2-SAT (the 'chains' of numbers that share illegal positions seem a non-trivial choice that could be matched with the selection of a truth-value), but I haven't seen an obvious way to do that as of now.

---

In case the interviewer would actually be satisfied with an exponential time algorithm, I'd simply generate all possible solutions by adapting a recursive backtracking algorithm to generate a permutation to exclude this particular case.
> 2 votes

# Answer
Is it possible you remembered the specific details wrong or misinterpreted the question?

In your description, element $a$ in position $b$ is restricted to $a-b \ne \pm M$.
But if they just meant the difference was restricted: $a-b \ne M$,
Then the problem appears tractable.

---

I worked out that simpler problem, and I tried to generalize in a way that I hoped might give some freedom in working out the larger problem. But this just clarified for me why a recursive approach is very unlikely to work, which I discuss at the end.

Consider the function $f(N,M,P)$ which gives the number of permutations of a list of elements labeled 1 to $N$, where the element $a$ in position $b$ (first position is 1) satisfies $a-b \ne M$, and $b-a \ne P$.

To visualize this, separating it into two constraints allows $M$ and $P$ to shift those restrictions around separately.

```
1 2 3 4 5  M=0, restricted values for each position
. . . . .  (positions in list)
1 2 3 4 5  P=0, restricted values for each position

3 4 5      M=2, restricted values for each position
. . . . .  (positions in list)
  1 2 3 4  P=1, restricted values for each position

```

For convenience, when $P \ge N$ so that it doesn't place restrictions on the permutations, define $g(N,M) = f(N,M,P)$. Similarly, $g(N,P) = f(N,M,P)$ when $M \ge N$ so that it places no restriction on the permutations.

In the special case $M=P=0$ the constraint from $M$ and $P$ are equivalent, so one can be ignored, allowing us to write $f$ in terms of $g$: $$ f(N,0,0) = g(N,0). $$

From the symmetry of the problem: $$ f(N,M,P) = f(N,P,M) $$

Let's first solve for $g(N,M)$, and then tackle the more general $f(N,M,P)$.

For $M=0$, each element has one placement restriction (and the restrictions are distinct). So choosing some element $i$, we will place it in some position $j$. There are $N-1$ different possibilities for the choice of $j$.

This selection removed the restricted position for element $j$, while the other $(N-2)$ elements still have one restriction. We can break the placement of $j$ into two options:

1. Place in $i$. This leaves all other elements with one restriction, so the remaining placement problem is now reduced to $g(N-2,0)$.
2. Place in a position $\ne i$. This now gives one placement restriction for $j$, and so each element has one restriction, and the remaining placement problem is reduced to $g(N-1,0)$

So this gives the recursive formula: $$g(N,0) = (N-1) \left\[ g(N-2,0) + g(N-1,0) \right\] $$

And by looking at the simple situations by hand, can get the base cases. $$g(1,0) = 0, \ \ g(2,0) = 1$$

This is the usual derangement recursive formula.

While I can't imagine someone coming up with this on the spot, it also turns out there is a closed form solution for this (see the derangement wiki article for details).

$$ g(N,0) = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor $$

For $M \ge N$, there is no restriction on any of the placements:

$$(M \ge N) \implies g(N,M) = N! $$

With $0\<M\<N$, the first $M$ elements will have no restrictions and the remaining elements will have one placement restriction. It terms of the positions, the last $M$ positions will allow all numbers.

For the last position, select an element $i$. There are two possibilities for what the remaining placement looks like:

1. If $i\<M$, then $i$ had no placement restrictions, so using $i$ does not change the restrictions on any position. We have also removed one position with no restriction, so the remaining placement looks like $g(N-1,M-1)$.
2. If $i\>=M$, then $i$ had a placement restriction, and we removed one position with no restriction. Because $i$ is placed, the position it was restricted from now can accept any of the remaining numbers. So the remaining placement looks like $g(N-1,M)$.

So this gives the recursive formula: $$(0\<M\<N) \implies g(N,M) = (M-1) g(N-1,M-1) + (N-M+1) g(N-1,M) $$

This finishes the recursive solution for $g$.

When $M+P \ge N$, the first $N-M$ positions have a single number restriction on them, the last $N-P$ positions have a single number restriction on them, and the middle $M+P-N$ positions have no restrictions. This is just like the $g(N,M+P-N)$ case.

$$(M+P)\ge N \implies f(N,M,P) = g(N,M+P-N)$$

We have handled all cases currently except $0\<M\<N$ and $0\<P\<N$ such that $M+P\<N$. This is where some elements have multiple restrictions. Because of the symmetry in $f$, we can consider $0\<M\le P\<N$ without loss of generality.

The first $P$ positions will have a single restriction, then $N-M-P$ positions with two restrictions, then the last $M$ positions have a single restriction.

Looking at the elements, the first $M$ elements will have a single restriction, then $N-M-P$ elements have two restrictions, then the last $P$ elements have a single restriction.

However this is where we must end. As there is no way forward with this method.

---

I separated the two constraints because I could see that placing a number in a selected position could unbalance how many single constrained positions there were for the "+" constraint and the "-" constraint of $a-b \ne \pm M$.

But in the more general problem, removing a position by placing a number in it, does not always result in a subproblem that is described with $f(N,M,P)$.

To visualize these constraints on the permutation, consider a directed graph with $2N$ nodes, one set of $N$ labeled $\\{A\_1,A\_2,...,A\_N\\}$ and another labelled $\\{B\_1,B\_2,...,B\_N\\}$. A directed edge $(A\_i,B\_j)$ exists if $i - j = M$, and directed edge $(B\_j,A\_i)$ exists if $j - i = M$ and $M \ne 0$.

The set of $A$ nodes can be considered the numbers we are permuting in some list, and $B$ nodes their possible positions. This graph represents the constraints. There will be no cycles in the graph. It will always be disjoint nodes or chains of length one or more.

So we want a function which takes as input this constraint graph, and outputs the number of permutations that satisfy the constraints.

In the case where $M+P\ge N$, the graph is just disjoint nodes and single edges. So removing an A and B node will give a subgraph that is also disjoint nodes and single edges.

However for $0\<M \le P\<N$, the graph can have long chains. To place a number in an available position, regardless of whether we fix the node or the position, we need to consider all the subgraphs of possible ways to build that. All the different ways of breaking up the chains will result in a "recursion" that is on the order of $N$ parts each round, and thus can't expect much if any savings compared to checking all $N!$ permutations.

Because there are so many possible subgraphs once chains are allowed, I really don't see how this can be solved with the usual recursive methods unless there is a clever relation saying how non-isomorphic constraint graphs are somehow equivalent for the number of permutations.

I think most likely, the question was misinterpreted. Possibly even by the interviewer (who may have forgotten the answer details themselves).
> 2 votes

---
Tags: algorithms, permutations, algorithm-design
---


# Question
Title: Which type compilers report if they cannot infer a precise type?
In the presence of subtyping, a type checker can usually infer only some inequality constraints on the type rather than the exact type. Of course, internally it will store the full constraints. But what is the common practice in case it needs to display the inferred type to the programmer?

I thought it might be reasonable to just display the lowest type that satisfies all the constraints (I guess it exists and unique if the types form a lattice). That would mean the programmer would know all the contexts where the name can be used. But then, if there's no constraint from below, the type checker would be displaying `Bottom`, and I don't think it's commonly done.

What am I missing?

# Answer
> 6 votes
It is important to keep in mind that this is a question about *human-computer interaction* and *not* about compilers. As far as the machine is concerned, the constraints are the constraints, and the obvious thing to do is just to show all the constraints to the user. However, when the user is a human, they may find the constraints too complex to process, and so the machine needs to dumb down the information for the cognitively handicapped user. This is in fact what happens, see for instance Pretnar's paper on inference for effects where he discusses what to show the user (that's just the first paper that came to my mind, and is by no means the only one or the first one).

As you notice, showing just the lower bounds may be useless. Symetrically, showing just the upper bound may be useless as well. However, in many situations one has *either* useful lower bounds *or* useful upper bounds, in which case you just show the useful part (and you need to indicate whether you're showing the lower or the upper bound). Other than that, people try various strategies. A common one is to *simplify* the constraints in the hope that we won't lose much information, and then show those to the user. Simplification can also be useful to control the size of constraints, which can easily grow so much that the whole system becomes useless.

# Answer
> 2 votes
Depends on where the type appears.

On *values* (including return values), the *lower* bounds are the most interesting since it gives you more freedom on where to use them.

On *parameters*, the *upper* bounds are more relevant since they tell you what kinds of values you may pass into the function.

---
Tags: programming-languages, type-theory, type-checking, type-inference, types
---


# Question
Title: route and/or packing optimization algorithm
What type of problem would this question fall under, are there known algorithms/heuristics for it, what would be good resources to learn more about solving it?

**Given**:

* a list of items each with a destination location: the number of items per destination is unbounded (and can be zero for some locations). All items are at a central location.
* a number of destination locations, each awaiting a set number of the items: the number of locations is finite, and small \[under a thousand\]
* a number of couriers, all at the same point initially (the same initial location as the items); each courier has a maximum number of items they can carry: the number of couriers is very small \[a dozen\]
* the duration of travel between all locations \[all couriers travel at the same speed\]

**Problem**: minimize the maximum wait time of each location \[the time it takes for all the items due at that location to be delivered\] by allocating items to couriers.

# Answer
> 1 votes
This specific problem seems to be an variation of minimizing the makespan in the job shop scheduling problem. Essentially, your couriers are modeled as 'workers' that need to process certain 'tasks', which are the delivery requests. We look for an assignment of tasks to workers that minimizes the time until the last worker is finished, the *makespan* of the assignment.

The current problem is slightly different from the basic version, as it assumes all workers are equally skilled, but here some workers can process faster, as they can carry more items.

The job shop scheduling problem is an NP-complete problem, which means that we do not expect to solve this problem exactly in polynomial time.

One option is to model this problem and various extensions as an (mixed) integer linear program, but this generally means you either have an exponential time algorithm or have no guarantees over the quality of your result.

A better idea for this specific problem is to use an *approximation algorithm* for the job shop scheduling problem. These approximation algorithms run in polynomial time and although they do not guarantee an optimal solution, they can give you an upper bound on the quality of the solution (e.g. The solution given will be at most twice the size of the optimal solution). There is extensive literature about this problem, so where to start mostly depends on the type of solution you're looking for.

---
Tags: optimization, weighted-graphs, packing, routing
---


# Question
Title: What kind of LTL formula can be represented by DBAs
I am looking for the portion of LTL formula that can be expressed by deterministic buchi automata. Is there any classification of this such?

# Answer
> 4 votes
You can define syntactic fragments of LTL that ensure that all properties expressible in these fragments are representable as DBAs. An example is given in the paper "A LTL Fragment for GR(1)-Synthesis". Also, the common fragment of ACTL and LTL only contains properties that are representable as DBAs.

But note that such a fragment will never be complete in the "if a formula is not in the fragment, then it is not representable as a DBA" sense. The reason is that if we have LTL formulas that are not representable as DBAs, then we may be able to combine them to a formula that *is* representable as DBA. For example, the properties "FG p | GF q" and "FG q | GF p" are both not expressible by DBA, but both their conjunction and their disjunction are.

Note that there are also DBAs that are not representable in LTL. So a fragment of LTL cannot be equiexpressive to DBAs.

---
Tags: automata, logic, linear-temporal-logic, buchi-automata
---


# Question
Title: Finding any $\epsilon$ vs finding minimal $\epsilon$ for case 3 of Master theorem
I have a recurrence relation: $$T(n) = 3T(\frac{n}{4}) + n\lg n$$

and I want to prove that $T(n) = \Theta(f(n))$ using Master theorem. There's also an example in my textbook on this relation, they're choosing $\epsilon = 0.2$. For example:

$$n^{\log\_b a}=n^{\log\_4 3} \Rightarrow n\lg n = \Omega(n^{0.79+\epsilon})$$

Why would we choose $\epsilon = 0.2$, why couldn't we have chosen something like $\epsilon = 0.0001$, wouldn't this already be enough?

# Answer
First, note that $\log\_4 3 = 0.792...$. Now the key observation is that $n^{0.792..}$ grows asymptotically slower than $n \lg n$, i.e., $n^{0.792...} = O(n \lg n)$, or if you prefer, $n \lg n = \Omega(n^{0.792...})$. Why? Well, one way to see it is to notice that $n^{0.792...} = O(n)$ and $n = O(n \lg n)$: $n^{0.792...}$ grows asymptotically slower than $n$, because the exponent is smaller; and $n$ grows asymptotically slower than $n \lg n$.

What's up with the $\epsilon=0.2$? That's probably a clunky way of getting at the fact that $n^{0.792...}$ is smaller than $n^{1.000...}$. In particular, $0.792 + 0.2 \< 1.0000$. Personally, I don't find it a particularly helpful explanation for why $n^{0.792...} = O(n)$, so I would suggest you ignore it. If you find it confusing, it's not just you, and it doesn't represent some shortcoming in your understanding; it just seems like a confusing way to explain it to me.
> 1 votes

---
Tags: time-complexity, recurrence-relation, master-theorem
---


# Question
Title: Is reference counting GC vs. tracing GC a language property or an implementation property?
We sometimes hear "Swift doesn't do classic (tracing) GC, it uses ARC."

But I'm not sure if there is anything in the Swift semantics that requires reference counting. It seems that one could build one's own Swift compiler and runtime to use tracing GC.

So what exactly is "reference-counted" about Swift? Apple's implementation or the language itself? Are there parts of the language or the library that so strongly support ARC that we can use that label for the language itself?

# Answer
Swift guarantees that once the last reference to an object is dropped the object is deinitialized, and the `deinit` code is immediately run.

Obtaining this kind of guarantee through GC is not possible - at least, not without sacrifying performance. Standard GC mechanisms only ensure the `deinit` code is eventually run, e.g. at the next GC cycle. For precise semantics, you need a reference count somewhere.
> 10 votes

# Answer
chi has answered the specific question in the body about swift, this answer answers the more general question in the title.

> Is reference counting GC vs. tracing GC a language property or an implementation property?

reference counting GC and tracing GC provide the programmer with different gaurantees.

Reference counting provides determinism in the location in the program flow where an object is destroyed, that can be important if the object owns scarce resources that must be freed quickly. On the other hand it can't deal with cycles of "strong" references.

It is up to the specification of an individual language what if any characteristics are gauranteed and therefore which choices are available to a compliant implementation.
> 4 votes

# Answer
You could take the language known as Swift and rename it to "Swift with ARC". You could then create a new language named "Swift with GC" with exactly the same syntax, but with fewer guarantees about when objects are deallocated.

In Swift with ARC, once the reference count is 0, the object will go. With garbage collection, as long as you have a weak reference, you could assign that weak reference to a strong reference to "recover" the object. (In Swift, once the reference count is 0, weak references are nil); that is a major difference.

And of course Swift with ARC guarantees that killing the last reference count will deallocate the object immediately. For example, you might have a FileWriter class, where you are not allowed to have two instances writing to the same file in existence at the same time. In Swift with ARC you could say oldWriter = nil; newWriter = FileWriter (...) and you would know that the new FileWriter is only created after the old one is deleted (unless you kept another reference around); in Swift with GC this wouldn't work.

Another difference is that in "Swift with ARC", objects that are only referenced through strong reference cycles, but not actually reachable, are *guaranteed* to be not deallocated.
> 1 votes

---
Tags: semantics, garbage-collection
---


# Question
Title: Is $\ L = \{ \ w \in \{a, b, c\}^* \ | \ w = uv \ \ and \ \ \#_a(u) + \#_b(u) = \#_b(v) + \#_c(v) \ \} $ regular?
I wonder whether the following language is regular: $$ L = \\{ \ w \in \\{a, b, c\\}^\* \ | \ w = uv \ \ and \ \ \\#\_a(u) + \\#\_b(u) = \\#\_b(v) + \\#\_c(v) \ \\} $$ where $\ \\#\_x(w) $ is the number of occurrences of$\ x $ in$\ w $.

# Answer
> 3 votes
Your language is not regular, since $$ L \cap a^\*bc^\* = \\{ a^n b c^m : n \neq m \\}. $$ I'll let you figure out why.

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


# Question
Title: Understanding google's user level threads in kernel threads
I came across Paul Turner work on increasing efficiency of M:N threading model. I am not able to grasp the concept at slide 18 of LPC-User-Threading

It says : for two threads `A and B` :

`Minimal scheduling operation.
● B inherits A’s virtual runtime.
● B was not runnable, so we don’t need to remove it from runqueues.
● B holds references on same objects as A`

What does virtual runtime mean in this case ?

Will not a random thread `B` inheriting `A`'s environment and referencing same objects cause any problems ?

The video is present at video for the interested.

# Answer
This is talking about user level threads, so they should all have the same memory context (virtual memory map). So while the threads need to be careful in doing so, they can all access each other's objects directly without using inter-process communication.

The scheduler will give each thread a time slot to run in (length possibly depending on priority). He is discussing an addition to the kernel to allow a request:

> pid\_t switchto\_switch(pid\_t tid)
>
> * Synchronously transfer control to target sibling thread, leaving the current thread unscheduled.
> * Analogous to: Atomically { Resume(t1); Wait(NULL); }

So as a programmer, if you had work on a task that you need to stop and wait for information from another task before you can continue, then you could request to immediately switch to that specific thread.

Your intial thread would immediately be put in a wait state, and the other thread would resume execution using the initial thread's currently scheduled time ("B inherits A’s virtual runtime").
> 2 votes

---
Tags: operating-systems, process-scheduling, threads
---


# Question
Title: Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?
Look at this solution:

Is the lower bound $m\log n$ because we are only looking at the lower bound for union by rank only? If we make $n$ MAKE-SET operations, then there would be $\log n$ UNION operations, and then $m - 2n + 1$ FIND-SET operations. The lower bound seems larger to me but what am I missing?

# Answer
> 0 votes
You are asking two questions.

> Is the lower bound only for this specific implementation?

Yes. If you also use path compression, the running time will be $o(m\log n)$.

> The lower bound seems to large to me.

Your mistake is that you assume that there are only $\log n$ UNION operations, whereas there are $2^{\lfloor \log\_2 n \rfloor}-1 = \Theta(n)$, as the answer clearly .

---
Tags: algorithm-analysis, data-structures, lower-bounds, union-find
---


# Question
Title: A better upper bound to a recursive function
it's my first answer here.

I do have an algorithm to calculate the factorial of a given number $n$ recursively, but without using any multiplication like the usual one, only sums are available.

I've ended up with an algorithm with a complexity function $T(n) = 1 + nT(n - 1)$.

Opening the recurrence relation ends up in:

$T(n) = 1 + n T(n - 1)$

$T(n) = 1 + n\[1 + (n - 1)T(n - 2)\]$

$T(n) = 1 + n + n^2 T(n - 2) - n T(n - 2)$

$T(n) = 1 + n + n^2\[1 + (n - 2) * T(n - 3)\] - n T(n - 2)$

$T(n) = 1 + n + n^2 + n^3T(n - 3) - n T(n - 2) - n^2T(n - 3)$

Because of the subtractions, I'm not able to reach good upper-bound for $T(n)$. Any tips ?

Before asking the question, I've managed to state that $T(n) \in \mathcal{O}(n^n)$. Which is 'loose' upper bound, but I'm neither able to figure out a tighter upper bound.

# Answer
> 5 votes
Solving your recurrence, assuming the base case $T(0) = 1$, we get $$ \begin{align\*} T(n) &= 1 + nT(n-1) \\ &= 1 + n + n(n-1)T(n-2) \\ &= 1 + n + n(n-1) + n(n-1)(n-2)T(n-3) \\ &= \cdots \\ &= 1 + n + n(n-1) + \cdots + n(n-1)\cdots2 + n! \\ &= n! \left(\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots + \frac{1}{n!}\right) \\ &= n! \left(e - O\left(\frac{1}{(n+1)!}\right)\right) \\ &= e \cdot n! - O\left(\frac{1}{n}\right). \end{align\*} $$ In particular, $T(n) = \Theta(n!) = \Theta(\sqrt{n}(n/e)^n)$.

---
Tags: recurrence-relation, recursion
---


# Question
Title: Is it decidable if a given TM accepts infinitely many words in a fixed number of moves?
$L=\\{\langle M \rangle \mid \text{There are infinitely many words accepted by M in less than 10 moves}\\}$

I am having hard time understanding this language and I have several questions:

1. How is it possible to derive infinite amount of words in finite moves?
2. How can we determine if a word is or isn't in the language at all?
3. Why is this language decidable? I understand that it is because it halts on every input, but what are we looking for after 10 moves to decide if it will reject or accept?

Any further clarifications on this language will be highly appreciated.

# Answer
I'm going to assume that you mean

$\qquad L = \\{ \langle M \rangle \mid |L\_{\leq 10}(M)| = \infty \\}$

with $L\_{\leq m}(M)$ the set of words that $M$ accepts after at most $m$ steps. In particular, it does not say a thing about all the other inputs.

1. > How is it possible to derive infinite amount of words in finite moves?

The Turing machine that does nothing but accept clearly accepts an infinite language. While it's true that machines that qualify for $L$ have to work with finite prefixes, but they can accept arbitrarily many inputs based on these prefixes!
2. > How can we determine if a word is or isn't in the language at all?

I don't know what "we" is here; but clearly, we can just run $M$ on the input. If it accepts after at most ten steps, fine; otherwise, it's not relevant for the criterion of $L$.
3. > Why is this language decidable?

Who says so?

*Hint:* How many symbols of the input can any TM examine in ten steps? Let's call this number $k$. What does it tell you if it accepts or rejects an input of length at most $k$? What does it tell you if it accepts or rejects an input of length greater than $k$?

> I understand that it is because it halts on every input.

How so? If you *had* an algorithm that decides $L$, then yes, it would halt on every input. But we can not assume that -- that's the claim we have to prove!

The *inputs* for this algorithm are *all* Turing machines, in particular also such that don't halt.

> but what are we looking for after 10 moves to decide if it will reject or accept?

You have one bit of information: did the machine accept or not? You can have some more, if that helps: did the machine visit a state twice? Did it move, and how?
> 2 votes

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


title: Pumping lemma for linear languages

text:
# Question
Title: Pumping lemma for linear languages
Let $L$ be a linear language. Then there is a constant $p$ such that for all $w$ in $L$ with $|w| \ge p$, $w$ can be written as $uvxyz$ where (i) $|uvyz| \le p$ (ii) $|vy| \> 0$ (iii) $uv^ixy^iz$ is in $L$, for all $i \ge 0$. How do I prove the first condition? I am having difficulty proving the bound and relating the bound k to the grammar.

# Answer
Study the proof of the pumping lemma for context-free languages. The pumping property is obtained by finding a repeated non-terminal on a path in the derivation tree. By looking at the first repetition you can find a bound on the length of that path in the tree, and hence a bound on the length of the substring $uvyz$.

What is k?
> 3 votes

---
Tags: formal-languages, pumping-lemma, linear-languages
---


# Question
Title: How to show that there are $\binom{M+K}{M}$ different number of type bins?
In textbook by Vazirani's textbook, chapter 9 about Bin Packing. He give the following lemma.

> Lemma 9.4 Let $\epsilon \>1$ be fixed, and let K be a fixed nonnegative integer. Consider the restriction of the bin packing problem to instances in which each item is of size at least $\epsilon$ and the number of distinct item sizes is K. There is a polynomial time algorithm that optimally solves this restricted problem.

Proof. The number of items in a bin is bounded by $1/\epsilon$. Denote this by M. Therefore, the number of different bin types is bounded by $R = \binom{M+K}{M}$. Which is a large constant. Clearly, the total number of bins used is at most n. Therefore, the number of possible feasible packings is bouned by $P=\binom{n+R}{R}$, which is polynomial in n. Enumerating them and picking the best packing gives the optimal answer.

Question: We know a fact which is: $\binom{n+k-1}{n}$, now in order to find the number of different bin types we it should be something like $\binom{M+K-1}{M}$ why in the proof it is different?!!

# Answer
The bins contain *at most* $M$ elements rather than *exactly* $M$ elements. This is why your formula doesn't work. In order to use your formula, we need to allow for one more type of element, a dummy type, and then we get $\binom{M+(K+1)-1}{M} = \binom{M+K}{M}$.

As an example, suppose that there is one type of element (so $K=1$). In that case, a bin can contain $0,\ldots,M$ elements, in total $M+1 = \binom{M+K}{M}$ choices.
> 1 votes

---
Tags: algorithms, optimization, packing
---


# Question
Title: Why can't we simulate an NP oracle with an NP machine?
In this question : Does $NP^{NP}=NP$? ,
it says that one of the reason is that we don't know how to detect 'no' answers from the oracle.
Why is that true though? There is an NTM for any language L in NP, that runs in polynomial time. IIRC we can simulate the NTM with a deterministic TM M that runs in exponential time, that tries every non-deterministic option, and decides L... So why can't we simulate the oracle using that M in another NP machine?

Thanks.

# Answer
> 3 votes
You don't have exponential time, what you have is a nondeterministic polynomial time machine.

What you can try to do, in order to simulate the oracle call to $\mathcal{O}\in NP$ on a string $s$, is to run the nondeterminstic polynomial machine $M\_\mathcal{O}$ on input $s$. If $M\_\mathcal{O}$ returned "yes" then you know $s\in\mathcal{O}$, but if it returned "no", then you cant be sure, and you don't have enough resources to try out all possible branches in an NP machine.

---
Tags: complexity-theory, turing-machines, time-complexity, np, oracle-machines
---


# Question
Title: Is the mate-in-n problem of infinite chess with each color using traditional pieces plus one huygens decidable?
I noticed in a paper that the mate-in-n problem of chess, even played on an infinite board is decidable. The mate-in-n problem of inﬁnite chess is decidable

I believe the paper assumes only **traditional chess** pieces are used.

What if one of the chess pieces is a **huygens**? (A huygens is a chess piece which jumps **prime numbers** of squares).

Is the mate-in-n problem of chess on an unbounded board with each color using traditional chess pieces plus at least **one huygens** also decidable?

# Answer
> 2 votes
Presburger arithmetic with a predicate for the primes is probably undecidable, so at least the technique used by your question's link should not easily generalize to allowing a huygens.
For example, although decidability of the special case I'm about to mention
would follow from there being only finitely many positive even integers that
are neither prime gaps nor sums of two *distinct* primes, I don't see any way of
*proving* decidability of mate-in-ONE for king+huygens against a smothered king:

---
Tags: computability, undecidability, board-games
---


# Question
Title: To what extent is my interpretation of computable numbers correct?
**Interpretation:** Consider the comic strip below, where a person tries to prevent a robot from dismembering them by asking the robot to compute $\pi$ - the robot quickly produces an algorithm to calculate all of the digits of $\pi$ and begins dismembering the person. This is possible because $\pi$ is a computable number.

In contrast, if the person had asked the robot to calculate Chaitin's constant (assuming the robot didn't say something like "which Chaitin's constant?" or "insufficient parameters") or some other non-computable number, would the people have been able to escape the robot's dismembering?

As far as I understand (1)(2), the robot could make an algorithm to calculate the first $n$ digits for any $n$, but to attempt to compute "all" of Chaitin's constant would take an infinite amount of time, because each new digit would require a new program, or something like this.

**Question:** Is this interpretation at all correct or am I completely off the mark here? To what extent could one describe computable numbers as numbers which "prevent a robot in this specific situation from dismembering people"?

I.e., do all non-computable numbers have algorithmically random (decimal, binary, etc.) expansions?

Source.

# Answer
This is exactly the incorrect interpretation of "computable", resulting of trying to replace the precise definition with (possibly misplaced) intuition.

$\pi$ or any other irrational number also has an infinite digit representation, so according to your logic, it shouldn't be computable. This just shows that it is meaningless to require all of the digits as output, and we actually need a "better" definition.

To fix this issue, we say a number $p$ is computable, if we can approximate $p$ up to any given precision. One way of formalizing this is requiring the existence of a program $M\_p(n)$, which upon receiving a number $n$ outputs (in finite time) a number $\hat{p}$ such that $|\hat{p}-p|\le\frac{1}{n}$. The comic actually refers to this definition, as $\pi$ having an infinite expansion does not prevent the robot from dismembering the guy.

If your goal is to avoid dismembering, then it is not clear how to use uncomputable numbers. What exactly is the meaning of calculate $x$? If i ask for some fixed approximation of an uncomputable number, then the robot can give me one (sure, it has no way of algorithmically producing the approximation, but perhaps this is some weird robot with a table of all approximations to any natural constant up to $10^{-100}$). You would probably stand more chance with incompleteness issues, rather than with computability issues. I would ask the robot for a proof in $ZFC$ of its consistency. If it is consistent, he wont find any, and if it isn't, who wants to live anyway.
> 11 votes

# Answer
First off, I'm not sure what the intuition you're proposing is, so I'll make some general remarks.

In the comic, the problem given to the robot was ill-posed; the interpretation of the request is not clear, and for any reasonable interpretation it is very obviously impossible.

Then, the robot cheated by not giving the answer but a recipe to find the answer (arguably).

I'm not sure what you would expect the robot to do if you asked: "Compute this incomputable function!". It could not even start. You'd have to get it into an *actual* computation that does not terminate. For instance: "Find the smallest $i$ for which $f(i)≠i$ with $f:i↦i$!" Of course, the robot may perform elementary static analysis and conclude that there is no such $i$, at which point it will happily start dismembering you.

So it'll have to be a semi-computable problem whose answer is not immediately obvious, and the actual instance needs to loop -- good luck making that up on the spot!

In robocalypse-preventing practice, I'd just give the robot a (hopefully) hard instance of an NP-hard problem and hope that I run fast enough. "What is the shortest route to visit every Starbucks in the world (once)?" That should keep it busy for a while. Of course, if I built the robot any individual on its kill list would also be on the black-list of its spam filter.
> 3 votes

# Answer
I think there are too many kinds of sort-of uncomputability involved here:

* Uncomputable because ill-defined. "The smallest rational larger than 1.0" would be an example.
* Uncomputable because of assumptions that contradict known theorems. Example: "Largest prime number.".
* Uncomputable because of assumptions that contradict axioms (this is a trivially degenerate case of the previous point). Example: "Largest integer."
* Uncomputable because undecidable. Chaitin Numbers (percentage of randomly generated programs that will not terminate) is a particularly nasty version.
* Uncomputable but any correct answer could be checked computably. It would be hardest to justify a non-answer.
* Uncomputable because algorithm is known to exist but not discovered yet. I think unsolved mathematical problems can fall in that category. Maybe "what's the lower bound for sorting algorithms" - we *believe* it's O(N log N), but there was never a proof for that, and there should either be an O(N) algorithm or a proof that nothing faster than O(N log N) is possible.
* Uncomputable because insufficient data. "How old is the oldest living field mouse?"
* Uncomputable because subjective. "What's the nicest mathematical theorem in literature?"

In other words, computability, decidability and all that hard-math stuff is only marginally related to the topic of the comic.

There's also your assumption that a better understanding of computability would have somehow improved the scientist's situation.
However, that's entirely arbitrary, because the robot could have likewise answered "I don't mind about your questions or orders", or said "impossible to calculate, I'll rend your limbs anyway", or whatever else the author's whims dictate. For that reason, your question *does not have a good answer*.
> 1 votes

---
Tags: computability, computation-models, intuition
---


# Question
Title: Let $G = (V,E)$ be an infinite digraph: $E \subset \mathbb{N}\times \mathbb{N}$ is decidable. Does it imply that $\delta (i,j)$ is a total function?
**Problem:**

> Let $G = (V,E)$ be an infinite digraph, such that $V = \mathbb{N}$, and $E \subset \mathbb{N}\times \mathbb{N}$ is decidable set. Does it imply that $\delta (i,j)$ is a total function?
>
> \*(where $\delta (i,j)$ is the shortest path function between vertex $i$ and $j$).

I'm having a hard time trying to understand the problem, so any help would be appreciate.

---

Well, this is what I know (hopefully I'm not misunderstanding anything here):

A language (or set) $L$ is decidable if $\exists$ and algorithm $A$, such that if $v \in L$, then $A(v) = \text{Accept}$ and halts and if $v\not\in L$, then $A(v) = \text{Reject}$ and halts.

A function $f$ is total if $\exists$ and algorithm $B$ that computes it $\forall v\in \mathrm{Dom}(f)$ and always halts.

---

**My attempt:**

Suppose $\delta (i,j)$ is a total function and let algorithm $B$ be the Bellman-Ford algorithm ($BFA$).

The relaxation step in $BFA$ is given by

```
// Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

```

Because $|V| = \infty$ we have that the algorithm never halts, since `size(vertices) - 1` $= |V| -1 = \infty$. This implies that $BFA$ doesn't compute $\delta (i,j) \implies \delta (i,j)$ is not a total function (So, to my understanding it would be only a partial function, since $\exists$ some vertices $u,\ v$ for which the function $\delta (u,v)$ is undefined).

Although to me at first glance it makes kind of sense, I guess I'm wrong, mainly because I didn't consider the fact that $E$ is a decidable set.

# Answer
> 1 votes
This function is not necessarily total, even when the set of edges is decidable. Note that you haven't proved it, but simply showed why we can't directly use some classic algorithm for finite graphs, though perhaps some smarter algorithm exists?

Imagine $G$ is a "universal configuration graph". To explain what i mean, lets first discuss what is the configuration graph of a Turing machine $M$. Given a Turing machine $M$, let $G\_{M}$ denote the graph whose vertices are configurations of the form $C=(q,s\_1,s\_2)$ where $q$ is the machine state, and $s\_1,s\_2$ are the strings to the right and left of the read/write head correspondingly (the first symbol of $s\_2$ is the current symbol under examination). $(C\_1,C\_2)\in E$ if you can go from $C\_1$ to $C\_2$ in a single step. The number of vertices in $G\_M$ is countable (since we go over all possible contents of the tape).

Now I want to define $G$ as $\bigcup\limits\_{M} G\_{M}$. The graph $G$ is the disjoint union of all possible configuration graphs (so we go over all Turing machines, note that the number of vertices remains countable). To identify each vertex (configuration) in $G$ to the graph $G\_{M}$ it's belonging to, we can add the encoding of the machine to the description of each vertex. The set of edges of $G$ is clearly decidable, since given two vertices $v\_1=\left(\langle M\rangle , C\_1\right)$ and $v\_2=\left(\langle M'\rangle , C\_2\right)$, we check if $\langle M\rangle=\langle M' \rangle$, and if so, we check if $M$'s transition function allows us to move from $C\_1$ to $C\_2$ in a single step.

If reachability in $G$ is decidable, then you can decide the halting problem. Given a Turing machine $M$ and input $x$, check if the accepting configuration of $M$ is reachable from the initial configuration of $M$ on input $x$ (for simplicity, you can assume there is a unique accepting configuration).

---
Tags: algorithms, graphs, computability
---


# Question
Title: Prove the equivalence between a CFG and a Context free language
I have to prove that the language $L=\\{a^ib^j:2i=3j+1\\}$ and the CFG G with the following rewrite rules:

$S\rightarrow a^2Tb$

$T\rightarrow a^3Tb^2 |\epsilon$

are equivalent to each other.

I'm going to prove this by saying $L(G)\subseteq L$ and $L \subseteq L(G)$. I was able to prove the first one. I should be able to prove the second one with induction on the length on a word $w$. But how can I do that? The induction basis should start at length 3, because the smallest word $w \in L$ is $aab$. But the second word has a length of 8. This means the stepsize in the induction proof is 5. I've never done an inductive proof with a stepsize different from 1. How can I do something like this as it's not possible to state in the induction step that "We assume that the theorem holds for $|w|=n$, now we are going to proof that it holds for $|w|=n+5$"?

**UPDATE:** I think I found a solution to my own question:

**Inductionbasis:** Suppose $|w|=3$. Then $w$ must be $aab$ because that's the only word of length 3 that satisfies the requirements for the language L. But $aab$ is also an element of $L(G)$. The basis is OK.

**Induction hypothesis:** Assume that the theorem holds for all words $w\`$ with length $|w\`|=3+5n$. We are now going to proof that the theorem also holds for all words $w$ with length $|w|=3+5(n+1)$.

$w$ must be of the form $\alpha a^3b^2 \beta$ to be an element of $L$. Now consider the word $z=\alpha \beta$ with length $|z|=3+5n$. Then, by induction, we know that $z \in L \implies z \in L(G)$. Because $z \in L(G)$ it must hold that $z$ is of the form $a^nb^m$ with $2n=3m+1$. If we add the 3 $a$'s and 2 $b$'s from $w$ to this equation, we find that $2(n+3)=3(m+2)+1$. The following applies to this equation:

$2(n+3)=3(m+2)+1$

$\iff 2n+6=3m+6+1$

$\iff 2n+6=3m+1+6$

$\iff 2n+6=2n+6$

Thus, $w$ also satisfies $L(G)$. **QED**

Is this proof correct?

# Answer
> 1 votes
Since this is a very simple "linear" grammar, its language can be determined by looking at the possible derivations.

Clearly a successful derivation has to start with $S\to a^2Tb$, then repeats $k$ times the production $T\to a^3Tb^2$ and closes with $T\to \epsilon$. That will give strings of the form $a^{2+3k}b^{1+2k}$ with $k\ge 0$. (1)

Then we need to establish that these are exactly the strings of the form $a^ib^j$ with $2i=3j+1$. (2)

One direction is easy, strings of the form (1) satisfy (2) -- you solved that yourself -- by observing that $2(2+3k) = 3(1+2k)+1$.

Your proof for the other direction sounds good, but it is not clear to me how one argues that the induction has step size $5$ (other than by trial and error).

The following would work. Start with (2) for natural numbers $i,j$.

This implies $3j+1$ is even (and non-negative).

Or, $3j$ is odd, so $j$ is odd, which means it is of the form $j=2k+1$ for $k\ge 0$.

Then $2i=6k+4$, or $i=3k+2$, and we are done.

This argument seems rather ad hoc. Note the similarity between this exercise and linear algebra. There are two different representations for a line in 2D: using vectors or equations. Here these are:

* $\\{ (2,1)+ k\cdot(3,2) \mid k\in \mathbb R \\}$
* $\\{ (x,y) \mid 2x-3y=1 \\}$

Unfortunately, I do not think linear algebra tricks directly work, as we here must restrict ourselves to integers and not the real numbers.

---
Tags: formal-languages, context-free, proof-techniques, induction
---


title: Is javascript scripting?

text:
# Question
Title: Is javascript scripting?
This one goes both ways at this point in my computer science studies... Is it scripting in the same sense as a Python script (for example)?

Are they the same?

I'm learning Javascript at the moment as part of a Web design textbook but at the very start of my programming lessons I got quite far in programming with Python and would like to finish it **IF** it is conducive to Web design.

Many thanks in advance to anyone who can help me here and I'll be sure to vote up the best answer for reputation.

# Answer
JavaScript and Python are both interpretive languages (as opposed to compiled languages like Java) with JavaScript being (mostly) a client-side language and Python a server-side language.

You would do well to learn them both, especially JavaScript.
> 0 votes

---
Tags: programming-languages
---


# Question
Title: How to solve this problem of architecture and scalability?
I know this question may seem weird, mainly, why the context (OS, kind of system, etc) isn't explicit. I am studying for an exam, and, according to the studies guide, one of the questions types can be:

"Assuming that a system has a large volume of access, and has a restricted capacity of devices. What difficulties would we face? How could we get around them?"

# Answer
> 0 votes
The access cost to devices may be high, so caching and/or request coalescing may be employed to maximize the benefit of access while minimizing the cost.

---
Tags: computer-architecture, software-engineering
---


title: How important is balance of a tree?

text:
# Question
Title: How important is balance of a tree?
I am exploring variations of trees. I know that a quality which is sometimes desired is balance in the tree so that tree depth is reduced.

But I am imagining that in situations in which several paths of a tree have to be explored such as in an R-tree, balance might not always be necessarily desired?

# Answer
Tree balance is usually preferable as the depth of the tree is shortest and the tree itself is most compact. However, there are few situations in which the fact that is unbalanced is what gives it efficiency. Huffman Coding is an example of this, where shorter paths in a binary tree represent frequently used items.
> 1 votes

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


# Question
Title: Finding dimensions of a point cloud - floating point issues
I have $N$ data points of some dimension $D$.

I want to know the dimension of the shape that those data points represent - for instance they might be a 2 dimensional triangle, even though they are in 8 dimensional space.

A way of doing this mathematically is to pick one of the points and subtract it from all of the other points to get $N-1$ vectors.

If i make these vectors into a matrix, the rank of the matrix will tell me the dimension of the shape of the data points.

The problem though is that implementing this using floating point math, not all vectors will cancel out that should.

I was wondering, is there a better way to do this when using floating point math? Or, is there a way to get a thickness in each dimension so that very thin dimensions can be ignored?

# Answer
> 2 votes
One common way to do this is to apply a Principal Component Analysis (PCA) to your data. The operation essentially consists of rotating the data around the mean to align with the principal components. Most of the variance is moved to the first components. If you know the dimension of your manifold, then you can simply select the first $k$ components and reconstruct the lower dimensionality data. If you don't, there are simple criteria such as threhsolding the ratio of the variances. Of course more elaborate Bayesian methods also do exist, such as this one. I'll quickly give an overview of the simple method. Let $\mathbf{\lambda}=\\{\lambda\_1..\lambda\_N\\}$ denote the sorted eigenvalues (giving you the variances). We could create a monotonically increasing CDF-like curve:

$$ f(i) = \frac{\sum\limits\_{j=1}^i \lambda\_j}{\sum\limits\_{j=1}^N \lambda\_j} $$ where each element represents the variance explained up to that eigenvalue (or component). We could then pick a threshold $\tau$ (e.g. \tau=0.98). Then we throw out the components which remain above that (meaning low contributions)

$$ f(i)\>\tau $$

Similarly, one could also threshold the difference $g(i)=max(f(i)−f(i−1))$, as this will be the value where adding a dimension really makes sense. If $g(i)$ is small, there would be no real contribution to explain the variance.

This problem sounds like 'dimensionality estimation' or 'dimension discovery'. There are also other methods available. PCA is just the most easy-to-implement and famous one. If your structure is linear (such as a triangle as you mentioned) PCA should be suitable.

---
Tags: linear-algebra
---


# Question
Title: Could Subset Sum Problem Be Solved In linear Time Using Logarithmic Space?
Is there any known lower bound on the complexity of subset sum problem? For example, could it be solved in linear time using logarithmic space?

# Answer
No such bound is known; for all we know, it may be possible to solve it in linear time. In fact, for all we know, there might be an algorithm for it that uses $O(\log(n))$ space on its work tape.

We know one thing: There is not an algorithm which uses both linear time *and* logarithmic space. That is, there is a time-space lower bound! A Subset Sum instance of size $n$ can be reduced to a 3SAT instance of size $O(n^2)$ (perhaps there is a better reduction), and for 3SAT, we know that, if $t(t+s)\<2$, then

$$3SAT \not\in TiSp\left(n^{t},n^{s}\right) $$

With $TiSp(t(n),s(n))$ the class of problems solvable in $O(t(n))$ time and $O(s(n))$ space. This is not the strictest bound, see *Computational Complexity: A Modern Approach* for more details.

But that still leaves open whether there is an algorithm which uses $O(n)$ time and $O(n)$ space. (Of course, the non-deterministic time hierarchy theorem tells us that for every $t(n)\in poly(n)$, there is a problem $L\in NP$ which provably requires $\Omega(t(n))$ time, the question is whether the subset sum problem is one of them.)

So yeah, that bound is not great. It's not the bound we deserve, but it is the bound we have right now.
> 5 votes

---
Tags: complexity-theory, time-complexity, np-complete, np, decision-problem
---


# Question
Title: Post Correspondence Problem - algorithm that solves the problem for a word with maximum K length
The question is as follows:

> Let's observe the following Post correspondence problem.
>
> Input: Two finite lists of words $A$ and $B$ and a natural number $k$.
>
> Question: Is there any words correspondence with a length of $k$ **at the maximum**?
>
> Describe an algorithm to solve the problem and analyze its runtime.

I really don't understand how to solve this problem. From my understanding, the Post correspondence problem is undecidable so how come we can describe an algorithm to solve this question?

# Answer
PCP is undecidable essentially because, if there is a match, it could be arbitrarily long. But, here, the question specifically excludes any string longer than $k$ characters. There are only about $2^{k+1}$ possible strings of length at most $k$ over alphabet $\\{a,b\\}$. Does that help you find an algorithm?
> 2 votes

---
Tags: algorithms, decision-problem
---


title: Tight Bound of the Insertion Sort

text:
# Question
Title: Tight Bound of the Insertion Sort
I'm asking this question because I was confused by some of the articles in the internet.

I already know that the asymptotic lower and upper bounds of insertion sort is $\Omega(n)$ and $O(n^2)$.

Therefore according to my understanding of the $\Theta$ notation, we cannot make a statement about the $\Theta$ for all cases.

So is it $\Theta$ undefined for the insertion sort?

Or is it $\Theta(n^2)$?

# Answer
> So is $\Theta$ undefined for insertion sort?

This question contains a category error. It's like saying, "I know that Donald Trump has a height of at least 5 and at most 7. So are numbers undefined for Donald Trump?

$\Theta$ is notation for expressing the growth rate of mathematical functions. "Insertion sort" is not a mathematical function, so if you want to talk about $\Theta$ and insertion sort in the same sentence, you need to say what property of insertion sort you're measuring with a mathematical function that you wish to describe with $\Theta$.

We measure the resource usage of algorithms in terms of the length of the input, which is usually denoted $n$. You've proposed a function which is the number of execution steps of insertion sort on some input. However, this is a function of the input itself, not of its length. Some inputs of length $n$ will take roughly $n$ steps to sort (I'm using "roughly" to hide constant factors), and some inputs of length $n$ will take roughly $n^2$ steps. So you can't write this as a function of $n$ at all – the number of steps required isn't just a function of the length of the input but, rather, it's a function of the whole input. Because the thing you're trying to measure isn't a function of the length of the input, you can't directly measure it using $\Theta$ at all.

So we need to come up with a function that does just depend on the length of the input. Two natural functions are the best-case and worst-case number of execution steps. We know that, for an input of length $n$, the best case is that insertion sort finds that the input is already sorted, and in this case, it takes a linear number of steps. No more, no less, so we're entitled to say that the best-case running time of the algorithm is $\Theta(n)$. Similarly, we're entitled to say that the worst-case running time is $\Theta(n^2)$.

If the best and worst case was (asymptotically) the same (up to constant factors), then the running time would actually just be a function of the *length* of the input, so it would make sense to say that the running time was, e.g., $\Theta(n\log n)$. However, unless the running time really is a function of $n$, this is an abuse of notation. In the case or insertion sort, where the best and worst case running times are different, we can abuse notation a little harder and say the running time is $\Omega(n)$ and $O(n^2)$. This says that, for any (sufficiently large) input, the running time will be somewhere between $n$ and $n^2$ steps (up to constant factors) but, again, there is no actual function of $n$ that is "the running time." It would be more formal to say that the running time $T(x)$ for an input $x$ satisfies $c|x|\leq T(x)\leq c'|x|^2$ for large enough $|x|$ and some constants $c$ and $c'$.
> 3 votes

---
Tags: algorithm-analysis, asymptotics, sorting
---


# Question
Title: Is the language $\{a^n b^n c^i | i \leq n\}$ context free?
I'm trying to apply the CFL pumping lemma. And, I've already tried words $a^pb^p$ and $a^pb^pc^p$. Not sure where to go from here.

# Answer
> 1 votes
Classical pumping works. According to the pumping lemma we can find a segmentation $uvwxy$ such that $uv^iwx^iy$ is in the language for all $i$.

Start with your own suggestion $a^pb^pc^p $.

Three easy steps.

* Each of the "pumping segments" $v$, $x$ can only be within the boundaries of one the "letter segments" $a^p$, $b^p$, $c^p$.
* It is not possible to have one of $v$ or $x$ to be in the $a^p$ segment without the other being inside the $b^p$ segment. And the other way around. In that case pump down ($i=0$).
* Final possibility both $v$ and $x$ are in $c^p$. Pump up.

---
Tags: formal-languages, context-free, pumping-lemma
---


# Question
Title: Implicit Leading 1 in Binary Floating Point
Is the convention of dropping the leading 1 when storing the significand a given in all binary floating point representations or not necessarily?

# Answer
> 1 votes
As @BugKiller says, if it is IEEE format, it doesn't matter how many bits (32, 64, 43, etc) uses your representation, you drop the leading 1. And I think is the same thing with subnormal numbers taking a leading 0. Other floating point representations not specified within IEEE takes the same idea, because this dropped 1 comes from binary representation as any non-zero number will have a leading one, you drop it and you gain 1 bit to expand your representation.

# Answer
> 1 votes
The convention of dropping the leading 1 is not universal among practical floating point implementations. Namely, the very common x87 extended precision format does not follow this convention.

---
Tags: floating-point, number-formats
---


# Question
Title: Given snapshot and boolean circuit how to compute coNP formula?
> Theorem 6.20: If $\mathsf{EXP\text{}} \subseteq \mathsf{P\_{poly}\text{}}$ then $\mathsf{EXP\text{}} = \Sigma\_2 ^{p}$.

**My attempt** : Let $L \in \mathsf{EXP\text{}}$. Then $L$ is computable by an $2^{p(n)}$-time Turing machine $M$, where $p$ is some polynomial. Let $x \in \\{0,1\\}^n $ be some input string. For every $i \in \[2^{p(n)}\] $, we denote by $z\_i$ the encoding of the $i$th snapshot (the machine's state and symbols read by all heads) of $M'$s execution on input $x$. If $M$ has $k$ tapes, then $x\in L \iff $ for every $k+1$ indices $i,i\_1,i\_2,\cdots,i\_k$, the snapshots $z\_i,z\_{i\_{1}},\cdots,z\_{i\_{k}}$ satisfy some checkable criteria.

As $\mathsf{EXP\text{}} \subseteq \mathsf{P\_{poly}\text{}}$, then there is a $q(n)$-sized circuit $C$ (for some polynomial $q$) that computes $z\_i$ from $i$. **Now the main point is that the correctness of the transcript implicitly computed by the circuit can be expressed as a $\mathsf{coNP\text{}}$ predicate (namely, one that checks that the transcript satisfies all local criteria)**. Hence, $x\in L$ iff the following condition is true

$$ \exists C \in \\{0,1\\}^{q(n)} \forall i,i\_1,i\_2,\cdots,i\_k \in \\{0,1\\}^{p(n)} T(x,C(i),C(i\_1),\cdots,C(i\_k)) = 1$$

> **Question** : I am not able to understand, how transcript implicitly computed by the circuit can be expressed as a $\mathsf{coNP\text{}}$ predicate ?

**Reference** : http://theory.cs.princeton.edu/complexity/circuitschap.pdf

# Answer
> 0 votes
You want to know how, given a circuit $C$, one can express the statement "given $i$, $C$ correctly computes $z\_i$, the i'th snapshot in the computation of $M$ on some fixed input $x$", by a coNP predicate. Note that if this can be done, say using the predicate $\varphi (C,x)$, then $$\psi(x)=\exists C: \varphi(C,x)\land C\left(2^{|x|^c}\right) \text{ is accepting}$$

is exactly the $\Sigma\_2$ formula you're looking for. To see why, note that $x\in L$ iff the last snapshot is accepting, or equivalently if $C\left(2^{|x|^c}\right)$ is accepting, and $C(i)$ correctly computes $z\_i$. So if $\varphi(C,x)$ indeed expresses "C correctly computes $M$'s snapshots on input $x$", then $x\in L \iff \psi(x)$. If you have a guarantee that polynomial circuits for $L$ exist, then you can bound the existential quantifier, and only look for poly-size circuits.

So how do we write $\varphi(C,x)$ as a coNP predicate? Using locality, you know that the $i'th$ snapshot depends on some $k$ previous ones (where $k$ is a constant depending on the number of tapes). $C$ correctly computes the snapshots if for all $i,i\_1,...,i\_k$ (this gives you the universal quantifier) it holds that $T\left(x, C(i), C(i\_1),...,C(i\_k)\right)$, where $T$ depends on $M$'s transition function. Intuitively, $T$ checks whether $i\_1,...,i\_k$ are the previous indicies of snapshots who determine $z\_i$, and if so verifies that the transition was indeed according to $M$'s rules.

---
Tags: complexity-theory, circuits
---


# Question
Title: 1 bit register with data flip flop doesn't store bit?
A 1-bit register:

> Credit:
> Elements of Computing Systems
> by Noam Nisan and Shimon Schocken
> ISBN-13: 978-0262640688

I know that the data flip flop outputs the input at the previous time step.

Based on this, I created this table (not sure if correct):

Note: For the `Mux`, 1 is for `in` and 0 is for `DFF` output.

$$ \begin{array}{|c|c|c|c|} \hline \text{In} & \text{DFF In} & \text{Load} & \text{Out} \\ \hline 1 & 1 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 \\ \hline 1 & 1 & 0 & 0 \\ \hline \end{array} $$

The output is always alternating, no bit is being stored. It should constantly output 1 while load is 1 because that's what we initially stored.

I know that a register does actually store data, so something is wrong in my understanding of this.

# Answer
> 0 votes
So I figured this out, the storage happens over the whole `tock (high)` of the master clock.

`t -> t+` is the `tick` and `t+ -> t+1` is the `tock`

`Load` and the `bit` we are trying to store must remain constant for at-least one whole `tock`.

So something like this:

$$ \begin{array}{|c|c|c|c|c|} \hline \text{Time} & \text{In} & \text{DFF In} & \text{Load} & \text{Out} \\ \hline 0+ & 1 & 1 & 1 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline 1+ & 0 & 1 & 0 & 1 \\ \hline 2 & 0 & 1 & 0 & 1 \\ \hline \end{array} $$

# Answer
> 0 votes
Your table is incorrect. A MUX element selects one of its inputs based on a secondary input. In this case it's a binary mux and `load` is used to select the input.

If we say that `load = 0` means it selects the DFF and `load = 1` means that it selects `in` you shall see that when `load = 0` the circuit repeatedly refreshes the previous value, and `load = 1` will read the new value from `in`.

---
Tags: computer-architecture, memory-hardware, storage
---


title: Time Complexity OF NTM vs TM

text:
# Question
Title: Time Complexity OF NTM vs TM
In Sipser, It is given Pg. 284

> Let t(n) be a function, where t(n) ≥ n. Then every t(n) time non-deterministic single-tape Turing machine has an equivalent 2 O(t(n)) time deterministic single tape Turing machine

In the given proof, at end they conclude

> O(t(n)bt(n)) = 2O(t(n)).
>
> where b is the maximum number of legal choices given by N’stransition function

I am unable to understand how did they conclude so\>

# Answer
You can write, if $b\gt 1$, $$b^{t(n)}=2^{\log\_2{b}\times t(n)}=2^{O(t(n))}$$

So, $$O(t(n)b^{t(n)})=O(t(n)2^{O(t(n))})=O(2^{\log\_2{t(n)}}2^{O(t(n))})=2^{O(t(n))}$$

To elaborate, $$O(x2^{O(x)})=O(2^{\log x}2^{O(x)})=O(2^{O(x)+\log x})=O(2^{O(x)})$$ which means it is eventually upper bounded by some $$c2^{O(x)}=2^{\log cO(x)}=2^{O(x)}$$

Note that if $b=1$, then the non deterministic Turing machine is effectively a deterministic Turing machine, so you can still write it as $O(t(n))$, which is as expected.
> 2 votes

---
Tags: complexity-theory, turing-machines, time-complexity, nondeterminism
---


# Question
Title: Can someone help me understand this proof: there exists a complement of an RE language is not RE
I'm trying to understand this proof in Peter Linz's book

The math just doesn't make any sense, I don't understand how this is a proof. First of all, the author says let's define a language such that:

for all i\>0: a^i ∈ L(Mi)

That seems ok. Then he says let's consider the complement of L.

L'={a^i:a^i ∉ L(Mi)}.

How is this even possible? The author just stated a statement that is in itself a paradox. The set of turing machines is countable and for all "i" there is a corresponding machine; so how can we say later that for some a^i there is no turing machine? And isn't the complement going to be the empty set anyway? But the author keeps going and deduces a contradiction, I understand that part, but isn't the contradiction a result of what seems to me a paradoxical statement in the first place?

The way I understand it's like saying:

---

For all fruits, there exists a tree that produces a specific one.

An apple is a fruit. Let a be an apple and define A to be the set of all apples and T(Ai) be the tree that produces a specific apple.

Now define A' to be the set of all apples that don't have a corresponding tree T(Ai).

Assume A' to be a set of fruits, then there must exists a corresponding tree T(Ak) for all elements. (\**)

Consider a^k. Is it in A or in A'?

if it is in A', then a ∉ A' a contradiction. by (\**)

if it is in A, then a ∈ A , but also a ∉ T(Ak) which means it is in A'. A contradiction.

We get contradiction either way so A' isn't a set of fruits.

---

I put this example to illustrate my point. What went wrong in the apples example is that I defined a set to have apples that don't have corresponding trees, even though I stated before that all apples have corresponding trees since they're all fruits. Thus, if anything, A' should be the empty set. In Linz's example, we know that for all a^i there is a corresponding turin machine. Then he goes on to say there is a set for which there are strings that don't have corresponding machines. How does this count as proving that there are strings not in the language if all we did is just use a contradiction to deduce a contradiction?

I tried to make my question as clear as I can, let me know if something need clarification.

# Answer
> 2 votes
1. The phrase "there exists a complement of an RE language is not RE" shows that you might be confused about complements. *Every* language has *the* complement, simply because every subset has a unique complement. You should have said "there exists an RE language whose complement is not RE". One does not have to justify the existence of a complement, that's just part of foundations of mathematics.
2. It is false that the author defines $L$ using the condition "for all $i \> 0$, $a^i \in L(M\_i)$. The correct condition is that $a^i \in L$ *if and only if* $a^i \in L(M\_i)$. In other words, we have $$L = \\{a^i \mid a^i \in L(M\_i) \\}.$$ For instance, whether $42 \in L$ depends on what the $42$-nd Turing machine $M\_{42}$ does: if it accepts 42 then $42 \in L$, otherwise $42 \not\in L$.
3. A language may be *any* subset of the set $\Sigma^{\*}$ of all words (over a given alphabet). It does not matter whether there is a Turing machine that accepts it. If there is one, that's a special kind of language. Anyhow, if you accept that $L$ is well-defined subset of $\Sigma^{\*}$, then you have to accept that its complement is also a subset of $\Sigma^{\*}$, therefore a language. It just so happens that this language is not recognized by any Turing machine. In fact, that is what the gist of the argument in the book is about.

# Answer
> 0 votes
$M\_i$ is the $i^{th}$ machine in the enumeration of all Turing machines whose alphabet is $\\{a\\}$. $L(M\_i)$ is the language recognized by that Turing machine.

The set $L$ is the set of all strings $a^i$ (i.e. strings whose alphabet is $\\{a\\}$ such that the string is recognized by the $i^{th}$ Turing machine in the enumeration. So its complement includes a string $a^i$ if it is *not* recognized by the Turing machine $M\_i$. That certainly does not involve a paradox; it is a simple statement of fact.

You seem to be reading $a^i \notin L(M\_i)$ as though it were the complement of $\exists j ( a^i \in L(M\_j))$. It is not. It is simply a statement about a single value of $i$.

---
Tags: computability, turing-machines, proof-techniques
---


# Question
Title: Could be solved a NP-complete problem in constant time?
Under the assumption that P would be equal to NP, it could exist a NP-complete problem that is solved in constant time?

# Answer
> 4 votes
Write down the definition of NP-complete. Then take your assumption that P = NP, so in the definition of NP-completeness you can replace "NP" with "P". Figure out which functions exactly are NP-complete. (Hint: There is a simple and obvious solution that is almost but not *quite* correct. Read the definition carefully). Do these functions contain any constant time solvable problems?

Each step is actually quite simple, you just have to follow all the definitions very precisely.

---
Tags: complexity-theory, np-complete, p-vs-np
---


# Question
Title: Are IEEE floating point numbers intervals or point values?
The context is IEEE 754-2008 floating point number systems. The systems defined by the standard comprise, as far as I understand it, a bit-level representation and a set of guarantees on the precision for a given number of computations.

Now, I am wondering whether floating point numbers, i.e., the objects represented and manipulated in such a system, should be looked at as intervals—a contiguous set real numbers—or as point values—a unique real number. (Which interval? Crudely, with round-to-nearest, the nominal value plus-or-minus half a ulp.)

The arguments for intervals I see come mostly from the representational aspects of the system:

1. Numbers from ‘outside’ of the system—measurement data, say—are encoded with reduced precision and so the bit-level representation is in general clearly not the ‘true’ value, but—given the information about the rounding rule used—represents an interval in which the ‘true’ value lies.
2. Numbers from ‘inside’ of the system that are the result of a series of computations within the system have also been subject to the effects of intermediate rounding and so again—given the information about the rounding rule used—represents an interval in which the ‘true’ resulting value of the computation lies.

The arguments for point values I see come from the computational aspects of the system and the typical discussions of floating point:

3. Computations are performed on the real value that nominally corresponds to the bit-level representation, using some extra bits to enable precision guarantees. They are not applied to the interval bounds implied by the bit-level representation (and information about the rounding rule used in its generation), which would be possible in principle using some extra bits and double the effort (each computational step…). Put differently: interval analysis is not applied.
4. If interval analysis were used, rounding rules would not be needed.
5. In the discussions of floating point I have seen, they are always generally treated as point values, e.g., depicting them as discrete points on the real line.

Now, the above arguments are composed by someone that has not read up on the floating point literature in detail, so they may not represent the common view among knowledgeable people in the field. I would like to learn the views of these people and the arguments used. (So I am not necessarily looking for an answer ‘point values’/‘intervals’ to the binary question of the title of this question.)

I have not specified restrictions to the binary or decimal systems. This may be relevant, I feel: in the binary case, the representations are normalized, so no significance information is available, but in the decimal case, the representation is not normalized. This means, I think, that in the latter case a crude way of doing interval analysis is possible (by reducing the number of significant digits)—not that this means it is actually done—, but in the former case, such crude analysis is not possible (although it would be far less crude, given the small magnitude steps—factors of 2).

# Answer
That has been long established. Most IEEE 754 floating point numbers represent exactly one real number. The exceptions are +0 and -0, +Inf and -Inf, and NaN with special meanings. (Thanks for one comment stating that "In IEEE Std 754-2008, Table 3.1 states that floating point numbers are projected into the (extended) reals, which implies that indeed they are seen as point values". )

If you tried to claim that IEEE 754 floating point numbers did represent intervals, then you would run into deep, deep trouble when you try to define floating-point arithmetic.

We can see that in the comments: There an assumption is made that a floating point number is or has an interval x ± eps. That assumption is wrong. Let u be the value of the last bit in the mantissa of 1.0. Then if say x = 1.5 all numbers in the interval \[x - u/2, x + u/2\] are rounded to x, but if x = 1.5 + u then that interval is (x - u/2, x + u/2) - an open interval instead of a closed one. And if x = 1.0, then the interval is \[x - u/4, x + u/2\]. Not even a symmetric interval!

And the suggested arithmetic with these intervals seems to be "we take the numbers in the middle of the intervals, calculate the result, and find the interval containing the result" - which is essentially arithmetic with "point" floating point numbers, with a bit of fuzz added at the beginning and the end.

When you try to convert between binary and decimal numbers, these intervals come into play for real if you want a high quality conversion, and from experience this is an absolute PITA. Don't go there unless you enjoy that kind of thing.
> 4 votes

---
Tags: floating-point, intervals, real-numbers, rounding
---


# Question
Title: Converting indirect recursion to direct one
I want to remove left recursion in grammar:

$G = ({S, A,B,C,D}, {a,b,c},P,S)$

$S → A$

$A → Aa | Bc$

$B → B a |CD$

$C →C b | ε$

$D → Bb | a$

We see that this grammar contains direct recursion ( $A → Aa$ ) and indirect recursion ( $B → CD → D → Bb$ ). We need to remove indirect recursion and convert it into direct recursion.

The problem in this grammar is $C → ε$ rule , so we remove epsilon rules , after that we are left with

$B → B a |CD |D$ which is another indirect recursion so we remove simple rules.

Then we can remove left recursion step by step by alghoritm.

My question is , having large grammar , finding indirect recursion may be difficult. Is there any universal way how to convert indirect recursion to direct recursion? Thanks for answers

# Answer
$S\to A$

$A\to aA'|EP$

$B\to CDB'$

$B'\to AB'|EP$

$C\to bC|EP$

$D\to aD'|bC'DB'bD'$

$D'\to B'bD'|EP$

There is a standard algorithm to remove indirect left recursion check here https://en.wikipedia.org/wiki/Left\_recursion#Indirect\_left\_recursion
> -1 votes

---
Tags: context-free, formal-grammars, left-recursion
---


title: Hamiltonian path in directed graph

text:
# Question
Title: Hamiltonian path in directed graph
Let G be a **directed** graph such that every two vertices are connected by a single edge. How do I proof that such G has an hamiltonian path?

# Answer
# Proof by induction

**Basis**. All complete oriented digraphs with two vertices have Hamiltonian path - it's obvious.

**Induction step**. Let's assume that complete oriented digraph $G\_{n-1}$ with $(n - 1)$ vertices contains Hamiltonian path $(s, ..., t)$ from vertex $s$ to vertex $t$. We'll show how to build Hamiltonian path for complete oriented digraph $G\_n$, which is constructed from $G\_{n-1}$ by adding a vertex $p$.

*Case 1*. The $G\_n$ has an edge $(p, s)$. The Hamiltonian path in $G\_n$ will be $(p, s, ..., t)$.

*Case 2*. The $G\_n$ has an edge $(s, p)$. Then we need to scan the Hamiltonian path $(s, ..., t)$, trying to find an edge $(v\_{i-1}, v\_i)$, such that the graph $G\_n$ contains edges $(v\_{i-1}, p)$ and $(p, v\_i)$. There are two subcases:

*Subcase 2.1*. We *can find such a pair* \- then the new Hamiltonian path will consist of three parts - $(s, ..., v\_{i-1})$, $(v\_{i-1}, p, v\_i)$ and $(v\_i, ..., t)$.

*Subcase 2.2*. We *can't find such a pair* \- it means, that all the edges from vertices on the path $(s, ..., t)$ to the additional vertex $p$ are oriented *to* this vertex. The new Hamiltonian path will be $(s, ..., t, p)$.
> 4 votes

---
Tags: graphs, hamiltonian-path
---


# Question
Title: Computing the size of an m-associative cache
I am trying to answer this question:

*Consider a computer with a byte-addressable memory. A 40-bit memory address is divided as follows for cache processing. First, the 8 low-order bits are chopped off to expose the cache-line number. Second, the next 17 low-order bits are inspected to get the cache-container index. Third, the remaining 15 bits are used as the cache tag. Hint: What do the direct-mapped and set-associative placement formulas have in common?*

*What is the cache size in bytes?*

I've figured out that the cache line size is 2^8 bytes and that there are thus 2^32 cache lines in memory. Furthermore I know that there are 2^17 cache sets in the cache. To compute the capacity of the cache, I am using the equation

**capacity = line size x #of sets x associativity**

However, even using the tag field, I can't see how I can find the associativity of the cache here.

# Answer
> 1 votes
I'm not sure if the first question is actually a question or a Hint. Anyway cache size can be calculated as follows.

Memory is byte addressable. Masking off 8 bits for cache line, that means, cache line in 2 ^ 8 bytes. Using 17 bits for TAG indexing, that is 2^17 cache entries. Therefore, you have 2^8\*2^17 bytes in the cache. That is 2^25 = 2^5\*2^20 = 32 MB.

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


# Question
Title: Boolean circuit with two inputs and advice input is hard-wired
> Claim : $\cup\_{c,d} $ DTIME$(n^c)/n^d \subseteq$ $P\_{poly}$

Proof : if $L$ is decidable by a polynomial-time Turing machine $M$ with access to advice family $\\{\alpha\_n\\}\_{n\in \mathbb{N}}$ of size $a(n)$, then we can use the cook-levin construction for every $n$ a polynomial-sized circuit $D\_n$ such that on every $x \in \\{0,1\\}^n$, $\alpha\_n \in \\{0,1\\}^{a(n)}$, $D\_n(x,\alpha) = M(x,\alpha)$. That is, $C\_n$ is equal to the circuit $D\_n$ with the string $\alpha\_n$ "hard-wired" as its second input.

**Question** : I am not getting the part that circuit is going to have two inputs one hard-wired as second input. How a circuit will like with two inputs. I have seen circuits with one input but not with two inputs (i.e. one input is hard-wired). I am thinking that it may be the case that they are attaching advice bit to each of AND and OR gate (increasing the fan-in). So I am not getting, how they are hard-wiring the advice string ?

Reference : http://theory.cs.princeton.edu/complexity/book.pdf

# Answer
> 1 votes
Just imagine the circuit $D\_n(x,\alpha)$ has $n+a(n)$ bits of input, where the first $n$ bits are treated as the first parameter for the machine $M$, and the last $a(n)$ bits are treated as the advice. To forget about this separation and have a simpler notation, we just say $D\_n$ accepts two inputs. Now fix the "second parameter" with the correct advice $\alpha\_n$, and this induces a polynomial circuit for $L$ with $n$ inputs.

---
Tags: complexity-theory, circuits
---


# Question
Title: Algorithm SAGE- PARI? for splitting polynomials over field extension
I tried to follow with SAGE the solvability of solvable quintic polynomial. I took the example of the solvable polynomial $f=T^5+15T+12$, fully studied in Dummit. I understand that the splitting field $L$ is radical with $\[L:\mathbb{Q}\]=20$.

The square root of the discriminant is (SAGE) $2^53^25^2\sqrt5$ so we have a quadratic subfield $k=\mathbb{Q}(\sqrt{5})\subset L$. This polynomial (as a function) is strictly increasing over $\mathbb{R}$ so has a unique real root $x$. We consider the extension $k(x)/k$ of degree $5$ ($f$ is still irreducible over $k$) so the last extension of the chain of subfields $\mathbb{Q}\subset k=\mathbb{Q}(\sqrt{5})\subset k(x)\subset L$ is quadratic. The polynomial $f$ must split over $k(x)\\;(\subset\mathbb{R})$ into a product of the linear factor $(T-x)$ and two quadratic factors $P\_1,P\_2 \in k(x)\[T\]$ whose roots are the pair of complex conjugated roots $x\_1$,$\bar{x}\_1$,$x\_2$,$\bar{x}\_2$ of $f$.

We can write the euclidean division $f(T)/(T-x)$ in the form: $$P\_1P\_2=T^4+xT^3+x^2T^2+x^3T+x^4+15$$ $$= \left(T^2 +A(x)T+N\_1(x)\right)\\;\left(T^2 +C(x)T+N\_2(x)\right)\in k(x)\[T\]$$

How does SAGE gives the coefficients of $P\_1=(T^2 +A(x)T+N\_1(x))\in k(x)\[T\]$? The result given by SAGE is: (recall that the ground field is $\mathbb{Q}(\sqrt{5})$ and that $x$ is a root of $T^5+15T+12$, in other words $x^5\equiv -15x-12$)

$A(x)=\frac{\sqrt{5}}{10}x^4 + \frac{\sqrt{5}}{10}x^2 +(\frac{\sqrt{5}}{10} + \frac12) x + \frac{6\sqrt{5}}{5}=x\_1+\bar{x}\_1$

$N\_1(x)=(\frac{\sqrt{5}}{20}+\frac14)x^4+ (\frac{\sqrt{5}}{20} - \frac14) x^3 + (-\frac{3\sqrt{5}}{20} + \frac14)x^2 + (\frac{3\sqrt{5}}{20} - \frac34) x + 3=x\_1\bar{x}\_1$

and I feal that understanding how SAGE/PARI computes this would give a better understanding of field extensions.

Further, the simplier example for the last quadratic extension $L/k(x)$. It is generated by any other root. Take one root $x\_1$, so $x\_1^2\in k(x)$, and define the quadratic extension $L=\\{k(x)+x\_1k(x)\\}$ generated by this root. It's conjugate (over $k(x)$) is $x'\_1=-A-x\_1$. The other pair is $x\_2=a+bx\_1$ whose conjugate (over $k(x)$) is $x'\_2=a'-bx\_1$, and both are roots of $P\_2=T^2+CT+N\_2$ with $x-A=C$ and $xN\_1N\_2=-12$. How does SAGE finds the values $a,a',b$?

# Answer
I though the answer was easier than what I found, so no real chance to do this "by hand". The article from Factoring Polynomials describes a process over $\mathbb{Q}$ called the Zassenhauss method: first factor modulo $p$ (say Berlekamp algorithm, rather accessible), then Hensel lift back and check bounds on coefficients and other tests. The Klueners article describes the "van Hoeij" algorithm which I admit is above my math understanding capabilities.

It also describes the "Trager method" over a field extension. Find a primitive element, compute it's minimal polynomial over $\mathbb{Q}$, factor it with say the previous method, so the extension is the field modulo the maximal ideal generated by the minimal polynomial, and apply chinese remainder to decompose the given polynomial.
> 1 votes

---
Tags: algorithms
---


title: MST: Are all safe edges, light edges?

text:
# Question
Title: MST: Are all safe edges, light edges?
Following are some definitions from CLRS:

> **DEFINITIONS** :
> 1. **Cut (S ,V-S)** : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.
> 2. **Light edge**:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.
> 3. A cut **Respects** a set A of edges if no edge in A crosses the cut.
> 4. **Safe edge** is the edge which we can add to MST without any violation of MST's property.These are those edges which are the part of final MST.

# Answer
> 5 votes
Yes, all safe edges (edges which are part of some MST) must be the lightest edge for some partition $(S, V-S)$ of the graph. For if $e=uv$ is a safe edge, it is part of some MST $T$, and $T-e$ partitions the vertex set of the graph into two parts $(S, V-S)$, where $u \in S$ and $v \in V-S$. If $e$ was not a lightest edge between $S$ and $V-S$, then $e$ can be removed from $T$ and replaced with a lighter edge $f$, giving a tree $T-e+f$ with a smaller weight than $T$, contradicting the fact that $T$ is an MST.

As a concrete example, suppose $G$ is the path graph on vertex set $\\{a,b,c\\}$ and edge set $\\{ab, bc\\}$, with the edges $ab$ and $bc$ having weights $1$ and $2$, respectively. Then, edge $bc$ is not the lightest edge available, but it is a safe edge to add first and it is the lightest edge between $S$ and $V-S$ if we take $S = \\{a,b\\}$.

---
Tags: graphs, terminology, minimum-spanning-tree
---


# Question
Title: Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?
I was under the impression that our computers, being finite, are ultimately no more powerful than (extraordinarily large) Finite State Machines. However, Linearly Bounded Turing Machines are also finite, but it seems that Regular Languages are strictly an improper subset of Context-Sensitive Languages.

Obviously, I'm missing something here. What is going on?

# Answer
> 22 votes
The linear bounded Turing machine is restricted to a tape whose length is a linear function of the length of the input.

If the length limit were a constant, then the machine would be no more powerful than a DFA. However, a DFA cannot grow more states to cope with a longer input, which in effect the LBTM can do (taking the state to be the entire machine configuration.) So the LBTM is strictly more powerful.

# Answer
> 4 votes
I think we must first understand the description of a machine and the input size, so that the comparison is of only valid objects. Let say ***N*** is a input size. This means machines will have these resource bounds.

\begin{array}{|l|l|l|} \hline \mbox{Resource} & \mbox{Finite Automata:}\quad \mathcal{A} & \mbox{LBTM:} \quad \mathcal{M}\\ \hline \mbox{Input Tape Size} & O(N) & O(N)\\ \mbox{Tape Operations} & \mbox{Read Only}& \mbox{Read, Write}\\ \mbox{Tape Movement} & \mbox{Left to right, One pass only}& \mbox{Both directions, No pass limit}\\ \mbox{# of Locations (States)} & M & M\\ \mbox{Input Alphabet} & \Sigma & \Sigma\\ \mbox{Acceptance Condition} & \mbox{Reach finite location: }\ell\_f & \mbox{Reach finite location: }\ell\_f\\ \hline \end{array}

Now, here $\mathcal{M}$ is more expressive than $\mathcal{A}$. That's simply because tape movement and restrictions are limited for $\mathcal{A}$.

Now let's make an **invalid** comparison. \begin{array}{|l|l|l|} \hline \mbox{Resource} & \mbox{Finite Automata:}\quad \mathcal{A'} & \mbox{LBTM:} \quad \mathcal{M}\\ \hline \mbox{Input Tape Size} & O(N) & O(N)\\ \mbox{Tape Operations} & \mbox{Read Only}& \mbox{Read, Write}\\ \mbox{Tape Movement} & \mbox{Left to right, One pass only}& \mbox{Both directions, No pass limit}\\ \mbox{# of Locations (States)} & M \times 2^N & M\\ \mbox{Input Alphabet} & \Sigma & \Sigma\\ \mbox{Acceptance Condition} & \mbox{Reach finite location: }\ell'\_f & \mbox{Reach finite location: }\ell\_f\\ \hline \end{array}

Here $\mathcal{A}'$ and $\mathcal{M}$ have same expressive power. But, note that the size of $\mathcal{A}'$ depends on input $N$ in exponential manner. Earlier size of $\mathcal{A}$ did not depend on $N$. This means for every input to $\mathcal{M}$, you will need to generate new FA, even though $\mathcal{M}$ remains unchanged.

---
Tags: finite-automata, computation-models, linear-bounded-automata
---


# Question
Title: How can every regex be accepted by an infinite number of finite automata?
In The (New) Turing Omnibus by A K Dewdney, chapter 2, it says:

> Moreover, for every regular expression there is an automaton which accepts the language symbolized by that expression. Thus, in a sense, regular expressions capture precisely the behavior of automata in terms of the language they accept. However, for every regular expression there are an infinite number of automata which accept that language.

But for a simple regex, e.g. `a`, I can think of exactly one finite automaton that corresponds to it: `(start state) -a-> (accepting state)`. I don't see how there can be an infinite number. What am I missing?

For context, at this point in the book he has not yet introduced DFAs vs NFAs, and all examples of automata so far have been DFAs.

# Answer
There's at least one more DFA - consider the DFA with one state which is both the start and accepting state, and on input a transitions to itself. This accepts a\* (and therefore a). If you allow ε-NFAs, it is fairly obvious that there are infinitely many, as you can always add another ε-transition before the transition leading to the accepting state. By corollary, you could add infinitely many states and transitions to any given DFA, so long as there is only one transition from the start state to a unique accepting state on input a.
> -1 votes

# Answer
There are at least two ways of doing this.

The first is kind of trivial: there's no requirement that all states of an automaton be accessible from the start state. So, take your favourite automaton that accepts some language, and then add as many new states as you want, with arbitrary connections between them, as long as they're not connected to the original automaton.

A second way keeps the automaton connected. I'll give an informal description; I wrote a more formal one in response to another question. Take your favourite automaton and make $n$ copies of every state. Modify the transition function so that if, in the original automaton, $\delta(q,a)=q'$ then, in the new automaton, reading $a$ in the $i$th copy of state $q$ takes you to the $(i+1)$st copy of $q'$ (with addition modulo $n$). The start state is the first copy of the original start state; every copy of an accepting state is accepting. This isn't guaranteed to keep the automaton connected but you can delete the disconnected states and you are guaranteed to end up with an automaton with at least $n$ states.
> 7 votes

# Answer
Consider the following automata. The notation used is $D=(Q,\ Σ,\ δ,\ q\_0,\ F)$

$D\_1=\\{\\{0,1\\},\\{a\\},δ,0,\\{1\\}\\}$ with $δ(0,a)=1$

$D\_2=\\{\\{0,1,2\\},\\{a\\},δ,0,\\{1\\}\\}$ with $δ(0,a)=1$

$D\_3=\\{\\{0,1,2\\},\\{a\\},δ,0,\\{1\\}\\}$ with $δ(0,a)=1$ and $δ(2,a)=1$

$D\_4=\\{\\{0,1,2,3\\},\\{a\\},δ,0,\\{1\\}\\}$ with $δ(0,a)=1$ and $δ(2,a)=3$

$...$

they all accept just $w=a$

What is unique is the **minimal DFA**, but in general for a regular expression there are an infinite number of DFA which accept the language described by the regular expression.
> 3 votes

# Answer
Let me build two more automata accepting $a$ for you. Hope you got the point.
> 0 votes

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


# Question
Title: Forward checking vs arc consistency on 3-SAT
If I were to let the variables be the propositions and, constraint be all clauses being satisfied, which technique would be more effective in solving 3-SAT? Forward checking or arc consistency? From what I gathered forward-checking is $O(n)$, while Arc consistency is about $O(8c)$ where c is the number of constraints (According to this page). So perhaps forward -checking is faster somehow? How should I determine which to use?

# Answer
Both forward checking (FC) and arc consistency (AC) are methods of inference. Regardless of the problem you are solving, choosing a specific method of inference is always a tradeoff. Basically, the more you are willing to pay in terms of time, the more you gain in terms of strength of inference. So yes, it is faster to perform forward checking than arc consistency, but arc consistency is more effective at pruning the search space. If you are willing to pay even more, there are even stronger forms of consistency. The book by Russell & Norvig gives a nice, quick introduction.

Both FC and AC are relatively cheap and easy to implement, too. The suitable choice depends on the specific structure of your problem. I think at least in general, it is best that you experiment with both.
> 7 votes

# Answer
In practice, for almost all SAT problems except the most trivial, AC will be faster -- usually exponentially faster.

While AC is slightly slower per node, it can often perform reasoning steps which remove any exponential part of search.
> 0 votes

---
Tags: algorithms, satisfiability, heuristics, 3-sat, sat-solvers
---