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.
101
questions
1
vote
2
answers
73
views
Union of non regular and regular language
So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not.
Since I found counterexamples for both cases I want to look at more ...
- 11
0
votes
0
answers
39
views
Union of non-regular and finite language
So i got this problem where should prove whether the union of a non regular language $L$ and a finite Language $L'$ is regular or not.
My Idea was to show that any regular Language $L_r$ cannot be ...
- 11
0
votes
0
answers
54
views
Question about implication in proof that predecessor subgraph is a breadth-first tree
Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:
Theorem 22.5: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, ...
- 67
-1
votes
1
answer
49
views
Trying to give a proof about graphs. Having a hard time giving proof for Kruskals algorithm. Can you check my answer?
Question: Let G(V, E) be an undirected connected finite graph with the weight function
w : E → R+. Let T be a minimum spanning tree of G. Prove that there exists a run of
Kruskal’s algorithm that ...
- 19
1
vote
1
answer
196
views
Question about step in proof that predecessor subgraph forms a breadth-first tree
Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS:
Theorem 22.5: (Correctness of breadth-first search)
Let $G = (V, E)$ be a directed or undirected graph, ...
- 67
1
vote
1
answer
59
views
Validity of time complexity analysis
Given recurrence equation :
$T(N) = T(N-1) + T(N-2) + N$
Given base case
$ T(1) = -3$
So I rewrote the equation as
$ T(n)+ n - T(1) = T(n-1)+ (n-1) - T(1) + T(n-2)+(n-2)-T(1)$
Substituting $ V(n) = T(...
- 113
0
votes
0
answers
26
views
Is the min-cut size of a directed graphs transpose the same as that of the original?
I was wondering whether the transpose of graph maintains the same size of the minimal cut in a directed graph (digraph).
This may be trivial as I haven't been able to find anything here or on Google ...
2
votes
1
answer
296
views
if P = NP, does it mean that P = NP = NP-complete?
Lets assume P = NP, so all problems in NP are decidable in polynomial time,
Therefore I can solve all problems in NP in polynomial claiming P = NP = NPC.
But then, how come Σ* belongs to P = NPC ...
- 23
0
votes
0
answers
28
views
Consolidating my proof for the merge step of mergesort
I've been spending time strengthening my ability to conduct inductive proofs and made one for the mergesort algorithm - specifically the merge part, as the entirety of the algorithm is comparatively ...
- 1
1
vote
0
answers
19
views
Errors in examples of Vardi's paper "Linear Temporal Logic and Linear Dynamic Logic on Finite Traces"
The paper Linear Temporal Logic and Linear Dynamic Logic on Finite Traces has the following examples on page 4:
Q1. (Update to Q1: solved. See the comment by DCTLib.) The first example says that the ...
- 1,055
3
votes
3
answers
150
views
Find a unit square containing most of the points
Given points $p_1,\ldots,p_n$ in $\mathbb{R}^2$, the task is to find an axis-aligned unit square containing the maximum number of points. I came up with and $O(n^3)$ algorithm as follows.
Observation ...
- 267
0
votes
0
answers
16
views
Need help verifying the complexity of an algorithm [duplicate]
I have the following algorithm which takes as an input a non negative integer n :
i = n
while i > 0 do :
$\,$ $\,$ $\,$ $\,$i = i - 1
$\,$ $\,$ $\,$ $\,$j = 1
$\,$ $\,$ $\,$ $\,$ $\,$ $\,$ $\,...
0
votes
2
answers
159
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,111
2
votes
1
answer
59
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
216
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 ...
- 47
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
220
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
583
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
68
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
55
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 ...
- 159
2
votes
1
answer
133
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,112
1
vote
1
answer
72
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
93
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
270
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
135
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
325
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,112
2
votes
2
answers
803
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
316
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
659
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
99
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
37
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
137
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
462
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
258
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,111
0
votes
2
answers
562
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
127
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
80
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 ...
- 737
1
vote
1
answer
64
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
39
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
78
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
116
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,112
0
votes
1
answer
244
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,112
1
vote
1
answer
68
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,112
0
votes
2
answers
90
views
Asymptotic calculation check for triple-nested for-loops
I have the following repetition structure:
...
- 29
4
votes
2
answers
923
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
156
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
363
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
657
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
261
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
445
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