title: What does "dummy argument" mean?

text:
# Question
Title: What does "dummy argument" mean?
What is does it mean when an argument to a function is called a **dummy argument**? I have not encountered this term outside Fortran, is it a general term in computer science? What would be examples of arguments passed as dummy and not passed as dummy?

I found this definition, which I am not sure that I understand, but it sounds like a dummy argument is a variable that is passed by reference, in which case in Fortran all variables are dummy variables? (confused)

Edit: I just run into the following essay which helped me to understand better Fortran's argument/function calling teminology: Dortor Fortran: I've come here for an argument

# Answer
In fortran a **dummy** argument is what other languages refer to as a **formal argument**. So the dummy arguments are the list of arguments in the function (or subroutine) definition.

The **actual arguments** are the list of arguments in the calling list, at the point in the source code where a function is called (ie used).
> 22 votes

# Answer
## "Dummy" as "unused"

In general (not in Fortran) a dummy argument is an argument that will not be used by the body of the function.

For example, in the following function, `z` is a dummy argument but `x` and `y` are not.

```
int f(int x, int y, int z) {
  return (x + y);
}

```

They can be used for several reasons:

* depending on another argument or some configuration, the argument will be used (not dummy) and sometimes it won't (dummy) but the programming setting imposes to pass an argument anyway. In that case, you can usually pass anything to the function, i.e. `NULL` or `0`, depending on the setting;
* the argument is no more needed, but you have to give one for backward compatibility reasons;
* the function does not take any argument (it can be called a procedure) but the setting imposes to give at least an argument. You can find this in unpure functional programming languages but in general it is not called "dummy" because the type (`unit` in ocaml) suggests it.

## "Dummy" in Fortran and Pascal

In Fortran and Pascal, and probably in your case, there is a more obscure notion of passed-object dummy argument that I have failed to comprehend. But it seems to concerns more the specification than the actual argument-passing procedure. (Some explanations: link 1 with both languages, link 2 in French).

I don't know if this notion is still used.

## "Dummy" as "bound"

I would not advise this terminology in any case, but "dummy variable" can mean "bound variable" but this notion is more of a math and computer science thing.
> 16 votes

# Answer
A function is a well defined as: relation between a set of inputs and a set of permissible outputs. A dummy variable would be any input that had no effect on the output.

In "C" the time function takes a pointer to a time\_t object as input. As this pointer is only used to get output it could be considered a "dummy variable".
> 3 votes

# Answer
A dummy argument is actually an argument in a function which is not been used in the function but rather it is substituted in the function expression when it is referenced
> 1 votes

---
Tags: terminology, programming-languages, functional-programming
---


title: Converting this NFA to Turing Machine

text:
# Question
Title: Converting this NFA to Turing Machine
I'm asked to choose a DFA and convert it to NFA and then convert it to Turing machine... I have done the first two parts as follows:

# DFA:

# --\> NFA:

# --\> Turing machine:

# ???

I haven't found any explanation/tutorial on how to do this. So, a final solution containing a state diagram with an explanation on what steps were followed would be great.

# Answer
A DFA is simply a Turing machine that moves the head to the right on every transition until it reaches the first blank tape cell.

Thanks to Ryan for a comment that clarified this answer.
> 5 votes

---
Tags: turing-machines, finite-automata, nondeterminism, simulation
---


title: Transitions triggered by sets of events

text:
# Question
Title: Transitions triggered by sets of events
In automata theory books, I always studied examples where a state transition from A to B occurs due to a single event $e$ (say, receiving a particular character). Is it theoretically possible that a transition could be triggered by a set of events, such as receiving any one of some set of characters?

# Answer
Technically, a transition has to be an atomic event (in the context of formal languages, the reading of a *symbol*). That said, there are two situations in which you could imagine something different:

1) You could use a set of symbols as an *abbreviation* of multiple alternative transitions from one state to the other, or a string of symbols as an abbreviation of a sequence of transitions that happen one after the other. In fact, a number of different abbreviations are commonly used when dealing with finite automata on practical situations.

2) You could have a language whose symbols have an internal structure (for instance, they are encodings of sets). Of course, this internal structure should be transparent to the formal treatment of the language.

As with any alternative representation of a formal expression, these variations should be used when their understanding is clear, from definition, or context.
> 2 votes

# Answer
Yes, it's perfectly possible to have a transition triggered by a set of events. There's no real difference between saying that the automaton moves from state $A$ to state $B$ when it receives one of the characters $\\{x,y,z\\}$ and saying that it moves from $A$ to $B$ when it receives $x$, and it moves from $A$ to $B$ when it receives $y$ and it moves from $A$ to $B$ when it receives $z$.

Indeed, the state removal method converting a DFA to a regular expression involves as intermediate stages, objects that are essentially DFAs but where the transitions are triggered by any string that matches a particular regular expression. (Could somebody remind me what such automata are called?)
> 1 votes

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


# Question
Title: Would it be possible to use the cloud for RAM?
I'm not sure if this is the right place to ask but I had this idea. Since the cloud can be used for storing memory, would it be possible to use it for RAM too?

# Answer
Network latency is orders of magnitude too high for a remote server to usefully share its RAM directly, even if you could cobble together a virtualization layer to make it work. However, today's network speeds are high enough that remote RAM based key/value stores like memcached can compete favorably with hammering a local database due to insufficient local memory for caching.

Since this question has the virtual-memory tag, I'll also point out that network servers (which is what "cloud computing" is the latest name for) have been used for virtual memory (also known as "swap") since the diskless workstations of the late 1980's. These machines are called "thin clients" today.
> 8 votes

---
Tags: virtual-memory, memory-access, memory-allocation
---


# Question
Title: Computer Programs and lambda terms without normal form
λ-calculus an ideal mathematical model in which to interpret programs. A program can be interpreted as a lambda term, and the term can have or not have a normal form. What role the terms without normal form play when analyzing programs?

# Answer
> 4 votes
A troublesome one unfortunately. When one goes to examine programs there are two main ways to do it

1. Operationally

This is the sort of obvious approach to analysing a program in the lambda calculus. We give a set of rules for what it means for one program to step to another and then go on to prove things about programs stepping. Here a step is one small tweak to the program. We continue to step until we end up at a value at which point no more steps are applicable. A value in the lambda calculus is just a lambda term.

Now the obvious impact of nontermination is that for any term there is no guarantee that there is a finite number of steps leading it to a value. We can prove useful theorems like "Either a term is a value or there is an applicable step" (a form of type safety) and "A term can only step to at most one unique value" (a corollary of the Church Rosser Theorem). These are all still useful results that justify statements like "there are unequal lambda terms".

2. Denotationally

Here we're trying to understand the lambda calculus by mapping each term to a particular mathematical object so that the mapping is coherent in some way. Mostly we want it so that $denote(e) = denote(e')$ if and only if $e = e'$. With this theorem in hand we can go on and prove things in the denotation equal and actually generate useful theorems about the lambda calculus.

Here nontermination causes some real pain. We can't just treat lambdas as "normal" math functions because normal math functions terminate. Instead we explicitly model nontermination by dedicating a specific element in our mathematical collection as what nonterminating programs denote to. Then we go on and prove a theorem along the lines that if $denote(e)$ gives that nonterminating object, then $e$ doesn't run to a value (runs to in the sense of operational semantics).

However the lambda calculus is a pain to denote for a much more fundamental reason though: recursion. The nontermination in the lambda calculus emanates from the fact that the lambda calculus is built on top of this sort of cyclical definition: a lambda term is a function from $A \to A$ where $A = A \to A$. This recursive definition gives us self-application eg $\lambda x. x\ x$ which gives us nontermination.

Building a denotation involves building a collection where $$A \cong A \to A$$ which is just absurd if $A$ is a set and $A \to A$ is the normal collection of set-theoretic functions!

Indeed proving that such an $A$ exists was the impetus for a large field in programming language semantics called "domain theory". Dana Scott constructed such an $A$ by cleverly defining $A$ with an ordering relation on it and restricting functions to be continuous with respect to that ordering operation. Even with this the proof is very technical (and cool).

---
Tags: terminology, lambda-calculus, computation-models
---


# Question
Title: Fit stack of stone of varying length into a well of varying length
I have a stack of m stones of different Diameter.

```
stack = [5,4,9,20,1]

```

And a Well that is of depth n with varying diameter at different depths .

```
wellDiameters = [7,9,1,25,6,7]

```

EDIT:

Only one stone from the top of stack can be taken and after placing that we can take the next stone.

Each level can fit only one stone.

Now I need to make an algo to find the number of maximum stones I can place in well. Now I can place 5 in diameter 9 and then 4 on top of it as diameter 5 stone can not get fit into 1.

So the answer is 2

The algo I used is brute-force and hence its order O(m\*n).

```
count=0
filledIndex =len(wellDiameters)
for stoneDia in stack
     for wellDia in wellDiameters
         if index (wellDia) > filledIndex
            break
         if stoneDia < wellDia
            continue
         else
            count +=1
            filledIndex = index (wellDia) -1

```

I need to know if there are any faster way to get the count.

# Answer
This can be done in $O(n\log(n))$ time (I am assuming they are the same length since, if one is longer, you just treat it like it is only its first $n$ elements, where $n$ is the length of the shorter array). Here is a hint --

First, you should preprocess the well diamater array to make it easier to check a stack of stones against.

Then, you should binary search for how large of a stack you can fit.

I can edit my response to include a more detailed answer if you would like, but I don't want to spoil the problem as you only asked if there were a faster way.
> 0 votes

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


# Question
Title: Quadratic Diophantine equation - Polynomial Time Cases
In number theory, solving a Quadratic Diophantine equation (a, b, c constants) $$ a\*x^2+b\*y= c $$ is an NP-Complete problem. Even for a=1, the problem remains NP-Complete.

The solution (x, y) are positive integers.

Query: What are the conditions on values of constants for which solving the problem is Polynomially feasible? Any link to the references?

# Answer
> 1 votes
You shouldn't expect a complete characterization of all parameters that can be solved in polynomial time, but here are two cases where it can be solved in polynomial time:

If $b$ is prime, you can solve this in polynomial time by letting $x = \sqrt{c/a} \pmod{b}$ and then $y=(c-ax^2)/b$. You can compute modular square roots in polynomial time by standard methods.

If $b$ has known factorization, similar methods can be used (use the Chinese remainder theorem).

Dealing with the requirements $x\ge 0,y \ge 0$ (which were added to the question after I wrote this answer) is more challenging. When $b$ is prime, you can enumerate both modular square roots and see if either of them leads to a valid solution. When $b$ is not prime but has known factorization, in the worst case this might require enumerating exponentially many modular square roots (though you might be able to randomly sample a few square roots and hope that at least one will lead to a positive solution).

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


# Question
Title: Assignment to make formula unsatisfiable
Lets imagine we have a satisfiable formula $F(A\_0, A\_1,...A\_k,S\_0,...,S\_n)$ The problem to solve is "Is there an assignment for variables $(S\_0,...,S\_n)$ which will make F unsatisfiable?". One way of solving is to find all solutions for F in terms of variables $S\_0,...,S\_n$ and if the count is \< $2^n$, the missing solution will be the answer, but the complexity of this algorithm is huge, if the number of such assignments is small.

