Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Questions asking us to check whether your solution is correct are considered [off-topic](http://meta.cs.stackexchange.com/questions/597/) and should not be posted on this site.

-1
votes
0answers
22 views

Syntax error in the my Mysql procedur [closed]

I have this procedure that will work every night to delte information, i tried to save it in mysql but the mysql tell me that thier is a synatx error. ...
-1
votes
0answers
11 views

How to find all occurrences of some event given constraints in domain relational calculus?

I have a table rooms(start_date, start_time, room_id, building_id, event_id, duration) which represents a schedule of events that take place in a certain campus which consists of multiple buildings. I ...
0
votes
0answers
61 views

Show that P is a subset of NP

Okay, before I start with the question I would like to point out that I am aware that there are many proofs of this question online. However, I am interested in showing this with the definitions of my ...
0
votes
0answers
55 views

Prove DFA constructed by subset construction has exactly the states and transitions of NFA plus transitions to new dead state

Prompt: if $N$ is NFA that has at most one choice of state for any state and input symbol, then the DFA constructed from $N$ by subset construction has exactly the state and transitions of $N$ plus ...
2
votes
1answer
75 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 ...
2
votes
1answer
46 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 ...
1
vote
1answer
27 views

Solving Recurrence relation with master method?

I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that? $$T(1) = c>0 $$ $$T(n) = 9T(n/3) + f(n)$$ $$f(n) = n^2\cdot lg^3 (n) +...
0
votes
0answers
46 views

Two Pointer Algorithm Proof (Greedy) Roadblock

I am practicing some competitive programming problems and encountered a version of the two pointer algorithm that I got stuck trying to prove its correctness. Here is the outline. Input : An array of ...
1
vote
1answer
65 views

Maximum value of LOOP-Program turing-computable

Lets consider the class of "simple" LOOP-Programs. A LOOP-Program P is inducively defined as: $P_1: x_i = x_j$ and $P_2:x_i = x_i +1$ are LOOP-Programs. We also define a length property $l(P)$ ...
1
vote
1answer
78 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 ...
-1
votes
1answer
72 views

Universal Lossless Compression? [closed]

It is not possible to losslessly compress all files of size $n$ using a single algorithm, as there are more files of size $n (2^n)$ than of size $p, p: p < n ( 2^n-1)$. Via the pigeon hole ...
0
votes
1answer
91 views

How to prove this language is not regular (via Fooling Set)

By using this fooling set, I am able to prove that the concatenation of bz is in the language L, but I still need to prove that az is not in the language to complete the proof. This is also the ...
1
vote
3answers
141 views

Is Goedel's 1st theorem not algorithmically derivable?

First let me explain what I mean by algorithmically derivable. An algorithm must be able to come up with the proof without prior knowledge of the proof, in the same way mathematicians and computer ...
1
vote
2answers
92 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
1answer
52 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
479 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
291 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
32 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 ...
0
votes
1answer
634 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 ...
2
votes
1answer
321 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
565 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
157 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
103 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
157 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
86 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
157 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
769 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
286 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
574 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, ...
6
votes
2answers
333 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
171 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
582 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
144 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
175 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
92 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
1k 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
571 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
1k 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
586 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
514 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 ...
11
votes
5answers
5k 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
96 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:...
17
votes
1answer
308 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
1k 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: $...
1
vote
1answer
976 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
293 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
227 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
607 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 ...