Problem Solving Session

     I just realized that proving upper bounds and lower bounds are easy if you are given whether its true or false.  However, coming across a3 I realized an issue that stumped me.  When proving or disproving, I feel like the choice of c is given too much freedom and I feel like I'm able to disprove and prove both ways.  For example,

5n^3 - 3n^2 + 2n + 3 is in Big O of 2n^3 - n^2 + n + 1

So proving this would mean that
/exists a c in the positive reals, /exists a b in the naturals, such that for any n in the naturals, n is greater or equal to B implies that 5n^3 - 3n^2 + 2n + 3 <= c(2n^3 - n^2 + n + 1)     (where <= means less than or equal to)

Pick c = ___
Pick B = ___
Assume n in natural, s.t n >= B

5n^3 - 3n^2 + 2n + 3 <= 5n^3 + 2n + 3

5n^3 - 3n^2 + 2n <= 5n^3 + 2n       # cancel 3 from each side, preserve inequality

                                  5n^3 + 2n <= 5n^3 + 2n^3 = 7n^3

Now we must go the other way to prove that 2n^3 - n^2 + n + 1 >= 7n^3

2n^3 - n^2 + n + 1 >= 2n^3 -n^3 + n + 1

2n^3 - n^2 + n >= 2n^3 - n^3 + n               # cancel 1 from each side
                          = n^3 + n  >= c(n^3)

So we have that c(n^3) >= 7n^3,   well if we choose c = 8, then our equality would hold true as long as
n >= 1,  so B = 1.

Now if I wanted to disprove it, so we want to prove the negation of it

For any c in the positive reals, for any B in the naturals, there exists a n in the naturals such that n>= B and
 5n^3 - 3n^2 + 2n + 3 > c(2n^3 - n^2 + n + 1)

Assume for any c in positive reals
Assume for any B in the naturals
Pick n = ___, s.t. n >= B

c(2n^3 - n^2 + n + 1) < c(2n^3 + n + 1)
       2n^3 - n^2 + n    <  c(2n^3 + n)                     # subtract 1 from each side
                                  < c(2n^3 + n^3)
                                  = c(3n^3)

Now we work our way on the other side

5n^3 - 3n^2 + 2n + 3 > 5n^3 - 3n^3 + 2n + 3
                                 = 2n^3 + 2n + 3
                                 > 2n^3 + 2n
                                 > 2n^3

So we've reduced it to
     2n^3 > c(3n^3)

This inequality holds if we choose c = 1/3 and our n = 1 then our inequality holds.
So it seems as though I'm able to disprove/prove both but I know I've probably gone wrong somewhere in this problem.
Anyways, that's my thought on this problem solving session and I hope you guys enjoyed reading it.

Thanks!
                         

Big O of N

     The material over the last few weeks hasn't been too bad.  I'm finding the big O of n stuff alright.  The proofs for finding the upper bound and lower bound isn't too complex but I find it can sometimes be a bit misleading since I feel that there is more than 1 way to prove a upper or lower bound.  I think the one thing I need to go over is the number of steps an algorithm takes and all that.

     I've read a few blogs from the CSC165 website and found them quite interesting. http://halsrislog165.blogspot.ca/
I've read the above blog and one thing I really enjoyed about their blog was the overall progression and understanding of the course.  Their first post is about how troublesome and confusing the material is, but as the course continues, they find it easier and easier.  One thing I found that could use improvement about their blog was their punctuation and sentence structure.
    Another blog that I read was Dan's.
http://go-get-em-slogger.blogspot.ca/
I found his blog enjoyable as he talks about his problems in the course and what he finds difficult, however I feel that he could post more regularly.

