# Tagged Questions

25 views

### A property regarding intervals

While I was solving a problem on TopCoder I used the following assumption. I have n intervals: $[a_1,b_1], [a_2,b_2],...,[a_n,b_n]$ and a number $T$ such that:  a_1 + a_2 + ... + a_n \leq T \leq ...
3k views

### Is a brute force method considered a proof?

Say we have some finite set, and some theory about a set, say "All elements of the finite set $X$ satisfy condition $Y$". If we let a computer check every single member of $X$ and conclude that the ...
172 views

### Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
74 views

### Easy Proofs with Functions and Big-O

I have these two questions. I tried answering them, but got them wrong and I don't know how to answer them correctly. This is not homework --- I'd appreciate a solution (at least to one), and an ...
66 views

### Cut-off Subtraction in Coq

I am new to the world of computer assistant proof programs in general, and Coq in particular. As a result, I have sought to prove some elementary results about integers as a way to … At the moment, I ...
437 views

### Proving a tight bound on the worst case running time of an algorithm?

This exercise I don't understand what 'give a tight bound' implies here. The correct way to prove this is to consider that the runtime is in O and then use the definition of BIG O to prove that it ...
51 views

### Prove that if $x$ is a real number, and $x-\lfloor x\rfloor \ge 1/2$, then $\lfloor 2x\rfloor=2\lfloor x\rfloor +1$

Prove that if $x$ is a real number, and $x-\lfloor x\rfloor \ge \frac{1}{2}$, then $\lfloor 2x\rfloor=2\lfloor x\rfloor +1$ I'm so confused because i don't completely understand the rules for floor ...
208 views

### Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
597 views

### Learning Proofs (for Computer Science)

Harvard's math curriculum, for freshmen, is divided into 4 classes beyond the BC Calculus level, Math 21, 23, 25 and 55. Math 21 is your classic plug-and-chug multivariable calculus and linear algebra ...
734 views

### Formally prove that $\Theta(\max(f,g)) = \Theta(f+g)$

I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g)$ where $(f+g)(n) = f(n) + g(n)$ and $(\max{f,g})(n) = \max(f(n), g(n))$ I know that $\Theta$ is the combination of the ...
165 views

### Connected Components Graph proof

I am trying to do this one problem for a homework set, and am not entirely sure how I would even start this proof. Here is the question Prove, by induction on k, that a connected component of k nodes ...
73 views

### Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...
916 views

415 views

### Order of growth proofs?

I was wondering how people go about showing the proofs with orders of growth? Currently, I have the following functions and I know what order they go in, but I'm not sure how to prove them. I simply ...