-3
votes
1answer
59 views

State whether the following claim is true, and then prove or disprove it. Give a detailed structured proof, justifying every step. [closed]

State whether the following claim is true, and then prove or disprove it. Give a detailed structured proof, justifying every step. $$\forall n \in \mathbb{N}, [(\exists k \in \mathbb{N}, n = ...
0
votes
2answers
34 views

Trying to disprove a statement - some partial working included

I am trying to find a counter example to show that the statement below is false, but I am having difficulty in trying to find a reasonable argument. Here is the statement: $n^2-12n + 35 \geq 0$ for ...
0
votes
3answers
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 ...
2
votes
3answers
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 ...
22
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
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?
0
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
2answers
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 ...
0
votes
0answers
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, ...
2
votes
1answer
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 ...
7
votes
2answers
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 ...
2
votes
2answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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, ...
0
votes
1answer
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 ...
1
vote
2answers
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
2
votes
1answer
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 ...
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
286 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 ...