# Question
Title: Is something missing in this EXPLORE algorithm?
It took me about a week to understand how does it works, but still, I'm wondering if it actually works!

# I. The algorithm EXPLORE

```
EXPLORE (S:sommet, D:following vertices of vertex X, visited:TAB)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LIST ≠ 0
    selectionner i ∈ LIST
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
    ELSE LIST←LIST - {i}

```

# II. running the algorithm

Then I tried on this Graph:

array of the following vertex of each vertex:

\begin{array}{|l|cr|} x & \Gamma^+(x)\\ \hline a & b,c,d\\ b & d,e\\ c & d,f \\ e & d,h \\ f & g,i \\ g & h, e \\ h & \emptyset\\ i & g,h \\ \end{array}

M: the visited tab L: the given list, which is empty in the beginning

Explore (a,$\Gamma$,M)

M$\leftarrow${a}

L$\leftarrow${a}

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

*list $ \ \ \ \ \ \ \ $notvisited*

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b}$ why do we add b to L??

$\Gamma(b) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d}$ why do we add b to L??

$$...$$

$\Gamma(e) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,b,d,f,g,h}$ That seems normal on the aglorithm, it corresponds to

```
Else LIST = LIST - i

```

$$...$$

Until

$\Gamma(d)$

$L\leftarrow a$

which leads to the components we didn't searched for:

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a,c}$ Still, wher the hell does this e comes in the algorithm?

$\Gamma(c) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ M\leftarrow {a,b,c,d,f,g,h,e}$ we add b to the visited list

$ \ \ \ \ \ \ \ \ \ L\leftarrow {a}$ I'm okay with its disparition

$\Gamma(a) ∩ (X \backslash M)=bcd \ne0$

$ \ \ \ \ \ \ \ \ \ L\leftarrow {\emptyset}$ I'm okay with its disparition

# III. My ideas to make it works

if ever it doesn't work!

I wonder if something is not lacking in the algorithm, if we shouldn't add an Explore within the 'if' loop.

```
EXPLORE (S:sommet,  Γ, visited)
var LIST;
i,j:vertices
visited[S] ←true;
LIST ←{S};
WHILE LISTE ≠ 0
    selectionner i ∈ LISTE
    IF ∃ j ∈ D[i] , not visited[j]
      visited[j]←true;
      **EXPLORE(j,Γ,visited)**
    ELSE LISTE←LISTE - {i}

```

# Answer
> 0 votes
This might be a bit too much, but I tried the best I could to condense it. Unfortunately, Java doesn't allow one to write concise code... So, here's breadth-first and depth-first traversal of a graph (I used JGraphT) library for graph implementation. This should better illustrate the idea.

```
package tld.se.doodles;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;

import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.DefaultDirectedGraph;

public class GraphSearch {

    public static void main(String ...args) {
        DefaultDirectedGraph<Integer, DefaultEdge> graph =
                new DefaultDirectedGraph<>(DefaultEdge.class);
        int[][] vertices = {
            {1, 2}, {1, 3}, {2, 1}, {2, 3},
            {3, 5}, {3, 6}, {3, 4}, {4, 7},
            {5, 2}, {5, 6}, {6, 3}, {6, 7}
        };
        Arrays.stream(vertices)
                .forEach(pair -> {
                        graph.addVertex(pair[0]);
                        graph.addVertex(pair[1]);
                        graph.addEdge(pair[0], pair[1]);
                    });
        depthFirstTraversal(graph);
        breadthFirstTraversal(graph);
    }

    private static void depthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Depth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        dftHashed(start, graph, cache);
    }

    private static void dftHashed(
        Integer from, DefaultDirectedGraph graph, HashSet cache) {
        if (!cache.contains(from)) {
            cache.add(from);
            System.out.format("Visiting: %d%n", from);
            graph.<DefaultEdge>edgesOf(from).stream()
                    .forEach(edge ->
                             dftHashed((Integer)graph.getEdgeTarget(edge),
                                       graph, cache));
        }
    }

    private static void breadthFirstTraversal(
        DefaultDirectedGraph<Integer, DefaultEdge> graph) {
        System.out.println("Breadth-first traversal");
        HashSet<Integer> cache = new HashSet<>();
        Integer start = graph.vertexSet().stream().findFirst().get();
        HashSet<Integer> firstGen = new HashSet<>();
        firstGen.add(start);
        bftHashed(firstGen, graph, cache);
    }

    private static void bftHashed(
        HashSet previous, DefaultDirectedGraph graph, HashSet cache) {
        cache.addAll(previous);
        HashSet<Integer> next = (HashSet<Integer>)previous.stream()
                .flatMap(vertex -> {
                        System.out.format("Visiting: %d%n", vertex);
                        return graph.<DefaultEdge>edgesOf(vertex)
                            .stream().map(graph::getEdgeTarget);
                    })
                 .collect(Collectors.toCollection(HashSet::new));
        next.removeAll(cache);
        if (!next.isEmpty()) bftHashed(next, graph, cache);
    }
}

```

---
Tags: algorithms
---


# Question
Title: Are all context-free and regular languages efficiently decidable?
I came across this figure which shows that context-free and regular languages are (proper) subsets of efficient problems (supposedly $\mathrm{P}$). I perfectly understand that efficient problems are a subset of all decidable problems because we can solve them but it could take a very long time.

Why are *all* context-free and regular languages efficiently decidable? Does it mean solving them will not take a long time (I mean we know it without more context)?

# Answer
> 17 votes
Regular language membership can be decided in $\cal{O}(n)$ time by simulating the language's (minimal) DFA (which has been precomputed).

Context free language membership can be decided in $\cal{O}(n^3)$ by the CYK Algorithm.

There are decidable languages that are not in $\sf{P}$, such as those in $\sf{EXPTIME}\setminus \sf{P}$.

# Answer
> 1 votes
Refinement/"fine print" on answer by DC: all CFLs in the form of Chomsky Normal Form can be parsed efficiently with the CYK algorithm and all CFLs can be converted to CNF. *However, converting* an arbitrary CFL to CNF may take exponential space in worst case depending on some algorithms. (I am not aware of an algorithm that guarantees P-time conversion here, is anyone else? One must consider all edge/worst cases such as nondeterministic CFLs or ambiguous ones.) Wikipedia states on the CNF section Order of transformations

> Moreover, the worst-case bloat in grammar size\[note 4\] depends on the transformation order. Using |G| to denote the size of the original grammar G, the size blow-up in the worst case may range from $|G|^2$ to $2^{2 |G|}$, depending on the transformation algorithm used.\[6\]:7

Therefore it seems there may exist CFLs that are not efficiently parseable. Most programming languages are efficiently convertable to CNF (or perhaps mostly *defined* in CNF or near-CNF) therefore CFL parsing for "typical" languages is "practically" in P. There is probably some modern research into this worst case complexity (but did not find recent papers on it on cursory search). Eg this older (1973) research paper by Greibach also seems to indicate that worst case performance may not bounded by P. see eg.

---
Tags: formal-languages, regular-languages, context-free, efficiency
---


# Question
Title: Which attributes to consider for credit card fraud detection on an ATM?
I am working on a project in which I am supposed to come up with a system that detects fraud from a credit card transaction. I read about techniques that others have used and decided to use Artificial Neural Networks for their adaptability.

**WHAT THE SYSTEM MUST DO**

My system is supposed to detect fraud on a credit card used on an ATM, that is, I am assuming that the user has already been granted access to the account by entering their PIN on an ATM. *In other words, I am saying before the transaction is authorized, pass it through the fraud detection system so we can check if it is fraudulent or not*.

**ATTRIBUTES THAT I AM THINKING TO CONSIDER**

1. The amount of money to be withdrawn - *here I am assuming that each user has a certain range of money that they usually withdraws; any deviations are treated a suspicious.*
2. Time taken to input PIN - *here I am thinking that each user has a range of time that they usually take to input PIN; any deviation is treated as suspicious.*

**Questions**

1. Which attributes can I take into consideration that enables me tell whether a transaction is fraudulent or not?
2. What others have considered to solve this problem?
3. What do you recommend me?
4. What can be inputs to my Neural network?

Thanks for your ideas.

# Answer
# Location based trends

Number of transactions from a particular ATM in a particular location, compared to the home area. So if the user usually uses a small set of ATMs near to their address, and then suddenly there are 5 large transactions from an ATM on the other side of the country.

## Another little suggestion

If it was up to me, I would use a system where the attempted transaction is given a suspiciousness rating, where each factor is given a score and then the overall decision whether or not to authorize the transaction is based on the average score. This would also allow you to prioritize different factors. Does that make sense? (Sorry, it's my first post, I'm still getting used to the etiquette)
> 1 votes

---
Tags: algorithms, machine-learning, artificial-intelligence
---


# Question
Title: Scientific soundness of computer science papers
First of all, this question relates to an issue that affects several areas of science, but since StackExchange doesn't have a meta science section I'll make it specific to computer science, which is pertinent because the solution to the bigger problem may actually come from computer science.

In the context of the news that Springer and IEEE published more than 120 nonsense papers my question is as follows:

What rigourous set of methods can we apply to the process of publishing scientific papers so that we can quickly verify the reproducibility of the experiments?

We already have systems like Turnitin that are highly efficient at detecting plagiarism, yet I don't know of any system that can score a piece of work on its *scientific soundness*.

Is there any ongoing work related to this? I found out about Semantic Publishing whilst composing this question, but I have no idea what other approaches, if any, are being actively worked on.

# Answer
This is a complex issue that affects all areas of science but has been getting higher visibility as the mainstream media has reported some cases in headlines. An answer seems to be better review systems. However, one might argue that nonsense papers are not *necessarily* a failure of the peer review system. All peer review systems must be human to some degree and all human systems are fallible/ subject to failure. any peer review system will have both *false positives* and *false negatives* in the sense of papers that were accepted but shouldnt be on 2020 hindsight, and papers that were rejected but were of acceptable quality. There is some increasing awareness/ sociological study of peer review systems. Cyberspace can in fact aid the process in some ways by increasing reviewers, increasing visiblity of reviews, adding rating systems, etc. and it can have downsides such as computational ease of creating fake submissions, increased AI capabilities to fool humans, etc.

An example of a CS specific peer review (meta-) analysis can be found in the recent NIPs experiment where peer reviewers were split into two groups, the same papers were given to each, and the overlap in acceptance/ rejection decision was measured. not unsurprisingly to many, results had quite high variance. Researchers overcome "false negatives" by resubmitting papers to other conferences. Unfortunately this NIPs experiment never seemed to be documented except across a lot of CS blogs and there is already some "link rot" of key links. It was announced informally at the conference and many insiders blogged on it including those participating. A full documentation might be considered "airing dirty laundry".
> 2 votes

---
Tags: machine-learning, semantics, natural-language-processing
---


# Question
Title: Complexity of special instance of Knapsack
Consider the following algorithmic task:

