# All Questions

36,727 questions
Filter by
Sorted by
Tagged with
7 views

### CFG-Infinite recursion

As you see, the string production process never ends. Can someone explain me if this language is regular or not ? $S->ΑΒS$ $A->S$ $B->aBb$
7 views

### Finding Smallest Frontier for Graphs of bounded “width”

Let $G$ be a graph and $X=x_1,x_2,...,x_n$ be an permutation/ordering of the vertex set of $G$. We then let $S_i = \{x_j:j\le i\}$, and $F_i$ be the number vertices $v\in S_i$ that are adjacent to ...
10 views

### Context-free language

L1 = {a^n b^m c^k | 0<2n<=m<=3n, k = m , n,k,m∈N} L2 = {a^n b^m c^k | 0<2n<=m<=3n or 0<5n<=m<=7m , n,k,m∈N} Im trying to prove which language is Context-free and which isn't....
18 views

### Myhill-Nerode to prove a language is non-regular

L = {a^n b^2n c^3n | n∈N^+} I'm trying to prove that L is a non regular language using Myhill-Nerode theorem.
7 views

### Stress Detection using speech

I am a college student who is currently doing fyp on "Stress Detection System using Speech". My sv asked me to use datasets from DEAP and SEED (ecg signal), and using MFCC. But, I am really ...
10 views

### Universal gate proof using De Morgan Theorem?

How to implement of Universal gate using NAND and NOR gates, and how to verify them with DeMorgan's theorem whether they are right? I need expert solution in simple English. Thanks in advance!
21 views

### Two sets such that their closures are equal

I am trying to solve the following problem: Find languages S and T over the alphabet {a, b} such that $S \not\subset T$ and $T \not\subset\ S$ (S is not contained in T and not equal to T, T is not ...
18 views

### Reducing Dominant Set Problem to SAT

I am trying to solve a problem and I am really struggling, I would appreciate any help. Given a graph $G$ and an integer $k$ , recognize whether $G$ contains dominating set $X$ with no more than $k$ ...
13 views

51 views

### Best algorithm to find highest possible number of points from unique cards

I am looking for the optimum algorithm for the following: 10-15 players Each player has between 20 and 40 cards. Each card can have one of up to 200 possible characters, and a separate numerical ...
7 views

### When would you use an edge list graph data structure instead of an adjacency list or adjacency matrix?

In what applications would you choose an edge list over an adjacency list or an adjacency matrix? Sample Question, VisuAlgo: Which best graph DS(es) should you use to store a simple undirected graph ...
22 views

### Runtime difference bewteen Union by Rank and Union by Size for union-find

I was studying Union Find, and according to Wikipedia, there are 2 types of union: union by rank and Union by size. My question is, what is the runtime difference between the two (if any)? Intuitively,...
6 views

### Lower bounds for orthogonal matrix multiplication

Is it possible, according to the current state of knowledge, that orthogonal matrices can be multiplied faster than arbitrary matrices? More precisely, let $T(N)$ denote the worst-case time of the ...
29 views

### Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other

I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two ...
39 views

### $\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al. In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$...
If $X$ is polynomial-time reducible to $Y$ and $X$ is polynomial-time reducible to $Z$, $Y$ is polynomial-time reducible to $Z$? If $X \leq_p Y$ and $X \leq_p Z$ then $Y \leq_p Z$? True, false or we ...
### If X is in NP then $\overline{X}$ is in NP. True, false or “we don't know”? Why?
If X is in NP then $\overline{X}$ is in NP. True, false or "we don't know"? Why?