Computer Science Stack Exchange Community Digest

Top new questions this week:

How to define a similarity between two graphs?

Let's say we have a set of vertices $V$, and two (undirected) graphs over the same set $V$, but not necessarily the same set of edges $G_1 = (V, E_1)$, $G_2 = (V, E_2)$. $\newcommand\mG{\mathbb G}$(...

graphs graph-isomorphism  
asked by flawr 9 votes
answered by eru-cs 14 votes

Integral solutions to circulation problem

Suppose we have a circulation problem (with only one commodity), where all lower bounds, upper bounds, and costs are integers. Are we guaranteed that if there is a solution, then there is an integral ...

asked by D.W. 5 votes
answered by orlp 4 votes

Min path cover for a three-layer graph with all paths traversing all layers

Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. ...

graphs combinatorics discrete-mathematics  
asked by Rohit Pandey 4 votes
answered by D.W. 3 votes

Sampling from specific random distribution on sets

I have a random distribution on sets in mind, that has three parameters: $n, w, k$. The goal is to sample sets of $k$ integers from $[0, n)$ (without replacement) such that the elements within each ...

randomness sampling  
asked by orlp 4 votes
answered by D.W. 1 vote

What are the implications of Homotopy Type Theory?

I've recently come across the topic of homotopy type theory and I'm interested to learn more. I have a very limited background in type theory. Can anyone tell me, in functional programming terms or ...

type-theory functional-programming mathematical-foundations proof-assistants homotopy-type-theory  
asked by thoughtpolice 3 votes
answered by jmite 0 votes

Upper bounds for a binomial coefficient

I have an algorithm with worst-case time complexity in $\mathcal O (\binom{k}{p-1})$, where $k$ is a parameter and $p$ is the input size of that algorithm. I further have determined that $p-1 \leq k $...

algorithm-analysis runtime-analysis big-o-notation  
asked by Rafael Bankosegger 3 votes
answered by Steven 4 votes

Annotated type system problem about conditional branch

I am reading the book "Principle of Program Analysis" by Flemming Nielson for annotated type systems. In the first chapter, section 1.6 they mentioned the simple type system for various ...

compilers type-inference  
asked by Prasanna Sasne 3 votes

Greatest hits from previous weeks:

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 52 votes

Why are there so many programming languages?

I'm pretty fluent in C/C++, and can make my way around the various scripting languages (awk/sed/perl). I've started using python a lot more because it combines some of the nifty aspects of C++ with ...

asked by Suresh 137 votes
answered by Dave Clarke 122 votes

Is there a name for the class of algorithms that are the most efficient for a particular task?

This would be analogous to the Kolmogorov complexity of a string, except that in this case, I'm interested in the algorithm that solves a given problem using the least number of steps. We would ...

algorithms time-complexity terminology  
asked by Feynmanfan85 27 votes
answered by Juho 34 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 16 votes
answered by Matthieu M. 4 votes

Definition of the state of an object in OOP

I need a concise definition of the "state of an object" in object-oriented programming (for a paper). For about half of a day I searched for a paper that I can cite on this topic, but I couldn't find ...

terminology reference-request programming-languages object-oriented  
asked by mrsteve 12 votes
answered by Vor 10 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 19 votes
answered by Ravindra Bagale 26 votes

What is the difference between user-level threads and kernel-level threads?

After reading several sources I'm still confused about user- and kernel-level threads. In particular: Threads can exist at both the user level and the kernel level What is the difference between ...

operating-systems terminology concurrency os-kernel  
asked by Sheldon 33 votes
answered by Gilles 'SO- stop being evil' 28 votes

Can you answer these questions?

Circuit complexity of hardest monotone function

Show there exists a monotone function $f\colon \{0,1\}^n \mapsto \{0,1\}$, such that the minimal size of a monotone circuit that computes $f$ is $\Omega(2^n / n^2)$. Use the fact that the number of ...

complexity-theory circuits boolean-algebra  
asked by Ido 2 votes

Automated algorithm design

There is a huge field of study dedicated to automated theorem proving. Is there any similar research dedicated to automated algorithm design? And is there any form of "duality" between these ...

asked by Vladislav Bezhentsev 2 votes

Counting paths by their type

An edge-labelled directed graph is the data of $G = (V, E, l)$ where $(V, E)$ is a directed graph, and $l \colon E \to \mathbb{P}$ is some function. (For the graph I am considering, labels take values ...

graph-traversal counting  
asked by Joppy 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