End of the Road

Alas, CSC236 is coming to a close. The course has been challenging, especially in the last few weeks, but overall I’ve enjoyed the course. I think Professor Heap taught the material clearly and intelligently (and my course evaluation reflects that), and the TAs were absolutely amazing (wink wink). Seriously though, the few TAs that I talked to and my tutorial section’s TA have been helpful.

Assignment 3 went well, I think. Though, looking at the sample solutions now, my proofs are quite different. Good thing the sample solutions only represent one (for each question) of the possible solutions. Anyways, because of my other course work I had to complete the assignment the day before it was due, which was the same day my CSC258 final project was due. Between those two projects I spent 20 hours straight working from Thursday to Friday. Hopefully I won’t ever have to do that again.

In lectures this week we covered more about NFSAs, DFSAs, regular languages, and regular expressions. As of this writing I feel OK with NFSAs and DFSAs, but I’m lost on how to perform state combination to convert a state diagram to a regular expression. Obviously, that is something that I’ll have to study before the final on next Wednesday. Good luck to my peers and I hope to see you in CSC263!

Yet Another Problem Solving Episode!

Because I enjoyed the first problem solving episode so much, I’ve decided to solve another problem from cut-the-knot.org. This week I will be solving this problem: Four Knights. This problem is not as math heavy as my previous problem, but since I’ve already solved a math-oriented problem, I figure it would be alright to tackle a logic problem.

Problem: The problem involves a 3 x 3 chess board and four knight pieces arranged, as depicted below.

The objective of the problem is to get the blue knights and the red knights to switch spots, given that they move like regular chess knights, preferably with the minimum number of moves.

Attempt(s): Firstly, I noted that there was no way to reach the middle square given standard knight moves, meaning that there are only 8 possible spaces for me to utilize. This gives me one space per knight to move out of their original square. Secondly, I realized that through a sequence of <8 moves any knight could reach any other spot on the board. Thirdly, given the knight’s starting positions each knight has two possible spaces to move.

Solution: From these ideas, I realized that every two moves, a knight could move to an adjacent corner. Furthermore, because there is one space in between each knight, one knight can make a move and then the knight behind it can follow, and so on. Therefore, if we “chain” each knights’ moves based on the diagram below, we can swap the red and blue knights in 16 moves (2 moves to get to an adjacent corner times 4 knights times two adjacent corners to get to).

