All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
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 $
0
votes
0answers
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 ...
0
votes
0answers
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....
-1
votes
0answers
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.
0
votes
0answers
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 ...
-2
votes
0answers
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!
0
votes
1answer
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 ...
0
votes
0answers
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$ ...
0
votes
0answers
13 views

Describe this Turing machines

I need to describe a Turing machine that it can be multitape. $M = (Q,Σ,Γ,δ,q_0,q_a,q_r)$. Who decide that language. $L=\{\#uqv\#u'q'v'\#:u,v,u'v'∈(Γ\setminus\{\sqcup\}^*,q,q'∈ Q$ and$ (u,q,v) \...
2
votes
1answer
58 views

Randomized Algorithms: High-Probability vs. Expectation

Hopefully this question isn't too general, but I was wondering what the relationship is between randomized algorithms that perform well with high-probability and those that perform well in expectation....
0
votes
0answers
14 views

Greedy Probabilistic Algorithm for Exact Three Cover

I have a probabilistic greedy algorithm for Exact Three Cover. I doubt it'll work on all inputs in polytime. Because the algorithm does not run $2^n$ time. I will assume that it works for some but not ...
-1
votes
0answers
29 views

If B ∈ NP and A <= B then A ∉ EXP?

If B ∈ NP and A <= B then A ∉ EXP. True, false or we don't know?
-1
votes
0answers
28 views

If A ∉ NP then A ∈ co-NP. True, false or we don't know?

If A ∉ NP then A ∈ co-NP. True, false or we don't know?
4
votes
1answer
20 views

Isn't this Commentz-Walter algorithm buggy?

I've been trying to piece together an implementation of the Commentz-Walter string search algorithm. The idea is to construct a state machine from a trie, working backwards from the earliest feasible ...
0
votes
1answer
24 views

Call stack is hard to maintain in my brain. What should I?

When I study Binary Search Tree, I try to use a pencil and paper to scratch the process of in-order traversal. However, I find that it is hard to maintain the call stack in my brain without paper and ...
0
votes
4answers
73 views

Existence / non-existence of a sequence with short longest increasing subsequence and decreasing subsequence?

Can there exist any integer sequence $A$ of length $N$ with all unique elements such that the length of its Longest Increasing Subsequence as well as that of its Longest Decreasing Subsequence is less ...
-2
votes
0answers
26 views

The amount of final states of the NFA's and DFA's that accept all regular languages

I have to prove or disprove that there exists a natural number N, so that for every regular language there exists an NFA(without $\epsilon$-transitions) that has maximum N final states. This is ...
0
votes
0answers
10 views

Consistent theory based on L and not(A->A) is a theorem

I am working on this problem in which I have a theory T based on L language and the only information we have is that T is consistent and |- not(A -> A). Given this information, how can I know if ...
-3
votes
0answers
23 views

How to solve turn based algorithm (from Hackerrank) [closed]

someone help me to solve : https://www.hackerrank.com/contests/moraxtreme-4-0/challenges/sad-meiers-trivilization if someone know the strategy please explain me.
1
vote
0answers
22 views

Compile most likely text based on faulty snippets

Input: Recognized text from images of labels taken with a cell phone in varying conditions. One image may enclose the entire text, or just a part of it. Expected output: The most likely version of the ...
0
votes
0answers
17 views

Strings and Lcp

We are given a string S with |S|=N We have to answer Q queries Each query has an integer x as input We have to report $\sum_{i=x}^n LCP(i,x)$ Where Lcp(i,x) denotes the length of the largest ...
2
votes
0answers
17 views

Ensuring integral result from integral linear program

An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is ...
0
votes
1answer
47 views

How to solve balancing parentheses problem?

I'm new to dynamic programming and find this problem in http://www.hackerrank.com which is impossible to do I've been trying to solve it by 3 days now, the main issue with this problem is that the ...
0
votes
1answer
24 views

Worst Case for AVL Tree Balancing after Deletion

After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST). The Balancing ...
0
votes
0answers
11 views

Extracting informations from a graphic

I'm currently working on a data processing algorithm which involve (for now) grabing values from bidimentional graphs (x;y values) by hand. It is used to do polynomial fitting. I speak about this kind ...
0
votes
1answer
23 views

If A is polynomial-time reducible to B and B is NP-Complete, can I say that A is NP-Complete as well?

I searched a lot on internet, including here, but I couldn't find an explanation that could convince me. The problem is the same of the title, if A is polynomial-time reducible to B and B is NP-...
-1
votes
0answers
16 views

