Week 9 - March 16, 2013

I haven't posted anything for a few weeks now.  I was very busy during midterms and therefore neglected to make any posts for some time.  Today we had our second term test.  We had three proofs and about 50 minutes to complete them.  On the first question we had to prove a statement, the second we had to disprove by first negating the statement and finally we had to prove another statement.

I understood and completed all three proofs with time to spare.  I found them to be very straight forward and also very similar to the proofs we had done previously in the course.  At this point in the course, that is now that we are moving away from proofs and towards algorithm complexity, I can now say that I am not having any significant difficulties with any proofs that we have done so far.  This is something worth noting because as I've said in previous posts, when I was first introduced to proofs a few years ago, I never came anywhere near as close to understanding what I was doing as I have now.

Last term I watched several online MIT lecture videos regarding complexity, purely out of curiosity.  They were very informative and I believe have helped me understand the material we are currently covering in this course more easily.  Complexity is very interesting because it allows a programmer to determine the most (or least) number of steps that a program will go through as it is moving through an algorithm.  This allows a programmer to compare for example the efficiency of one algorithm to another, where each may use a different approach to solve the same problem.

I've been working on a game for a few months now, programming in Visual Basic 6.0.  In this 2D game the player can control persons on a map.  This is map contains walls, chairs and doors, all of which the persons must collide with.  Recently I've been working on an algorithm that takes lines and squares and creates a polygon mesh that the persons use to navigate around the map.  At first I was using an algorithm that created points that the persons would use to move around an obstacle, however the problem was that I was creating at most 6 points per line.  At first this algorithm worked very well and was quite accurate, however as the map grew in size, the number of points increased to such a number that the program would take several seconds just to calculate the movement path of a person.

As a result I began working on a polygon navigation mesh, which will reduce the number of points the program will have to search through when calculating the person's path.  In terms of complexity, the path finding algorithm I used before was operating in O(n^2) time.  With my new algorithm, the program is now operating in O(n) time making it much faster.  Now simply running the two different algorithms would clearly show me what algorithm is more efficient.  I would just have to keep track of how long it took for the algorithm to find the shortest path using the points or the navigation mesh.  However, if before ever even writing the code for these two algorithms, I instead calculated the worst case scenario using complexity, I could have easily determined which algorithm would be more efficient without ever having to test them.  From what I understand this is one of the main uses of complexity, that is to determine beforehand the efficiency of an algorithm.

As I continue to create my 2D game, I will now use complexity to determine which algorithms I should or should not implement before I ever write a single line of code.

Week 5 - February 9, 2013

Last week I did not post anything as I simply had nothing to say.  We began our introduction to proofs but for the most part I had nothing to write that was worth noting.  However this week I do have a few things to discuss.  We had our first term test yesterday in class.  We were given about 50 mins to complete the test which consisted of 3 questions on 6 pages.  Throughout the week I was a little nervous about the test because I really wanted to do well, not only for academic credit but also for reinforcement.  As I stated in the previous post I am feeling very confident in my understanding of the course material so far.  If there was a concept that I didn't fully grasp I either figured it out through practice problems provided on the course website or through watching lecture videos online.  Having said that, I really didn't want to take this test and find out that in fact I really didn't understand everything that I thought I did.  If however I do well on the test then I will feel that indeed the methods I have been using so far have been working and that my future in the course should be promising.

Now regarding the test, all I can say is that I found it to be very straight forward.  The first problem was about the Python 'quant' functions we had seen before.  This problem tested our understanding of universal and existential quantification, as well as our ability to negate such statements.  The second question involved two statements similar in form to an epsilon-delta proof.  It asked to negate each statement and determine which of the two, the original or the negation, was true and to explain why.  The last question involved an English statement.  We were asked to write in symbolic form the contrapositive, converse and negation of the statement.

I look forward to receiving the results of the test as I feel I did very well.  I completed the test in about 30 mins and had ample time to review the test once over.  The only thing that still bothers me in terms of course material is when we are asked to write the negation of an implication.  Now I feel very comfortable with negation, however at the beginning of this course we learned that the contrapositive of say S1: A -> B is

Not B -> Not A.  The converse would be B -> A, and what was called the negation would be 