Given: primes $p\_1,\dots,p\_k$, and positive integers $e\_1,\dots,e\_k$, and a positive integer $M$
Find: integers $d\_1,\dots,d\_k$ that maximize $\prod\_i p\_i^{d\_i}$, subject to the requirements that $0 \le d\_i \le e\_i$ and $\prod\_i p\_i^{d\_i} \le M$.

What is the complexity of this problem? Is it NP-hard?

This problem is equivalent to the following:

Given: primes $p\_1,\dots,p\_k$, and positive integers $e\_1,\dots,e\_k$, and a positive integer $M$
Find: integers $d\_1,\dots,d\_k$ that maximize $\sum\_i d\_i \log p\_i$, subject to $0 \le d\_i \le e\_i$ and $\sum\_i d\_i \log p\_i \le \log M$.

This can be seen to be an instance of bounded knapsack with $k$ items, where the $i$th item has weight $\log p\_i$ and value $\log p\_i$ and can be used at most $e\_i$ times, and where the capacity of the knapsack is $\log M$. (See the footnote below for a more careful statement.) Thus, my problem is a special case of bounded knapsack. It follows that my problem is in NP.

But is my problem NP-hard?

For instance, is there a way to reduce from bounded knapsack to my problem? It's not clear, because my problem limits the weights and values to be something specific related to the log of primes, rather than arbitrary values.

---

Footnote: strictly speaking, the bounded knapsack requires item weights and values to be integers, whereas $\log p\_i$ isn't an integer. However, we can fix this up by picking a sufficiently large constant $K$ and using $\lfloor K \log p\_i \rfloor$ as the weight and value of the $i$th item, and use $\lfloor K \log M \rfloor$ as the capacity of the knapsack. With this fix-up, my problem now becomes a special case of bounded knapsack, or reduces to bounded knapsack.

# Answer
Your problem is at least as hard as the known-prime-factor version of this problem. Shor's reduction also applies to that version, and can be made effective by using this answer rather than the Wikipedia link in Shor's answer.
> 1 votes

---
Tags: algorithms, optimization, np-hard
---


# Question
Title: Algorithm for generating coprime number sequences?
Does anyone know of an algorithm to generate a set of numbers of size $N$ which are all co-prime to eachother?

Ideally I'm looking for something that has random access abilities so i could ask for the 100th item in the set without having to first calculate items 0 to 99.

Also, I would like to be able to specify a minimum value for these numbers, to specify that none of them should less than 50 for example.

Does anyone know of an algorithm to do this, or at least satisfy part of my asks?

Thanks!

# Answer
Yes. It's possible to satisfy all of your requirements, by combining some standard tools:

* Let $F$ be a function that, given a sequence of random bits as input, outputs a random 1000-bit prime. $F$ can be implemented by repeatedly picking a random 1000-bit number, then using a primality test to check if it is prime, and outputting the first prime number you see.
* Let $G$ be a pseudorandom generator that expands a short random seed to a long sequence of pseudorandom numbers, e.g., AES-CTR mode.
* Let $H$ be a cryptographic hash function, e.g., SHA256.
* Let $s$ be a random seed.

Now define

$$f(i) = F(G(H(s,i))).$$

Then the sequence

$$f(1),f(2),f(3),f(4),f(5),\dots$$

satisfies all of your requirements:

* Every number in the sequence is prime, and it is super-unlikely that any prime will repeat (this can be quantified using the birthday paradox), so all of the numbers in the sequence are co-prime.
* It is super-unlikely that any number will be less than 50. If you prefer an absolute guarantee, you can tweak the definition of $F$ to require that the number is both prime and at least your lower bound.
* The sequence can be efficiently computed: each of the building blocks $F,G,H$ has efficient instantiations, so $f$ can be computed efficiently. Moreover, this construction permits efficient random access into the sequence.
> 2 votes

---
Tags: sets, primes
---


# Question
Title: $k$th Largest Algorithm in a range $[k, k+c]$
The well-known algorithm for computing the $k$-th largest element in an unsorted array of size $n$ runs in $O(n)$ time.

How about for a range $\[k, k+c\]$, where $c$ is not necessarily independent of $n, k$? The obvious "brute-force" algorithm is to find the $k$th largest using the original $O(n)$-time algorithm, then the $k+1$-th largest the same way, ..., find the $k+c$-th largest (and also, the algorithm outputs these in sorted order). However, this takes $O(nc)$ time, and $c$ can possibly be $\Theta(n)$, which can lead to an $O(n^2)$ algorithm. In this case, we could have just sorted the array and extracted the elements, which takes $O(n \log n)$ time.

Is there a better (known) way of doing this? I can't find any references online.

# Answer
> 2 votes
Step 1. Use QuickSelect to find the $k$th largest number in the array. Call it $x$.

Step 2. Use QuickSelect to find the $k+c$th largest number in the array. Call it $y$.

Step 3. Find all elements in the array that are at least $x$ and at most $y$. This can be done by simply iterating over the array and comparing each element to $x$ and $y$.

Each step can be done in $O(n)$ time. Therefore, the total running time is $O(n)+O(n)+O(n) = O(n)$ time.

---
Tags: algorithms, selection-problem
---


title: How to reduce this regular expression?

text:
# Question
Title: How to reduce this regular expression?
I was converting a DFA to regular expression with the help of state equations and came up with this regular expression. How do I further reduce this regular expression? $$b+aaa^\*b+abb^\*+a$$ I can feel it's same as $$a^\*b+ab^\*$$ but how do I proceed to simplify the first one to the second mathematically?

# Answer
Minimizing a regular expression is PSPACE-hard. Therefore, if you're looking for a general set of techniques to minimize a regular expression, there's no good solution: there is no good set of techniques that always works and is always efficient. See https://cs.stackexchange.com/a/12278/755 and https://cs.stackexchange.com/a/43863/755 and https://cstheory.stackexchange.com/q/12361/5038.

Of course, none of these results rule out the possibility of techniques that work for your particular example or that sometimes work. However, they show that you shouldn't expect any general technique, i.e., any technique that works for all regular expressions and always gives the optimal answer and is asymptotically efficient.

---

That said, there are some ad-hoc methods you can use. For instance, by staring at it, you can quickly recognize that

$$abb^\* + a = ab^\*,$$

since $ab^\* = a(b^\*) = a(\varepsilon + b b^\*) = a + abb^\*$.
> 1 votes

---
Tags: regular-expressions
---


title: Relative Importance in Graph Theory

text:
# Question
Title: Relative Importance in Graph Theory
I am working on an algorithm that ranks a set of nodes in a graph with respect to how relative this node is to other predefined nodes (I call them query nodes). The way how the algorithm works is similar to recommendation algorithms. For instance, if i want to buy an item from an online store, the algorithm will look at my preferences (and/or history of purchased items) and recommend new items for me. Applying this to graph theory, the set of nodes are items and my preferred items are the query nodes. The problem am facing right now is how to benchmark my results (i.e. I want to run recall and precision on my results) but I don't have a ground truth data. My question is: does anyone know a benchmark for this problem, if not, how do you think I can evaluate my results.

**Note:** My algorithm has nothing to do with recommendation algorithms (i.e. the application is different), but I gave this to deliver the general idea of the RELATIVE IMPORTANCE algorithms. I am looking for any dataset with benchmark that may help me in this context.

**Edit:** Based on some requests, I will explain my algorithm with more details. The algorithm takes as input: graph (can be directed or undirected, weighted or unweighted), and a set of query nodes (included in the graph). **The algorithm will try to rank the nodes in the graph according to their importance with respect to the query nodes**. The importance of a node increases as the relationship between it and the query nodes increases. Depending on the application, this relationship is quantified by a value (the weight of an edge) that reflects the level of association between two nodes. For instance, in the DBLP co-authership dataset, the relation between two nodes is the number of common papers between the two nodes (authors). Therefore, in this case, the algorithm will rank the authors in the DBLP graph according to how close they are to all query nodes (the predefined authors). I hope that this is clear.

Thank you

# Answer
> 1 votes
You can for instance take as *ground truth data* the movielens dataset, remove some rating links between users and movies. You can rank your algorithm by counting the number of link that you can guess right. Usually machine learning algorithm also guess the rating score.

# Answer
> 0 votes
The answer is: you can't. You cannot evaluate your results or your algorithm without ground truth data. The quality of your predictions is "the accuracy of your algorithm, when run on real-world data". This means that the only way you can evaluate the quality of your predictions is by looking at how accurate they are on realistic, representative data sets. This requires ground truth. If you don't have ground truth data, your first step is to acquire ground truth data -- without it, you're stuck.

Evaluating on randomly generated graphs is not a substitute for ground truth data. If you evaluate on synthetic data, all you learn is how accurate your algorithm is on synthetic data, but you have no way of knowing whether the synthetic data is representative of real-world data, so this might not tell you anything about how accurate your algorithm will be on real data. There's no free lunch.

---
Tags: graphs, data-sets, recommendation-systems, benchmarking
---


# Question
Title: Simulating continuous time semi-Markov state machine and changing transition probability on the fly
The problem that I'm trying to solve (well, I think that I almost did, but need a review from someone more experienced) is about changing probability of the transition for semi-Markov state machine during simulation.

Let's assume that `M=<S,T>` defines machine with `S` states and `T` probabilistic transitions between states. Elements of `T` are triplets `(s_out, s_in, lambda)`. So the probability of moving from state `s_out` to `s_in` is exponential and defined as `exp(-lambda*t)`.

To simulate it I get random value from `[0;1)`, transform it to exponential and save as next event. What happens is that after saving it but before invoking another event may occur (so it is not a pure Markov state machine) and change the lambda. So the event time should be recalculated.

The problem is that it cannot be just recalculated as such changes may occur quite frequently constantly shifting the event time to the future.

What I think is correct is to adjust recorded event time on ratio `time_to_event_from_now * lambda_old / lambda_new`. Does it sounds right to you? Maybe the problem description recalls the paper/book where this problem solved?

# Answer
As it happens, recalculating the event time *is* exactly the right thing to do. This follows from the fact that the exponential distribution is memoryless; or from the fact that exponential distribution is the time until the next event in a Poisson process. I realize this might sound miraculous and unbelievable, so let me explain why, in detail.

Let's suppose that at time $t\_0$ you have lambda equal to $\lambda\_0$; then at time $t\_1$, lambda changes to the value $\lambda\_1$. In other words, at every point in the time interval $\[t\_0,t\_1)$, the value of lambda is $\lambda\_0$; at every point in the time interval $\[t\_1,t\_2)$, the value of lambda is $\lambda\_1$.

You are simulating a Poisson process with parameter lambda. During the time interval $\[t\_0,t\_1)$, the Poisson process has parameter $\lambda\_0$. During time interval $\[t\_1,t\_2)$, the Poisson process has parameter $\lambda\_1$. You want to simulate this process. In particular, you want to simulate the time of the first event.

