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

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

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

 <3