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.

Filter by
Sorted by
Tagged with
0
votes
1answer
247 views

Proof Review: Integer Factorization is in NP

I want to prove that integer factorization is in NP I have a general idea of how to prove this, and was wondering if I could get a sanity check: I'll show it's in NP by using a non-deterministic TM ...
2
votes
1answer
908 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: ...
0
votes
1answer
3k views

$ADD = {x=y+z}$ with $x, y, z$ binary integers, and $x$ is the sum of $y$ and $z$. Pumping lemma to show that $ADD$ is not regular

Consider the alphabet $\Sigma = \{0, 1, +, =\}$ and the language $ADD = \{x=y+z|x,y$ are binary integers $x$ is the sum of $y$ and $z$ $\}$. This is the (informal) solution I came up with (not sure ...
0
votes
0answers
44 views

Verification of extendible hashing proof

I have to proof this theorem: "An extendible hashing table always contains at least one bucket where only one pointer points to after an element is added". I made this proof, but I'm not completely ...
1
vote
1answer
3k views

Every AVL tree may be red black tree

I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof. Look at my proof. Induction for height. Let's ...
3
votes
2answers
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
1answer
916 views

Prim's algorithm: difference between brute force and PQ approaches

I'm trying to figure out the different way we obtain an MST with a brute force Prim's algorithm compared to the optimized version based on priority queues. Given a graph $G=(V,E)$, the former can be ...
1
vote
1answer
1k views

Optimal prefix code: full binary tree existence

I'm ok following the passages generally used to prove this theorem, like in this question concerning the same subject. Anyway i've the unpleasant feeling that the proof lacks something to be ...
5
votes
1answer
208 views

Simpler proof of Rabin's Compression Theorem?

I was doing a presentation on Rabin's Compression Theorem, when someone in the audience brought up a point I have no answer to. Rabin's Compression Theorem states that every reasonable complexity ...
0
votes
0answers
149 views

Designing a 2 place function that is not Turing computable

I'm just refreshing my memory on Turing machines and computability, and I was wondering how to design a function of 2 arguments that is guaranteed not to be computable. I've seen the proof (by ...
2
votes
0answers
40 views

How to use homomorphisms to prove irregularity [duplicate]

I'm a bit confused on how to use homomorphims to prove irregularity or to prove that a language is not context free. This is what I'm currently thinking: Example 1: Let $L = \{ a^{i}b^{j}c^{k} : i ...
0
votes
1answer
308 views

Proving that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular with pumping lemma

I'm trying to understand the pumping lemma for regular languages and would like to prove that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular. My suggestion is as follows: Assuming $L\in{}REG$...
0
votes
1answer
143 views

Algorithm to recognize Strongly Regular Graph (SRG)

I am looking for an algorithm to determine whether a graph is Strongly Regular Graph (SRG) or not.
4
votes
3answers
412 views

If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$? [duplicate]

Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$. If the statement is true, then can anyone provide a ...
0
votes
1answer
2k views

Multiprocessor Scheduling is NP-Complete [closed]

Consider this version of MS where we have set $A$ of tasks, $l(a)$, length of each task in $A$ and $m$ number of processors and also a deadline $D$. The question is where we can partition A into m ...
0
votes
2answers
482 views

Hoare Calculus Incorrect Assignment Axiom

I'm currently preparing for an exam and recently came across the following exercise and would like to know whether my solution would be correct. Exercise: Prove that the following axiom is not ...
4
votes
2answers
809 views

Solve recurrence relations

A) Solve this recurrence where $T(0)=0$ and write it in O-notation: $T(n)= {2 \over n} (T(0)+T(1)+...+T(n-1))+c$ So, I started to calculate: $T(1)=2(0)+c=c$ $T(2)=1(0+c)+c=2c$ and so on, ...
7
votes
2answers
847 views

Existence of Efficient Set Difference Algorithm

As a foreword, I'm not asking what the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great). Basically, given two sets $S$...
3
votes
1answer
297 views

Proof or refute $n^n = \Omega(n!)$ with the help of Stirling's approximation

I'm trying to proof/refute the following equation: $$n^n = \Omega(n!)$$ Generally I would try to use Convergence Criteria and or l'Hôpital's rule to solve such a problem. $$\lim_{n\to \inf}{{f(n)}\...
2
votes
0answers
733 views

Single machine job scheduling (Greedy heuristic)

Here is a variation of a job-scheduling Problem. Let $J = \{j_1,...j_n\}$ be a set of Jobs for $1 \leq i \leq n$. Given Job length $|j_i|\in \mathbb{N}$, deadline $f_i \in \mathbb{N}$, profit $p_i \ge ...
3
votes
3answers
181 views

Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set

Let $B = \{z \mid (\exists x)\; P(x,z)\}$ and $P$ be a computable predicate. Show $B$ is a recursive enumerable set. My attempt As $P$ is a computable predicate then there is a program that computes ...
5
votes
1answer
187 views

Proving that a language is not in P using diagonalization

Pardon me if i'm missing something which is very obvious here but i cant seem to figure it out. $E=\{ \langle M, w \rangle \mid \text{ Turing Machine encoded by $M$ accepts input $w$ after at most $ ...
4
votes
1answer
107 views

Quasigroups, congruences and recognizable subsets

My question refers to the draft of Mathematical Foundations of Automata Theory, IV.2.1 (pages 89ff in the pdf). I will repeat everything necessary nevertheless: Let $M,N$ be monoids and $\varphi: M \...
-1
votes
2answers
2k views

Using pumping lemma to show $L = \{a^i b^j a^k \ | \ k > i + j\}$ cannot be accepted by an FA

$L = \{a^i b^j a^k \ | \ k > i + j\}$ Use the pumping lemma to show that this language cannot be accepted by an FA. Proof: Suppose $L$ can be accepted by an FA. Suppose a string $s = xyz \...
0
votes
2answers
793 views

Did I correctly prune this min-max search tree using alpha-beta pruning?

I am studying some old past test questions. Is this search tree correctly pruned?
0
votes
1answer
2k views

CFG for $\{a^i b^j : 2 i<j\}$ [duplicate]

So I have a question: Give a CFG for $\{a^i b^j : 2 i<j\}$ And this is my approach: $S\to AB$ $A\to aAb\mid \varepsilon$ $B\to b \mid bB$ A confirmation, or correction, along with how you ...
1
vote
1answer
927 views

How can I show a linear languages are closed against concatenating with regular ones?

This was given as a homework problem but I have already submitted the assignment. I'd like to resolve it at this point for my own satisfaction. Given that $L_1$ is a linear language and $L_2$ is a ...
5
votes
1answer
827 views

Lower bound for sorting n arrays of size k each

Given $n$ arrays of size $k$ each, we want to show that at least $\Omega(nk \log k)$ comparisons are needed to sort all arrays (indepentent of each other). My proof is a simple modification of the ...
14
votes
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 ...
2
votes
2answers
117 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:...
18
votes
1answer
421 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 ...
5
votes
2answers
4k views

String of minimum length in $\{a, b\}^*$ not in a regular expression

I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression. a. $b^*(ab)^*a^*$ My answer: $...
2
votes
1answer
2k views

Context Free Grammar for language L

Can someone help with this: $L=\{a^ib^j \mid i,j \ge 1 \text{ and } i \ne j \text{ and } i<2j\}$ I'm trying to write a grammar for this language? I tried this: $S \to S_1 \mid S_2 \\ S_1 \to aXb ...
1
vote
1answer
403 views

Show $H_1(x)$ is partially computable

I need to show that $H_1(x)$ defined as follows is partially computable. \begin{equation} H_1(x)= \begin{cases} 1 \;\;\;\;\;\text{ if } \Phi(x,x) \downarrow \\ \uparrow \;\;\;\;\; \text{ otherwise} \...
2
votes
1answer
392 views

Prove $\varphi(x)$ to be primitive recursive

Let $\varphi(x)=2x$ if $x$ is a perfect square, $\varphi(x) = 2x+1$ otherwise. Show $\varphi$ is primitive recursive. In proving $\varphi$ to be a p.r. function I think it could come in handy the ...
3
votes
2answers
2k views

Show $x^y$ is a primitive recursive function

As this thread title gives away I need to prove $x^y$ to be a primitive recursive function. So mathematically speaking, I think the following are the recursion equations, well aware that I am ...
6
votes
1answer
857 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 ...
3
votes
1answer
5k 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 ...
3
votes
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 ...
1
vote
1answer
2k views

How to prove transitivity in small-o of asymptotic analysis?

Here is my proof, but I am not sure whether it is correct. We know: $\qquad \begin{array}{l} \forall {c_1},\exists {n_1},0 \le f\left( n \right) \le {c_1}g\left( n \right),\forall n \ge {n_1} \\ \...
7
votes
2answers
91 views

Compute relational composition in $O(|E||V|)$

Definitions: Let $G=(V,E)$ be a DAG without self-loops, and $X \subseteq G$ and $Y \subseteq G$ be graphs. Input: $X,Y$. Output: The relational composition relational composition $X \circ Y$ in $\...
1
vote
3answers
203 views

Proving $\Omega(cf) = \Omega(f)$

I'm trying to prove the following lemma: $c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that: $\Omega(cf(n))$...
2
votes
1answer
156 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 ...
6
votes
1answer
348 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 ...
13
votes
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 ...
0
votes
2answers
3k views

Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid? Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
6
votes
1answer
454 views

Show that the halting problem is decidable for one-pass Turing machines

$L=\{<\!M,x\!>\, \mid M's \text{ transition function can only move right and } M\text{ halts on } x \}$. I need to show that $L$ is recursive/decidable. I thought of checking the encoding of $...
7
votes
1answer
2k views

Proving NP is a subset of the union of exponential DTIME

I need to prove that $\mathsf{NP}$ is a subset of the union of $\mathsf{DTIME}(2^{n^c})$ for all $c > 1$. Let $L$ be a language/decision problem in $\mathsf{NP}$. Then $L$ can be decided given a ...
11
votes
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$ ...
7
votes
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 ...

1
2