The brute-force way to simulate this process would be to divide time up into very small increments, say of length $\epsilon$, so that time is broken up into small intervals $\[t\_0,t\_0+\epsilon)$, $\[t\_0+\epsilon,t\_0+2\epsilon)$, $\[t\_0+2\epsilon,t\_0+3\epsilon)$, ..., $\[t\_2-\epsilon,t\_2)$. In each interval, you have a value for lambda: its value is $\lambda\_0$ for the first $(t\_1-t\_0)/\epsilon$ small intervals and $\lambda\_1$ for the next $(t\_2-t\_1)/\epsilon$ small intervals. In each small interval, you draw from a Poisson distribution with parameter $\lambda \epsilon$ (i.e., $\lambda\_0 \epsilon$ or $\lambda\_1 \epsilon$, depending upon whether the small interval falls before or after $t\_1$). Because $\lambda\_i \epsilon$ will be a very small value, this is essentially equivalent to flipping a biased coin for each small interval; with probability $\lambda\_i \epsilon$, you say that the event has happened in that small interval, and with probability $1-\lambda\_i \epsilon$ nothing happens in that small interval.

Thus, this gives you a brute-force strategy to simulate your process. This brute-force strategy *will* give you the right distribution of events. However, it has the disadvantage that it is computationally expensive: it requires $(t\_2-t\_0)/\epsilon$ coin flips.

Fortunately, there is an equivalent way to do it that yields the same distribution of events, but is much more computationally efficient. Here is the optimized strategy for how to simulate the time of the first event:

* Randomly draw a value $d$ from the exponential distribution with parameter $\lambda\_0$. If $d\<t\_1-t\_0$, then output that the first event happens at time $t\_0+d$.
* Otherwise (if $d \ge t\_1-t\_0$), randomly draw a value $d'$ from the exponential distribution with parameter $\lambda\_1$ (independent of $d$). Now, if $d'\<t\_2-t\_1$, then output that the first event happens at time $t\_1+d'$; otherwise, output that no event happens during $\[t\_0,t\_2)$.

This optimized strategy lets you simulate the time of the first event. (If you want to simulate the time of all events in the interval $\[t\_0,t\_2)$, you can simulate the time of the first event, if any, and then iterate to figure out the time of the next event if there was a first event, repeating until done.) It is efficient, as you can see.

Moreover, this optimized strategy gives the correct distribution. It is equivalent to the brute-force method described above: it gives the same distribution on the time of the first event (as $\epsilon \to 0$). The equivalence follows from the fact that, if you have a Poisson process with parameter $\lambda$, then the time of the first event is exponentially distributed with parameter $\lambda$. (See Wikipedia.)

Finally, you can note that my optimized strategy is *exactly equivalent* to recalculating whenever lambda changes. It follows that recalculating whenever lambda changes *does* give you the right answer. Amazing, huh?

Don't expect this to work for all distributions. This is a special property of the exponential distribution.
> 1 votes

---
Tags: probability-theory, simulation, markov-chains
---


# Question
Title: Could my algorithm be considered Divide-and-Conquer?
So for my homework, I was supposed to design an algorithm which was divide-and-conquer that fulfilled the task of finding the two smallest numbers in an array of size n.

I recognize that my version is a bit cheap in that regard, in that it uses reference variables and only does work on the size 1 cases of the recursion. Is this still technically considered divide-and-conquer? Or is it practically too close to a linear search. If it is divide-and-conquer, how could you express the recurrence relation when the work is being done only on the "leaves" of the recursion.

```
   find_mins(int A[], int& min, int& sec_min, int l, int r){
    int pivot = (l+r)/2;

    if(l==r){
      if(A[l] < min){
        sec_min = min;
        min = A[l];
        return;
      }
      else if(A[l] < sec_min && A[l] > min){
        sec_min = A[l];
        return;
      }
      return;
    }

    find_mins(A,min,sec_min,1,pivot);
    find_mins(A,min,sec_min,pivot+1,r);

}

"Pseudocode"

FUNCTION(Array, min1, min2, left, right)
  Find pivot
  if(size of subproblem is 1)
    calculate mins
  function(Array,min1,min2,1, pivot)
  function(array,min1,min2,pivot+1,right)

```

Keep in mind, the code really isn't all that relevant, I just am curious if the structure fits divide-and-conquer description. My concern is that because work is only being done on the case where the size is 1, that it's more of a "linear search" than anything else.

# Answer
# TL;DR

Divide and concur doesn't have any rigorous definition. So any argument you make for or against will be just an emotional argument. The situation is made worse by the fact that the task accomplished by this algorithm doesn't need D&C. So, the answer is "probably".

# Long version

One scenario where it would make sense to use D&C in finding the minimum is a distributed system (eg. Hadoop), where the size of input may require from you that you do computation in chunks. The algorithm as you designed it is not suitable for this task because it would have to communicate the best result found so far to all parts of the program handling the computation of each chunk. The version I've written below eliminates this problem by computing local minima for given sublists and then calculating the minima of the previously computed minima and so on. This feels (remember emotional argument?) more like D&C. Besides, it makes the algorithm more language-agnostic and eliminates the corner-case errors.

1. Empty lists have no minimum.
2. Lists with only one element have only one minimum (not two).
3. If a list happens to have more than one minimum element, then the second minimum will be equal to first minimum.
4. Solution doesn't require guessing the minimum before running the algorithm.

The code is set in Prolog. I believe it is better than conventional pseudo-Pascal in that it allows to avoid "uninteresting" parts of the algorithm.

```
two_mins([], _, _) :- !, fail.  /* Empty list has no minimum */
two_mins([Min1], Min1, _) :- !. /* There is only one element */
two_mins([Min1, Min2], Min1, Min2) :- Min1 < Min2, !.
two_mins([Min1, Min2], Min2, Min1) :- !.
two_mins(List, Min1, Min2) :-
    length(List, N),
    LenA is N div 2,
    length(A, LenA),
    append(A, B, List),
    two_mins(A, Min1A, Min2A),
    two_mins(B, Min1B, Min2B),
    Min1 is min(Min1A, Min1B),
    /* In case A or B had only one element, we will get
       rid of non-instantiated solutions. */
    include(ground, [Min2A, Min2B], Ground),
    min_list([max(Min1A, Min1B) | Ground], Min2).

```
> 2 votes

---
Tags: algorithms, divide-and-conquer, algorithm-design
---


title: Church-Turing thesis is a dualism

text:
# Question
Title: Church-Turing thesis is a dualism
Church-Turing thesis : Every **effectively** calculable function is a TM-computable function.

But, hypercomputation models are strictly more powerful than TM and can solve TM-uncomputable problems on the paper.

Does this imply that, for one who believes in the Church-Turing thesis, there is only two options :

