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.

Flooded with assignments.

    Ahh...  Another long week at uoft.  Getting swamped with exercises and problem sets and I just so happened to be lucky enough to have the 165 assignment due the same day as my 301 problem set.  Life is good (sarcasm, of course).  The assignment wasn't too horrible.  The only parts that I found difficult were the negation translations of certain conjunctions such as the "or" and "and" as well as an "if and only if".  Question 3 was quite brutal in terms of translating long symbolic logic into English that made sense.  Translating it from symbols to English was not a problem at all, however, trying to make it sound like natural and non-robotic was what I found difficult.  I've written most of my assignment 1 up, but just need to clarify 2-3 questions with Danny.  During the write up process, it was pretty painful I must say, to look for each symbol in word or to copy and paste it from wiki, so I just ended up using "/exists", "/and" and "/forany" etc etc.

    So far the course hasn't been too heavy for me.  However, I do admit that it is very time consuming and I do have to review the lecture notes from time to time as there are conjunctions and negation translations that I have not yet drilled into my head.  I've been able to keep up with my tutorial problem sets as well, and I'm pretty caught up in the course.  I've also found that Danny's teaching strategy is very helpful.  He lectures but posts the slides online so that way in class, you can fully devote your attention to what he's saying.  Most of my math courses are not like this.  I'm usually focusing all my attention on copying notes and whatever the professor says, just flies right through my head.  Not exactly a great way of comprehension.  I really wish my other professors would adopt the same teaching strategy but I guess it would just encourage students to not come to class etc. etc.

Thanks for reading, Patrick.

Quantifiers, Negation and Logic

    So, as the second week of the term comes to an end, I've concluded two things about this course.  The first is that I realize there will not be any actual mathematics being used in this course, even though its called mathematical expression.  Second is that I've realized its purely based on symbolic logic.  I've realized why this is such a crucial course in the computer science department.  The use of symbolic logic helps you develop critical thinking processes and skills required for programming or that may be very useful in programming.  Sometimes when I'm reading over someones code and I try to decipher their code or make sense of what they're trying to do, its tough.  There will be while loops over for loops over a while loop with a counter in the back, etc, etc, and it gets all boggled up in your head.  Courses like 165 will help with these type of situations and thinking steps.  I realized this, this week, during lecture when Danny was using tons of symbols in the scope of quantifiers with sets and subsets etc etc.

Anyways, that's what I thought of this weeks lecture.
Thanks for reading, Patrick.

First week of 165

Hey readers!

    I usually don't do blogs but since it's required I guess I'm here.  Over the semester, my blog will be covering my experience with the courses, what I find easy, difficult, how I found past assignments and tests and what I think of the overall course and my experience, of course.  My sentence structure and grammar as well as proper use of punctuality may not be as strong as most blogs on this website, mainly because my focus of study is Math and Computer Science (double major).  I'm in third year math and first year computer science.  I'm currently about a semester or two away from finishing my math major and I'm enrolled as a third year student at uoft.  The courses I'm currently taking this semester are MAT315, MAT301, CSC148, CSC165, AST251.  Anyways, thats enough about me, I'll start talking about my experience for the first week in csc165.

    My first week in csc165 was warmly welcomed by my professor Danny Heap.  He introduced himself as Danny, and requested that we not call him professor, sir or anything like that other than Danny.  I found this very reassuring as this was a very kind and friendly gesture to the first day of class.  As Danny introduced the course, I knew right away what type of course I would be dealing with this semester.  It appeared to be symbolic logic.  Being in third year math, not trying to brag or anything, I've had quite some experience with the notations being introduced during the end of the first week, such notations being "there exists" and "for any".  With that being said, I didn't find the first week or that particular class very unfamiliar.  I can, however, say that Danny did a good job on introducing the notations to the many students who are unfamiliar to this language as I can imagine if I hadn't seen these symbols before, I would be a bit confused myself.
Overall, I enjoyed the first week of class and look forward and actually surprisingly, am somewhat excited for this course to proceed further into the school year.

Cheers,
Patrick.