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.

98 questions
Filter by
Sorted by
Tagged with
4 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 ...
27 views

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 ...
53 views

27 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{...
26 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 ...
41 views

517 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 ...
112 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 ...
121 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 ...
75 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 ...
63 views

70 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 ...
516 views

### Proof that G is a Tree After DFS and BFS form the same tree T [closed]

Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth first search ...
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 ...
1k 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 ...
266 views

### Proving a language is non-regular using the Pumping Lemma for non-binary strings [duplicate]

I am unsure of how to prove this language is non-regular. I do not even know where to start to develop a string that would prove the language is non-regular by contradiction. Any help would be ...
91 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{...
46 views

### Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle?

As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle. My attempt is that: So this graph would be an counter example that ...
96 views

### Optimizing coin splitting - Is this algorithm as fast as I think?

In a recent exam, I've been asked to solve the following problem: The problem Two players play the following game: Given a sequence of coin values $v_1,\ldots,v_n (n \vert 2)$ the players ...
955 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 ...
343 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 ...
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 ...
72 views

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 ...
55 views