Computer Science Stack Exchange Community Digest

Top new questions this week:

Minimum set cover with incompatible sets

I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously). To state it more formally: We have a finite base set $X$ and a family $\...

algorithms reference-request np-hard set-cover  
asked by Tassle 4 votes

Las Vegas algorithm for finding 00000 in bit string

Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). ...

algorithms algorithm-analysis strings randomized-algorithms  
asked by spektr 4 votes
answered by Yuval Filmus 2 votes

Compiler Design Question

Consider the following ANSI C code int main(){ Integer x; return 0; } What will be the type of error? a)Lexical, b)Syntax, c)Semantic, d)None According to me, Syntax Analysis phase should detect the ...

asked by gatecs 2 votes
answered by mazzespazze 2 votes

Sorting algorithm for ranking hundreds of Images based on pairwise comparison

I am facing the task of designing an algorithm to rank some hundred of images (around 300). The ranking is to be based on pairwise comparison judged by human (done through Amazon mechanical Turk). I ...

algorithms sorting  
asked by PhysicsMath 2 votes
answered by D.W. 2 votes

Karger's min cut and tips on bounding nonlinear recurrences

I was recently working on an old qualifying exam problem asking us to generalize Karger's randomized global min cut algorithm to that of a global min $k$-cut. I recalled the strategy of running a ...

recurrence-relation randomized-algorithms minimum-cuts  
asked by spektr 2 votes
answered by Yuval Filmus 2 votes

Efficient algorithm to compute the diameter of a convex set?

Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set? It is possible to do it efficiently for a set of points, but imagine that the ...

complexity-theory optimization computational-geometry linear-programming convex-hull  
asked by amos 2 votes
answered by Steven 3 votes

How do computers *really* work? (at the most basic level)

While learning about computers I will read about RAM and Storage and the CPU, and while these explain the architecture of a computer and how parts of a computer work together, I still don't understand ...

computer-architecture logic cpu binary  
asked by icantcode 2 votes
answered by nir shahar 3 votes

Greatest hits from previous weeks:

Minimum spanning tree vs Shortest path

What is the difference between minimum spanning tree algorithm and a shortest path algorithm? In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and ...

algorithms shortest-path spanning-trees  
asked by flashburn 61 votes
answered by Yuval Filmus 51 votes

Why is writing down mathematical proofs more fault-proof than writing computer code?

I have noticed that I find it far easier to write down mathematical proofs without making any mistakes, than to write down a computer program without bugs. It seems that this is something more ...

correctness-proof mathematical-foundations philosophy  
asked by user56834 209 votes
answered by Yuval Filmus 241 votes

The math behind converting from any base to any base without going through base 10?

I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on but I'm still ...

algorithms arithmetic number-formats  
asked by Griffin 39 votes
answered by Andrej Bauer 54 votes

What exactly is the difference between supervised and unsupervised learning?

I am trying to understand clustering methods. What I I think I understood: In supervised learning, the categories/labels data is assigned to are known before computation. So, the labels, classes or ...

machine-learning data-mining clustering  
asked by Prot 29 votes
answered by Dave Clarke 23 votes

What is tail recursion?

I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the ...

algorithms reference-request recursion  
asked by Geek 67 votes
answered by Matt Lewis 63 votes

Why do more powerful programming languages tend to have slower implementations?

I was reading this article. The author talks about "The Blub Paradox". He says programming languages vary in power. That makes sense to me. For example, Python is more powerful than C/C++. ...

asked by Shashank V M 18 votes
answered by Matthieu M. 7 votes

What are the differences between computer vision and image processing?

What are the differences between computer vision and image processing? For example, in object recognition, what are the roles of computer vision and image processing?

terminology computer-vision image-processing education  
asked by gena 21 votes
answered by Ravindra Bagale 28 votes

Can you answer these questions?

Strong NP-completeness of numerical perfect matching

This is a follow-up to post Perfect matching problem, where nir proved weak NP-completeness. Suppose you are given two sets of integers $L$ and $M$ both having $N$ elements. We want to match each ...

complexity-theory np-complete  
asked by Mohammad Al-Turkistany 1 vote

Textbook on Abstract Data Types

I'm looking for a textbook or reference material to learn about the theory of abstract data types, the ways in which they are specified (axiomatic specification vs abstract model), imperative vs ...

books abstract-data-types  
asked by El Gallo Negro 1 vote

Better version of heavy-light decomposition: always draw path to largest subtree

Can someone tell me if this works? It seems to be easier to implement and also creates slightly less paths (though still O(log N) ). The problem: given any tree of size N, find a way to split it into ...

algorithms trees  
asked by Nathan Wang 1 vote
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