My questions are:

* Is there a way to solve the problem with less SAT solver calls?
* Is it a well-known problem in theory (What I should google to read about it)?

# Answer
> 6 votes
Your problem is the canonical $\Sigma\_2^P$-complete problem: $$ \exists \vec{S} \forall \vec{A} \lnot F(\vec{A},\vec{S}). $$ As such, it is thought to be more difficult than SAT (which is $\Sigma\_1^P$). Solving it with a few SAT-oracle calls is akin to solving SAT itself efficiently (the P vs. NP question), though it could be that $\Sigma\_2^P = \Sigma\_1^P$ while $P \neq NP$, so in some sense there is more hope for your problem than for SAT itself.

# Answer
> 4 votes
This is a well-known problem: it is the 2QBF problem. Unfortunately, it's significantly harder than SAT. There are QBF solvers available. You could try finding a QBF solver (or, even better yet, a 2QBF solver) and seeing if it can solve your formula. However, QBF solvers don't scale as well as SAT solvers; QBF is significantly harder than SAT.

See https://cstheory.stackexchange.com/q/11022/5038 and http://www.qbflib.org/ for some resources that might be helpful.

---
Tags: logic, satisfiability, sat-solvers
---


# Question
Title: Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement?
When talking about turing machines, it can be easily shown that starting from two machines accepting $L$ and its complement $L^c$, one can build a machine which can fully decide if a word is inside $L$ or not.

But what about PDAs? starting from two different PDAs, one accepting $L$ and one accepting $L^c$ can we build another PDA, which accepts $L$, and only crashes or halts in non-final states (rejects) when $w\notin L$?

# Answer
> 3 votes
Yes, it is possible to do so. Although a given PDA may have $\varepsilon$ loops that can induce infinite computation, we can sidestep this by converting the PDA to a CFG, then back to a PDA (using the standard methods). The second PDA is guaranteed to halt on all inputs (this is not too hard to see if you know the conversion method - essentially you guarantee that either a non-terminal from the CFG is added to the stack, or a terminal is read from the input at each broad step and the nondeterminism takes care of the rest, or equivalently, CFGs can always be parsed).

So then we can take the PDA for $L$, apply this transition, and we get a machine that always halts, and only halts in an accept state if the input is in $L$.

# Answer
> -1 votes
DPDA class is close under complement.

if you have a PDA for $L$ and an other one for $L^c$ then $L \in \\{ L\subset \Sigma | \quad \exists DPDA\quad \text{ such that} L=L(DPDA)\\} $ so you can make a non-deterministic decider for L.

---

After Edit:

@Ali.S: It seems you are right. Although it’s difficult for me to make a PDA for $L- WW^R$.

But again I think it’s possible to have non-deterministic decider!

Let $M\_1$ be a non-deterministic acceptor for $L$ and $M\_2$ be a nondeterministic acceptor for $L^c$. $\forall w \in L^c$ , $M\_2$’s answer is “Yes” and it means $\forall w \notin L$ , $ M\_2$ will halt. We can construct a non-deterministic decider as follows:

Put a new initial state and add two lambda transition from it to $ M\_1$ and $ M\_2$ initial states. Wherever in $M\_2$ we have “Yes” we change it to “No” and if it has “No” answer we stuck in loop. Wherever in $M\_1$ we have “yes” it is what we wanted and if it has “No” answer we stuck in a loop.

By this way if $w \in L$ if PDA decide to goes $M\_1$ initial state and continue it will get answer "Yes" and halts. if it chooses to start by $M\_2$ initial state and continues it won't get answer "No". if $w \notin L$ and PDA choose to goes in $M\_1$ if will get stuck in loop and if it goes in $M\_2$ it will get answer "No" and halt.

---
Tags: context-free, pushdown-automata, nondeterminism
---


# Question
Title: Find the 10 top most occurring strings in a huge array of objects
Find the 10 top most occurring strings in a huge array of Strings.

Since the array is huge, it is not possible to load it in memory completely. My idea is to parse the arrays one by one and put the strings in a hash table with string as key and occurrence count as value. But this would take too much memory.

Is there any other optimized solution? Given that we only care about top 10 keys.

# Answer
One optimized way is a streaming algorithm given by Charikar, Chen and Farach-Colton, known as *CountSketch*. See

It takes logarithmic space (in the size of your input), and gives an approximation for the $k$ most-frequent elements in that input. $k$ is an input parameter, that also affects the memory in use.

There are also extensions for sliding windows algorithms, and to other ways of measuring which element is considered "frequent".
> 1 votes

---
Tags: algorithms, space-complexity, streaming-algorithm
---


# Question
Title: the name of state when data reading from hard drive
In computer organization and architecture, what is the name of the state when data must be read from hard drive? I have tried to search it on StackOverflow and textbooks but could not find the answer.

# Answer
Do you mean "page fault" ? That is when a virtual page has to be loaded from the disk, because it is not in RAM and has to beaccessed. Actually page fault is the name of an interrupt that is caused by that situation, and will lead to the loading of the needed page.
> 1 votes

---
Tags: terminology, computer-architecture, operating-systems
---


# Question
Title: Dijkstras Shortest Path with Distance and Quality
I want to write up a shortest as well as optimal path program for indoor navigation for people with disabilities. For the initial part of the assignment i wish to test my program through graph traversal. My application is supposed to take in a user group then based on that give the appropriate path. The edges are supposed to have 2 values. One for distance and one for quality. I.e distance for path and quality could be set as is it wheelchair accessible or not.

Want program to take in graph with 2 values for edge (weight, quality). Remove all paths going through stairs immediately. Regardless of the distance of going through stairs. Then i want program to check the shortest path among the wheelchair accessible path to see if any is available or not. I want a quality value of 1 for accessible and 2 for inaccessible. So if there is a long path going through an elevator with quality 1 then that path should be taken otherwise the shortest path with quality 1 should be displayed. All edges as W are elevators and S are stairs

What I want in the code is this. A graph which has 2 things defined on its edge (weight, quality) new Graph.Edge("b", "e", 4,1),

Weight could be for the distance but the quality decides the optimal route. I.e. if this is the easiest way to reach there even though it is short. All nodes indicating W indicate elevators. All nodes S are stairs. What I want the code to do is build the map using both defined edges (dist, qual) Then I want all routes going through stairs removed. (The reason they are there is because later on I need this to accommodate abled people too so the program would work in different user groups) Right now I am only bothered with the wheelchair accessibility.

This is how the program should go: Remove all stair nodes from being browsed through. Find shortest path to destination going through elevator (W) only Compare that path to the second value quality- new Graph.Edge("b", "e", 4,1), If the quality is = 1 then that is the optimal path to take is ok. If the quality is = 2 then give the longer path instead. If there are 2 paths with the same weight then obviously give the path with quality =1 If both have quality = 1 then just give the one going through least nodes.'

The below code that i have gives a shortest distance using only the distance value and now i am trying to modify that to suit the above criteria but have no idea how to go about it.

```
   import java.util.HashMap;
   import java.util.Map;
   import java.util.NavigableSet;
   import java.util.TreeSet;

public class Dijkstra {

private static final Graph.Edge[] GRAPH = {
      new Graph.Edge("a", "b", 2,1),
      new Graph.Edge("a", "w", 5,1),
      new Graph.Edge("a", "e", 5,2),
      new Graph.Edge("a", "d", 7,1),
      new Graph.Edge("a", "s", 6,1),
      new Graph.Edge("b", "c", 3,1),
      new Graph.Edge("b", "e", 4,1),
      new Graph.Edge("b", "w", 3,2),
      new Graph.Edge("b", "s", 4,2),
      new Graph.Edge("b", "d", 6,1),
      new Graph.Edge("c", "e", 4,1),
      new Graph.Edge("c", "w", 1,1),
      new Graph.Edge("w", "c", 1,1),
      new Graph.Edge("c", "s", 2,2),
      new Graph.Edge("c", "d", 3,1),
      new Graph.Edge("d", "w", 2,2),
      new Graph.Edge("d", "s", 1,1),
      new Graph.Edge("d", "e", 3,1),
      new Graph.Edge("e", "w", 4,2),
      new Graph.Edge("e", "s", 5,1),
      new Graph.Edge("w", "h", 5,1),
      new Graph.Edge("h", "w", 5,2),
      new Graph.Edge("s", "h", 1,1),
      new Graph.Edge("h", "i", 10,1),
      new Graph.Edge("i", "h", 10,1),
      new Graph.Edge("i", "g", 5,1),
      new Graph.Edge("h", "g", 11,1),
      new Graph.Edge("h", "j", 12,1),
      new Graph.Edge("i", "j", 3,1),
      new Graph.Edge("g", "j", 2,2),

   };
   private static final String START = "d";
   private static final String END = "h";

   public static void main(String[] args) {
      Graph g = new Graph(GRAPH);
      g.dijkstra(START);
      g.printPath(END);
      //g.printAllPaths();
   }
}

class Graph {
   private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges

   /** One edge of the graph (only used by Graph constructor) */
   public static class Edge {
      public final String v1, v2;
      public final int dist;
      private int qual;
      public Edge(String v1, String v2, int dist, int qual) {
         this.v1 = v1;
         this.v2 = v2;
         this.dist = dist;
         this.qual = qual;
      }
   }

   /** One vertex of the graph, complete with mappings to neighbouring vertices */
   public static class Vertex implements Comparable<Vertex> {
      public final String name;
      public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity
      private Object qual;
      public Vertex previous = null;
      public final Map<Vertex, Integer> neighbours = new HashMap<>();

      public Vertex(String name) {
         this.name = name;
      }

      private void printPath() {
         if (this == this.previous) {
            System.out.printf("%s", this.name);

         } else if (this.previous == null) {
            System.out.printf("%s(unreached)", this.name);
         } else {
            this.previous.printPath();
            System.out.printf(" -> %s(%d)", this.name, this.dist, this.qual);
         }
      }

      @override
      public int compareTo(Vertex other) {
         return Integer.compare(dist, other.dist);
      }
   }

   /** Builds a graph from a set of edges */
   public Graph(Edge[] edges) {
      graph = new HashMap<>(edges.length);

      //one pass to find all vertices
      for (Edge e : edges) {
         if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1));
         if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2));
      }

      //another pass to set neighbouring vertices
      for (Edge e : edges) {
         graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist);
        // graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph

      }
   }

   /** Runs dijkstra using a specified source vertex */
   public void dijkstra(String startName) {
      if (!graph.containsKey(startName)) {
         System.err.printf("Graph doesn't contain start vertex \"%s\"\n", startName);
         return;
      }
      final Vertex source = graph.get(startName);
      NavigableSet<Vertex> q = new TreeSet<>();

      // set-up vertices
      for (Vertex v : graph.values()) {
         v.previous = v == source ? source : null;
         v.dist = v == source ? 0 : Integer.MAX_VALUE;
         q.add(v);
      }

      dijkstra(q);
   }

   /** Implementation of dijkstra's algorithm using a binary heap. */
   private void dijkstra(final NavigableSet<Vertex> q) {
      Vertex u, v;
      while (!q.isEmpty()) {

         u = q.pollFirst(); // vertex with shortest distance (first iteration will return source)
         if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable

         //look at distances to each neighbour
         for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) {
            v = a.getKey(); //the neighbour in this iteration

            final int alternateDist = u.dist + a.getValue();
            if (alternateDist < v.dist ) { // shorter path to neighbour found
               q.remove(v);
               v.dist = alternateDist;
               v.previous = u;
               q.add(v);
            }
         }
      }
   }

   /** Prints a path from the source to the specified vertex */
   public void printPath(String endName) {
      if (!graph.containsKey(endName)) {
         System.err.printf("Graph doesn't contain end vertex \"%s\"\n", endName);
         return;
      }

      graph.get(endName).printPath();
      System.out.println();
   }
   /** Prints the path from the source to every vertex (output order is not guaranteed) */
   public void printAllPaths() {
      for (Vertex v : graph.values()) {
         v.printPath();
         System.out.println();
      }
   }

```

}

