Computer Science Stack Exchange Community Digest

Top new questions this week:

What are GPUs bad at?

I understand that GPUs are generally used to do LOTS of calculations in parallel. I understand why we would want to parallelize processes in order to speed things up. However, GPUs aren't always ...

asked by John Zhau 51 votes
answered by Mark 98 votes

Find and sort 2d array elements like radar

I don't know relevant keywords about this algorithm. I can show you visually Any ideas are appreciated

asked by Andrew Koser 6 votes
answered by anion 9 votes

How come correctness proofs aren't tautological?

Consider the following function on binary trees, which is supposed to tell whether a given int is a member of a binary tree t: type tree = Leaf | Node of int * tree * tree;; let rec tmember (t:tree) ...

logic correctness-proof  
asked by Nicolas 5 votes
answered by ryan 0 votes

Is there such a notion as "effectively computable reductions" or would this be not useful

Most reductions for NP-hardness proofs I encountered are effective in the sense that given an instance of our hard problem, they give a polynomial time algorithm for our problem under question by ...

complexity-theory computability np polynomial-time-reductions theory  
asked by StefanH 4 votes
answered by 6005 5 votes

Maximum matching in a bipartite graph

Given a bipartite graph $G=(V_1 \cup V_2, E)$ and a set $V' \in (V_1 \cup V_2)$. What is the complexity of finding a maximum matching in $G$ that uses only $x$ vertices from $V'$?

complexity-theory graphs bipartite-matching bipartite-graph  
asked by Farah Mind 4 votes
answered by Antti Röyskö 5 votes

Good book on the history of programming languages?

I'd like to read a book on the history of programming languages, that places their development into the context of their times. What was the context in which concepts like structured programming, ...

reference-request programming-languages books  
asked by user56834 4 votes
answered by Jörg W Mittag 5 votes

Existence of walk in undirected connected graph where nodes must end with assigned value

We have a graph with $N$ nodes and $N-1$ undirected edges, where it's possible to reach one node from any other node. Each node will get assigned a value randomly from [1,...,10]. We want the value of ...

algorithms graphs graph-traversal  
asked by moontartan 3 votes
answered by Antti Röyskö 0 votes

Greatest hits from previous weeks:

Difference between Turing machine and Universal Turing machine

I've read what's a Turing machine and an UTM are, but I don't get the difference. What does an UTM can do which a normal Turing machine can not?

asked by Moltimor 7 votes

What important/crucial real-world applications use blockchain?

As part of some blockchain-related research I am currently undertaking, the notion of using blockchains for a variety of real-world applications are thrown about loosely. Therefore, I propose the ...

asked by rshah 75 votes
answered by Pål GD 95 votes

What threads share in general?

Well this is general question. And if anyone want to make it implementation specific then I will prefer Unix related stuff. But first need to know following problems in generality: I read single ...

operating-systems threads  
asked by Maha 23 votes
answered by Wandering Logic 15 votes

Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$. I have ...

algorithms graphs  
asked by Saurabh 34 votes
answered by Nicholas Mancuso 38 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 11 votes

How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic complexity for an array of $n$ elements. ...

algorithm-analysis asymptotics landau-notation reference-question  
asked by Smajl 35 votes
answered by Raphael 40 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 55 votes
answered by Patrick87 42 votes

Can you answer these questions?

Unconditionally fair, weakly fair, and strongly fair scheduling

I am trying to understand the difference between weakly fair and strongly fair scheduling. For example, what scheduling policy would ensure that a process delayed at its first await statement will ...

concurrency scheduling mutual-exclusion  
asked by HotWheels 1 vote

Calculate probability in graphical model

I have the following graphical model, in which I wish to compute $p(Intelligence = 1|Letter = 1, SAT = 1)$ But I'm not sure how to rewrite $p(Intelligence = 1|Letter = 1, SAT = 1)$? I was told to ...

machine-learning probability-theory graphical-models  
asked by LRS25 1 vote

Is cubical type theory still consistent with univalent excluded middle and univalent choice?

I want to formalize some undergraduate maths in cubical agda, and learning cubical type theory in the proccess. The problem is that I will need univalent excluded middle and univalent choice (and ...

homotopy-type-theory cubical-type-theory  
asked by Borja Sierra 1 vote
answered by Dan Doel 0 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