Not A -> Not B, however on Wikipedia at least, this is not referred to as negation but rather the inverse of S1.  So negating both sides of an implication is really called the inverse and not the negation of the implication.  Instead, the negation of S1 would be A ^ Not B, (read as A and not B).  Now A and not B is not the same as: If not A then not B, which is the inverse, so clearly the inverse is not the same as the negation of an implication.  So on the test for example, when we were asked for the negation, I simply wrote A ^ Not B, A being the antecedent and B being the consequent.  I do hope that this is correct and that I wasn't really asked to provide the inverse of the implication.  So at this point I see the inverse and the negation as being two separate things.  I'm still not sure if this is correct or not; in any case I wonder why we referred to the inverse of an implication as the negation at the beginning of this course?

Week 3 - Jan 29, 2013

I missed the tutorial this week since I was sick.  Luckily the my TA sent me a copy of the quiz and the professor provided the solution.  I was happy to find that the solution I found was indeed correct.

I don't really have much to say about this past week, except that so far I feel fairly comfortable with the course material.  The professor posted a PDF on the course website which contains many problems along with the solutions.  I have been working on those problems and found them very helpful in getting me used to the material, especially when it comes to concepts that I'm not sure I understand.

I have also completed the first assignment which is due this Wednesday.  At first glance it seemed a little daunting, however after I worked on the problems from the PDF above I found the assignment to be fairly straight forward.  I am very comfortable with negation, implication and laws of distributivity and associativity and such.  The only thing I can say that I am not one hundred percent comfortable with is when we are translating a statement from English into symbolic language.  For the most part I don't have a problem with it, however sometimes it can be difficult as English sentences are sometimes quite vague.  The professor had said in class that this problem is quite common and that most people find translating English to symbols more difficult then the converse.

At this point, since I've understood most if not all the material covered so far, I am feeling very eager to tackle proofs.  As I've stated in my first post, I have seen proofs before, but when they were introduced to me we had never gone through all the symbols and concepts at the foundation of proofs which we have done in this course.  Since I understand the fundamentals now, I am very confident that this time around I will understand what it is that I am doing when it comes to proofs.

Week 2 - Jan 19, 2013

This past week we covered a number of different topics, however I feel there is one concept that stands out. We looked at universal and existential quantification; that is how to identify one from the other as well as how to prove and disprove both.  So far I feel very comfortable with this material and I believe this will set the foundation which will be used to approach proofs in the future (a foundation I had never been introduced to before this class).  

We also covered topics such as implication, equivalence and looked at some new notation which will allows us to translate English statements into mathematical statements.  The one thing I had some trouble with was predicates.  In class as well as in the online course notes I could never find an explanation as to what exactly the predicate, P(x) for example, represented.  Fortunately I was able to find a video online (https://www.youtube.com/watch?v=DmCltf8ypks) which explained in detail what a predicate was, as well as what the statement "For all x, P(x)" means.  I had first thought that when we define a predicate we indicated the situation in which that predicate was true.  For example, P(x) : x > x + 1.  Initially I thought this meant that P(x) is true when x > x + 1.  

After watching the video above I now understand that the predicate P(x) is either true or false, but only when it's input variables are bound by either a value or a quantifier thus making it a proposition.  Once the predicate P(x) is bound, it is no longer a predicate but a proposition.  This proposition is then either true or false.  In the example above with P(x) : x > x + 1, if we bind x = 1 then the proposition P(1) is false.  We could also bind P(x) with a quantifier.  For example, "For all x, P(x)".  This statement says "For all x, the proposition P(x) is true".  This statement is of course false, because for any x, x > x + 1 will always be false.

Week 1 - Jan 10, 2013

After being on the waiting list for a few days I was finally approved for the course.  I am a second year physics student who has decided to pursue a computer science degree instead. As a result, I have already taken a fair number of mathematics courses.  In my first year I took MAT137 and along with most of the class I had a really hard time.  The one subject that I really wasn't prepared for was proofs.  I had never seen proofs in high school and to this day I am not at all comfortable with them.  I can't speak for everyone else, but I really didn't like the way proofs were taught to me in MAT137.  I'm someone who learns best by reading, but the textbook was terrible and the professor no better.  In any case, I never really understood what I was doing when it came to proofs, and I really hope that this course will change that.

From what I've seen so far professor Danny Heap seems to really care about the students actually learning the material instead of just putting chalk to board.  At this time I can say that I am very excited about this class.