 ## Top new questions this week:

### Can any known sub-Turing-complete model of computation enumerate precisely the set of prime numbers?

I wish there were more, but the subject pretty much captures my whole question. Is there a non-Turing-complete model (some constrained term rewriting system or automaton or what have you) which is ...

computation-models turing-completeness enumeration primes asked by Trev 9 votes answered by Ivan Smirnov 20 votes

### N points with maximum sum distance

Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100. To calculate the sum of ...

algorithms graphs runtime-analysis computational-geometry matrices asked by user2349481 3 votes answered by Yuval Filmus 1 vote

### Algorithm that finds a matrix with a specific number of 1s in its rows & columns

Question: Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A[i]$ $1$s and whose $j$-th ...

algorithms greedy-algorithms matrices asked by mynamejeff 3 votes answered by John L. 3 votes

### Computational Complexity of 3SAT variant with additional restrictions on variables/clauses

Given a 3SAT problem with the additional constraints that: No clause or set of clauses is the 3SAT instance is 'redundant'. Thus, this 3SAT cannot eliminate any clauses. For any/every clause, the ...

complexity-theory time-complexity asked by J.Doe 3 votes

### Finding the most profitable path

I will be working on a project soon and as I'm clearly not a star (see what I did?) in CS, I'm not sure what to think about this. To put it simply, the problem is the following: We want to go from ...

algorithms graphs shortest-path asked by PabPabPab 3 votes answered by Steven 3 votes

### How do search engines implement fuzzy search?

When googling for the phrase "large horse walks into house" results that contain "close matches" for the phrase are also returned, e.g. "large horse in a house" and "...

algorithms data-structures asked by theonlygusti 3 votes

### Decidable languages unconditionally not in P/poly

What are some nice/natural examples of languages not contained in $P/\mathit{poly}$, preferably decidable ones? I'm interested in unconditional results rather than examples such as the Karp–Lipton ...

complexity-theory circuits asked by Adelhart 3 votes answered by Yuval Filmus 3 votes

## Greatest hits from previous weeks:

### What is a safe programming language?

Safe programming languages (PL) are gaining popularity. I wonder what is the formal definition of safe PL. For example, C is not safe, but Java is safe. I suspect that the property “safe” should be ...

programming-languages asked by beroal 60 votes answered by Davislor 25 votes

### How to solve T(n)=2T(√n)+log n with the master theorem?

I'm trying to solve the recurrence $$T(n)=2T(\sqrt{n})+\log n$$ using the master theorem. Which case applies here?

recurrence-relation master-theorem asked by Nimbus9000 3 votes answered by John L. 8 votes

### Which law is this expression X+ X’.Y=X+Y

Question. Name the law given and verify it using a truth table. X+ X’.Y=X+Y ...

boolean-algebra asked by user2241865 2 votes answered by Rick Decker 8 votes

### Computer Program vs. Algorithm

It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and a computer program is also a ...

algorithms terminology programming-languages asked by Ahmad 8 votes answered by Pseudonym 12 votes

### How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free....

formal-languages context-free proof-techniques reference-question asked by Raphael 94 votes answered by jmad 73 votes

### Difference between cross edges and forward edges in a DFT

In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal). There are some leftover edges connecting some of the other nodes. What is the difference ...

algorithms terminology graphs graph-traversal asked by soandos 16 votes answered by Yuval Filmus 28 votes

### What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...

algorithms time-complexity optimization sorting asked by gen 60 votes answered by Patrick87 46 votes

## Can you answer these questions?

### Can A* with an inadmissible heuristic still be optimal?

It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...

search-algorithms heuristics asked by Chemin 2 votes

### List of algorithms that depend on sorting / ranking / argsorting

I am looking for a list of algorithms that depends on sorting / relative ranking / argsorting, not for a list of sorting algorithms. I want to study and illustrate the importance of fast sorting in ...

algorithms sorting asked by lcrmorin 1 vote

### Minimum number of registers for mutual exclusion

I was reading distributed algorithms (by Nancy lynch) and there is a part that I would kindly like to get a simpler explanation for. I know the book mentioned no algorithm can solve mutual exclusion ...

distributed-systems parallel-computing mutual-exclusion asked by user206904 2 votes
You're receiving this message because you subscribed to the Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy Stack Overflow, 110 William Street, 28th floor, New York, NY 10038

 <3