2 more weeks!

    I can't believe there's only 2 more weeks left at school.  This semester past by so quickly, its unbelievable.  I've learned a lot from this course, more than I actually thought I would to be honest.  Symbolic statements, the proper negation of statements, laws, axioms in symbolic logic etc etc.  I think thats where most of my learning came from in this course.  I also learned proper proof structures that which I did not know actually existed!  The indentation rules were all very new to me, as I'm used to just writing proofs free-handedly without any structure which is what we kind of do in math.

    I must say I'm also very happy to be in such a good department.  In comparison to the math department, the computer science department is so much better organized, and there are a lot more resources than in math.  The way the courses introduce proofs and concepts is done better than the math department.  I know CSC236 introduces induction and I can see very well that 165 does a good job at "seeding" the concept by the whole implication concept.  For example, you assume some statement is true for k, then if it is true for k, then it must be true for k+1.  In math, it was just straight diving into induction which I found very difficult and rushed.  Anyways, I'll post up my problem solving session sometime soon.


Cheers, Patrick

Order of algorithms

    So another midterm approaches next week.  There's a few things I have to review but where majority of my focus will need to be on the order of algorithms.  It seems as though the order is related to the amount of for/while loops in an algorithm but I remember Danny said not to look at it in such a way.  This is because there are certain algorithms that have a while loop but it doesnt contribute an order or something like that.  I also need to review the sequence a algorithm returns and the upper bounds and lower bounds.  I understand most of the concept but I need to go over computing it.  I should also briefly review the proofs and the proof structure.  Other than that, I should be (hopefully) prepared decently for this midterm.  Anyways, thats it for this week.

Cheers, Patrick.

Proofs and assignment 2

       So, another brutal week at uoft has passed by and there are 5 weeks remaining.  I can't believe how fast this course has passed by.  The proofs we're learning in class are actually very interesting to me.  I'm starting to get the hang of proving symbolic proofs as I find the statements can get quite messy to comprehend when proving.  However, when it comes to the proofs about modular arthimetic, primes, even and odd numbers, I find they're not too difficult.  One thing I learned this week and the week before was how to set up the proof aka "the proof layout" before writing the proof.  This is new to me since in my math courses, there isn't really a layout.  You start with an antecedent or assumption and just go along your way proving.  I also found it quite odd to work with the layout at times since you're kind of working on the conclusion before the proof, because what if there's a proof which you dont necessarily know the conclusion to or if its a proof by contradiction?


      Assignment 2 is coming along its way and I'm already done.  I just need to write it up and finalize it.  I found this assignment wasn't as bad as the first.  I'm finding this one more concise in terms of its statements.  The hardest question I would have to say is number 6 as it utilizes a small trick.  I took me a while to figure out but I think I've got it.  Anyways, I've got to come up with some sort of problem solving post sometime soon.  That's all for this week.

Thanks for reading!

A little more effort?

Hey guys,

    So after a brutal week of midterms, I got my assignments and midterms back.  I guess I need to start putting in a little more effort, as I might have underestimated it.  I didn't do well on either but it was just due to underestimating the course.  I think I lost mostly all my marks from list comprehensions as I didn't practice the past midterms.  Well, now that we're starting proofs, not that its a stranger to me, but I think I've learned my lessons and although I'm familiar with them, I should still keep up with the homework/notes.  The proofs in this course are different from the proofs that I usually do in my other courses, where they involve prime numbers or subsets etc etc.  The ones Danny presented in class and in his notes seem to involve more symbolic logic than concept so I've got to keep up with the material.  Anyways, lesson learned, I already know where I'll be spending my reading week next week (robarts) lol.

Thanks for reading, and cheers!
Patrick.

Proofs, Axioms and Truth Tables

    So yet again, another week has passed filled with equations, axioms, numbers and abstract symbols.  We're starting proofs on Friday, as Danny had introduced it on Wednesday as to what is a proof etc etc.  I'm actually somewhat excited to see what proofs we'll be doing in class and hopefully they wont be too difficult.  I noticed that symbolic logic, like any other mathematical branch, is just based on a finite set of axioms and from those axioms we can deduce and derive more axioms and theorems.  I'm assuming that we will be using the fundamental axioms of symbolic logic and much of its theorems to do our proofs.  I didn't really know what truth tables were used for until I went to tutorial/office hours.  I knew how to use them but didn't know their purpose.  Other than that, thats all I really have to say for this week's "slog" posting.

Thanks for reading.
Patrick.