Questions which also contain a solution that needs to be checked for correctness and completeness

learn more… | top users | synonyms (2)

2
votes
2answers
61 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 ...
4
votes
2answers
68 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 ...
3
votes
1answer
54 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 ...
1
vote
0answers
133 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 ...
2
votes
2answers
72 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
110 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
81 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
vote
1answer
269 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 = ...
0
votes
2answers
158 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
212 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
105 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 ...
3
votes
1answer
156 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 ...
6
votes
3answers
2k 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
1answer
84 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 ...
10
votes
1answer
151 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 ...
4
votes
2answers
271 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: ...
0
votes
1answer
332 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
136 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
107 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
568 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
292 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 ...
2
votes
1answer
1k 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 ...
3
votes
1answer
218 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
251 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
56 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
2answers
141 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: ...
1
vote
1answer
103 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 ...
5
votes
1answer
168 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 ...
6
votes
2answers
411 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
478 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
247 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 ...
6
votes
1answer
185 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 ...
10
votes
1answer
658 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 ...
6
votes
2answers
404 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. ...