20
votes
5answers
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 ...
1
vote
1answer
62 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?
0
votes
1answer
301 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 ...
0
votes
1answer
50 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 ...
3
votes
2answers
409 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 ...
0
votes
0answers
71 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, ...
2
votes
1answer
140 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 ...
7
votes
2answers
211 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 ...
2
votes
2answers
80 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 ...
1
vote
1answer
75 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 ...
1
vote
1answer
50 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 ...
1
vote
1answer
235 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, ...
0
votes
1answer
375 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 ...
1
vote
2answers
107 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
2
votes
1answer
162 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 ...
0
votes
2answers
2k views

Proof of correctness of binary search

I have just written a pseudo-code (actually in Python) of a binary search algorithm. ...
1
vote
4answers
279 views

Proving these are/are not regular

In my computing class we just finished studying regular languages. I didn't do as well as I had hoped on my work so I was wanting more insight on the correct way to go about these proofs. My ...
9
votes
2answers
1k views

How can I learn about proofs for computer science?

I study computer science at a university. My school offers several courses where various proofs are expected, but there is no course that introduces the fundamental concepts of proofs and how to write ...