# 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.

99 questions
Filter by
Sorted by
Tagged with
1answer
419 views

### Number of Hamiltonian cycles on a Sierpiński graph

I am new to this forum and just a physicist who does this to keep his brain in shape, so please show grace if I do not use the most elegant language. Also please leave a comment, if you think other ...
5answers
6k 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 ...
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 ...
1answer
3k views

### subsets of infinite recursive sets

A recent exam question went as follows: $A$ is an infinite recursively enumerable set. Prove that $A$ has an infinite recursive subset. Let $C$ be an infinite recursive subset of $A$. Must $C$ ...
0answers
105 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 ...
2answers
2k views

### Maximise sum of “non-overlapping” numbers in square array - help with proof

A question was posted on Stack Overflow asking for an algorithm to solve this problem: I have a matrix (call it A) which is nxn. I wish to select a subset (call it B) of points from matrix A. The ...
2answers
90 views

1answer
856 views

### Generalizing the Comparison Sorting Lower Bound Proof

Let's start with the comparison sorting lower bound proof, which I'll summarize as follows: For $n$ distinct numbers, there are $n!$ possible orderings. There is only one correct sorted sequence of ...
1answer
347 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 ...
2answers
4k views

1answer
115 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 ...
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 < ...
2answers
1k 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 ...
1answer
292 views

2answers
82 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 ...
1answer
907 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: ...
1answer
77 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]$...
1answer
549 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 ...
1answer
73 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 ...
1answer
155 views

### Error in Generating Function Solution

I am currently working my way through An Introduction to Analysis of Algorithms to stay sharp with recurrences as well as learn generating function techniques. However my analyses and the books ...
1answer
94 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{...
1answer
249 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 ...
1answer
2k views

0answers
732 views