Questions tagged [check-my-answer]
Questions asking us to check whether your solution is correct only are considered off-topic (per http://meta.cs.stackexchange.com/questions/597/). Please pinpoint your doubt and provide *a specific question* to which a meaty answer can resolve your doubt whether your answer is correct or not.
89
questions
0
votes
2
answers
122
views
My attempt at the "This statement is false" paradox
(I haven't read any literature on this paradox nor am I good at formal proofs, so this is just my intuitive thoughts on the paradox.)
If we assume the statement "This statement is false" as ...
- 1,101
2
votes
1
answer
46
views
Safety VS. Liveliness Property
I have to prove whether a certain property is safety or liveliness. The property represents the absence of deadlock so I expected it to be a safety property from what I read online.
The issue is that ...
- 121
0
votes
1
answer
60
views
4DM is NP-complete
Is 4DM NP-complete?
An instance of 4DM consists of four disjoint sets X, Y, W and Z of size k, and a set Q of quadruples $Q = \{ (x, y, w, z) \mid x ∈ X, y ∈ Y, w ∈ W, z ∈ Z \}$
Question: Is there a ...
- 37
0
votes
1
answer
37
views
Recurrence Relation Proof check
A question I was given
$T(0) = 1,$ $T(1)=0,$ $T(n)= 2T(n-2)$
I think the possible solution is $T(n)=2^n$
Proof: by induction. Base Case:
$n=0$ $T(0)=2^0=1$
Inductive Hypothesis: Assume for some $n$. $...
- 157
5
votes
0
answers
174
views
Prove: Self-organizing list that uses Move-to-Front is 2-Competitive
Preparing for my finals in my "advances algorithms" course. Usually there is a question to prove one of the theorems that was given over the course. I'm currently trying to write a full ...
- 223
2
votes
1
answer
306
views
Disprove: if L is decidable then Prefix(L) is decidable
The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
- 453
1
vote
1
answer
54
views
Is finding the union of all minimum hitting sets NP-hard?
Let's start with the well-known minimum hitting set problem (known to be NP-hard): given some collection of sets: $U = \{S_1, S_2, S_3\} = \{\{1, 2, 5, 9\}, \{1,2,7\}, \{42, 13, 23, 1, 2\}\}$ for ...
- 13
1
vote
0
answers
46
views
Prove that a dominating set has minimum cardinality in a "unit interval graph"
I am given the definition of a unit interval graph, e.g. $G = (V, E)$ such that $\forall v \in V$ there is a weight $x_v \in \mathbb{R}$ and nodes $u, w$ has an edge iff $|x_u - x_w| < 1$. I am ...
- 149
2
votes
1
answer
105
views
Tigers and elephants can't drink water from a pond simultaneously, while more than one tiger or more than one elephants can drink water simultaneously
Below is a question on synchronization mechanism which was asked in an interview in Indian Statistical Institute, M.Tech CS. I got hold of it from here.
There is a forest where there are tigers and ...
- 1,042
1
vote
1
answer
63
views
Why is $\mathsf{QP}$-hardness impossible?
I found this task in an old exam and couldn't get my head around it:
We define the class of languages $\mathsf{QP}$ as follows: $$\mathsf{QP} = \bigcup_{k \in \mathbb N} \mathsf{DTIME}(2^{\log(n)^k})$...
- 301
2
votes
1
answer
65
views
Another proof of a codeforces problem
Link to the problem: https://codeforces.com/problemset/problem/1221/A.
The problem:
You are playing a variation of game 2048. Initially you have a
multiset $S$ of $n$ integers. Every integer in this ...
0
votes
2
answers
177
views
Check Proof Using Pumping Lemma to Show Language Not Regular
Please check my proof where I use the pumping lemma to show that the language $B=\{0^n1^n | n≥0\}$ is not regular.
I'll state the pumping lemma here for clarity:
Pumping lemma If $A$ is a regular ...
- 33
2
votes
1
answer
105
views
Proving that the given Context free grammar generates strings with unequal number of a's and b's
Here is the grammar given on the wikipedia:
$$
S \rightarrow T \;|\; U \\
T \rightarrow VaT \;|\; VaV \;|\; TaV \\
U \rightarrow VbU \;|\; VbV \;|\; UbV \\
V \rightarrow aVbV \;|\; bVaV \;...
- 123
1
vote
1
answer
259
views
Hierarchy of parser grammars vs Chomsky hierarchy of grammars and the comparsion of the language acceptance power of each parser grammar
While reading the text Modern Compiler Implementation in C by Andrew Appel I came across the hierarchy of grammar given below.
The above diagram is very helpful in understanding the correlation among ...
- 1,042
2
votes
2
answers
346
views
Prove that $f(n)$ is $= \Omega(g(n))$ but not $= O(g(n))$
I am trying to prove the following statement.
if $\displaystyle \lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}= \infty$, then $f(n) = \Omega(g(n))$ but $f(n) \neq O(g(n))$
What I've done so far
Using ...
- 165
0
votes
1
answer
241
views
Prove that the greedy algorithm for the minimum edge cover problem is 2-approximation
As said, I had to prove that the greedy algorithm:
Initialize $C = ∅$
Look for an un-covered vertex and add one of its edges to $C$
Repeat 2 while there's uncovered vertices
Is a 2-approximation ...
- 217
0
votes
1
answer
548
views
Average time complexity of linear search
It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear).
I have read ...
- 125
0
votes
1
answer
76
views
Douglas-Peucker line simplification algorithm time complexity
I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of $O(n^2)$ where $n$ is the number of points ...
- 139
0
votes
0
answers
36
views
Please help me fix / finish this Fitch proof, I am stuck
Using the Fitch application and only Intro and Elim rules (& REIT if necessary), prove that
$$\forall x \forall y (P(x) \implies Q(y)) \iff (\exists x P(x) \implies \forall y Q(y))$$
is a logical ...
- 1
0
votes
2
answers
95
views
Show $\{0^𝑚1^𝑛|𝑚≠𝑛\}$ is not regular
So I have the question: show "Show $\{0^𝑚1^𝑛|𝑚≠𝑛\}$ is not regular". I've already seen various proofs for this question, but they all have one step I don't get.
They all take: $\bar{L}∩(...
- 27
1
vote
1
answer
367
views
Longest path in a strongly connected component
So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component.
My idea is: In a strongly connected component ...
- 27
0
votes
1
answer
176
views
DFA containing substring to not containing substring by flipping acceptability of all states?
For example, $D_1 = \{ w | w$ does not contain baba as substring$\}$
For $D_1$, I would make $F_1 = \{q_4\}$.
As I tried to design $D_2$ as the complement of $D_1$ ...
- 1,101
0
votes
2
answers
507
views
Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$
Solve the following recurrence-relations:
my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$ but i didn't get the same ...
- 211
1
vote
2
answers
123
views
Language of all even-length words with no 1's in left half
Consider the following language:
$$L=\{w \in \textstyle\Sigma_1 ^*\mid|w| \text{ is even and 1's can only occur in the second half of $w$}\},$$
where $\Sigma_1 = \{0,1\}$.
I need to show that this is ...
- 343
0
votes
2
answers
74
views
Are different assignments allowed for the implication graph proof of 2-SAT being in P?
One proof for $2-SAT$ being in $P$ uses the implication graph, i.e. one creates 2 vertices per variable $a$, one for each possible literal ($a$ and $\neg a$). One then adds 2 arcs per clause $(a \lor ...
- 665
1
vote
1
answer
42
views
Reduction from VC to {a,k | a is a 3DNF (disjunctive normal form) and there exists an assignment satisfying exactly k clauses in a}
I have the following question :
\begin{align}
L_2 = \{a,k\ \mid \text{ a is a 3DNF (disjunctive normal form) and} \\
\text{there exists an assignment $z$ satisfying exactly $k$ clauses in }a\}
\end{...
- 125
1
vote
1
answer
33
views
Not understanding this way of proving undecidability of the termination problem
I am reading some slides on Algorithm to understand why termination is an undecidable problem. The slides say the following:
– Assume termination(P) always terminates and returns true iff P always ...
- 374
-1
votes
1
answer
76
views
Use of pumping lemma for not regular languages. (Proof Verification)
$L=\{w \in \{0,1,a\}^* | \#_0(w) = \#_1(w) \}$
We show that L is not regular by pumping lemma.
We choose w=$0^p 1^p a$
|w| = 2p+1
Now |xy| has to be $\leq p$
So x and y could only contain zeros. And $...
- 51
2
votes
1
answer
110
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]$...
- 1,042
0
votes
1
answer
227
views
Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)
I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function.
The versions are as follows:
...
- 1,042
1
vote
1
answer
61
views
For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$
I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that ...
- 1,042
0
votes
2
answers
89
views
Asymptotic calculation check for triple-nested for-loops
I have the following repetition structure:
...
- 29
4
votes
2
answers
652
views
Proof for LeetCode: 11. Container With Most Water problem
UPDATE: I abandoned this initial approach in favor of a more powerful invariant I worked out after posting. I've detailed that one in an answer below.
I'm new to algorithm correctness proof-writing ...
- 206
0
votes
1
answer
155
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:
...
- 177
1
vote
1
answer
362
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 $...
- 177
0
votes
1
answer
631
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 ...
- 113
0
votes
2
answers
217
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 ...
- 3
1
vote
1
answer
324
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 ...
user107819
2
votes
2
answers
100
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 is ordered ...
- 145
-1
votes
1
answer
67
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| \...
- 11
1
vote
1
answer
258
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 ...
- 659
3
votes
2
answers
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 < ...
- 33
0
votes
0
answers
64
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
1
answer
750
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 ...
- 123
0
votes
1
answer
52
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 + ...
- 53
0
votes
1
answer
75
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 ...
- 53
1
vote
0
answers
779
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 ...
- 91
10
votes
0
answers
114
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 ...
- 237
2
votes
1
answer
2k
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 ...
- 43
-1
votes
1
answer
327
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 ...
- 155