# Answer
> 3 votes
What you may want is the use a "metric" on a pair of values, such that one value always has precedence over the other. In this way, you actually consider any length of stairs to be worse than any path without stairs, but you can discriminate also on the length of stairways.

The way you do this is to mesure a distance as a pair $\[w,c\]$, where $w$ stands for *walk* and $c$ stands for *climb*. The value $w$ can be a distance in meters, and the value of $c$ can be the number of steps to climb, or any other measure of inaccessibility. This is the same as weight and quality suggested by the question, but it seems a terminology closer to the problem at hand.

Then you define:

* $\[w,c\] \< \[w',c'\]\\;\\;$ iff $\\;\\;c\<c' \\;\vee\\; (c=c' \wedge w\<w')$, which is just lexicographic order on pairs of values.
* $\[w,c\] + \[w',c'\] = \[ w+w', c+c'\]$

Then you can just use the pairs as measure of distance in Dijkstra's algorithm, to get the most convenient path.

If you do not want to distinguish degrees of inaccessibility, you can take the value of $c$ in the set $\\{0,1\\}$, with $1+1=1$ for the $c$ component of the pair, which is the same as using a boolean value.

There are other variations, depending on what you want to take into account, and how. For example, you might consider that all stairs are equivalent, independently of the number of steps. Or that some stairs are more difficult for the same number of steps.

There is a coding trick that you can also use, if you know that you will never exceed a given walking distance $D$ on any path that you ever follow. Then you can encode $w,c$ as $w+cD$ and use that as distance. But the computational gain is probably not worth it, and it could lead you to bugging your algorithm as it evolves.

---
Tags: graphs
---


title: Why Turing wasn't wrong?

text:
# Question
Title: Why Turing wasn't wrong?
Computer science is a science and as a science each thesis can be refutable. So, why there is no "major" counter-thesis? After all, Einstein was a well known "genius" and has lived a long life and he has got many opponents. Why isn't it the same case for Turing?

# Answer
Computer science is a science only by name. In practice, it is a blend of engineering, mathematics, and empirical science.

With that out of the way, here are a few comments about the Church–Turing thesis. **First**, about the thesis itself. We can think of at least three interpretations of the Church–Turing thesis. Under the first, stronger interpretation, any computation that can be done in the physical world can be modelled by (say) a Turing machine. This is a thesis which indeed can be refuted, and people have tried to refute it, though so far unsuccessfully (Scott Aaronson suggests to regard this as a "law of nature").

The second, weaker interpretation only claims that any computation *done in practice* (now) can be modelled by a Turing machine. This thesis is essentially correct, though to make it truly correct you need to make it mathematically precise; Nachum Dershowitz and Yuri Gurevich have done just that, though their formulation doesn't necessarily reflect the intuitive content of the thesis.

The third interpretation, very related to the second, is that any pseudocode that we can describe can be implemented on a Turing machine. We use this thesis implicitly whenever we describe and analyze algorithms, both in very theoretical areas (recursion theory, computational complexity, theoretical algorithms and data structures, approximation algorithms) and in more applied areas, in which the pseudocode is often translated to code in practice.

**Second**, in practice the more interesting thesis is what is sometimes called the Cook–Karp thesis. This thesis states that the class $\mathsf{P}$ embodies all decision problems that can be solved efficiently in practice. In my view, this thesis is dubious. There are three main attacks on this thesis.

The first attack is that the class $\mathsf{P}$ is defined asymptotically, whereas we are interested in problems of finite size. It could be that for practical input size, a problem which is perhaps not in $\mathsf{P}$ can be solved efficiently (for example, small cryptosystems can be broken even if they are secure). Conversely, it could be that a problem is in $\mathsf{P}$ but it cannot be solved efficiently, since the polynomial time "kicks in" only for large problems.

This is very related to the second attack, which is that polynomial time algorithms need not be efficient: they could have a large (big O) constant or a large exponent. A good example for a large constant is fast matrix multiplication algorithms, which are not practical due to the large constant. A good example for a large exponent is deterministic primality testing (the AKS algorithm), which isn't practical due to the large exponent.

A third attack, which is more speculative at this point, is that quantum computers can efficiently solve some problems which we think classical computers cannot. While quantum computers still exist only on paper, unless we believe that there is some fundamental obstacle to constructing them (as some people indeed do, for example Gil Kalai), we have to contend that in the future the class $\mathsf{P}$ would have to be enlarged to the corresponding quantum class $\mathsf{BQP}$.

A related attack states that randomized algorithms can be stronger than deterministic ones: for example randomizes primality testing is practical while the AKS algorithm isn't. However, it is believed that "randomness doesn't help", in the sense that $\mathsf{P}=\mathsf{BPP}$ (which doesn't mean that randomized algorithms can't be faster; it only means that they can only be polynomially faster).
> 9 votes

---
Tags: church-turing-thesis
---


title: Binary tree node value maximization

text:
# Question
Title: Binary tree node value maximization
Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be included.

My intuition tells me dynamic programming (and possibly two-coloring) should be involved, but not sure where to start. Could you please offer me a hint?

# Answer
> 2 votes
This problem is known as Independent Set (and not two-coloring). Your intuition is quite correct though.

As a hint, I'd like to offer the following definitions:

Let $n$ be a node of the binary tree. Let $P(n)$ be the maximum profit that can be attained from the subtree rooted at $n$ given that $n$ itself may *not* be included. Similarly, let $Q(n)$ be the maximum profit that can be attained from the subtree rooted at $n$ given that $n$ itself may be included.

---
Tags: graphs, search-algorithms, dynamic-programming, binary-trees
---


title: About a particular use of hashing

text:
# Question
Title: About a particular use of hashing
Look at the last problem on page 2 here, http://www.cs.nyu.edu/~khot/CSCI-GA.3350-001-2014/sol3.pdf

* All one wants to do is to convert a $x \in \\{ 0,1\\}^n$ into a $y \in \\{0,1\\}^k$ . Then just a linear transformation would have been enough. Why install this vector "b"?
* If $a\_1,x\_1,x\_2 \in \\{0,1\\}^n$ and $b\_1,y\_1,y\_2 \in \\{0,1\\}$ then why is demanding simultaneous satisfaction of the equations $a\_1^Tx\_1 + b\_1 = y\_1, a\_1^Tx\_2 + b\_1 = y\_2$ the same as claiming the simultaneous satisfaction of the equations, $a\_1^T(x\_1 \oplus x\_2) = y, b\_1 = y \oplus y\_1$ ?( where $y = y\_1 \oplus y\_2$)

# Answer
> 2 votes
For your first question, the vector $b$ is necessary to make sure $\text{Pr}\_{A,b}\[\vec{a\_1} x^{T} + b\_1 = y\] = 1/2$, for $k = 1$.

Otherwise, it is easy to see that $\text{Pr}\_{A,b}\[\vec{a\_1} x^{T} = 0\] = 3/4$ and $\text{Pr}\_{A,b}\[\vec{a\_1} x^{T} = 1\] = 1/4$, for $n=1$. By conditional probability and the law of total probability, we can get $\text{Pr}\_{A,b}\[\vec{a\_1} x^{T} = 0\] = 5/8$ and $\text{Pr}\_{A,b}\[\vec{a\_1} x^{T} = 1\] = 3/8$, for $n=2$. This approach can be generalized to arbitrary $n$.

# Answer
> 1 votes
For your second question: it's not equivalent. $a\_1^T x\_1 + b\_1 = y\_1$, $a\_1^T x\_2 + b\_1 = y\_2$ is equivalent to $a\_1^T(x\_1 + x\_2) = y\_1 + y\_2$, $b\_1 = a\_1^T x\_1 + y\_1$.

Why? Well, if you subtract the two given equations from each other, you get $a\_1^T x\_1 - a\_1^T x\_2 = y\_1 - y\_2$. If you now use the fact that subtraction is the same as addition when working modulo 2, then you get $a\_1^T(x\_1 + x\_2) = y\_1 + y\_2$. Also the equation about $b\_1$ follows by simple manipulation of the first equation.

Conversely, if you know $a\_1^T(x\_1 + x\_2) = y\_1 + y\_2$ and $a\_1^T(x\_1 + x\_2) = y\_1 + y\_2$, then through similar algebraic manipulations you can conclude $a\_1^T x\_1 + b\_1 = y\_1,$ $a\_1^T x\_2 + b\_1 = y\_2$.

---
Tags: complexity-theory, hash
---


# Question
Title: If the decision problem can be solved in poly time, show the optimization problem also can
Here is a problem I am trying to solve:

> The bin packing decision problem is defined as follows: given an unlimited number of bins, each of capacity equal to $1$, and $n$ objects with sizes $s\_1$, $s\_2$, $\dots$, $s\_n$ ($0 \< s\_i ≤ 1$), do the objects fit in $k$ bins (where $k$ is a given integer)? The bin packing optimization problem is to find the smallest number of bins into which the objects can be packed. Show that if the decision problem can be solved in polynomial time, then the optimization problem can also be solved in polynomial time.

I know what it is asking but I don't know what the "optimization" problem for this is. Is it the grouping of all the objects into different bins (for instance, $s\_1$, $s\_3$, and $s\_6$ are in bin #$1$, $s\_2$, $s\_4$, $s\_5$ are in bin #$2$, etc.)? Or is it simply the number of bins you need to store them? I feel like the number of bins is the decision problem...

# Answer
In the decision problem, $k$ is given, so the answer is yes, or no (a **decision**). In the optimization problem $k$ is unknown, and we have to find out how small can it be (the **optimal** solution). The bigger question asks if there is a logical connection between possible solutions to these two problems, such that the complexity of the respective algorithms is corelated.
> 2 votes

---
Tags: np-complete, optimization, decision-problem, np
---


# Question
Title: Denotational semantics of expressions with side effects
I'm doing revision for a module on programming language semantics and I'm having trouble understanding the introduction of side-effects in expressions.