With Σ = {a,b}, give a dfa for L= w1aw2 : |w1 |≥ 3, |w2 |≤ 5}

I racked my brain,I saw other people's solutions and it don't make sense. I think my biggest problem is I don't know when one string ends,like for example w1 is >=3 and it can have how many ever b'...
0
votes
1answer
25 views

Count number of ways in which atomic operation(s) of n different processes can be interleaved

PROBLEM: Count the number of ways in which atomic operation(s) of n different processes can be interleaved. A process may crash mid way before completion. Suppose there are a total of n different ...
0
votes
0answers
11 views

deciding discounts on set (which can be multiple) of products [closed]

I tried finding this question on SO over here but I dont find it relevant. Let's say ...
0
votes
1answer
9 views

What is the difference between $SIZE(n^k)$ and $P/poly$?

$SIZE(n^k)$ is defined as the class of problems solvable with Boolean circuits (of fan-in two) with $O(n^k)$ gates. While $P/poly$ is defined as those problems over {0,1}* which can be solved by an ...
0
votes
0answers
18 views

What is a make sense (meaningful) example of language that an unrestricted grammar could generate?

I have learned that: Unrestricted grammar is used to define (or describe) a formal language. Unrestricted grammar is used to define recursively enumerable set [https://en.wikipedia.org/wiki/...
1
vote
1answer
33 views

What are the disadvantages of Fibonacci Heaps?

A Fibonacci heap is a data structure for priority queue / heap operations. It seems to have the best complexity for all operations: Since it has the best performance, why not use it everywhere? What ...
0
votes
1answer
32 views

Prove: If $T'$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

Prove: If $T'=(V,F')$ is a spanning tree, but not a MST of $G=(V,E)$, then there are edges $e' \in F'$ and $e \in $ $E$ \ $F'$ such that $w(e)<w(e')$ and $T'$ \ $\{e'\} \cup \{e\}$ is a spanning ...
0
votes
2answers
28 views

How do compilers assure stability?

Suppose you need a c compiler. It would be preferable to write that compiler in a c-like language, given the complexity of a compiler of that degree. At best, the c compiler would be written in c, but ...
1
vote
1answer
27 views

CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a $CFG$ $G$ generates $1^*$ is decidable. The proof goes like this: $1^* \cap G$ is context free since it is the intersection of a regular ...
1
vote
0answers
10 views

What is known about this independent set generalisation?

An applied problem I am working on could be modeled as the following problem on graphs: Given an undirected graph $G=(V,E)$ and an integer $k>0$, find the largest set $S\subset V^k$ such that for ...
0
votes
0answers
22 views

Is there a logic-to-numeral mapping which preserves uniqueness (contrary to the Gödel coding)?

Given the two equivalent terms $A \vee B$ and $B \vee A$, Gödel numbering returns two various codes $2^{4}.3^{\overline{A}+1}.5^{\overline{B}+1}$ and $2^{4}.3^{\overline{B}+1}.5^{\overline{A}+1}$, ...
1
vote
1answer
35 views

Is Monotone 3-SAT with exactly 3 distinct variables untractable?

I have given the following SAT variation: Given a formula F in CNF where each clause C has exactly 3 distinct literals and for each C in F either all literals are positive or all literals are negated....
2
votes
1answer
12 views

Algorithm to generate a token as survey summary

I'm searching for an algorithm but struggle to find anything, as I'm not sure how to formulate it correctly. I created a simple survey app in Angular with 24 questions and each has 2-5 answers. When ...
0
votes
0answers
11 views

Does $L \leq_p K$ and $K\in NP$ implies $L \in NP$?

I only find theorems like $L \leq_p K$ and $K\in P$ implies $L \in P$ in books, but I think the same should be true for NP as well. Or is there anything I am missing? I am asking since this would be ...
-1
votes
0answers
35 views

Runtime error : How do I avoid it for a large test case? [closed]

I have been solving the CSES problem set and I am stuck on the following problem : CSES-Labyrinth Here is my solution : ...
1
vote
1answer
20 views

Lower bound on comparison-based sorting

I have a question from one of the exercises in CLRS. Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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,...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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]$...
0
votes
1answer
36 views

If X is polynomial-time reducible to Y and X is polynomial-time reducible to Z then Y is polynomial-time reducible to Z?

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 ...
-1
votes
1answer
32 views

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?

15 30 50 per page
1
2 3 4 5
735