End of CSC165

Exams are about to start and classes are coming to an end. I remember seeing those symbols for the first time in class. I had no idea what they meant so I knew from that moment that this class would expand my knowledge by quite a bit. Reflecting on that last statement, I'd say its true.

I came into this class without much prior knowledge of mathematical expression or computational logic but now I know so much more. 

If i go to a party and people on the dance floor are talking about math or logic (which happens I swear), I can officially join in on the conversation.

Of course this is just the first course and there's a lot more to learn but that's an adventure for another time, right now... it's all about the exams.

Diagonal

In this post I will be attempting to solve the "Diagonal" problem given in class.

The problem is as follows: 

You have a rectangular grid made up of m rows and n columns where m, n represent positive whole numbers. Suppose you draw a line from the upper left corner to the lower right corner. How many of the grid squares will the line pass through the grid?

Understanding the problem: 
We are given a grid and we must determine how many squares will be intersected by a line drawn from the top left corner to the lower right corner.

Devise a plan: 

The goal here is to reduce the problem as much as possible. In other words, by reducing a larger grid into a smaller section which can be scaled back to the original grid, the problem can be simplified. We do this by dividing each side by the greatest common divisor of the two dimensions. For example, Figure 1 can be reduced to Figure 2 since Figure one is 4x2, it can be reduced to 2x1 since GCD(4,2) = 2

Figure 2

Figure 1

Once you have the smallest and simplest grid possible. You can compute the number of grids intersected by the equation L + W - 1 where L is the number of rows of this reduced grid and W is the number of columns of this reduced grid. Since this rectangle is a reduced version of the original, we must multiply (L + W - 1) by the GCD(X,Y) to get the number of grids intersected in the original grid.

The actual equation is GCD(X,Y) * (L + W - 1)
where X is the number of rows of the grid
where Y is the number of columns of the grid
where L = X/GCD(X,Y)
where W = Y/GCD(X,Y)

In python the code would be:
    from fractions import gcd

    def diagonal(length, width):
        return length + width - GCD(length, width)

Carry out the plan:
Let's suppose we are given the example in the handout where X = 4 and Y = 6.
In the diagram, 8 squares are intersected. If we use our solution with these values we get: 
Squares intersected = GCD(X,Y) * (L + W - 1)
                            = GCD(X,Y) * (X/GCD(X,Y) + Y/GCD(X,Y) - 1)
                            = GCD(4,6) * (4/GCD(4,6) + 6/GCD(4,6) - 1)
                            = 2 * (2 + 3 - 1)
                            = 2 * 4
                            = 8

Look back:
Does this solution work for every single possible combination of X and Y?
Of course, if the GCD of X and Y is 1, the reduced grid would have the same dimensions as the original grid but the solution would work regardless.
After verifying my solution with many different inputs, I believe this is the general solution. 
---------------------------------------------------------------------------------
If you look at a rectangular parallelepided that had X rows, Y columns and O layers, you'll notice that if you take the largest two of these three values and plug them into the equation for grids. It'll produce the number of cubes that a line from one vertex to the opposite vertex would intersect.

Proofs

A short haiku about proofs:

We did proofs this week.

I finished them all quite fast.

I still have more work.

Assignment 2 is officially over. Surprisingly, I found it easier relative to the first assignment. With proofs, once you figure out the crucial step, the rest of the proof writes itself. The crucial step is easy to find in most questions due to the nature of the question. They have obvious answers as to whether they are true or false which presents huge hints as to what the crucial step should be. Nevertheless there were some questions that took intensive thought and pen/paper to work out.

What I found challenging was incorporating the definition of MOD and GCD into the proofs. I've always had a hard time expressing my ideas clearly on paper. I'd say that I've improved since the beginning of the course.

The next part of the course will be focusing on the complexity of algorithms; this is probably one of the most important aspects of computer science since a program’s effectiveness is not solely based on functionality, but heavily on efficiency. I had a decent start to this next portion of the course, I understand the thought process that must go through one’s head when engaging a complexity problem. However, I’m not 100% clear on the part where you simplify the equation to only one variable and the part where you over count a variable. (n – 1  into n). I’ll keep working on it, but I’m going to end this post here. On a side note, I really need to keep up with these posts; the last few weeks have been quite hectic and I never got around to updating my Slog.

Hmmm, need to work on my time management.

Power of Truth Tables

Whenever I get stuck on a concept or problem, whether it be from a lecture or a tutorial problem set; I find it  helpful to create a truth table. So far this course has taught me numerous new concepts and my favorite way to reinforce these new concepts is to analyse them and see why each concept is true. 

For example, understanding DeMorgan's Laws:

1. The negation of a conjunction is the disjunction of the negations.
2. The negation of a disjunction is the conjunction of the negations 

(Source: http://en.wikipedia.org/wiki/De_Morgan's_laws)

Symbolically the laws can be expressed as

1. ¬(P ∧ Q) ⇔ ¬P ∨ ¬Q

2. ¬(P ∨ Q) ⇔ ¬P ∧ ¬Q

Let's see why this is true:

1. 

2. 

The truth tables show that ¬(P ∧ Q)  is equal to ¬P ∨ ¬Q for all cases of P and Q

and that  ¬(P ∨ Q) is equal to ¬P ∧ ¬Q for all cases of P and Q.

Of course this is only a glimpse of the power of the truth table. In the future, we will be presented with exponentially longer and convoluted statements but I'm sure it's nothing that the truth table can't conquer.

Start of CSC165

Hello reader, I probably don't know a thing about you and you probably don't know a thing about me so let me start off with a small summary of myself. I am a first year undergrad student currently enrolled in the University of Toronto (St.George Campus) for Computer Science. I am not an extremely chatty person in real life as I believe that the best way to communicate is to have your message sent in a short, concise manner. If you haven't figured already, I am a person who likes to get right to the point.

In this post and the posts of the near future I will document my experience as a student undertaking CSC165.

At the time I am writing this, a single week of lectures have passed. During this week, I was given the opportunity to indulge myself to a new type of class, mathematical expression and logic. With the experience of only one week of lectures I construe that this course will be challenging but rewarding. I cannot tell you the number of times I've gotten lost while trying to understand the material. However, after taking a second and mentally processing the information, I find myself repeatedly telling myself "Hey, that makes sense".

On days when my brain shuts off (lacking sleep), mentally processing the information just doesn't get the job done. I find that writing down the information in an organised manner really makes the problem a lot easier to tackle. Speaking of writing things down, I must say that I love the teaching style of my lecturer. Professor Heap includes annotations in his slides to emphasize points and to give his students a clearer picture of what's going on. His use of venn diagrams to depict sets, subsets, and other notation was nonetheless ideal. As I was saying, writing down info is really helpful. Whether you're a student in CSC165 or a teaching assistant or anyone else for that matter, try analyzing your problems on paper. Sometimes the hassle is worth the time saved.

In this week of lectures I learned about things that are buried in the back of many people's heads, things that most people know but never critically think about. For example, universal and existential claims. If you go on the street and tell people: "To prove that a universal claim is false, you must find at least one counter-example", most people would have no trouble with agreeing with you. However, I doubt that these people have, at some point in their lives, critically thought to themselves: "What is a universal statement and how do I prove such statement to be True or False?". This is one of the reasons why I find this course so intriguing. It's as if this course is helping me unlock the knowledge I already possess.

I think I'm going to cut this off here. This is my first attempt at writing a blog so please criticize me if you will in the comments, after all, this is a learning experience. I hope you'll join me again in my next post and join me as I undergo the course that is CSC165.