The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [check-my-answer]

Questions asking us to check whether your solution is correct are considered off-topic (per http://meta.cs.stackexchange.com/questions/597/) and should not be posted on this site.

Filter by
Sorted by
Tagged with
0
votes
1answer
27 views

Prove $\epsilon(S\cap T)\subseteq S \cap T$

Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$. Prove $\epsilon(S\cap T)\subseteq S \cap T$ Definition of $\epsilon$- closure for epsilon NFA is: ...
1
vote
1answer
62 views

Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$

Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$. I would like to prove this by contradiction but I don't know if my idea is correct. Definition of $...
0
votes
1answer
88 views

How to prove by contradiction that every nonempty hereditary language contains the empty string?

A language L is called hereditary if it has the following property: For every nonempty string x in L, there is a character in x which can be deleted from x to give another string in L. Prove by ...
0
votes
2answers
73 views

how to prove that log(n!) >= c n log(n) for some c >0?

as reading the book Algorithms by Dasgupta, C.H Papadimitriou. on Page 63. And it is well known that $\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$. There are many ways to see this. The ...
1
vote
1answer
60 views

In-place matrix transposition using rotations

Some time ago I invented an algorithm for in-place matrix transposition using rotations. A matrix of size N×M is represented as a one-dimensional array of size N*M, which is also the future storage ...
2
votes
2answers
50 views

Number of possible heaps on $\{1,…,2^h-1\}$

Let $C_h$ be the number of possible heaps for the set of keys $\{1,...,2^h-1\}$. Determine a recurrence relation for $C_h$ via the substitution method and prove it. Definition A binary tree ...
-1
votes
1answer
53 views

Show that the Language L is not regular (pumping lemma) [closed]

$L = \{cda^nb^n\mid n\in \Bbb N\} \cup \{a,b,d\}^*$ Assuming $L$ is regular then there exist a pumping length $n$ for $L$. Lets use w = $cda^nb^n$. Thus $w \in L$ and $|w| = 2n+2$ $\implies$ $|w| \...
0
votes
1answer
51 views

Minimal paths as solution of a linear program of a special network flow

Let $G= (V,E)$ be a given directed weighted graph, and $s,t$ two specified nodes, so that there is no negative cycle reachable from $s$, and $t$ is reachable from $s$. We're looking for the shortest ...
3
votes
2answers
3k views

Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead?

First Slide: Find Max(A) // INPUT: A[1..n] - an array of integers // OUTPUT: an element m of A such that m >= A[j], for all 1 <= j <= A.length max = A[j==1] for j = 2 to A.length if max < A[...
3
votes
2answers
651 views

Sorting an “almost sorted” array in sub linear time

I am given an "almost sorted" array with the condition that each element is no more than $k$ places away from its position in the sorted array. I need to show that it is impossible to sort this array ...
2
votes
1answer
297 views

Proof of NP Completeness of set-partition problem

I have reduced subset sum problem to set partition problem but do not know whether it is correct and so I need your help. MY METHOD In subset sum problem we have to find a subset $S_1$ of set $S$ so ...
0
votes
0answers
27 views

Search operation in hash table

Suppose that we have a hash table of some size $s$ and we have a set of keys $K$. We decide to hash the keys using chaining. Now assume that we randomly select $k \in \mathbb{N}$ keys from $K$ and ...
2
votes
1answer
48 views

Is this proof for showing that $EQ_{CFG}$ is co-Turing-recognizable incorrect?

I have been searching for proofs that show that $EQ_{CFG}$ is co-Turing-recognizable. When searching for proofs I can only find proofs on the following form: Construct a TM $M$ which recognizes the ...
0
votes
1answer
56 views

Is complement $L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ context-free

$L = \{ w : |w|_{a} \equiv |w|_{b} \vee |w|_{c} \equiv |w|_{d} \}$ In my opinion complement of the L language is $L^{C} = \{ w : |w|_{a} \neq |w|_{b} \wedge |w|_{c} \neq |w|_{d} \}$ I choose to ...
0
votes
1answer
41 views

$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$

$ L = \{xyyz\in\{0,1,2\}^{*} : y \neq \epsilon \wedge \exists_{a \in \{0,1,2\}} |y|_a \equiv 0 \}$ I think this languages is regular. I write regular expression: $(1 + 2 + 0) ^ {*} (11 + ...
1
vote
0answers
175 views

Proof that G is a Tree After DFS and BFS form the same tree T [closed]

Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth first search ...
9
votes
0answers
99 views

Can we say McCarthy and Hoare had the same objective in the 60s regarding a mathematical theory of computation?

I don't think there's any way to ask a very precise question here, so this might be considered opinion based. Nevertheless, it seems the question is clear enough because I'm asking whether these two ...
-1
votes
1answer
87 views

Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
3
votes
1answer
43 views

Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle?

As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle. My attempt is that: So this graph would be an counter example ...
2
votes
1answer
56 views

How to Apply Elementary Axioms from Kleene Star to an Inequality

Axioms For * \begin{align} 1 + aa^* &\leq a^* \\ 1 + a^*a &\leq a^* \\ b + ax &\leq x \to a^*b \leq x \\ b + xa &\leq x \to ba^* \leq x \\ \end{align} Elementary Results \begin{...
1
vote
3answers
74 views

Optimizing coin splitting - Is this algorithm as fast as I think?

In a recent exam, I've been asked to solve the following problem: The problem Two players play the following game: Given a sequence of coin values $v_1,\ldots,v_n (n \vert 2)$ the players ...
4
votes
1answer
101 views

Prove: if $\delta_D(q0, w) = p$ then $\delta_N(q0, w) = {p}$

In my textbook, it presents the theorem, "A language L is accepted by some DFA if and only if l is accepted by some NFA". My textbook explains that the "if" portion of the proof is given by the subset ...
0
votes
0answers
403 views

Show that P is a subset of NP

Okay, before I start with the question I would like to point out that I am aware that there are many proofs of this question online. However, I am interested in showing this with the definitions of my ...
0
votes
0answers
244 views

Prove DFA constructed by subset construction has exactly the states and transitions of NFA plus transitions to new dead state

Prompt: if $N$ is NFA that has at most one choice of state for any state and input symbol, then the DFA constructed from $N$ by subset construction has exactly the state and transitions of $N$ plus ...
2
votes
1answer
64 views

Question about proving that Rado's function is non-computable

I am currently following the proof, found here, that Rado's function $$ \Sigma (n) = \max \{ \text{# of 1's that may be written to a tape by an n-state turing machine} \} $$ is non-computable. Within ...
1
vote
1answer
38 views

Solving Recurrence relation with master method?

I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that? $$T(1) = c>0 $$ $$T(n) = 9T(n/3) + f(n)$$ $$f(n) = n^2\cdot lg^3 (n) +...
12
votes
5answers
5k views

Flaw in my NP = CoNP Proof?

I have this very simple "proof" for NP = CoNP and I think I did something wrongly somewhere, but I cannot find what is wrong. Can someone help me out? Let A be some problem in NP, and let M be the ...
1
vote
1answer
109 views

Maximum value of LOOP-Program turing-computable

Lets consider the class of "simple" LOOP-Programs. A LOOP-Program P is inducively defined as: $P_1: x_i = x_j$ and $P_2:x_i = x_i +1$ are LOOP-Programs. We also define a length property $l(P)$ ...
1
vote
1answer
208 views

Show that function is not turing-computable?

We have two functions: $f_1: \mathbb{N}\rightarrow \mathbb{N} \quad $ $f_2: \mathbb{N}\rightarrow \mathbb{N}$ By definition $f_1$ is turing-computable while $f_2$ is not. Then we define a third ...
0
votes
1answer
212 views

Universal Lossless Compression? [closed]

It is not possible to losslessly compress all files of size $n$ using a single algorithm, as there are more files of size $n (2^n)$ than of size $p, p: p < n ( 2^n-1)$. Via the pigeon hole ...
0
votes
1answer
281 views

How to prove this language is not regular (via Fooling Set)

By using this fooling set, I am able to prove that the concatenation of bz is in the language L, but I still need to prove that az is not in the language to complete the proof. This is also the ...
1
vote
3answers
150 views

Is Goedel's 1st theorem not algorithmically derivable?

First let me explain what I mean by algorithmically derivable. An algorithm must be able to come up with the proof without prior knowledge of the proof, in the same way mathematicians and computer ...
12
votes
2answers
2k views

Is Karp Reduction identical to Levin Reduction

Definition: Karp Reduction A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if ...
1
vote
2answers
160 views

Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$

I need to find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$. I thought first to make a substitution: $m=\log n$. Then: $$ T(2^m)=T(2^{m \over 2})+10\log m $$ Let $S(m)=T(2^m)$: $$ S(m)=S\big({m ...
0
votes
1answer
76 views

Proof Review: Integer Factorization is in NP

I want to prove that integer factorization is in NP I have a general idea of how to prove this, and was wondering if I could get a sanity check: I'll show it's in NP by using a non-deterministic TM ...
2
votes
1answer
817 views

Proving the loop invariant for a simple program in Hoare logic

I was studying loop invariant and came across Tomas Petricek's example. Here's the equivalent(I believe) program after I revised it a bit for proof in Hoare logic: ...
0
votes
1answer
987 views

$ADD = {x=y+z}$ with $x, y, z$ binary integers, and $x$ is the sum of $y$ and $z$. Pumping lemma to show that $ADD$ is not regular

Consider the alphabet $\Sigma = \{0, 1, +, =\}$ and the language $ADD = \{x=y+z|x,y$ are binary integers $x$ is the sum of $y$ and $z$ $\}$. This is the (informal) solution I came up with (not sure ...
0
votes
0answers
40 views

Verification of extendible hashing proof

I have to proof this theorem: "An extendible hashing table always contains at least one bucket where only one pointer points to after an element is added". I made this proof, but I'm not completely ...
4
votes
2answers
748 views

Solve recurrence relations

A) Solve this recurrence where $T(0)=0$ and write it in O-notation: $T(n)= {2 \over n} (T(0)+T(1)+...+T(n-1))+c$ So, I started to calculate: $T(1)=2(0)+c=c$ $T(2)=1(0+c)+c=2c$ and so on, ...
3
votes
3answers
160 views

Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set

Let $B = \{z \mid (\exists x)\; P(x,z)\}$ and $P$ be a computable predicate. Show $B$ is a recursive enumerable set. My attempt As $P$ is a computable predicate then there is a program that computes ...
1
vote
3answers
190 views

Proving $\Omega(cf) = \Omega(f)$

I'm trying to prove the following lemma: $c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that: $\Omega(cf(n))$...
-1
votes
2answers
2k views

Using pumping lemma to show $L = \{a^i b^j a^k \ | \ k > i + j\}$ cannot be accepted by an FA

$L = \{a^i b^j a^k \ | \ k > i + j\}$ Use the pumping lemma to show that this language cannot be accepted by an FA. Proof: Suppose $L$ can be accepted by an FA. Suppose a string $s = xyz \...
1
vote
1answer
1k views

Every AVL tree may be red black tree

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof. Induction for height. Let's ...
2
votes
1answer
549 views

Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
1
vote
1answer
864 views

Optimal prefix code: full binary tree existence

I'm ok following the passages generally used to prove this theorem, like in this question concerning the same subject. Anyway i've the unpleasant feeling that the proof lacks something to be ...
5
votes
1answer
188 views

Simpler proof of Rabin's Compression Theorem?

I was doing a presentation on Rabin's Compression Theorem, when someone in the audience brought up a point I have no answer to. Rabin's Compression Theorem states that every reasonable complexity ...
0
votes
0answers
142 views

Designing a 2 place function that is not Turing computable

I'm just refreshing my memory on Turing machines and computability, and I was wondering how to design a function of 2 arguments that is guaranteed not to be computable. I've seen the proof (by ...
2
votes
0answers
40 views

How to use homomorphisms to prove irregularity [duplicate]

I'm a bit confused on how to use homomorphims to prove irregularity or to prove that a language is not context free. This is what I'm currently thinking: Example 1: Let $L = \{ a^{i}b^{j}c^{k} : i ...
0
votes
1answer
119 views

Algorithm to recognize Strongly Regular Graph (SRG)

I am looking for an algorithm to determine whether a graph is Strongly Regular Graph (SRG) or not.
0
votes
1answer
249 views

Proving that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular with pumping lemma

I'm trying to understand the pumping lemma for regular languages and would like to prove that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular. My suggestion is as follows: Assuming $L\in{}REG$...