1. There is two distincts worlds : The **effective** one (where Church-Turing thesis applies) and the paper one (where Church-Turing thesis doesn't apply necessarily). That is the physical world and the ideas world of the classical dualism theory.
2. All the hypercomputation models are inconsistent. Using an hyper-TM in a reasoning is the same than, for instance, using an integer both even and odd in a reasoning, this can lead to false conclusions.

?

# Answer
There's another possibility: hypercomputation is not implementable in the real world, and is only an imaginary/theoretical concept. If this is the case, then there is no contradiction with the Church-Turing thesis.

Of course, anyone can invent imaginary worlds where strange things are true. For instance, there's the computer scientist's Superman: not only can he leap tall buildings in a single bound, he can also solve undecidable problems in his head! I suppose one could imagine such a thing, but that doesn't mean it has any correspondence to the real world, and the possibility of imagining such a Superman doesn't contradict the Church-Turing thesis. The study of hypercomputation can be thought of as asking, well, ok, so Superman might not be real, but *what if he were*?

The Church-Turing thesis is a hypothesis about the real world, so imaginary schemes that can't be implemented in the real world don't contradict it.
> 8 votes

# Answer
The Church–Turing thesis only purports to describe the types of processes that qualify as “computational”. It does not assert that “hypercomputational” processes are mathematically inconsistent. Most widely accepted formalizations of mathematics do allow us to define and reason about noncomputable functions.

Some take “computation” to mean “process that can be performed on a Turing machine”. In that view, the Church-Turing thesis is just a definition of the word “computation”, and does not really claim anything.

Some take “computation” to mean “process that matches our intuitive understanding of an algorithm”. In that view, the Church-Turing thesis is just an encoding of our intuition, and its only claims are about what our intuition says.

Some take “computation” to mean “process that can be performed in the real world”. In that view, the Church–Turing thesis becomes a much stronger assertion, but it’s an assertion about *physics*, not about computer science. It asserts that we cannot build a device capable of hypercomputation within our physical universe. There’s still no reason to think that such a device would be inconsistent with itself mathematically.

(In fact, it’s not even obvious whether such a device would be inconsistent with known theoretical physics—see Malament–Hogarth spacetime. And there’s still a lot about physics that we don’t know. It’s possible that new physics could establish that the universe itself has a Turing-computable model, in which case the Church–Turing thesis would be true. It’s just as possible that some new phenomenon allows us perform real hypercomputation and the Church–Turing thesis would be false.)
> 5 votes

# Answer
No, you are confused.

Turing machines and Hypercomputation are both mathematical models, and they are both consistent because we can build mathematical models in which all functions are Turing computable, as well as models in which hypercomputable functions exist. These are of course different models. There is no mystery about having a lot of mathematical models of various theories, for instance, there are models of both euclidean and non-euclidean geometry.

The mathematical theory of computation should not be confused with "the real world". This is a bad thing to do because Turing machines are a piece of mathematics. Do you also think that infinite straight thin lines really exist in the physical world? Or maybe that they are slightly bent because of gravity?

Church's thesis is a piece of *premathematical* or *philosophycal* analysis which essentially says "Turing's mathematical definition of computation correctly models what can actually be computed in the real world". This is not a mathematical statement.

In one of the comments you made the following faulty line of reasoning: *"... that imaginary worlds are from our mind and, since our brain is physical, that imaginary worlds are part of the physical world."* To see why this makes no sense, consider a similar line of reasoning: *"Yesterday I imagined a fairy with golden wings, and since the fairy was in my mind, and my brain is physical, the fairy is part of the physical world"*. The problem is that you are confusing the thoughts in your mind with their physical representation (the electro-chemical functioning of your brain).

A Belgian artist put it very eloquently:
> 5 votes

---
Tags: computability, church-turing-thesis, philosophy, hypercomputation
---


# Question
Title: Easiest improvement on first-fit for bin packing algorithm
See the interactive example here. First-fit on the left, optimal on the right.

I know that in general, optimal bin-packing is NP-hard, so I'm not looking for a perfect solution. I'm looking for the lowest cost improvement over the current solution.

The problem is the one most of the web pages on the internet have: **How to best pack a set of rectangles into an enclosing rectangle, preserving order, with no overlaps.** Actually the enclosing rectangle is only a fixed width, it expands to arbitrary height needed to fit all the rectangles, but we still want everything aligned along the top.

Real web browsers do it by relying on a rather restrictive set of rules, one of the most significant of which is that the items are presented in a given order and that order must be maintained when laying out the items in the same way text is laid out, which for English is left-to-right, top-to-bottom.

For some cases, though, such as a set of images, **the order could be changed somewhat in order to achieve better packing**. We do want to limit the reordering, so that an item ends up no more than *n* places out of position, but we don't need *n* to be zero.

A web library called Packery implements this with a basic first-fit algorithm. With "gravity" pulling the rectangles to the top-left, it places the first item where it will fit, which of course is the top-left of the enclosing rectangle. It then places the next item where it will fit, and so on, until all the items are placed.

This works very well when the rectangles are all related by small integers, e.g. 1x1, 1x2, 1x3, 2x1, 2x2, 2x3, 3x1, 3x2, 3x3, with the enclosing rectangle being some integer width, and there are enough small rectangles. In our example the outer rectangle is 3 units wide. Our inefficient packing algorithm on the left becomes optimal on the right with the addition of just 2 more rectangles that match the voids.

So the question is: is there a low-cost way to detect the inefficient packing and backtrack or make some other alteration to get to the efficient packing in the middle? Keep in mind that we want to preserve order as much as possible, so the optimization of pre-sorting the list so that the largest rectangles are first is not acceptable.

# Answer
> 1 votes
One "easy" option is to, after the first-fit algorithm has run, do a local search, i.e. checking if there are any `k` swaps / moves that you can do to improve the packing (i.e. removing a row or column) (for a relatively small value of `k`).

I also suspect, although this isn't rigorous by any stretch of the imagination, that you could, to a specified maximum depth, do a search-and-backtrack with the current element and next element every time you hit an element that is larger than the next element. In this case, for instance, you have the elements `[1x1, 2x1, 1x1, 1x2, 1x3]`. You specify a maximum depth, say 1. Then you start packing elements. In this case just packing \[1x1\] so far. When you hit the `2x1`, you try packing `[2x1, 1x1, 1x2, 1x3]`, , but you also branch and try packing `[1x1, 2x1, 1x2, 1x3]`. Ideally with an alpha-beta search, but you can also just try going to a specified lookahead and then seeing which is better.

Also, note that that particular packing library has... issues. In particular, when you tell it to pack `[1x1, 1x1, 2x1, 1x2, 1x3]` it does this:

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


title: Is chess game movement TM decidable?

text:
# Question
Title: Is chess game movement TM decidable?
If we have a finite chess board and two figures x and y. Is it possible to get y from x by following chess rules and when white is y and white starts from y placement. Is this decidable?

My reasoning is, that we have a finite sets of moves and since all finite languages are decidable and at some point x is going to get y this problem is decidable. What do you think?

# Answer
> 6 votes
The chess board problem is, although complex, a **finite** problem. Specifically, the number of moves, starting from any board position, is finite.

Then, a TM can just go over all the possible moves (there are only $C$ such moves, for some "small" constant $C$), and verify if a certain position is feasible continuation of a prior position. Hence, any such question is decidable.

---
Tags: turing-machines, automata, undecidability, decision-problem
---


# Question
Title: How do I output a single pixel on the monitor using assembly language?
I want a low-level understanding of how a pixel is displayed on a monitor.

I am guessing that the point at which I want to display a pixel must be modified in the frame buffer, which should be sent as a signal to the monitor. But, on low level, how do I find out what part of memory represents the frame buffer? I also guess that the monitor contains circuitry that decodes a signal and displays pixels on the monitor.

So, I basically want to know what happens underneath a Graphics API call like setpixel(x, y).

# Answer
It depends on the screen, and other devices in the chain (for instance, is the screen connected by VGA cable, or HDMI, or directly to the memory via a DMA access, etc.), so your question is too broad to answer per se.

Just to give a superficial answer, when someone builds a computer, a common practice is to reserve a segment in the memory that "reflects" the screen (i.e., each cell in this memory represents a pixel). The exact location of this segment may vary. Then, according to the way the screen is connected to the "computer", one needs to repeatedly "read" that segment and load its content to the "screen".

For instance, the graphic card may read this content, convert it into a VGA signal and output it on the VGA output (which is then "read" by the screen, which presents the pixels according to the content).
> 1 votes

---
Tags: graphics
---


# Question
Title: Kolmogorov complexity of strings in a given language
Consider the language

$$L = \\{1^i 0^j 1^k \mid i + j = 2k, k ≥ 1\\}\\,,$$

and let $x\_n$ be the canonical $n$'th word in $L$. My problem involves proving that the Kolmogorov complexity of $x\_n$ can be bounded by

$$K(x\_n) \leq c + 2\log\_2 |x\_n|$$

for some constant $c$.

***My ideas :***

(please note that I'm not writing this in a formal way, I am neglecting some constants/factors)

we want to be able to compress the string given by x\_n above, thus we could set :

$$K(x\_n) = K(1^i) + K(0^j) + K(1^k)$$

(to do this compression I evaluate that only i, j and k need to be compressed, thus we only consider the length of the binary representation of i,j and k as the upper-bound of their corresponding Komolgorov Complexity)

$$ \leq log\_2 (i) + log\_2 (j) + log\_2 ((i+j)/2) + C$$

$$ = log\_2 (i) + log\_2 (j) + log\_2 (i+j) - 1 + C$$

$$ = log\_2 (i^2j + ij^2) + K$$

Now we might want to evaluate the length of X\_n $$|x\_n| \leq i + j + k = i + j + (i + j)/2$$

now to show the supposition we just need to show that :

$$ log\_2 (i^2j + ij^2) \leq 2log\_2 |x\_n| = log\_2 (|x\_n|^2) $$

and this is where I get stuck

# Answer
You haven't explained what is meant by the *canonical $n$th word*, but I assume that there is an algorithm generating all words in $L$, and the canonical $n$th word is just the $n$th word in this list. One such algorithm could go over all possible words in size-lexicographic order, and check for each word whether it belongs to $L$, outputting the words that are in $L$ in size-lexicographic order.

Given such an algorithm, you can construct a new algorithm which gets $n$ and outputs $x\_n$. Using the new algorithm, you can generate $x\_n$ by running the new algorithm on the input $n$. Since the new algorithm is fixed, it has some size $C$. A prefix-free encoding of $n$ takes $2\log n$ (in fact, you can do almost twice as good), leading to a description length of $C + 2\log n$. (Depending on your definition of Kolmogorov complexity, you might be able to do away with prefix-freedom, and then you can replace $2\log n$ with $\log n$.)

Note that we have only used the fact that the canonical $n$th word is generated by some algorithm which gets $n$ as input. The particular form of $L$ wasn't important.
> 0 votes

---
Tags: complexity-theory, kolmogorov-complexity
---


title: What is token-type in Lexical analysis?

text:
# Question
Title: What is token-type in Lexical analysis?
I'm currently studying compiler construction book "Compilers Principles, Techniques, and Tools (2nd Edition)" , in page unit 3.1 , page 113 , example 3.2 .

i cannot understand what is this kind of method ?

> E = m * 2;
>
> conversion to **token types(this method)** below

```
<id , E> <op=> <id , m> <op*> <number , 2> <op;>

```

it is token-type pairs ? or is there any technical term associated ?

# Answer
> 3 votes
I don't know what is the proper name for what you're seeing, but it is the standard way to lexically analyze text. You divide it into tokens of specific types. For the sake of context-free parsing (the next step in the parsing chain), you only need the *type* of each lexeme; but further steps down the road will need to know the semantic content (sometimes called *annotation*) of each lexeme. For example, the context-free parser doesn't care which number $2$ is; it only needs to know that it's a number. Further down the road, it will suffice to know that this number is an *integer*. Even further, you would need to know that this integer is specifically $2$.

Some lexemes are *atomic*, for example the various operators (though in principle we could group, say, + and - together). We need to separate them because syntactically = is different from +, and + is different from * (due to operator precedence). These don't need any annotation.

---
Tags: terminology, compilers, lexical-analysis
---


title: The Space of an Unsatisfiable Formula

text:
# Question
Title: The Space of an Unsatisfiable Formula
I am reading the paper *Measuring the hardness of SAT instances* by Ansótegui, Bonet, Levy and Manyà (Proc. 23rd AAAI Conf. on AI, pp. 222–228, 2008) (PDF). I am trying to understand the demonstration of the last part of the Lemma 3 (in bold). For this, I get an example. Let be $\Gamma = (a+b)(a+b')(a'+c)(a'+c')$ then its tree-like refutation is:

Following the demonstration of the last part of the Lemma 3, $\[b\rightarrow 1\]\Gamma=(1)(a)(a'+c)(a'+c')$, and adding the literal $b'$ where $\[b\rightarrow 1\]$ has removed it, we get $\Gamma' = (1)(a+b')(a'+c)(a'+c')$. In accordance the paper the tree-like refutation of $\Gamma'$ is a proof for $\Gamma \vdash b'$. The natural question, I think so, How it is posible that the tree-like refutation of $\Gamma'$ be a proof for $\Gamma \vdash b'$ if $\Gamma \neq \Gamma'$?.

> **Lemma 3** The space satisfies the following three properties:
>
> 1. $s(\Gamma \cup \\{\Box\\})$ = 0
> 2. For any unsatisfiable formula $\Gamma$, and any partial truth assignment $\phi$, we have $s(\phi(\Gamma))\leq s(\Gamma)$.
> 3. For any unsatisfiable formula $\Gamma$, if $\Box\notin\Gamma$, then there exists a variable $x$ and an assignment $\phi\colon\\{x\\}\to\\{0,1\\}$, such that $s(\phi(\Gamma))\leq s(\Gamma)-1$.
>
> **The space of a formula is the minimum measure on formulas that satisfy (1), (2) and (3). In other words, we could define the space as:3**
>
> **$$s(\Gamma) = \min\_{x, \overline{x}\in\Gamma, b\in\\{0,1\\}} \big\\{ \max\\{s(\[x\mapsto b\](\Gamma))+1, s(\[x\mapsto\overline{b}\](\Gamma))\\}\\;\big\\}$$** **when $\Box\notin\Gamma$, and $s(\Gamma\cup\\{\Box\\}) = 0$**.

# Answer
> 4 votes
Here is the original refutation:

1. From $a'+c$ and $a'+c'$ deduce $a'$.
2. From $a$ and $a'$ deduce $\square$.

When you add $b'$ back, you get:

1. From $a'+c$ and $a'+c'$ deduce $a'$.
2. From $a+b'$ and $a'$ deduce $b'$.

More generally, since the only difference between $\Gamma$ and $\Gamma'$ is the addition of $b'$, it is not hard to prove by induction that for every line $\ell$ proved in the refutation of $\Gamma$, the corresponding line in the corresponding $\Gamma'$ proof is either $\ell$ or $\ell+b'$. Hence the $\Gamma'$ proof proves either $\square$ or $b'$. It can happen that it indeed proves $\square$, in which case we can deduce $b'$ by weakening, which is an *admissible rule* for resolution space (we can get rid of it without increasing the space).

---
Tags: satisfiability
---


# Question
Title: Algorithm to minimize surface area, given volume
Consider the following algorithmic task:

Input: a positive integer $n$, along with its prime factorization
Find: positive integers $x,y,z$ that minimize $xy+yz+xz$, subject to the restriction that $xyz=n$

What is the complexity of this problem? Is there a polynomial-time algorithm? Is it NP-hard?

---

This problem basically asks: out of all rectangular solids whose volume is $n$ and whose dimensions are all integers, which one has the least surface area?

This problem was posed by Dan Meyer, under the title The Math Problem That 1,000 Math Teachers Couldn’t Solve. So far none of the math teachers he worked with has found a reasonable algorithm for this problem. In his context, the definition of "reasonable" is a bit imprecise, but as computer scientists we can ask a more precise question about the complexity of this problem.

The obvious approach is to enumerate all possibilities for $x,y,z$, but that takes exponential time. Commenters at Dan Meyer's blog have proposed many efficient candidate algorithms that unfortunately all turned out to be incorrect. Martin Strauss suggests that this problem seems vaguely reminiscent of 3-partition, but I can't see a reduction.

---

Let me also clear up some misconceptions that I've seen in the comments/answers:

* You can't reduce from 3-partition by simply replacing each number $q$ with its power $2^q$, as the objective functions of the two problems are different. The obvious reduction simply doesn't work.
* It is not true that the optimal solution involves picking one of $x,y,z$ to be the nearest divisor of $n$ to $\sqrt\[3\]{n}$. I see multiple people who are assuming this is case, but in fact, that is not correct. This has already been disproven on the Dan Meyer blog post. For instance, consider $n=68$; $\sqrt\[3\]{68} \approx 4$, and 4 divides 68, so you might think that at least one of $x,y,z$ should be 4; however, that is not correct. The optimal solution is $x=2$, $y=2$, $z=17$. Another counterexample is $n=222$, $\sqrt\[3\]{222}\approx 6$, but the optimal solution is $x=37$, $y=3$, $z=2$. (It *might* be true that for all $n$, the optimal solution involves making at least one of $x,y,z$ be equal to either the smallest divisor of $n$ larger than $\sqrt\[3\]{n}$ *or* the largest divisor of $n$ smaller than $\sqrt\[3\]{n}$ -- I don't have a counterexample right now -- but if you think this statement is true, it would need proof. You absolutely cannot assume it is true.)
* "Make $x,y,z$ be the same size" does not appear to necessarily yield the optimal answer in all cases; see Dan Meyer's blog post for counterexamples. Or, at least, for some reasonable interpretations of the phrase "make them roughly the same size", there are counterexamples showing that this strategy is not in fact optimal. If you want to try some strategy of that sort, make sure that you state the claim precisely and then provide a careful mathematical proof.
* A running time of $O(n^3)$ is not polynomial. For this problem to be in P, the running time must be a polynomial in the *length of the input*. The length of the input is something like $\lg n$, not $n$. The obvious brute-force algorithm can be made to run in $O(n^3)$ or $O(n^2)$ time, but that is exponential in $\lg n$ and thus counts as an exponential-time algorithm. Thus that is not helpful.

# Answer
Here is a modified version of a "choose divisor near cube root" algorithm. It still must brute force many cases, so I'm not sure how much of a real improvement it is speed wise over the enumeration of all cases. However, I submitted it as a correction to the algorithm on OEIS (that which generated incorrect results) because I believe it should be accurate at least.

Here is the algorithm to find (s1,s2,s3) and surface area of a rectangular prism given its volume n:

1. Given n, find the cube root.
2. Set an initial value integer s1 at the ceiling of that cube root.
3. Test to see if s1 is a divisor of n, and if not, reduce s1 by 1.
4. If a divisor s1 is found, set an initial s2 to be the ceiling of the square root of (n/s1).
5. Then test to see if s2 is a divisor of n/s1, and if not, reduce s2 by 1.
6. When a divisor s2 is found, s3 then is set to n/(s1\*s2).
7. The current surface area is calculated by 2\*(s1\*s2 + s1\*s3 + s2\*s3).
8. The current SA is compared against the current minimum. If its the first surface area calculated, it is stored as minSA. After the first, we test to see if the current SA is smaller than minSA, and if so, store it in minSA.

This algorithm enumerates some of the triples (s1,s2,s3) but needs only to test the divisors under the cube root. (Since not all three divisors can be above the cube root). In a similar fashion, s2 needs only to test divisors of n/s1 under the square root of n/s1, since not both divisors can be above the square root)

A note on step 3: if the cube root is a divisor then n is a cube and we can stop there with minimal surface area 6\*s1^2 from the box (s1,s1,s1).

Python:

```
import math
def minSArectprism(n):
    s1_0 = int(math.ceil(n ** (1 / 3.0)))
    minSA=-1
    s1 = s1_0
    while s1>=1:
        while n % s1 > 0:
            s1 = s1 - 1
        s1quot = int(n/s1)
        s2_0 = int(math.ceil(math.sqrt(n/s1)))
        s2 = s2_0
        while s2>=1:
            while s1quot % s2 > 0:
                s2 = s2 - 1
            s3 = int(n / (s1 * s2))
            SA = 2*(s1*s2 + s1*s3 + s2*s3)
            if minSA==-1:
                minSA=SA
            else:
                if SA<minSA:
                    minSA=SA
            s2 = s2 - 1
        s1 = s1 - 1
    return minSA

```
> 1 votes

# Answer
### Edit

Here’s an informal argument for why a fast algorithm is unlikely to exist. *That sentence hasn't changed,* but I’ve taken out what used to be here because it was structured too much like the formal proof in the next section and the discussion was getting sidetracked onto its bugs, some of which I noticed myself and one of which D.W. kindly pointed out to me. Let me instead try to express the intuition behind it.

The clever approaches to this problem seem to be focusing on finding ways to partition the prime factors of $N$ into three lists and quickly prune most of the combinations without needing to check them. So suppose this approach works, that is, it gives you a P-time algorithm for finding the optimal box.

What happens when we translate the same steps into a different algebra, such as addition and subtraction instead of multiplication and division? We know (see lemma below) that our algorithm will find a 3-partition whose *products* are equal, if one exists, or else determine that no such 3-partition exists. So, if we could translate the same techniques into the additive group, we could find a 3-partition whose *sums* are equal, or determine that no such partition exists. In other words, we could solve 3-partition in polynomial time. That’s not very plausible.

So, why might such an algorithm work for multiplication and fail for addition? One possible reason is that every integer has a unique prime factorization under multiplication, but is cyclic under addition. Another is that multiplication forms a ring with addition, so you have another set of operations you can use. Another is that you would have to generalize the algorithm to work for non-primes, and it might depend on their primality. The one D.W. pointed out is that the specific method of translation might exponentially increase the size of your inputs. And maybe P = NP after all.

But if those are the loopholes that let a fast algorithm work, I think it’s still useful to know, because it suggests where we should focus our efforts. We should be looking for something that would break if we tried to apply it to a NP-complete problem. An approach that would generalize to other algebras is probably barking up the wrong tree. I suspect, though, that multiplication is not really different enough for that to work, but that’s just a hunch.

### Lemma

Let $m = \sqrt\[3\]{N}$. For any solution $(am, bm, \frac{m}{ab})$, where $a$ and $b$ are positive, the weight of the solution is $(ab + \frac{1}{a} + \frac{1}{b})m^2$ and is minimized when $a = b = 1$.

**Proof:** We see immediately from the restriction $xyz = N$ that any arbitrary solution has this form.

Its weight is $(am)(bm) + (am)(\frac{m}{ab}) + (bm)(\frac{m}{ab}) = abm^2 + \frac{m^2}{b} + \frac{m^2}{a} = (ab+\frac{1}{a}+\frac{1}{b})m^2$.

Let $f(a,b) = ab + \frac{1}{a} + \frac{1}{b}$. To minimize this function, we take the partial derivatives $\frac{\delta f}{\delta a} = b - \frac{1}{a^2}$ and $\frac{\delta f}{\delta b} = a - \frac{1}{b^2}$. The critical point where these partial derivatives are zero comes where $a = b^2, b = a^2$, and therefore, since $a$ and $b$ must be real numbers greater than 0, $a = b = 1$. We see from the matrix of second-order partial derivatives that this is a global minimum.

My immediate motivation to prove this was to fill in a hand wave in my proof above that, if a perfect-cube solution exists, it is optimal. However, this formula could be useful for pruning the search tree.

### Assorted Thoughts

I don’t see any obvious symmetry except the interchangeability of x, y and z, which only gives us at best a constant factor of 6. We do have some speedups for the 2-partition that basically say we’d want both terms to be as close to each other as possible, but I don’t immediately see an application to this problem.

Off the top of my head, simply taking the log of all the numbers immediately reduces this to a classic 3-partition problem using addition, or equivalently, taking some number to the power of the numbers in any 3-partition addition problem turns it into a multiplication problem such as this. That implies this problem should not be any easier. We do have here the prime factorization, whereas that factorization would not be prime, but does that help us?

Graphically, the surface xyz = 0 would look like the union of the xy-, yz- and xz-planes, and for any positive n, the equation would look like y = n/xz, so each slice along a coordinate plane would be a hyperbola. We can generally say that the quantity we’re trying to minimize is lowest at the origin and grows most rapidly along the line where x = y = z. If we can search only along this manifold, we might be able to reduce to a two-dimensional problem.
> 0 votes

# Answer
The problem would of course be related to factoring complexity if prime decompositions were not given. Given the factors, and taking logs of all the prime factors, this problem appears to be about the same as minimizing the deviation-from-mean of $k$ partition sums (exercise, maybe either analytically or experimentally, find how closely this intuitive approximation of the problem holds).

Here this is the 3-way case (partition sums are $\log(x), \log(y), \log(z)$). the 2-way case has been extensively studied and is NP hard (from 1st ref). (This 2-way case is not quite the same as the known NP-complete 2-way Partition problem where partition sums are equal. Note equal partition sums implies 0 deviation in partition sums and *vice versa.*) The 2nd ref studies 3-way and $n$-way partitioning, partly empirically, where there is not as much study as the 2-way case.
> 0 votes

---
Tags: algorithms, optimization, integers
---


# Question
Title: Can high-order unification be applied to programming by example?
In 2007, it has been proven that high-order unification is decidable on the pattern matching case. If that is true, what is stopping someone to write an equation like:

```
(F [1,3,2], F [4,1,3,2], F[3,1]) = ([1,2,3], [1,2,3,4], [1,3])

```

If the unification works, wouldn't it probably find an `F` which implements a sorting algorithm - essentially generalizing the programming by example technique and, to an extent, replacing a programmer's job?

# Answer
> 3 votes
It's incredibly unlikely that a complete sorting algorithm that works for ANY input would be deduced from just 3 inputs.

In particular, there's a problem: sorting is a problem that matches an infinite set of inputs to an infinite set of outputs. You've only given a finite set of inputs, so there's an infinite number of problems which could be described by those input/output pairs.

For example, what if we want to sort numbers lexographically (i.e. dictionary order) instead of numerically? So 1, 11, 112, 1123, all come before 2. But, your example also describes lexographically sorting the given inputs. How does the algorithm know which one?

In short, it can't figure out that you want a sorting algorithm, because you haven't told it you want a sorting algorithm.

For that, you need a specification of some sort. The problem of "Given an arbitrary specification, find an algorithm that meets that specification" is undecidable.

So, there will never be a computer program which, 100% of the time, generates a correct algorithm solving any problem you give it.

It's possible that with machine learning, we can automatically derive some algorithms, but there will always either be a risk that those algorithms are incorrect, or there will be a risk that our procedure will say "I couldn't find a solution."

This is an unavoidable fact of mathematics.

---
Tags: algorithms, artificial-intelligence, unification
---


# Question
Title: Weak hashing function for memorable IPv6 addresses
IPv6 addresses in the form of `862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0` are much harder to memorize or even transcribe than the 4 octets of IPv4.

There have been attempts to mitigate this, making IPv6 addresses somehow more memorable.

Is there an intentionally-weak hashing function which could be reversed to find that the phrase, say, "This is relatively benign and easy to spot if the phrase is bent so as to be not worth paying" would hash to a target IPv6 address? The hash would, of course, have many colliding inputs to choose from, and a potentially more memorable sentence, such as this example phrase, could be automatically offered.

I guess there are two parts: First a weak hash with good distribution in both directions. Second is an algorithm for selecting memorable phrases from among the many collisions (short, consisting of words from a specified language, perhaps even following a simplified grammar).

Although the hash function would need to be weak, I don't doubt that the effort is still significant - however, once the phrase is known, the computation of the hash to the target address is very quick.

**EDIT**

I found this related idea, Piphilology, for memorizing some digits of π:

> How I wish a drink, alcoholic of course, after the heavy lectures involving quantum mechanics!

# Answer
> 2 votes
Take the IP address and a wordlist. Then turn the IP address into a list of words from the wordlist based on the digits of the address, base {length of wordlist}.

So, for instance, taking the diceware wordlist and your example, I get: `862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0` -\> `mew hades cup viii 72 grit photo pick raid dey` (or potentially the other way around, and/or padded on the other end).

Note this isn't lossy. Although you can relatively easily apply any lossy techniques to this. You may just wish to truncate the IP address, or only select every second bit or something before running it through this mapping.

# Answer
> -1 votes
It sounds like you have two use cases:

* Given a phrase, it will hash to a unique IPv6 address
* Given an IPv6 address, multiple phrases can hash to it (colliding inputs). Corollary: Given an IPv6 address, general multiple memorable phrases, which the user can choose from.

I believe you would have to roll your own solution here. IPv6 addresses are long enough that you probably have to use a function like SHA1 to be able to cover the address space.

To maximize the number of colliding phrases, you could try ignoring vowels, or the hundred most common words.

---
Tags: cryptography, computer-networks, hash, user-interface
---


title: A factoring conversion

text:
# Question
Title: A factoring conversion
There was a comment here that " It is possible in principle to reduce the factorization of a $256$-bit number (which is computable in TFNP) to the Permanent on a matrix of dimension $N\times N$ where $N\leq c\cdot256^c + c$ for some hopefully small constant $c$. However the computation of a nice upper bound on $c$ would probably take substantial effort. It's possible c is no more than 2 or 3."

Is it possible to convert factoring integers to calculating permanent? That is given $\log N$ bit integer to factor, how can one reduce factoring such an integer to calculating permanent of $(\log n)^c\times(\log n)^c$ matrix for a fixed $c$?

---

I also ask if computing $a(a+1)(a+2)\dots(a+n)$ with $a\in\Bbb N$ is also easy (done in $\log^cn$ steps if permanent of $N\times N$ matrix is easy (done in $N^c$ steps). Note that at $a=1$ we have $n!$, and permanent of all $1$ matrix needs $n\times n$ size and hence needs $n^c$ time even if permanent is easy.

# Answer
The language of tuples $\langle n,i,j,b \rangle$ such that the $j$th bit of the $i$th prime factor of $n$ is $b$ is in NP. In particular, it is in #P. More accurately, there is a #P algorithm that on input $\langle n,i,j \rangle$ gives the $j$th bit of the $i$th prime factor of $n$ (either $0$ or $1$). Since the permanent is #P-complete, we can reduce this algorithm to the computation of some polysize permanent.
> 4 votes

---
Tags: factoring
---


# Question
Title: Algorithm to create n arrays with maximum difference
Let's suppose I want to generate n equal sized boolean arrays with maximum "difference". - "Difference" in this case is defined as that the arrays share as low as possible fields with one another. (an example of share: array1 = {1,0,0,0) and array2 = {1,1,1,1} -\> array1 and array2 share 1 field (array1\[0\] / array2\[0\])

Just for example: n would equal 2 and the size of the field would be 6 -\> the optimum solution would be the arrays \[0,0,0,0,0,0\],\[1,1,1,1,1,1\] because they share no fields and so are very "different" from one another Another example: n was equal to 4 and the size of the array would be 4 -\> a solution would be \[0,0,0,0\], \[1,1,1,1\], \[1,1,0,0\], \[0,0,1,1\] - the arrays share 1.33 fields per array by average

Has anybody an idea of an algorithm or solution strategy that could solve this problem (generate n of these arrays) perfectly (or very good - so that they are as different as possible) (in a realistic runtime)? Thanks very much in advance :D

# Answer
This problem is posed and solved in Ahlswede and Katona, Contributions to the geometry of Hamming spaces, page 10. If the number of vectors $N$ is even, the best solution is to choose $N/2$ pairs of a vector and its complement (obtained by switching 0s and 1s). If $N$ is odd then choose $N/2$ such pairs and add an arbitrary vector.

Curiously enough, if you want to *minimize* the average distance, then the answer is still unknown, though it is suspected to be a Hamming ball.
> 3 votes

---
Tags: algorithms, optimization, arrays
---


# Question
Title: Understanding Closest Pair Algorithm (CLRS)
I'm reading CLRS Section `33.4 Finding the closest pair of points`. At exercise `33.4-2` they say

> **33.4-2**
>
> Show that it actually suffices to check only the points in the 5 array positions following each point in the array Y'

But I'm getting 4 array positions following each point in the array Y' will be suffice to check. See the fig below

Which possibility I'm missing. Can anybody point it out.

# Answer
> 3 votes
Assume that a point exists in every corner in the figure (including the inside corners). If points cannot overlap, then you have 6 points that can reside in the x2 box, and since you must be looking at one of them, you need only compare it to the next 5 in Y'.

---
Tags: algorithms, computational-geometry, divide-and-conquer
---


title: DFS traversal: explanation required

text:
# Question
Title: DFS traversal: explanation required
I am studying about DFS these days from the book "Algorithm Design" by Jon Kleinberg. Here a DFS algo is given which is as follows:

```
DFS(s):
    Initialize S to be a stack with one element s
    While S is not empty
        Take a node u from S
        If Explored[u] = false then
            Set Explored[u] = true;
            For each edge (u,v) incident to u
                Add v to the stack S
            Endfor
        Endif
    Endwhile

```

Now, how will the following graph be traversed using the above algo?

\[TIP\] We have to use stack as a data structure

Why I am asking this is because I am confused about the contents of stack at any point of time. I want to see how would you guys do it.

# Answer
> 3 votes
Suppose that vertices are retrieved in alphabetical order, then we'd have:

1. Iteration

```
Before stack is modified
stack: [a], visited: []
After stack is modified
stack: [c, b], visited: [a]

```
2. Iteration

```
Before stack is modified
stack: [c, b], visited: [a]
After stack is modified
stack: [f, a, b], visited: [a, c]

```
3. Iteration

```
Before stack is modified
stack: [f, a, b], visited: [a, c]
After stack is modified
stack: [c, a, b], visited: [a, c, f]

```
4. Iteration

```
Before stack is modified
stack: [c, a, b], visited: [a, c, f]
After stack is modified
stack: [a, b], visited: [a, c, f]

```
5. Iteration

```
Before stack is modified
stack: [a, b], visited: [a, c, f]
After stack is modified
stack: [b], visited: [a, c, f]

```
6. Iteration

```
Before stack is modified
stack: [b], visited: [a, c, f]
After stack is modified
stack: [d, e], visited: [a, c, f, b]

```
7. Iteration

```
Before stack is modified
stack: [d, e], visited: [a, c, f, b]
After stack is modified
stack: [b, e, e], visited: [a, c, f, b, d]

```
8. Iteration

```
Before stack is modified
stack: [b, e, e], visited: [a, c, f, b, d]
After stack is modified
stack: [e, e], visited: [a, c, f, b, d]

```
9. Iteration

```
Before stack is modified
stack: [e, e], visited: [a, c, f, b, d]
After stack is modified
stack: [e], visited: [a, c, f, b, d, e]

```
10. Iteration

```
Before stack is modified
stack: [e], visited: [a, c, f, b, d, e]
After stack is modified
stack: [], visited: [a, c, f, b, d, e]

```
11. Iteration

Finished

For me, the culprit was to notice that when the algorithm encounters the first element on stack which was already visited, it will not add more vertices to the stack. This happens in iterations 4, 5, 8, and 10.

---
Tags: algorithm-analysis
---


title: Sum of products of n-tuples

text:
# Question
Title: Sum of products of n-tuples
Let's say I have an array of numbers {a,b,c,d,e} and want to calculate the sum of product of all triples abc+abd+...+cde. I can calculate it very fast without generating all triples using this formula
F(n,k)= k\*F(n-1, k-1)+ F(n-1, k) with two loops

```
       int[] values={a, b, c, d, e...};
       int k = 3;
       int[,] F = new int[values.Count, k];
       ...
        for(int i = 0; i < values.Count; i++)
            for(int j = 0; j < k && j <= i; j++)
                F[i, j] = values[i] * F[i - 1, j - 1] + F[i - 1, j];

```

Now I have this array of groups {{a1,a2,a3..an}, {b1,b2,b3 ...bn}, {c1,c2...} } and every element of a triple must be in different group. a1\*b2\*c1 is a valid triple but a1\*a2\*b1 is not allowed because a1, a2 are in the same group. It's possible to generalize the above algorithm to find the sum of valid triples (quadruple or n-tuple)?

# Answer
> 2 votes
We have the following identity:

$$\sum\_{i,j,k} a\_i b\_j c\_k = (a\_1+\dots+a\_n) \times (b\_1+\dots+b\_n) \times (c\_1 + \dots + c\_n).$$

Therefore, one can compute the sum of all valid triples in $O(n)$ time by first computing the sum of the $a\_i'$, the sum of the $b\_i$'s, the sum of the $c\_i$'s, and then multiplying these three sums. This generalizes: you can find the sum of valid k-tuples in $O(kn)$ time.

---
Tags: algorithms
---


# Question
Title: Priority inversion in Hoare and Mesa monitors
I understand the difference between Hoare and Mesa monitors. However I don't understand why priority inversion (when a lower priority process gets done before a higher priority process) is possible in the Hoare type but not possible in the Mesa type. Can someone explain this?

# Answer
> 5 votes
Unless you are careful priority inversion is possible in either Hoare type or Mesa type monitors. This is because monitors implement a form of *mutual exclusion* (only one process can be "in" the monitor at a time), and mutual exclusion and priorities don't mix well. Boosting the priority of the thread in the monitor, mitigates (but does not completely solve) the problem. Priority boosting is typically done either with a priority ceiling, or priority inheritance, or both.

Hoare type condition variables introduce an additional priority inversion problem, though. In Hoare type condition variables a low-priority thread may `WAIT` on the condition variable (thus giving up the monitor lock), then a high-priority thread could run, make the condition true and `SIGNAL` the condition variable. In a Hoare type condition variable, the high priority thread immediately loses the monitor lock and gives it to the lower-priority thread.

In a Mesa type condition variable this particular priority inversion won't happen. The low-priority thread `WAITs` on the condition variable, giving up the monitor lock. Then a high-priority thread runs, makes the condition true and `NOTIFYs` the condition variable. The high-priority thread does *not* give up the monitor lock, and keeps running.

---
Tags: operating-systems, synchronization, real-time
---


title: Computational problem - definition

text:
# Question
Title: Computational problem - definition
How should I understand the definition of computational problem?

> A computational problem is a mathematical object representing a collection of questions that computers might be able to solve. For example, the problem of factoring
>
> "Given a positive integer n, find a nontrivial prime factor of n."

What is the mathematical object in the example above? Quoting Wikipedia again:

> Commonly encountered mathematical objects include numbers, permutations, partitions, matrices, sets, functions, and relations.

So how can you 'represent' a collection of questions with numbers or permutations, matrices etc.? What is meant here is probably the following collection of sentences:

'find a nontrivial prime factor of 1', 'find a nontrivial prime factor of 2' and so on...

But the thing is - these sentences are not mathematical objects.

A little further in the article it reads:

> A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.

which makes perfect sense, but I don't quite see the relationship with the first definition.

# Answer
> But the thing is - these sentences are not mathematical objects.

Yes, they are. A set of sentences can be a mathematical object. Just about anything can be a mathematical object.

> > A computational problem can be viewed as an infinite collection of instances together with a solution for every instance.
>
> \[...\] but I don't quite see the relationship with the first definition

Well, "an infinite collection of instances together with a solution for every instance" **is** a mathematical object (representing a collection of questions that computers might be able to solve).
> 1 votes

# Answer
The mathematical object is "a collection of questions". A "collection" is another word for a "set". You listed sets as one kind of mathematical object.

The connection between the two definitions is: each instance represents a slightly different question that a computer might be able to solve. So, you have one instance per question.
> 0 votes

# Answer
A sentence can be a mathematical object, but it isn't very helpful in your case. One way to approach the answer would be to analytically decompose the problem into simple and familiar mathematical objects and then to build a more complex mathematical object representing your problem. So:

> "Given a positive integer n, find a nontrivial prime factor of n."

1. You can salvage $n$ - a familiar mathematical object, an integer.
2. Investigating further, you can salvage $p$ - a prime factor of $n$.
3. The question establishes a relation between $n$ and $p$, restated using Greek and Hebrew of mathematics: $R = \\{(n, p) \\;|\\; \forall q \in (\mathbb{N} \setminus \\{1, p\\}): (p \div q) \not \in \mathbb{N} \land \exists m \in \mathbb{N}: p \cdot m = n \\}$, which is a relation, a familiar mathematical object, further written as $n R p$.
4. Now it's time to state the problem. For example, you could use the language of first order logic to formulate it: $p \impliedby n R p$. The logical interpretation of such formula is "if $p$ is a non-trivial prime factor of $n$, then $p$. Computational interpretation of this formula is "find all $p$ which are non-trivial factors of $n$".
5. Finally, you can go one step further and implement it in a programming language, for example, in Prolog:

```
prime_factor_of_n(P, N) :- M in 2..N, P is N / M, prime(P).

```
> 0 votes

---
Tags: terminology, computation-models
---


# Question
Title: A list of n strings lexicographic order using the merge-sort algorithm. The worst case running time of this computation is
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is \__________.

1. $O(n log n)$
2. $O(n^2 log n)$
3. $O(n^2 +log n)$
4. $O(n^2)$

---

My attempt:

If we are used **in-place merge sort** , then time complexity for the worst case $Θ(n^2)$ . so none option is correct , since for worst case $O$ are used but not $Θ$ .

---

This question was from competitive exam GATE (see-Q.no.-39) , and answer key is given by GATE "Marks to all(means there is no option correct)" (see-set-A-Q.no.-39) .

# Answer
(2) is the only correct answer. Merge sort makes $\Theta(n \log n)$ comparisons. Here, we are comparing strings of length $n$, and comparing two length-$n$ strings takes $\Theta(n)$ time in the worst case. Therefore, the running time is $O(n^2 \log n)$.

It is easy to arrange a set of inputs that makes Merge sort take this long. For instance, consider an input that contains $n$ identical strings; or $n$ strings that all start with the same common prefix (where this common prefix has length $n/2$, say). Then each comparison will take $\Theta(n)$ time, and Merge sort will do $\Theta(n \log n)$ comparisons, for a total of $\Theta(n^2 \log n)$ running time.

Consequently, (2) is correct, and none of the other answers are correct.

---

Your reasoning is incorrect.

In general, merge sort makes $\Theta(n\log n)$ comparisons, and runs in $\Theta(n \log n)$ time if each comparison can be done in $O(1)$ time. Therefore, if for some reason we were promised that comparing two strings could be done $O(1)$, *all* the options would be correct: they would all give an upper bound on the running time of merge sort. $O$ is used to give upper bounds, so $O(n^2)$ is also a correct upper bound for any algorithm whose running time is $O(n \log n)$ (since $n\log n \leq n^2$). In this case, the problem statement didn't make that promise, and in the worst case comparing two strings can take $\Theta(n)$ time, so answers (1), (3), and (4) are not correct.

There's an important difference between $O$-notation, $\Theta$-notation, and $\Omega$-notation; they are not equivalent.

---

The problem statement doesn't say anything about *in-place* merge-sort, so I'm not sure why you're bringing that up in your answer. That seems irrelevant. Anyway, while the standard merge sort algorithm is not in-place, there exist ways to do in-place merge-sort with the same asymptotic running time as the standard merge sort algorithm.
> 4 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Time/Space Optimal k-Subset Operator Application - Is this a named problem?
I have searched extensively and unsuccessfully for references to a combinatorial problem that arises in my work. I am hoping someone can tell me if this type of problem has a "name" and provably optimal solutions.

The problem: Given a set of objects denoted by $X\_1,\ldots,X\_N$, a commutative and associative operator $\oplus$, and $K \leq N$, generate all $N \choose K$ subset-applications of the operator in a way that first minimizes the number of operator applications, and then minimizes the number of partial results that must be stored, assuming that once a complete combination is generated its storage can be recovered. For example, for $5 \choose 4$ we need to generate the five new objects $$ X\_1 \oplus X\_2 \oplus X\_3 \oplus X\_4, \\ X\_1 \oplus X\_2 \oplus X\_3 \oplus X\_5, \\ X\_1 \oplus X\_2 \oplus X\_4 \oplus X\_5, \\ X\_1 \oplus X\_3 \oplus X\_4 \oplus X\_5, \\ X\_2 \oplus X\_3 \oplus X\_4 \oplus X\_5 \\ $$ which naively requires 15 operator applications and a single accumulator. However a better solution requires only 11 operator applications if storage is allocated for 3 partial results.

Note that no negation or inverse of the operator $\oplus$ is assumed. This rules out using most popular combination-generation schemes such as Gray codes. In the motivating application the operator is also idempotent ($X \oplus X = X$) but I don't think this fact is helpful to a solution.

I have developed a good algorithm to solve the problem using at most $N$ accumulators. However it strikes me that others have probably analyzed this type of problem and I simply don't know the correct terminology to guide my search.

# Answer
> 1 votes
For $K \ll 2N/3$, a good solution goes as follows, for $K$ even (the case $K$ odd is very similar):

1. Generate all XORs of length 2.
2. Generate all XORs of length 3.
3. ...
4. Generate all XORs of length $K/2$.
5. Generate all XORs of length $K$.

This requires $\binom{N}{K/2} + \binom{N}{K/2-1} \approx \binom{N}{K/2}$ memory and $\binom{N}{2} + \cdots + \binom{N}{K/2} + \binom{N}{K} \approx \binom{N}{K}$ operations. This is close to optimal in terms of number of operations, since clearly at least $\binom{N}{K}$ are needed.

You can optimize this a bit as follows:

1. Generate all XORs of length 2 of $X\_1,\ldots,X\_{N-K/2+2}$.
2. Generate all XORs of length 3 of $X\_1,\ldots,X\_{N-K/2+3}$.
3. ...
4. Generate all XORs of length $K/2$ of $X\_1,\ldots,X\_N$.
5. Generate all XORs of length $K$.

The savings are not significant.

---
Tags: algorithms, optimization, combinatorics
---


# Question
Title: Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher
I have a field in my data store which must take exactly 180 bits of information. Some users will choose to make this data encrypted, some won't, so some of those 180 bit fields will be ciphertext some will be plaintext. A boolean will indicate which one the user is using. The important thing here is that I need this field to be exactly 180 bits long.

However, a 128-bit cipher will mean I have to put in 256 bits in as plaintext, which is fine, just use a buffer string, but this means that the output is 256 bits when what is stored must be exactly 180 bits. And I can't simply cut off the ciphertext or that would mess up the decryption.

# Answer
If you have a **unique, unchanging identifier** for each entry in your data store, you can use counter mode.

A nice thing about counter mode turns a block cipher into a stream cipher. No matter what the block size is, CTR mode encrypts an $n$-bit plaintext into an $n$-bit ciphertext.

In order to achieve that, CTR requires a unique counter value per block. Note: not just a unique counter value per message, but a unique counter value per block. The counter size is the same as the block size. In your case, you have messages that fit on two blocks, thus each message requires two counter values. If you have a unique identifier $k$ for each message, you can use $k$ and $k+1$ as the counter values for the two blocks (the second of which is partial) of the message.

Thus you need a 127-bit unique identifier for each message (128-bit block, minus one bit to distinguish the two blocks inside each message). The only security requirement for these 127 bits is that they are never reused for a given key. The initial counter value to encrypt a message is often chosen randomly, but this is not a requirement, just a convenience to ensure uniqueness. Of course, to decrypt the data, you need to be able to recover the unique identifier associated with each entry.

If your entries have some kind of unique identifier, which is often the case in databases, then you're set. Just remember that if you move data around or normalize it in a way that changes the identifiers, you will need to decrypt and reencrypt the data.

Some crypto libraries may present CTR mode through a function that randomly generates the initial counter value and prepends it to the message (so you'd input a 160-bit plaintext and get back a 288-bit ciphertext). Use a library that lets you specify the initial counter value (almost all implementations will increment the counter by 1 for each successive block, so pick initial counter values that are even, but you'll need to be aware of the endianness used by your library).

Keep in mind that encryption only gives you confidentiality, not integrity. In other words, someone who obtains the ciphertexts but not the key will not be able to find any information about the data; but if someone can inject fake ciphertexts or modify existing ciphertexts, the tampering cannot be detected. It is intrinsically impossible to detect tampering by cryptographic means in your scenario since there is no room for any redundancy.
> 5 votes

# Answer
One approach is to use what is known as format-preserving encryption. For instance, you could use VIL mode or FFX mode.

I recommend you spend some quality time on Cryptography.SE and with some research literature to learn more about these schemes. e.g.,

However, I do see two serious red flags with your scheme:

* There is no salt/tweak. This means that all instances of the field will be encrypted the same way: if the same input repeats twice, you'll get the same output both times. This is usually a bad mode, as it makes your scheme equivalent to ECB mode, which is notoriously a bad idea. Instead, I recommend you use a *tweakable* FPE scheme, and set the tweak to be some identifier that is different for each row (e.g., a primary key, a row number, etc.).
* None of these schemes provide any authentication/integrity. The lack of authentication/integrity is a red flag. In my experience, most schemes that use encryption without authentication/integrity are subject to a range of non-obvious attacks.

Due to these red flags, I recommend you talk to a professional cryptographer if security is important in your domain. You're in tricky waters.
> 4 votes

# Answer
The simplest solution is the following encryption procedure:

> Encrypt the first 128 bits.
>
> Encrypt the last 128 bits.

Decryption works the other way around:

> Decrypt the last 128 bits.
>
> Decrypt the first 128 bits.

Performance is $256/160 = 1.6$ times slower than AES. It's best to use two different keys for the two steps.

There is a slight problem with this procedure regarding data integrity: if the first 32 bits of the ciphertext are modified, then the last 32 bits of the resulting plaintext will stay the same. If this worries you, add an extra step:

> Encrypt the first 128 bits.
>
> Encrypt the last 128 bits.
>
> Encrypt the first 128 bits.

Performance drops to $384/160 = 2.4$ times slower than AES. Again, it's best to use three different keys.
> 1 votes

---
Tags: cryptography
---


# Question
Title: Communication Complexity and Prefix Codes
I need an advice.

There is in section "V. CONCLUDING REMARKS" of the paper \[1\],

a term that only the autho's paper use: "PREFIX CODING COMMUNICATION".

I googled the expression and the only result is the same paper \[1\].

It's difficult for a beginner in communication complexity to understand what the author is talking about because he doesn'st explain how to use a prefix code for solving the set intersection problem. He only writes "assigning an appropriate prefix code to the messages...". His explanation is too vague. Thanks in advance who ever can advice me.

\[1\] "Communication Complexity and Data Compression"

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.306.7941&rep=rep1&type=pdf

# Answer
> 1 votes
The author describes an algorithm due to Ahlswede and Cai to solve the set intersection problem, and then describes his generalization to the number-in-hand setting with any number of players. I will only describe the two player setting.

Ahlswede and Cai consider an algorithm of the following form. Alice gets a set $X \subseteq \\{1,\ldots,n\\}$, and Bob gets a set $Y \subseteq \\{1,\ldots,n\\}$. Then there are two rounds:

1. Alice sends Bob a description of $X$.
2. Bob sends Alice a description of $X \cap Y$.

It remains to determine the encoding of $X$ and $X \cap Y$. For the second round, things are simple: for each $x \in X$, Bob sends a bit describing whether $x \in Y$ or not, for a total of $|X|$ bits.

The first round is more complicated. One option is to always send the entire set $X$ in the same way, at the cost on $n$ bits. This algorithm uses $2n$ bits in the worst case, when $X = \\{1,\ldots,n\\}$. Another option is to use a more complicated encoding scheme. One thing which this scheme should accomplish is that after Alice finishes sending the message, Bob knows that it's his turn to speak. This only happens if the set of messages that Alice sends forms a prefix code.

Suppose that the length of the codeword that Alice sends when her input is $A$ is $\ell\_A$. The communication complexity of the protocol is then $\max\_A \ell\_A + |A|$. On the other hand, Kraft's inequality states that a prefix code exists if and only if $$ \sum\_A 2^{-\ell\_A} \leq 1. $$ Now suppose we're aiming at a communication complexity of $L$ bits. Then we need to have $\ell\_A \leq L - |A|$, and so $$ 1 \geq \sum\_A 2^{-\ell\_A} \geq \sum\_A 2^{|A|-L} = 2^{-L} \sum\_k \binom{n}{k} 2^k = 2^{-L} 3^n. $$ This shows that $2^L \geq 3^n$ and so $L \geq (\log\_2 3)n$. Conversely, if $L = \lceil (\log\_2 3)n \rceil$ then such a code exists, and we get a communication protocol with this complexity.

It so happens that this complexity is optimal. Ahlwede and Cai prove that using the rank bound, which states that the communication complexity is at least the base-2 logarithm of the sum of the ranks of the matrices $M\_z(x,y)$, given by $M\_z(x,y) = 1$ if on inputs $x,y$ the output is $z$, and $M\_z(x,y) = 0$ otherwise.

When $n=1$ the matrices are $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ and $\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}$, and we get that the communication is at least $\log\_2 3$. More generally, we have the identity $$ M\_z(x,y) = \bigotimes\_{i=1}^n M\_{z\_i}(x\_i,y\_i), $$ using tensor product notation, from which it easily follows that the rank of $M\_z(x,y)$ equals $2^{|z|}$ (Hamming weight of $z$). The rank lower bound is then $\log\_2 3^n = (\log\_2 3) n$, matching the algorithm.

The exact communication complexity of set intersection is therefore $\lceil (\log\_2 3) n \rceil$, and so the amortized communication complexity is $\log\_2 3$. This is better than running the best protocol for $n=1$ in parallel, which would result in $2n$ bits. Ahlswede and Cai's protocol thus in some sense compresses the communication.

Recently, the advent of information complexity has resulted in a much improved understanding of amortized complexity, especially in the randomized case in which a small error is allowed. In that case, the amortized complexity exactly equals the information complexity. In fact, when a small error is allowed, Braverman et al. show that the amortized complexity drops to 1.4923 bits. They also compute the amortized complexity of set disjointness to be 0.4827.

An outstanding open problem is finding a similar formula for the zero-error complexity of the direct product of a function – current techniques only work when a small error is allowed.

---
Tags: coding-theory, communication-complexity
---


# Question
Title: What is the maximum number of classes resulting from partitioning by DFA as function of number of states?
I was wondering whether it is possible (and if so, then how) to tell what is the maximum number of equivalence classes generated by a DFA as per Myhill-Nerode theorem (assuming it has no redundant transitions) as a function of number of accepting and rejecting states and cardinality of its alphabet.

My guess is that it should be something like $\log(n) \cdot |{\Sigma}|$, where $n$ is the number of states, since one could see this as tree of derivations created by something like left-regular grammar equivalent to the same automata, and classes would be the leafs of this tree. But this is just a guess.

# Answer
I'm not sure what you mean by classes, but if you mean Myhill–Nerode equivalence classes, then the classical construction shows that the (unique) minimal DFA has as many states as equivalence classes.
> 4 votes

# Answer
You mention motivations in comments, but in this question you seem to be asking about how to determine worst case bounds on a/the "compression ratio" of an unminimized DFA versus a minimized one. This is indeed studied systematically/scientifically but note that an unminimized DFA can have unbounded redundant states so this question must be formalized more carefully/cleverly to come up with some kind of metric.

Here are two example papers in the area that study it empirically. The first is in the context of router systems that use DFA rules for examining packets. The 2nd uses randomly generated DFAs somewhat analogous to Erdos-Renyi graphs and examines efficiency of different algorithms.
> 3 votes

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


# Question
Title: Hex Bit Pattern to IEEE 754 standard Floating Point Number
The question asks for the decimal number that 0x0C000000 represents if it is a floating number. I'm not too sure on how to approach this, but here's my thought process:

0x0C000000 = 0000 1100 0000 0000 0000 0000 0000 0000

The first digit is 0, so it's positive. The exponent is 0x0C = 12 - 127 = -116. The mantissa is 0x0C0000 = 12 * 16 ^ -2 = 0.046875, so the final answer is 1.046874 * 2 ^ -116. While my book has similar examples that I tried to follow along with, none were exactly of this type, so I highly suspect I'm doing something wrong. Any tips, hints, or strategies would be greatly appreciated.

# Answer
A good start is to expand the hex representation into binary like how you did it.

> 0000 1100 0000 0000 0000 0000 0000 0000

Then parse the word:

* the left-most bit is the sign bit
* the next 8 bits represent the biased-exponent
* the last bits represent the fractional part with the "hidden one"

> 0 | 00011000 | 00000000000000000000000

Then, follow:

* *s* represents the sign bit
* evaluate the binary representation of the exponent to decimal
* subtract the bias from the exponent (bias for single-precision is 127 and 1023 for double-precision)
* evaluate the normalized form to decimal and you have your floating point decimal number

I hope this helps. It took me a while to understand encoding and decoding using IEEE-754. Slow and steady wins the race.
> 3 votes

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


# Question
Title: How to speed up process of finding duplicates/similar items in a large amount of strings?
Our software receives documents (in the order of tens of thousands) from various providers, each document flows through a number of steps, one of those steps finds duplicates and similar documents (within 80% threshold) to this document.

We implemented Levenshtein distance algorithm and we limit amount of documents current document has to look over (via a set of hash codes), but this solution is still horribly slow (since it's M\*N problem) even after we launch it on multiple cores.

Are there any suggestions/techniques we can use to speed up the processing? The requirement for it is to work in near real-time (I guess we can accept up to 10-20 minutes gap). The only idea I have is to split exact duplicates and similar docs processing in two steps and use something like HyperLogLog for duplicates.

The texts are from social media (tweets, blog posts, etc.) so it's reasonable to assume that duplicates share are far greater than that of a similar docs.

I apologize if my usage of terminology isn't very accurate.

# Answer
Edit distance is definitely not the way to proceed. The standard approach toward near-identical document deduplication is to compute hashes of shingles. Here's one way to do it:

1. Compute a set of k-shingles (say 30 char shingles) for each document
2. Compute min-hashes for the documents
3. Use locally-sensitive hashing to look-up similar documents when inserting into the database

Here's a great article that explains how this can be done: http://deduplication.tumblr.com/

And you can pick up an existing tool do this, for example Solr: https://wiki.apache.org/solr/Deduplication
> 6 votes

---
Tags: strings, edit-distance
---