Computer Science Stack Exchange Community Digest

Top new questions this week:

Modifying digraph to make it strongly connected

I came across this problem and have not been able to find a solution. Given directed graph $G$, devise an algorithm to find the minimum number of edges to flip/change/transplant such that the ...

algorithms graphs  
asked by Raorm 5 votes
answered by j_random_hacker 3 votes

Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to ...

complexity-theory np-complete reductions  
asked by blallo 5 votes
answered by Antti Röyskö 5 votes

Are there any proofs of exponential lower bound time complexity

I'm trying to understand what are the techniques to prove an exponential time lower bound. For some problems, we can prove that the size of the output is exponential is the size of the input, thus it ...

complexity-theory time-complexity decision-problem  
asked by Antoine 4 votes
answered by Tom van der Zanden 7 votes

Rules for consistency with mutual inductive families?

I'm trying to use a proof assistant to define a type and a relation that are mutually dependent on each other: Vec : (a : Type) -> (n : Nat) -> Type0 Rel : (a : Type) -> a -> a -> Type ...

lambda-calculus type-theory functional-programming induction dependent-types  
asked by jmite 4 votes

Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$

I am trying to understand the asymptotics of \begin{equation} f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})} \end{equation} In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?

asymptotics big-o-notation  
asked by Ryan 4 votes
answered by OmG 5 votes

Fermat's last theorem: How to (partially) solve by programs

No three distinct positive integers $a, b, c$ can satisfy the equation : $a^n + b^n=c^n$, if $n$ is an integer greater than two. The above statement, known as the Fermat's last theorem is ...

discrete-mathematics mathematical-programming  
asked by xxx--- 3 votes
answered by Yuval Filmus 0 votes

An iterative algorithm for finding the partitions of a set into subsets of a fixed size

The question is whether someone could provide an algorithm for finding all the partitions of a set S into subsets of fixed size (assume the fixed size is 2, to make things simpler, in which case the ...

algorithms combinatorics  
asked by EGME 3 votes

Greatest hits from previous weeks:

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 132 votes
answered by Dave Clarke 117 votes

What are system clock and CPU clock; and what are their functions?

While reading a book, I came across a paragraph given below: In order to synchronize all of a computer’s operations, a system clock—a small quartz crystal located on the motherboard—is used. ...

computer-architecture clocks  
asked by swdeveloper 22 votes
answered by Benjoyo 17 votes

Cache Direct Map (Index, tag, hit/miss)

Alright, I thought I understood this concept but now I am confused. I looked up similar problems and their solutions to practice, and that's what threw me off. The question is a homework problem which ...

computer-architecture cpu-cache  
asked by GiH 5 votes
answered by Wandering Logic 5 votes

When to use recursion?

When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?

algorithms recursion  
asked by Taylor Huston 26 votes
answered by Juho 18 votes

Why are some programming languages "faster" or "slower" than others?

I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I ...

programming-languages compilers  
asked by evil_potato 83 votes
answered by chi 97 votes

What is the difference between object detection, semantic segmentation and localization?

I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic ...

terminology computer-vision  
asked by Martin Thoma 23 votes
answered by e_soroush 18 votes

Is Morse code without spaces uniquely decipherable?

Are all Morse code strings uniquely decipherable? Without the spaces, ......-...-..---.-----.-..-..-.. could be Hello World but perhaps the first letter is a 5 -- in fact it looks very unlikely ...

information-theory coding-theory  
asked by john mangual 54 votes
answered by celtschk 91 votes

Can you answer these questions?

How to build a set of closed chains with a sequence of different vertices?

I have a set of many bi-directional links like A-B, A-C, B-C, A-D, C-D, D-E, etc. I need to find a set of many closed chains with a sequence of different vertices (vertex-disjoint cycles). It would ...

graphs subsequences  
asked by Alex Shnaider 1 vote

Regular expressions for set of all strings on alphabet $\{a, b\}$

I came across following regular expressions which equals $(a+b)^*$ (set of all strings on alphabet $\{a, b\}$): $(a^*+bb^*)^*$ $(a^*b+b^*a)^*$ $(a^*bb^*+b^*ab^*)^*(a^*b+b^*a)^*b^*a^*$ I want to ...

asked by anir 1 vote

Meaning of $a\lor b \to b' \lor c'$

So I have done part a) but I have no clue what I am supposed to do for part b), I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know ...

finite-automata logic  
asked by Minvy 1 vote
answered by Yuval Filmus 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