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
5 votes
0 answers
70 views
+150

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 ...
1 vote
1 answer
80 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 votes
1 answer
97 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$ ...
0 votes
1 answer
195 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: ...
2 votes
1 answer
174 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 ...
1 vote
1 answer
44 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 ...
0 votes
2 answers
91 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 ...
0 votes
1 answer
65 views

Asymptotic calculation check for triple-nested for-loops

I have the following repetition structure: ...
1 vote
0 answers
36 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 ...
1 vote
1 answer
53 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})$...
2 votes
1 answer
59 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 ...
1 vote
1 answer
149 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 ...
2 votes
1 answer
61 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 \;...
0 votes
0 answers
99 views

My proof for equivalence of DFA and NFA

I came up with this proof for the following theorem: If $L$ is a language produced by an nfa, then there exists a dfa $M$ where $L(M) = L$. Is it correct? If it's not, what are the flaws of my proof,...
3 votes
2 answers
6k views

Inventory planning problem solved through dynamic programming

I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed). 15-11: Inventory Planning, p.411 The Rinky Dink Company makes machines that resurface ice rinks. The ...
2 votes
2 answers
103 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 ...
2 votes
3 answers
268 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
1 answer
160 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 ...
3 votes
2 answers
2k views

If $L$ is a regular language, how to prove $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular?

If $L$ is a regular language, prove that the language $L_1 = \{ uv \mid u \in L, |v| =2 \}$ is also regular. My idea: $L$ can be represented as a DFA and then you could add 2 consecutive ...
0 votes
1 answer
468 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 ...
0 votes
1 answer
57 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 ...
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 vote
1 answer
239 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 ...
0 votes
2 answers
78 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}∩(...
-1 votes
1 answer
68 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 $...
4 votes
2 answers
567 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 ...
0 votes
2 answers
432 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 ...
1 vote
2 answers
118 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 ...
0 votes
2 answers
66 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 ...
1 vote
1 answer
35 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{...
1 vote
1 answer
32 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 ...
2 votes
1 answer
95 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 vote
1 answer
56 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 ...
2 votes
2 answers
120 views

Not sure if my solution to following recurrence is correct

I have a recurrence relation, it is like the following: $T(e^n) = 2(T(e^{n-1})) + e^n$, where $e$ is the base of the natural logarithm. To solve this and find a $\Theta$ bound, I tried the following:...
6 votes
1 answer
370 views

What is the complexity of this subset merge algorithm?

Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath. The ...
0 votes
1 answer
153 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
1 answer
359 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
1 answer
564 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
2 answers
171 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
1 answer
241 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
2 answers
93 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 ...
-1 votes
1 answer
66 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
1 answer
188 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
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 < ...
3 votes
2 answers
1k 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
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 ...
0 votes
0 answers
52 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
645 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
1 answer
74 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
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 + ...