Computer Science Stack Exchange Community Digest

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 ...

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 ...

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

Stack Overflow, 110 William Street, 28th floor, New York, NY 10038