Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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.

Filter by
Sorted by
Tagged with
0 votes
2 answers
43 views

Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

I have a regular language $a(a+b)^*$ to which i applied pumping lemma. Let the pumping length be $'p'$ and the example string be $$w=a(a+b)^{p-1}$$. The string satisfies the condition that it is at ...
Dhruv's user avatar
  • 3
-1 votes
0 answers
11 views

Which type of language is need for web development [closed]

I wanted to become a Web developer which type of language is need
Engr naqib Ullah's user avatar
0 votes
1 answer
29 views

Decide if some DFA is accepted

Given Some(DFA) = {|A is a DFA and L(A) is not empty and L(A) is not equal to Σ^(*)} Show Some(DFA) is decidable. I produced the following answer and wanted to check if I am correct T="On input ...
keth's user avatar
  • 1
-1 votes
1 answer
32 views

is my attempt correct? proof that L in P or in NPC? $L=\{G$ is an undirected graph on n vertices VC $U$ and an IS $I$ such that $|U|+|I|=n+10$ \}

I am facing a problem with the validity of the reduction function, may I get some assist in solving this issue, please? $L=\{<G>| G$ is an undirected graph on n vertices that has a Vertex Cover $...
maya cohen's user avatar
0 votes
0 answers
108 views

Interval scheduling; sort by ending times

You have $n$ events on your calendar, defined as intervals with a start time $s_i$ and a finish time $f_i$. The events might overlap, and you want to attend all the events, so you are going to create $k$...
Lipid's user avatar
  • 9
1 vote
2 answers
92 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 ...
Theorynoob's user avatar
0 votes
0 answers
59 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, ...
Hugh Mann's user avatar
1 vote
2 answers
250 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 ...
kjkjkjkjkj's user avatar
1 vote
1 answer
252 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, ...
Hugh Mann's user avatar
1 vote
1 answer
60 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(...
Sung Jin-Woo's user avatar
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 ...
Uri Greenberg's user avatar
2 votes
1 answer
324 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 ...
Shy Cohen's user avatar
0 votes
0 answers
35 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 ...
blu's user avatar
  • 1
1 vote
0 answers
24 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 ...
Ayrat's user avatar
  • 1,075
3 votes
3 answers
316 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 ...
Michal Dvořák's user avatar
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 $\,$ $\,$ $\,$ $\,$ $\,$ $\,$ $\,...
pierrovoltela's user avatar
0 votes
2 answers
192 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 ...
ChocolateOverflow's user avatar
2 votes
1 answer
68 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 ...
davinci_07's user avatar
0 votes
1 answer
399 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 ...
Hjm's user avatar
  • 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$. $...
KetDog's user avatar
  • 157
5 votes
0 answers
258 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 ...
vesii's user avatar
  • 223
2 votes
1 answer
874 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 ...
Mohamad S.'s user avatar
1 vote
1 answer
74 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 ...
njk23's user avatar
  • 13
1 vote
0 answers
59 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 ...
NiRvanA's user avatar
  • 159
2 votes
2 answers
156 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 ...
Abhishek Ghosh's user avatar
1 vote
1 answer
80 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})$...
Algebruh's user avatar
  • 321
2 votes
1 answer
103 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 ...
MathematicsBeginner's user avatar
1 vote
2 answers
355 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 ...
billiam's user avatar
  • 43
2 votes
1 answer
162 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 \;...
somitra's user avatar
  • 123
1 vote
1 answer
399 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 ...
Abhishek Ghosh's user avatar
2 votes
2 answers
1k 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 ...
LukeTheWolf's user avatar
0 votes
1 answer
375 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 ...
RedYoel's user avatar
  • 217
0 votes
1 answer
764 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 ...
scand1sk's user avatar
  • 125
0 votes
1 answer
111 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 ...
DarK_FirefoX's user avatar
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 ...
timmer's user avatar
  • 1
0 votes
2 answers
189 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}∩(...
pk00's user avatar
  • 27
1 vote
1 answer
603 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 ...
pk00's user avatar
  • 27
0 votes
1 answer
312 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$ ...
ChocolateOverflow's user avatar
0 votes
2 answers
573 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 ...
convxy's user avatar
  • 221
1 vote
2 answers
130 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 ...
NimaJan's user avatar
  • 353
0 votes
2 answers
85 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 ...
J. Schmidt's user avatar
1 vote
1 answer
71 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{...
JaVaPG's user avatar
  • 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 ...
zell's user avatar
  • 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 $...
Rapiz's user avatar
  • 51
2 votes
1 answer
119 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]$...
Abhishek Ghosh's user avatar
0 votes
1 answer
258 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: ...
Abhishek Ghosh's user avatar
1 vote
1 answer
74 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 ...
Abhishek Ghosh's user avatar
0 votes
2 answers
91 views

Asymptotic calculation check for triple-nested for-loops

I have the following repetition structure: ...
bmanicus131's user avatar
4 votes
2 answers
1k 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 ...
scanny's user avatar
  • 206
0 votes
1 answer
163 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: ...
Mandy's user avatar
  • 177