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

network-flow 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 mathforum.org 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 ...

programming-languages 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++. ...

programming-languages 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

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

logic 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, 110 William Street, 28th floor, New York, NY 10038

 <3