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.

7 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9
votes
0answers
98 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 ...
2
votes
0answers
683 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 ...
0
votes
0answers
26 views

Search operation in hash table

Suppose that we have a hash table of some size $s$ and we have a set of keys $K$. We decide to hash the keys using chaining. Now assume that we randomly select $k \in \mathbb{N}$ keys from $K$ and ...
0
votes
0answers
358 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
236 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 ...
0
votes
0answers
40 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
0answers
139 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 ...