# Tagged Questions

59 views

44 views

### Strong Induction, assuming k<n where k and n are not numbers

In strong Induction for the induction hypothesis you assume for all K, p(k) for k If for example I am working with trees and not natural numbers can I still use this style of proof? For example if I ...
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 ...
70 views

### Does proving that a function is not in big O mean that the function is in big Omega?

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?
428 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 ...
577 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 ...
103 views

### In this insertion sort algorithm for example, how would I prove the algorithm's time complexity is O(n^2)?

Take the following insertion sort algorithm: I know it's O(n^2) fairly easy by examining it. But as far as proving it's O(n^2), how would I go about doing that? I could add up all the operations, ...
142 views

### Why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $N \log N$?

As the title says, why is it so difficult to prove that the discrete Fourier transform (DFT) cannot be calculated in faster time than $O(N \log N)$? This is a famous open problem in ...
215 views

### maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
87 views

### eccentricity in vertex transitive graphs

I am trying to prove the following.. If $G$ is a veretx transitive graph, then how can we prove that eccentricity of every vertex is same? Getting no idea from where to start? How to prove the same ...
82 views

### Why no cut-vertices or cut edges in a graph where eccentricity is same for all vertices

I need help to prove the following statement. There are no cut-vertices or cut-edges(bridges) in a graph where eccentricity is same for all vertices. I am getting that if the graph contains a ...
51 views

### Proof of algorithm refinement

I recently had an interview in which I was asked to produce an algorithm to that computes the pairs of integers, from a list, that add up to a integer k. I then had to increase the time efficiency of ...
251 views

### Reduction to prove that the function is not computable

Use reduction to show that the following function is not computable, where P is any python program that takes a single input x: sotrue(P) = true, if P(x) returns true for every value of x, ...
460 views

### Visibility and Kernel of Polygon

I have an exercise to a give very rigorous prove to two observations of computation geometry. Obviously there are related. I've tried to prove them and wrote few ideas. Please take a look at them, and ...
120 views

### Clarification about what is meant in this slide by “induction on the typing rules”?

I'm lost on what's happening here. This is regarding MinML( "an idealized programming language" ) . More pics below: Thank You Very Much
164 views

### Using pumping lemma to prove that $L = \{(01)^m 2^m \}$ is not regular?

I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \}$ is not regular. This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$. Consider ...
2k views

### Proof of correctness of binary search

I have just written a pseudo-code (actually in Python) of a binary search algorithm. ...