We assume a standard syntax for arithmetic expression, with the four usual operations, plus the unary prefix and postfix operator $\texttt{++}$, defined as in language C, applicable to variables only as in $\texttt{V++}$, and assigment statement $\texttt{V:=E}$.

We have seen how to define the denotation function $\[\\!\[\texttt{E}\]\\!\]\_{\mathrm{Exp}}$ when we have to evaluate an expression $\texttt{E}$ without side-effect, to return a value resulting from that evaluation.

In order to give a denotational semantics for expressions with side-effects, we need to change the type of the denotation function $\[\\!\[\texttt{E}\]\\!\]\_{\mathrm{Exp}}$ for expressions $\texttt{E}$, so that it returns both the value of the expression and the state as modified by the side-effects. I.e., we want to define a denotation function

$\[\\!\[\texttt{E}\]\\!\]\_{\mathrm{Exp}} : State → Int×State$

by induction on the form of expressions $\texttt{E}$. For example, in the case $\texttt{E}$ has the form $\texttt{E1+E2}$, we define:

$\[\\!\[\texttt{E1+E2}\]\\!\]\_{\mathrm{Exp}}(S) = (n\_1 + n\_2, S\_2)$

where $(n\_1, S\_1) = \[\\!\[\texttt{E1}\]\\!\]\_{\mathrm{Exp}}(S)$

and $(n\_2, S\_2) = \[\\!\[\texttt{E2}\]\\!\]\_{\mathrm{Exp}}(S\_1)$

This says first evaluate the leftmost expression $\texttt{E1}$, giving the integer value $n\_1$ and updated state $S\_1$, then evaluate $\texttt{E2}$ in that updated state, giving the integer value $n\_2$ and updated state $S\_2$; the value of the expression is $n\_1 + n\_2$, and evaluation has the side effect of updating the state to $S\_2$.

However this does not show when side effects actually take place, and I do not know how to write the denotation function for expressions that do produce side-effects. Can you tell me how to complete the inductive definition of $\[\\!\[\texttt{E}\]\\!\]\_{\mathrm{Exp}}$, including the case where $\texttt{E}$ is of the form $\texttt{V++}$?

Then, how should one change the definition of the denotation function $\[\\!\[\texttt{V:=E}\]\\!\]\_{\mathrm{Pgm}}$ for the assignment statement, to take account of the changes in the definition of $\[\\!\[\texttt{E}\]\\!\]\_{\mathrm{Exp}}$, which it necessarily uses?

Are there other changes that would need to be made to the denotational semantics of the language?

# Answer
> 5 votes
Since the question does not fully describe the language, I assume the simpler case when the $\texttt{++}$ operator applies only to variables given by an identifier, for example: $\texttt{foo++}$. Short of having more examples of the way you write denotational semantic, I have to improvise a bit. In particular, I avoid lambda notation since I do not know whether you are using it, but I would prefer using it.

Other arithmetic binary operators (substraction, multiplication) are similar to the $\texttt{E1+E2}$ case described in the question, and are explained similarly.

The simplest case is that of an expression which is only a lone variable $\texttt V$:

$\[\\!\[\texttt{V}\]\\!\]\_\mathrm{Exp}(S)= (S(\texttt V), S)$

What it says is to get the value $S(\texttt V)$ associated to the variable $\texttt V$ in the state $S$ and to return that value, of course, but associated with the state $S$ unchanged, since the type of the denotation function requires such a pair as result.

Then we complement as follow for the prefix and postfix $\texttt{++}$ operator the definition of the semantic function $Exp$ for expression $\texttt E$, when $\texttt E$ has the form $\texttt{V++}$ or $\texttt{++V}$, i.e., when it is a variable.

$\[\\!\[\texttt{V++}\]\\!\]\_\mathrm{Exp}(S)= (S(\texttt V), S1)$
where $S1(v\_1)=\\;\\; \text{ if } v\_1=\texttt V \\;\text{ then } S(\texttt V)+1 \\;\text{ else } S(v1)$

The value returned is the same as in the case of the variable $\texttt V$ alone. However, the state $S$ has to be changed to a new state $S1$ where the value corresponding to $\texttt V$ is incremented by $1$, the rest of the state being unchanged.

$\[\\!\[\texttt{++V}\]\\!\]\_\mathrm{Exp}(S)= (S(\texttt V)+1, S1)$
where $S1(v\_1)=\\;\\;\text{ if }v\_1=\texttt V \\;\text{ then }S(\texttt V)+1\\;\text{ else }S(v\_1)$

This case is identical to the previous one, except for the fact that the value returned is also incremented by one, i.e. is the value provided by the state $S$ for $\texttt V$, but incremented by $1$. But the state $S1$ returned is the same as in the previous case.

For the assignment statement, it would be easier if the question included the definition of $\[\\!\[\texttt{V:=E}\]\\!\]\_\mathrm{Pgm}$ that is supposed to be modified. I am guessing, trying to be in accordance with what little information you give.

I suppose the result should be something like:

$\mathrm{\[\\!\[\texttt P\]\\!\]\_{Pgm} : State \to State}$

$\[\\!\[\texttt{V:=E}\]\\!\]\_\mathrm{Pgm}(S)= S2$
where $S2(v\_1)=\\;\\; \text{ if } v\_1=\texttt V \\;\text{ then } n \\;\text{ else } S1(v\_1)$
and $(n,S1)= \[\\!\[\texttt E\]\\!\]\_\mathrm{Exp}(S)$

What this says in the first line is that the denotation of a statement is a function that takes a state as argument, and returns another state. The role of a statement is to modify the state.

Then the denotation function for the assignment statement $\texttt{V:=E}$ will first evaluate the expression $\texttt E$ in the environment $S$ provided as argument. This returns a value $n$ and a new environment $S1$ which may be different from $S$ if there have been side-effects while evaluating $\texttt E$. Then this environment $S1$ is modified into an environment $S2$ which associate the value $n$ to the variable $\texttt V$, and is otherwise identical to $S1$. This environment $S2$ is the one produced by execution of the assignment statement.

Other changes are probably necessary to fully account for side-effects in the language. But I cannot know exactly what because the question does not provide enough details about other language features. There are many ways to write denotational semantics, and it depends on the whole of the language and the way features interact.

The version given above is a bit simplified, assuming that $\texttt V$ is the actual variable name. I chose this simpler version because you do not provide examples of denotational semantics without side-effects, and I was not sure what presentation to choose. But there are other ways to present that.

---
Tags: programming-languages, semantics, imperative-programming, denotational-semantics
---


# Question
Title: Is the language $\{f(x)\mid \mbox{$x$ is the code of a machine accepting $f(x)$}\}$ recursively enumerable and undecidable?
This is text of an exercise I am working on:

Given a binary encoding scheme for the set of the deterministic Turing machines with alphabet $\\{0,1\\}$ and a bijective and computable function $f: \\{0,1\\}^\* \rightarrow \\{0,1\\}^\*$, prove that the language $$L=\\{f(x)\mid \mbox{$x$ is an encoding of a machine that accepts $f(x)$}\\}$$ is recursively enumerable and undecidable.

I don't know how to prove it, and I don't know where to start.

# Answer
Let $L\_f = \\{f(x)\mid x \text{ is the encoding of a TM }X\land X\text{ accepts }f(x)\\}$

We'll make use of a

**Lemma**. If $f:\\{0, 1\\}^\*\rightarrow \\{0, 1\\}^\*$ is a computable bijection, then so is $f^{-1}$.

*Proof hint*. Obviously, $f^{-1}$ is a bijection, since $f$ is. Then use dovetailing to construct a TM that for any input string $y$ returns the (unique) $x$ for which $f(x)=y$.

---

**I. $L\_f$ is r.e.**.

Construct a recognizer $R$ that will accept all and only strings $y\in L\_f$ as follows

```
R(y) =
   compute x such that f(x) = y     // using the Lemma above
   if x is the encoding of a TM, X  // obviously possible to check
      simulate X on input y         // obviously can do this, too
      if X accepts y
         return accept

```

**II. $L\_f$ is undecidible**.

Suppose, to the contrary, that there was a decider $D\_f$ for $L\_f$. Define another (decider) TM, $E\_f$, to do the "opposite" of $D\_f$, i.e., $E\_f$ accepts a string if $D\_f$ rejects and $E\_f$ rejects a string if $D\_f$ accepts it. Then let $z=f(\langle E\_f\rangle)$.

If $z\in L\_f$, then $E\_f$ accepts $z$ by the definition of $L\_f$ and so by the definition of $E\_f$, $D\_f$ rejects $z$ and so $z\notin L\_f$, a contradiction. Similarly, we can show that, $z\notin L\_f\Rightarrow z\in L\_f$, another contradiction, so $L\_f$ must be undecidable.
> 1 votes

# Answer
**Using formal notations rather than words would make your life easier.** Since you have a binary encoding of Turing Machines (TM), you should use a formal notation for it.

For example you can give it a name, say $g$. Then an encoding $x$ of a TM $M$ can be written $x=g(M)$, or if you want to use the common angle bracket notation: $x=\langle\_g M\rangle\_g$. Note that I keep $g$ as a subscript of the angle brackets, so that I can distinguish different binary encodings of Turing Machines.

Now, if $g$ is a binary encoding scheme for TMs, then its composition $h=f\circ g$ with a bijective and computable function $f$ (from binary numbers to binary numbers) is also a binary encoding scheme for TMs, such that (using the various possible notations) $h(M)=f(g(M))=\langle\_h M\rangle\_h=f(\langle\_g M\rangle\_g)$.

Now you can rewrite the definition of $L$ using this new binary encoding scheme: .$$\begin{align} L&=\\{f(x)\mid \mbox{$x$ is an encoding of a machine that accepts $f(x)$}\\}\\ &=\\{f(x)\mid \mbox{$x=\langle\_g M\rangle\_g$ and $M$ accepts $f(\langle\_g M\rangle\_g)$}\\} \\ &=\\{f(\langle\_g M\rangle\_g)\mid \mbox{$M$ accepts $f(\langle\_g M\rangle\_g)$}\\}\\ &=\\{\langle\_h M\rangle\_h\mid \mbox{$M$ accepts $\langle\_h M\rangle\_h$}\\} \end{align}$$

It is now easy to see that **L is recursively enumerable**, since for any value $x$, we can test whether it is in $L$ by running the machine $M$ such that $x=\langle\_h M\rangle\_h$ with input $x$, which does terminate when $x\in L$.

However, **$L$ is not decidable**. The proof goes by contradiction. We first suppose that $L$ is decidable. Thus its complement $\overline L$ is also decidable, and is recognized by a Turing machine $\overline M$

If $\overline M$ accepts $\langle\_h \overline M\rangle\_h$, then $\langle\_h \overline M\rangle\_h$ is in $\overline L$, the language that $\overline M$ recognizes by definition. But this implies, by definition of $\overline L$ that $\overline M$ does not accept $\langle\_h \overline M\rangle\_h$.

But if $\overline M$ does not accept $\langle\_h \overline M\rangle\_h$, then $\langle\_h\overline M\rangle\_h\notin L$ by definition of $L$. Thus $\langle\_h\overline M\rangle\_h\in\overline L$. Hence since $\overline M$ recognizes $\overline L$, $\overline M$ must accept $\langle\_h \overline M\rangle\_h$.