Problem Solving Episode (#1?)

This week I’ll be delving into my first (but not last?) problem solving episode! I’ve looked at Professor Heap’s problem solving wiki, but I get the impression that many of those problems have been done to death so I’m going to select a problem from cut-the-knot.org, specifically Make It All Zeroes.

Problem: In this problem, you are given a matrix of any size where each element is a positive integer. In each move, you are allowed to either double the integers in a row or subtract one from each column. The objective is to prove that with these two operations, you are able to create the zero matrix (a matrix containing all zeroes).

Attempt(s): Now, my first instinct was to go element by element creating zeros. This, of course, did not work because, as I soon realized, if I had a zero and a non zero element in the same column then I was unable to create a zero matrix. Subtracting one from the column would create a negative number and multiplying zero by two would only ever produce zero; I would be stuck.

Solution: This made me realize that I needed all elements in a column to arrive at zero simultaneously, which implied that all elements in a column would first have to be one simultaneously. As I discovered, to do this multiply every row in the matrix – except the row containing the largest element in the selected column – by two until (the second largest element in the selected column) <= (the largest element) / 2 in that column. After, subtract one from the column until one of the elements becomes one. Then repeat this algorithm until the selected column contains only ones, from which you can subtract one to achieve a column of all zeroes. Repeat this process on the next column until all columns contain zeroes, giving you the zero matrix.

Midterm Number Two (and More Program Correctness)

Sorry TAs and anyone else who’s reading my SLOG for the late post; it’s been a busy week, as usual. Though, speaking of visitors to my SLOG, well, there don’t seem to be many. In fact, I get about 1 visitor a week for those of you wondering…which is obviously very few. I don’t really mind, as I’m sure other SLOGs are seeing about the same number of visitors (as always, feel free to write a comment letting me know), and helps me feel more comfortable writing more informally. Anyways, I digress; onto the real content!

Midterm 2 was short and interesting, at least for the morning lecture section (more on that later). The first question was very similar to other recurrence questions proved in class and tutorial. In essence, you had to unwind a recurrence to discover the closed form of the equation and then prove that the closed form was equivalent to the recurrence with induction; straightforward stuff. However, I had difficulty discovering the closed form and ran into a few other small problems proving the closed form, which caused me to use 45 minutes of the test on the first question. Because of this, I didn’t have time to think over a full solution to the second problem, which was definitely harder than the first question. I believe it was about proving that a recurrence is increasing in gaps where n!=2^k, using the fact that it is increasing where n=2^k. Overall, I felt slightly rushed in the midterm, but Professor Heap mentioned in lecture he had received feedback from other students saying the same thing.

Also, I was told by a friend in the evening lecture section that their midterm was largely testing proving programs correct. This makes me believe that the morning section might have had an easier midterm, though we’ll see if that’s true when our marks are returned.

In lecture, we continue to cover more complex program correctness.

P.S. I’m going to try writing a problem-solving SLOG post next week. It will likely involve program correctness so I can test myself.

Program Correctness, Assignment Two, and the Master Theorem

The lectures this week focused on program correctness. Now, I’ve learned about this before in CSC165, but only briefly. I understand the basics of proving that the postcondition follows from the precondition. However, my hang ups lie in the loop invariant; I don’t fully understand how to choose it nor prove its termination at the desired index. I believe that Professor Heap said that the material covered this week was fair game, but feel free to post a comment correcting me if I’m wrong.

Another thing CSC236-related that I worked on this week was assignment 2. Overall, I found the assignment to be challenging. Though it was only two questions, my assignment ended up being a total of 5 pages! The second question seemed to be quite easy, as on the assignment sheet Professor Heap referenced an example in the textbook that basically gave away the whole first part of the question. Also, the second part of the question was proved in the following example. However, I found the first question to be much more challenging. Eventually, I took the long route (which is why my assignment was so long) by proving the closed form of the Fibonacci sequence and then proving that the recurrence of H(n) was equal to my proposed closed form.

Finally, (I didn’t intend this to be a long SLOG post) somehow I forgot to mention the Master Theorem last week; I must’ve not been paying careful attention in class when it was presented. Fortunately, I have this whole weekend free so I’ll have plenty of time to study for the midterm on Monday and re-learn all the topics that I’ve had trouble with so far (program correctness, master theorem, binary multiplication, some recurrence subtleties, etc.). Anyways, that’s it for this week; good luck to everyone on the midterm Monday (or Thursday if you’re in the other lecture section)!

Phew! What a Week!

I’ve had an exciting (read: busy and stressful) week because of the CSC207 assignment, the CSC258 lab, and the STA247 assignment. Unfortunately, those are stories for another SLOG because this one is all about CSC236!

In lectures this week we covered yet more complexity. Specifically, we looked at divide and conquer recurrences where you partition the equation that’s “to-prove” and prove each element of the partition individually, which I feel fairly confident about. However, I unfortunately missed class on Friday, and I’ve had some trouble wrapping my mind around the multiplying bit algorithms that were introduced. I haven’t had time to fully review the material (and the annotated slides haven’t been posted as of this post), but I’ll spend some time revising today for the tutorial quiz tomorrow. If I still don’t understand then I’ll ask my TA some questions tomorrow morning before the quiz.

Classes are hitting their high point in terms of workload so it’s taking all my free time just to keep up!

Not Much to Report Here

This week’s SLOG post will be fairly short, as I didn’t really do that much CSC236 work this week. With the STA247 midterm on Monday, possibly the hardest yet CSC258 lab on Thursday, and a fairly weighty (in terms of grade value) CSC207 quiz on Wednesday, I had to focus my efforts elsewhere.

However, this SLOG is about CSC236 so I should probably talk about it (my SLOG grade depends on it)! The quiz this week was on unwinding and proving recurrences with complex induction. Often, you also need to use a bit of intuition to discover a closed form of the recurrence, which is necessary to the proof. I did the tutorial handout on the weekend and felt fairly confident on the quiz.

The lectures this week covered more time complexity and unwinding and proving recurrences (also covered last week), but more in depth. I spent time reviewing the lecture notes after the lectures and feel OK with the material.

Midterm One, Done and Done

Yesterday (technically two days ago by the time of this post) was the first midterm for CSC236, and overall I thought it was pretty fair. In fact, that’s pretty much been my experience with the course so far. After the, ahem, challenge, that was MAT137 last year (boy, was that a steep learning curve), I’ve found the class to be much more interesting than difficult, which I’ve really enjoyed. That’s not to say that I think the course has been by any means easy, just much more fair and manageable, at least thus far.

For instance, the midterm was split up into three equally weighted questions. The first was a fairly simple question where you had to prove that some expression is bounded by another expression for all natural numbers. We had done several examples of this in lecture so I was confident that I could solve it. The next question was, if I remember correctly, a tree height question taken directly from the assignment (or was very similar). I had already solved the question before so I rewrote my proof.

The third question, however, was quite difficult. It was a (mandatory) structural induction proof, which is, unfortunately, what I had neglected in my studying. I had studied mostly from the sample quiz and the tutorial quizzes, which didn’t contain any structural induction. Also, I had (incorrectly) assumed that since Professor Heap had substituted complete induction for structural induction for a proof in lecture, that we would be able to do the same. I don’t think I solved the question correctly so soon as I got home I got on Wikipedia to fill my knowledge gap of structural induction.

Overall, I thought the midterm was fair because it allowed you to get 2/3 marks for having a basic knowledge of the material, but you really needed to know your stuff to get a great mark. However, I’m just speculating on marks and we’ll all see what we get when they exams are handed back.

From this midterm, I learned that though a sample quiz can be slightly representative of what’s to come, you still have to study everything because the teacher’s never going to make a quiz that tests exactly the same concepts. They’ve got to keep us on our toes.

Hello world!

My first post!

if (first_post == True):

print "Hello world!"