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

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

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

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

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

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

asymptotics big-o-notation

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

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

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

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

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

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

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

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

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

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

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