In both cases we have a contradiction. So the hypothesis that $L$ is decidable cannot hold.
> 0 votes

---
Tags: computability, turing-machines, proof-techniques, undecidability, encoding-scheme
---


# Question
Title: can network layers communicate between each other?
in a network architecture can two layers in different machines communicate between each other using some protocols, without having to go through the layers below, if yes how briefly ?

# Answer
> 1 votes
No. Ultimately, for two computers to communicate, something physical (such as a bunch of electrons or photons) must pass between them and that's the lowest possible level of the OSI model.

In general, though, you shouldn't view the layers too rigidly. They're a vocabulary for talking about networking, rather than a requirement for writing network protocols.

---
Tags: communication-protocols
---


# Question
Title: Determining most efficient algorithm for a problem
This is a very straightforward question, and I apologize if it is a repeat. All I want to know is if there is any general method for determining how efficient the most efficient algorithm for some problem is, in terms of time. Barring that, are there any specific methods used that have accomplished the same for a particular problem? If this is not possible in general or at all what are the hurdles to this, and is there any research along these lines?

# Answer
Note that there is a problem with no maximally efficient algorithm.
The problem "Is it the case that x has an even number of 1s and
the Turing machine M halts within length(x) steps?" is such that

$\\:$ if M halts then the problem takes linear time to solve, since for inputs whose length exceeds
$\\:$ the amount of time it takes for M to halt, the algorithm will have to look at each bit of x
$\\;\\;\\;\\;$ and
$\\:$ if M does not halt then the problem can be solved
$\\:$ in constant time, since the answer is no for all x

.
Therefore, deciding how efficient the most efficient algorithm for some problem is, to the
extent that makes sense, is at least as hard as the halting problem. $\\:$ On the other hand,
you may be interested in the circuit minimization problem and/or DFA minimization.
> 0 votes

---
Tags: algorithms, time-complexity, efficiency
---


# Question
Title: Minimum spanning tree and its connected subgraph
This problem is from the book \[1\]. In case of being closed as a duplication of that in \[2\], I first make a defense:

* The accepted answer at \[2\] is still in dispute.
* The proof given by `@eh9` is based on Kruskal's algorithm.
* I am seeking for a proof independent of any MST algorithms.

---

> ***Problem:*** Let $T$ be an MST of graph $G$. Given a connected subgraph $H$ of $G$, show that $T \cap H$ is contained in some MST of $H$.

---

My partial trial is *by contradiction*:

> Suppose that $T \cap H$ is not contained in any MST of $H$. That is to say, for any MST of $H$ (denoted $MST\_{H}$), there exists an edge $e$ such that $e \in T \cap H$, and however, $e \notin MST\_{H}$.
> Now we can add $e$ to $MST\_{H}$ to get $MST\_{H} + {e}$ which contains a cycle (denoted $C$).
>
> * Because $MST\_{H}$ is a minimum spanning tree of $H$ and $e$ is not in $MST\_{H}$, we have that every other edge $e'$ than $e$ in the cycle $C$ has weight no greater than that of $e$ (i.e., $\forall e' \in C, e' \neq e. w(e') \le w(e)$).
> * There exists at lease one edge (denoted $e''$) in $C$ other than $e$ which is not in $T$. Otherwise, $T$ contains the cycle $C$.
>
> Now we have $w(e'') \le w(e)$ and $e \in T \land e'' \notin T$, $\ldots$

I failed to continue...

---

1. Algorithms, Chapter 5: Greedy algorithms
2. "Minimum Spanning tree subgraph"@StackOverflow

# Answer
> 5 votes
If we construct a spanning tree for $H$ containing $T\_G \cap H$ then your approach leads to a trivial contradiction (meaning that your initial assumption is automatically contradicted by any direct proof). Here is the construction of a MST for $H$ from a MST for $G$:

Let $MST\_\Psi$ be the set of minimum spanning trees for the graph $\Psi$. The spanning tree $T\_\Psi$ is not minimum for $\Psi$ if there is another spanning tree for $\Psi$ with smaller weight. Start with $T\_H \in MST\_H, T\_G \in MST\_G$.

While there is an edge $e \in T\_G \cap H$ such that $e \not\in T\_H$ do:

1- Find $e$ and add it to $T\_H$ to create a cycle. For every other edge $e' \not\in T\_G$ in the cycle we have $w(e') = w(e)$ (because if $w(e)\>w(e')$ then replacing $e$ with $e'$ in $T\_G$ gives a better ST for $G$, thereby $T\_G$ is not minimum for $G$. If $w(e)\<w(e')$ then since $e \not\in T\_H$ we can replace $e'$ with $e$ in $T\_H$ to obtain a better spanning tree for $H$ contradicting $T\_H$ being MST for $H$). Let $e'' \not\in T\_G$ be one of these edges. We can safely replace $e''$ with $e$ in order to obtain $T'\_H = T\_H \setminus \\{e''\\} \cup \\{e\\} \in MST\_H$.

2- Rename $T'\_H$ to $T\_H$.

EndWhile

After the loop we have $T\_G \cap H \subseteq T\_H$.

# Answer
> 6 votes
***Flaws in the accepted answer:*** When I re-read the accepted answer given by @Mahmoud A. today, I find flaws in it.

Consider the figures for an example:

In this example, $e = CE$. In figure (5), the edge $CD$ in the cycle created by adding edge $e = CE$ into $T\_H$ is not in $T\_G$ shown in figure (2), but we have $w(CD)\<w(e=CE)$. So the claim "For every other edge $e' \notin T\_G$ in the cycle we have $w(e′)=w(e)$" does not hold.

***Note:*** In the following, I fix the flaws. I leave the answer given by @Mahmoud A. as accepted because it is original and insightful.

***Correction:*** While where is an edge $e \in T\_G \cap H$ such that $e \notin T\_H$ do:

1. Adding $e$ to $T\_H$ to create a cycle $C$.

* 1.1 Because $T\_H$ is an MST of $H$, for every other edge $e' \in C$ we have $w(e') \le w(e)$. Otherwise, for any edge $e' \in C$ such that $w(e')\>w(e)$, $T\_H + \\{ e \\} - \\{ e' \\}$ has smaller weight than $T\_H$.
    * 1.2 Let $e = (u,v)$. Remove $e$ from $T\_G$. Then vertices $u$ and $v$ are separated into two different connected components, denoted by $U \ni u$ and $V \ni v$, of $T\_G$. Because $T\_H$ is an MST of $H$ (which includes vertices $u$ and $v$) and $e \notin T\_H$, there must be an edge $e'' \in C$ which connects the two components $U$ and $V$ again.
    We claim that $w(e'') = w(e)$. In 1.1, we have proved that $w(e'') \le w(e)$ (replacing $e'$ there by $e''$). If $w(e'') \< w(e)$, then $T\_{G} - \\{ e \\} + \\{ e'' \\}$ has smaller weight than $T\_G$.
    * 1.3 According to 1.1 and 1.2 above, there are an edge $e'' \in C$ such that $e'' \neq e \land w(e'') = w(e)$. We replace $e''$ with $e$ in $T\_H$ to obtain $T'\_H = T\_H - \\{ e'' \\} + \\{ e \\} \in MST\_H$.
    Since $e'' \notin T\_{G} \cap H$ and $e \in T\_{G} \cap H$, $T'\_H$ contains one more common edge with $T\_{G} \cap H$ than $T\_H$ does.
2. Rename $T'\_H$ to $T\_H$

EndWhile

After the loop we have $T\_{G} \cap H \subseteq T\_H$.

# Answer
> -1 votes
First assume the edge weights are distinct. Kruskal's algorithm then implies that the MSTs $T$ of $G$ and $T'$ of $H$ are unique. Let $S = T\cap E(H)$ and suppose that $e\in S\setminus T'$. Because $e\notin T'$, the weight $w(e) \> w(e')$ for each $e'$ on the fundamental cycle $C$ of $e$ in $T'$. This then implies that, at the moment $e$ was added to $T$ in the Kruskal algorithm, each such $e'$ already was spanned by some connected component of a sub-forest $F$ of $T$.

In fact, $F$ has to be a sub-tree of $T$, since $C\setminus e$ is connected, and the trees of $F$ covering the endpoints of pairs of edges incident on a common vertex must be the same.

Now we are at a contradiction: both endpoints of $e$ are in a subtree of $T$ not containing $e$. This is impossible if $T$ is actually a tree.

For the non-unique weights case, just pick an order of the edges consistent with the weights and then perturb them to reduce to the distinct case.

---
Tags: algorithms, graphs, spanning-trees
---


# Question
Title: Terminology - the reason for symbol reuse in programming languages
What is the term in programming language creation that is the rationale for symbol reuse? Though potentially confused with overloading, it is not so much the application of symbol reuse, but the logical result of a limited vocabulary in the world of common symbols.

I seem to recall running in to the term when reading about the development of C - that one eventually runs out of simple symbols, so the language designers took a reasonable approach to use familiar symbols to mean different things, rather than invent new symbols for every new need. Additionally, they desired to stay within the 7-bit ASCII alphabet. The particular meaning is determined by the number/type of operators used or the broader context.

An example is from C/C++ where `<` is used as

1. a delimiter in template definitions (`template <int N>`)
2. #include delimiter, searching system headers first (`#include <filename>`)
3. a less-than comparison operator (`x < y`)
4. left bit shifts (`x << n`)
5. the ostream operator (`std::cout << val << std::endl`)

Point - there are cases of symbol reuse beyond strict overloading, and I believe that there is a one-word term whose definition is something like "the condition of using the same symbols for different purposes by necessity or for the sake of maintaining familiarity."

# Answer
> 0 votes
**Parsimony** \- after weeks of racking my brain, it finally hit me, but it's not a CS-specific word.

Generally, the word just means "miserliness in resource usage" or "stinginess," but it's a good word for what the professor intended. Language designers want to minimize resources, for reducing both character sets and the required familiarity of the programmer with character sets. Again, C designers for instance, wanted to stay within 7-bit ASCII.

An even closer application of 'parsimony' is the Maximum Parsimony problem. The goal is to find the minimum number of genetic sequences that can compose a given set of genotypes. It's particularly important in understanding evolutionary trees and gene inheritance, and generally NP-complete. Regarding programming languages, one might want to find the minimum number of character symbols required to express all necessary *tokens*, unambiguously, to the compiler.

Here is a Stanford project on the matter of Halotyping.

# Answer
> 2 votes
The main reason is very mundane. At the time C was designed, and notations for many things, we did not have any form of graphics, or very seldom (like one graphic screen for the whole university, even in major places). Actually, the main output devices were the teletype or the line-printer, with a standardized and limited character set. Even the alphanumeric screen came later for most. No windows or mouse excepts in rare labs (Xerox).q

So that was a general constraint for everyone. For writing papers, we could add hand-written symbols in blank spaces left by the typist. But for more mechanized works such as programs listing (i.e. the printed text of programs) and for execution result, we had to do with what characters were available on the printing device.

Another problem was that increasing the number of symbols was limited by the standard encoding in seven or eight bits. Memory was very costly. The syntax of Fortran (the version of that time) was influenced by the format of punched cards.

Then there is a tradition. Mathematicians have been reusing symbols too. And so does natural language. We get diversity by composing them, or using context. And this was fortunate for Gutenberg, and made writing generally much easier. Compare Chinese and Latin writing.

Regarding how this could be called, I must say there is no word that comes to my mind. Not even the feeling that there was a specific word for that. I did quite a bit of theoretical and practical work on programming language syntax and I do not remember this as an issue, except as explained below.

Short of knowing what word you may look for, I can try to guess, and some obvious candidates would be *homonymy* or *homography*. Or maybe *polysemy*.

A specific case, but which concerns more identifiers, is scoping rules. In some languages they apply also to operators.

So far, that is the best I can contribute to this onomasiological issue.

---
Tags: terminology, programming-languages, language-design, syntax
---


# Question
Title: Smallest class of automata model whose corresponding language class contains CFL and is closed against (dis)allowing nondeterminism in the model
From a comment, an interesting question popped up. The class of CFLs (the languages recognized by PDAs) are obviously not closed under nondeterminism - what I mean by this is that deterministic PDAs are not equivalent in power to nondeterministic PDAs.

However, all CFLs are decidable, and in this case, any deterministic TM is equivalent in power to a nondeterministic TM.

Now, this is a large gap - what is the smallest language "above" CFLs that is closed under nondeterminism?

# Answer
> 10 votes
The notion of a *PDA* can be generalized to an *$S(n)$ auxiliary pushdown automaton ($S(n)$-AuxPDA)*. It consists of

1. a read-only input tape, surrounded by endmarkers,
2. a finite state control,
3. a read-write storage tape of length $S(n)$, where $n$ is the length of the input string, and
4. a stack

In "Hopcroft/Ullman (1979) *Introduction to Automata Theory, Languages, and Computation (1st ed.)* we find:

**Theorem 14.1** The following are equivalent for $S(n)\geq\log n$.

1. $L$ is accepted by a deterministic $S(n)$-AuxPDA
2. $L$ is accepted by a nondeterministic $S(n)$-AuxPDA
3. $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$.

with the surprising:

**Corollary** $L$ is in $\mathsf P$ if and only if $L$ is accepted by a $\log n$-AuxPDA.

The proof consists of three parts: (1) If L is accepted by a nondeterministic $S(n)$-AuxPDA with $S(n)\geq \log n$, then $L$ is in $\operatorname{DTIME}(c^{S(n)})$ for some constant $c$. (2) If $L$ is in $\operatorname{DTIME}(T(n))$, then $L$ is accepted in time $T^4(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input). (3) If $L$ is accepted in time $T(n)$ by a deterministic one-tape TM with a very simple forward-backward head scan pattern (independent of the input), then $L$ is accepted by a deterministic $\log T(n)$-AuxPDA.

Part (1) is basically a rigorous proof that the "halting problem is decidable", where the number of operations was counted thoroughly. Part (2) is the creative idea that prepares the stage for part (3). Part (3) uses the auxiliary storage for tracking the time step, which allows to reconstruct the head position due to the very simple forward-backward head scan pattern, and the stack for recursive backtracking.

---

The above is a copy of large parts of an answer to another question. So in which sense does it answers the current question? It is not the smallest imaginable class that contains $\mathsf{CFL}$ and is closed under nondeterminism. But it is a very well known class (i.e. $\mathsf P$) and a natural machine model, which has been studied thoroughly in the past, and is still studied today (with an additional runtime restriction) in the context of LogCFL. Indeed, LogCFL is also closed under nondeterminism and is closer than $\mathsf P$ to $\mathsf{CFL}$, proving my point that the above (i.e. $\mathsf P$ = $\log n$-AuxPDA) is not the smallest imaginable class of this kind.

---
Tags: formal-languages, context-free, closure-properties, computation-models, nondeterminism
---


# Question
Title: Can someone help me come up with a formula for calculating the difference in time?
So my assignment is to write a program that prompts the user for two different times on the same day (with 0 being midnight, 0700 being 7:00 am and 2200 being 10 pm) and then returns the difference between the two times with the amount of hours and amount of minutes elapsed. For example, if the user inputted 1255 and 1305, the program should return 0 hours and 10 minutes. I'm fine with how to find the number of hours but I cannot come up with a formula for finding the difference in minutes. Here is what I have so far:

```
    Scanner keyboard1 = new Scanner(System.in);
    System.out.print("Train A departs at: ");
    int a = keyboard1.nextInt();

    Scanner keyboard2 = new Scanner(System.in);
    System.out.print("Train B departs at: ");
    int b = keyboard2.nextInt();

    int difference = Math.abs(a - b);
    int hours = difference / 100;
    int minutes = (I need help here);

    System.out.print("\nDifference: " + hours + " hours and " + minutes + " minutes");

```

# Answer
> 1 votes
The solution I originally provided here is wrong, the comments on why the question itself is out of scope are interesting though.

> int hours = Math.abs(a - b)/ 100;
> int minutes1 = Math.min(a,b) % 100; int minutes2 = Math.max(a,b) % 100; int mdifference = ((Math.min(a,b) / 100) == (Math.max(a,b) / 100)) ? minutes2 - minutes1 : (60 - minutes1) + minutes2; System.out.print("\nDifference: " + hours + " hours and " + mdifference + " minutes");

---
Tags: algorithms
---


title: Strongly connected components on a DAG

text:
# Question
Title: Strongly connected components on a DAG
What is supposed to be the right result of an SCC algorithm running on a DAG. should it return "no components" or "there are V components of size 1"?

I suspect it will return the latter (since it will start with the last sink, and then go back and mark each single sized vertex as a component, since each DFS will be of a single node before it can continue)

But is this a convention? E.g. if a treat SCC as a "great way to find if a graph has cycles" then I would expect it to return an empty result if there are none. e.g. components of size 1, who don't have a self-loop, don't really "go from A to A". is there a SCC variant that is more explicitly "find all groups that has cycles in them"? (e.g. is there a named variation)

Or what I'm looking for is basically "run SCC, then remove all components of size 1, and you got yourself a cycle detector, e.g. if after you do that you end up with no components, then your graph is a DAG"

Is there a name for that special SCC case? (assuming my understanding in the beginning of the question is correct)

# Answer
> 2 votes
I know of no convention; the right result depends entirely on what you want to do with the result. As an example, if you're trying to use strongly connected components to find satisfying assignments for 2SAT instances, then you likely want all the singleton cycles returned along with the larger components. But if you're just trying to find out if a graph contains a cycle, then the singletons won't be of interest to the caller so the SCC function could usefully omit returning them.

---
Tags: graphs, terminology, dag
---


# Question
Title: Counter example to graph coloring heuristic using BFS
I am considering the following heuristic for the graph coloring problem (i.e. to color a graph $G$ using a minimal number of colors so that no two adjacent vertices have the same color):

> Explore the vertices of $G$ in the order that they would be explored by a BFS search (with arbitrary starting vertex) and assign each vertex the lowest numbered color not yet used for one of its neighbors.

Since I don't think this algorithm is correct, I am trying to find a counterexample where coloring a graph in this way does not yield a coloring with the minimal number of colors. Does anyone know of such an example?

# Answer
> 1 votes
Here's one:

The labels indicate the intend BFS ordering (alphabetical). A different ordering can produce a different result, so more work would have to be done to get a graph where your BFS approach fails for every starting point (it would probably be very messy too).

Assuming we follow this ordering however, we get the following colouring:

The key being that $e$ and $f$ get coloured last, so $c$ removes blue from the possibilities, and $d$ removes red, so $e$ and $f$ must have two new colours.

However this graph is 3-colourable:

By choosing to use more colours earlier, it relaxes the constraints later.

I'll also throw in a conjecture that this is smallest counterexample, for no other reason than to challenge others to find smaller ones ;).

# Answer
> 0 votes
I think that published alleged "counter-examples" of the four-color theorem, usually predating the proof of the theorem should be rewritable as graph counter-examples for you. There is one published (as an April Fool's joke) by Martin Gardner in 1975.

You should find other candidates on this page, and you can easily translate them into graphs. The idea is that if you start with a wrong combination in some part of the graph, you may get blocked, though other choices might work.

---
Tags: algorithms, graphs, correctness-proof, colorings
---


# Question
Title: Is the number of nodes in an ORBDD 2n + 2?
Wikipedia says that the number of nodes in a ORBDD (Order Reduced Binary Decision Diagrams) of order $x\_1 \< x\_2 \< \dots \< x\_{2n}$ is $2n + 2$.

But I can't find proof. Anyone?

# Answer
> 3 votes
It doesn't say that. To quote:

> Let us consider the Boolean function $f(x\_1,\ldots, x\_{2n}) = x\_1x\_2 + x\_3x\_4 + \cdots + x\_{2n-1}x\_{2n}$. Using the variable ordering $x\_1 \< x\_3 \< \cdots \< x\_{2n-1} \< x\_2 \< x\_4 \< \cdots \< x\_{2n}$, the BDD needs $2^{n+1}$ nodes to represent the function. Using the ordering $x\_1 \< x\_2 \< x\_3 \< x\_4 \< \cdots \< x\_{2n-1} \< x\_{2n}$, the BDD consists of $2n + 2$ nodes.

It is only talking about that particular function, and demonstrating the difference that different variable orderings can make.

As it says a few lines later:

> There are functions for which the graph size is always exponential — independent of variable ordering.

Bryant \[1\] proves several functions have exponentially sized OBDDs, regardless of the variable ordering (see for example Theorems 2 and 4 in the paper).

**References**

1. Randal E. Bryant, "On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication", IEEE Trans. on Computers, 40(2):205-226, 1991.

---
Tags: combinatorics, bdd
---


# Question
Title: Complexity of dynamic programming algorithm for Knapsack
Dynamic programming algorithm for Knapsack is stated to have complexity $\mathcal O (nW)$.

However, I've also seen the complexity stated as $\mathcal O (n^2V)$, where $V=\max v\_i$.

(Here $n$ is the number of items and $W$ the weight limit).

I see from the algorithm that the first complexity measure is correct: http://en.wikipedia.org/wiki/Knapsack\_problem

Can someone tell me, why the other complexity measure works ?

# Answer
The first complexity measure is in terms of the target weight, the second in terms of the heaviest element. Since $W \leq nV$ (or rather, we can assume that $W \leq nV$), the first estimate $O(nW)$ implies the second $O(n^2V)$. So $O(nW)$ is a stronger estimate than $O(n^2V)$.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, dynamic-programming, pseudo-polynomial
---


# Question
Title: Why is testing if x > y primitive recursive?
$f(x,y)= 0$ if $x\>y$ and $1$ otherwise.

How can prove formally that this function is primitive recursive?

# Answer
> 1 votes
Hint: One possible approach is to compose the functions $x\dot{-}y = \max(x-y,0)$ and $\delta(z) = \begin{cases} 0 & z=0, \\ 1 & z\>0 \end{cases}$.

---
Tags: computability, primitive-recursion
---


# Question
Title: Prove Vertex-Cover of maximum degree 3 is NPC
This is a homework question. I need to prove that the following language is in NP Complete:

> 3-VERTEX-COVER = $\\{\langle G,k\rangle \mid$ G is an undirected graph, each vertex in $G$ has at most $3$ incident edges, and there is a vertex cover of size $k$ in $G\\}$

Showing that it is in NP is easy. Now, to show that it is in NPC I thought about showing a reduction from Vertex-Cover. But I can't seem to think of what to do with a graph I get as `<G,k>` which is in Vertex-Cover, to make each vertex degree at most 3 without changing the vertex-cover property. Any hints?

# Answer
> 3 votes
Hint: Here is how to handle vertices of degree 4 (taken from Alimonti and Kann).

Let $v$ be a vertex of degree $4$, with neighbors $x\_1,x\_2,x\_3,x\_4$. Replace $v$ with a path $v\_1-w-v\_2$ and connect $x\_1,x\_2$ to $v\_1$ and $x\_3,x\_4$ to $v\_2$ (arbitrarily). A vertex cover in the original graph containing $v$ corresponds to a vertex cover in the new graph containing $v\_1,v\_2$. A vertex cover in the original graph not containing $v$ corresponds to a vertex cover in the new graph containing $w$. In total, we get that the original graph has a vertex cover of size $k$ iff the new graph has a vertex cover of size $k+1$.

The same idea works for vertices of higher degree.

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


# Question
Title: What happens when two processes hold an election using bully algorithm simultaneously
A coordinator is used to sychronise the usage of resources in a distributed system.

The Bully Algorithm is a method to elect a new coordinator in a distributed system when the current coordinator disappears for some reason.

I am just wondering what happens when two processes realise the demise of the coordinator simultaneously and both decide to hold an election using the Bully Algorithm?

# Answer
> 3 votes
Both processes will anounce themselves. However, the one with the highest indentifier will become the leader. For example, 3 and 4 announce themselves. 3 asks who has an id greater than me, and 4 responds. Then 3 knows 4 is the new leader. 4 does the same. No process replies. 4 tells everyone that he's the new leader.

---
Tags: distributed-systems, synchronization
---


# Question
Title: For what kind of data are hash table operations O(1)?
From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there are techniques to help make these conditions broad.

However, from a programmer's perspective, I don't know in advance what my data will be: it often comes from some external source. And I rarely have all the data at once: often insertions and deletions happen at a rate that's not far below the rate of lookups, so preprocessing the data to fine-tune the hash function is out.

So, taking a step out: given some knowledge about data source, how can I determine whether a hash table has a chance of having $O(1)$ operations, and possibly which techniques to use on my hash function?

# Answer
There are several techniques that guarantee that lookups will always require O(1) operations, even in the worst case.

> How can I determine whether a hash table has a chance of having O(1) operations, and possibly which techniques to use on my hash function?

The worst case happens when some malicious attacker (Mallory) deliberately gives you data that Mallory has specifically selected to make the system run slow.

Once you have picked some particular hash function, it's probably over-optimistic to assume Mallory will never find out which hash function you picked. Once Mallory discovers which hash function you picked, if you allow Mallory to give you lots of data to be inserted into your hash table using that hash function, then you are doomed: Mallory can internally rapidly generate billions of data items, hash them with your hash function to find which data items are likely to collide, and then feed you millions of one-in-a-thousand data items that are likely to collide, leading to lookups that run much slower than O(1).

All the techniques that guarantee "O(1) lookups even in the worst case" avoid this problem by doing a little bit of extra work on each insertion to guarantee that, in the future, every possible lookup can succeed in O(1) time. In particular, we assume (worst case) that Mallory will sooner or later discover which hash function we are using; but he only gets a chance to insert a few data items before we pick a *different* hash function -- tabulation hashing or some other universal hashing -- one that we specially select such that all the data we have so far can be looked up in 2 or 3 probes -- i.e., O(1). Because we randomly select this function, we can be fairly sure that Mallory won't know what function we picked for a while. Even if Mallory *immediately* gives us data that, even with this new hash function, collides with previous data, we can then pick yet another a fresh new hash function such that, after rehashing, all the previous data he and everyone else has fed us can now be looked up in 2 or 3 probes in the worst case -- i.e., O(1) lookups in the worst case.

It's fairly easy to randomly select a new hash function and rehash the entire table often enough to guarantee that each lookup is always O(1). While this guarantees that each lookup is always O(1), these techniques, when inserting the Nth item into a hash table that already contains N-1 items, can occasionally require O(N) time for that insert. However, it is possible to design the system such that, even when Mallory deliberately gives you new data that, using the new hash function, collides with previous data, the system can accept lots of items from Mallory and others before it needs to do a full O(N) rebuild. Hash table techniques that pick-a-new-function-and-rehash in order to guarantee O(1) lookups, even in the worst case, include:

* cuckoo hashing guarantees that each key lookup succeeds with at most 2 hash calculations and 2 table lookups.
* hopscotch hashing guarantees that each key lookup succeeds after inspecting at small number H (perhaps H=32) consecutive entries in the table.
* dynamic perfect hashing -- the 1994 paper by Dietzfelbinger is the first one I've read that pointed out that, even though it rehashes "frequently" in order to guarantee that each key lookup always succeeds with 2 hash calculations and 2 lookups, it's possible to do a full rehash so rarely that even though each full rehash uses O(n) time, the expected average cost of insertions and deletion are O(1) amortized.

Data Structures/Hash Tables
> 4 votes

# Answer
Hash table lookup can always be $O(1)$ for static sets, see the 2002 paper by Arne Andersson and Mikkel Thorup: Dynamic ordered sets with exponential search trees

> Firstly, we give the ﬁrst deterministic polynomial-time (in n) algorithm for constructing a linear space static dictionary with $O(1)$ worst-case access cost (cf. perfect hashing). As mentioned earlier, a linear space data structure that supports member queries (neighbor queries are not supported) in constant time can be constructed at a worst-case cost $O (n^2 W)$ without division \[30\]. We show that the dependency of word size can be removed.

In the general case, Andersson et al provide an algorithm for hash-indexed data structures that support lookups and updates in $O(\sqrt{\log n / \log \log n})$. Furthermore, they prove that this bound is optimal. So we know exactly how close we can get to $O(1)$ in the general case.
> 6 votes

# Answer
I am not a data structures expert, but the usual theoretical approach to hashing is that one defines a *family* of functions (e.g., $h\_{a,b}(x) = ax + b \mod p$) and then considers the behavior on a *worst case* input on a *randomly chosen* member of the family, where the adversary *doesn't know the random choice* in advance. This is similar to how randomized algorithms are analyzed as well: the expectation is taken over the algorithm's choices, not the input distribution.

In the past, according to a Usenix paper by Crosby and Wallach, common programming languages didn't do anything like this, leaving lots of web apps (and other servers) open to a DoS attack based on manufacturing collisions. (The paper is from 2003, but it suggests that Dan Bernstein had discovered the same idea quite a bit earlier.)

A quick google search provides claims that the state of the art in terms of implementations has both improved and not improved.

Another aside is that in a high-bandwidth world, timing attacks make it not-so-hard to find collisions online (as opposed to offline as the Crosby-Wallach link suggests). I seem to remember that Daniel Golovin had results some years ago on data structures that aren't vulnerable to timing attacks, but I don't know if they are widely used.
> 6 votes

# Answer
The average-case analysis for the hash-tables is made under the usual assumption of uniformity of the inputs, which once makes due to occam’s razor.

If you have additional knowledge about the domain and the distribution of the keys you can take the same average-case analysis and replace the uniform distribution with your distribution and recalculate the expectations, at least in theory.

Of course the difficulty stems from the fact that non-uniform avaerage-case analysis’ are hard to do. And your “knowledge” may not be conveniently expressable as a distribution that can be used easily in such an analysis.

Obviously the easiest thing to do are simulations. Implement the hash-tables and oberserve how they perform for your typical set of inputs.
> 0 votes

# Answer
Permutations (of a fixed length), as a specific case of finite known sets: it is relatively easy to assign unique numbers to permutations, as in this paper. I have used this (in a somewhat less ghastly implementation) to map permutations of length $n$ into an array of size $n!$. But I could do this because I was eventually going to need every permutation; if you are only using a subset, you would need a function tailored to that subset or an efficient sparse array.
> -1 votes

---
Tags: data-structures, runtime-analysis, hash-tables, dictionaries
---


# Question
Title: Algorithm to return largest subset of non-intersecting intervals
I need an efficient algorithm that takes input a collection of intervals and outputs the largest subset of non-intersecting intervals.

i.e. Given a set of intervals $I = \\{I\_1, I\_2, \ldots, I\_n\\}$ of the real line, we need to output a set of intervals $O = \\{O\_1, O\_2, \ldots, O\_k\\}$ such that

* $O$ is a subset of $I$.
* For any $i \neq j$, $O\_i$ and $O\_j$ are non-intersecting.
* $k$ is the maximum possible.

Example: if the intervals are $\[1,100\], \[2,3\], \[4,5\], \[6,7\], \[3,20\]$ we should return $\\{\[2,3\], \[4,5\], \[6,7\]\\}$.

# Answer
> 8 votes
There is an $O(n \log n)$ time algorithm (which in some models is optimal, because of the bounds for the element distinctness problem).

We first sort the intervals by their right end point. Suppose the sorted order is $I\_1, I\_2, \ldots, I\_n$.

Now for each interval, we try to compute the size of the largest possible non-intersecting set, with that interval being the rightmost interval in that set. We pick the interval which gives the maximum (as any non-intersecting set has a rightmost interval).

This we do using dynamic programming.

Suppose we have computed the sizes (say $S\_1, \ldots, S\_n$) for intervals up to $k-1$. Now you want to compute for $I\_k = \[L\_k, R\_k\]$.

Pick $L\_k$, and do a binary search in $\[R\_1,R\_2, \ldots, R\_k\]$. Say $R\_j \lt L\_k \lt R\_{j+1}$.

Now all the intervals $1,2,\ldots,j$ do not intersect $I\_k$ (and all others up to $I\_{k-1} \cap I\_k$). Thus we need to pick the max among $S\_1, S\_2, \ldots, S\_j$ and add $1$ to it. This maximum can also be computed dynamically, in a separate array, along with the $S$.

This can be implemented so that the whole algorithm runs in $O(n \log n)$.

We can also modify this algorithm a little to give you the actual intervals which form the non-intersecting set.

# Answer
> 7 votes
This is called the "Interval Scheduling" problem in the book \[1\]. The greedy algorithm, along with an example, is as follows (please find the correctness proof in the book mentioned above):

* sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$.
* while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}$, do:
    + add $I$ into the result-set; (darker lines in the figure)
    + delete all intervals from $\mathcal{I}$ that conflicts with $I$ (dashed lines in the figure).

\[1\]: Algorithm Design. By Jon Kleinberg and Éva Tardos. (Section 4.1)

---
Tags: algorithms, optimization, integers, intervals, set-cover
---


# Question
Title: How to prove that ε-loops are not necessary in PDAs?
In the context of our investigation of heap automata, I would like to prove that a particular variant can not accept non-context-sensitive languages. As we have no equivalent grammar model, I need a proof that uses only automata; therefore, I have to show that heap automata can be simulated by LBAs (or an equivalent model).

I expect the proof to work similarly to showing that pushdown automata accept a subset the context-sensitive languages. However, all proofs I know work by

* using grammars -- here the fact is obvious by definition -- or
* are unconvinvingly vague (e.g. here).

My problem is that a PDA (resp. HA) can contain cycles of $\varepsilon$-transitions that may write symbols to the stack (resp. heap). An LBA can not simulate arbitrary iterations of such loops. From the Chomsky hierarchy obtained with grammars, we know that

1. every context-free language has an $\varepsilon$-cycle-free PDA or
2. the simulating LBA can prevent iterating $\varepsilon$-cycles too often.

Intuitively, this is clear: such cycles write symbols independently of the input, therefore the stack (heap) content does only hold an amount of information linear in the length of the cycle (disregarding overlapping cycles for now). Also, you don't have a way to get rid of the stuff again (if you need to) other than using another $\varepsilon$-cycle. In essence, such cycles do not contribute to dealing with the input if iterated multiple times, so they are not necessary.

How can this argument be put rigorously/formally, especially considering overlapping $\varepsilon$-cycles?

# Answer
The removal of $\varepsilon$-transitions has been studied for the more general model of *valence automata* by Zetzsche \[1\]. Valence automata are essentially finite automata with a *monoid* for storage.

Among other things, Zetzsche shows that for monoids $M$ from a rich class $\mathcal{C}$ of monoids (which contains (partially) blind counters, stacks, and combinations thereof), $\varepsilon$-free $M$-automata accept the same class of languages as $M$-automata.

Since PDAs with a $k$-symbol stack alphabet correspond to valence automata over monoid $\mathbb{B}^{(k)} \in \mathcal{C}$ ($\mathbb{B}$ is the bicyclic monoid), the result from Theorem 1 (resp. 7.1 in the preprint) applies here.

The proof is long and technical; the proofs of lemmas 8 and 10 (resp. 7.6 and 7.9) contain the relevant constructions. Note that while they do not use grammar models (as required in the question) they *do* use valence *transducers*.

---

1. Silent Transitions in Automata with Storage by G. Zetzsche (2013) \[more elaborate preprint on arXiv\]
> 3 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Relation between the "Point-Cover-Interval" problem and the "Interval Scheduling" problem
> ***Point-Cover-Interval Problem:*** Given a set $\mathcal{I}$ of $n$ intervals $\[s\_1, f\_1\], \ldots, \[s\_n, f\_n\]$ along a real line, find a *minimum* number of points $P$ such that each interval contains some point, that is $\forall I \in \mathcal{I}: \exists p \in P, p \in I$.
>
> ***Interval Scheduling Problem:*** Given a set $\mathcal{I}$ of $n$ intervals $\[s\_1, f\_1\], \ldots, \[s\_n, f\_n\]$ along a real line, find a *maximum* number of intervals such that no two of them overlap.

Interestingly, the two problems above have exactly the same greedy algorithm, illustrated by the following figure (from \[1\]; for the *interval scheduling problem*; see the **"Greedy Algorithm"** part below).

Since they share the same algorithm, I expect that they are the same (or, at least closely related) problem, say, in the view of *reduction*. However, I failed to reduce them to each other.

> **Question:** Are these two problems the same? Or what is the relation between them? Can we reduce them to each other?

**Note that** the first problem asks for a *minimum* solution while the second one for a *maximum* solution.

---

**Greedy Algorithm:** The greedy algorithm for the "Interval Scheduling" problem is as follows:

* sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$.
* while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}$, do:
    + add $I$ into the result-set; (darker lines in the figure)
    + delete all intervals from $\mathcal{I}$ that conflicts with $I$ (dashed lines in the figure).

For the "Point-Cover-Interval" problem, we simply collect the finishing time point of each interval $I$ chosen in each iteration in the algorithm above.

\[1\]: Algorithm Design. By Jon Kleinberg and Éva Tardos. (Section 4.1)

# Answer
Here is a proof that the two numbers are equal:

> For every interval $I$ consider the largest set of disjoint intervals with $I$ as the rightmost interval. This has a size, say $D\_I$.
>
> Now if $D\_I = D\_J$, then $I$ and $J$ have to intersect, so the set of intervals with equal $D\_I$ values all pairwise intersect each other, and so have a common point (by the 1D version of Helly's theorem, or by just considering the intervals arranged in order of their left endpoints).
>
> Now if $d = \max D\_I$ (the size of the largest set of non-intersecting intervals), then we have $D\_I$ taking all the values $\\{1, 2, \dots, d\\}$, and thus $d$ points are enough to cover all the intervals, and we need at least $d$ to cover the largest set of disjoint intervals.

For some related reading, look at Mirsky's theorem, which is a dual of Dilworth's theorem.

> **Dilworth's theorem** says that in a set of elements with a partial order defined on them, the size of the largest antichain (antichain is a set of elements not comparable to each other) is same as the size of the smallest partition into chains (each set of the partition is a total ordered set).
>
> **Mirsky's theorem** says that the size of the largest chain is the same as the smallest number of antichains into which the set might be partitioned.

In this case defines your order relation as follows:

$$I = (i,j) \lt I' = (i', j') \iff j \lt i'$$

Basically, two disjoint intervals are comparable, with the left one being smaller.

Because of Helly's theorem, the two numbers you are computing are exactly the numbers in Mirsky's theorem, which is defined as the *height* of the the partial order (Dilworth's theorem defines the *width*).
> 2 votes

---
Tags: algorithms, reductions, greedy-algorithms
---


# Question
Title: Is it known whether the MD5 algorithm is surjective?
Does MD5 map to all possible 128 bit numbers? To put it another way: For every 128 bit number `y`, does there exist at least one `x` for which `md5(x) = y`?

The answer probably is yes, for arbitrary `x`, and probably no proof exists. However, feel free to prove me wrong :)

But what if I impose some kind of limit on `x`, e.g. `x <= x_max`? Of course, for very small `x_max` the answer is no. But what is the minimum value of `x_max` for which the answer likely becomes yes? Or the maximum value for which the answer can be shown to be no?

I'm not really interested in the exact value for `x_max`, rather in the approximate order of magnitude.

# Answer
> **Q:** Does MD5 map to all possible 128 bit numbers?

Taking into account the facts that MD5 accepts input of the arbitrary length, the output is "only" 128 bits, and the algorithm itself which behaves similarly to random functions, I would expect that the all outputs are possible. However, without any strong mathematical evidence, this is merely a speculation, or in the best case, the hunch.

> **Q:** The answer probably is yes, for arbitrary x, and probably no proof exists.

Exactly, there is no proof (currently). Proving that MD5 is surjective would require either one of these:

* Brute force check - taking into account coupon's collector problem, it takes something like 10^40 inputs to hit all 128-bit outputs. Assuming again that MD5 behaves similarly to random function, that should be enough to verify **in the case that MD5 is surjective**.
* Concrete mathematical proof - eventual proof of surjectivity should be able for arbitrary 128-bit number y prove that there exists some input x such that MD5(x) = y. That should require deep mathematical analysis of MD5 function and it would probably shed some light on reversing this hash function. Even though MD5 is far from desirable hash function, it is still not known how to predict the input based on the given output.
> 3 votes

---
Tags: reference-request, hash
---


# Question
Title: Is the unsolvability of the N-Body Problem equivalent to the Halting Problem
There is no general analytic solution to the n-body problem that can produce an analytic function which can be used to give an n-body system's state at arbitrary time t with exact precision. However, there are some special cases of n-body systems for which an analytic function is known.

In much the same way, there is no general algorithm which can predict the result of an arbitrary Turing machine. Although, there are many kinds of Turning machine which can be determined to halt or run forever.

Are these two results equivalent? Does the proof of one of these imply the other? Would a magic machine that is able to solve the halting problem be able to predict the state of an n-body system with exact precision? Or vice versa, would a general analytic solution to the n-body problem allow us to decide the halting problem on an arbitrary Turing machine?

My initial guess on how to approach this would be to show that an n-body system under gravitation is Turing complete. I suspect that it is considering the universe is Turing complete and essentially operates under gravitation (and a few other forces that behave similarly), but I have no idea how to go about proving this.

But I am skeptical that that approach is sufficient considering I find it possible (though I think unlikely) that the lack of an analytic general solution to the n-body problem could be independent of it being Turing complete.

Edit: After reading some other tangentially related questions, I realized that the number of dimensions in which gravity is operating could be relevant to the question. I'm specifically asking about gravity in 3 spatial dimensions. But, given facts such as you need at least 3 rules to make a universal Turing machine and gravity in 2 dimensions would have just an inverse law $ \propto 1/r $ instead of an inverse square law $ \propto 1/r^2 $ resulting in no closed orbits, I can see it turning out that gravity in three dimensions is Turing Complete, but not in two or one.

# Answer
> 14 votes
There is some (somewhat scattered) research into the undecidability of the N-body problem from physics (in line with general study of undecidable phenomena in classical and quantum physics), which asks about calculating future trajectories or orbits of objects all subject to $n^2$ gravitational interactions; it has been studied for centuries including by e.g. Newton and Gauss. It basically reduces to a large array of differential equations and such systems have been proven to contain undecidability scenarios. However, this is a somewhat unusual crosscutting area of physics and mathematics that is not widely cited in either field and there do not seem to be widely cited single references either.

See e.g.

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


# Question
Title: what are the key advantages of pipelining
I was trying to look my book computer architecture and design, but I can not find the answer for this question. what are-the key-advantages of pipelining?

# Answer
I Googled your question and found this (and this):

> Consider the modern way of making cars - on an assembly line. Here, there is an orderly flow of parts down a conveyor belt, and the parts are processed by different stations (also called segments of the assembly line). Each segment does one thing, over and over. The segments are coordinated to exploit the sequentiality inherent in the automobile assembly process. The work gets done more smoothly (because of the orderly flow of input parts and output results), more efficiently (because each assembler at each segment of the pipeline does his or her task at what one hopes is maximum efficiency), and more reliably because there is greater consistency in one task being done repetitively (provided the assembly line is designed correctly).

To put it in a simple way: Suppose you build a car in 10 steps $(s\_1, s\_2, \dots, s\_{10})$. Suppose also that a single person can complete these 10 steps in 2 hours and a single step in 12 minutes. Let's also say that you have only 1 workplace for each step, so 2 people can't be working on the same step for 2 different cars. You'd have two ways to produce cars:

1. Put a single person that builds a car every 2 hours and uses all 10 workplaces.
2. Put a person per workplace (10 people in total) where each person completes a single step in 12 minutes and have a car every 12 minutes. The exception in this case is the first car which would take 2 hours to be completed, but from the second car and forward you'd have a car every 12 minutes.

The second way is the equivalent of pipelining.
> 5 votes

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