The Unsolvable Problem

Note: This post covers Week 12 (There was no class during Week 11),

Since the most difficult concept always gets introduced in the last class before the exam, this week we explored the Halting problem. Essentially, we were asked to create a function halt that predicts whether or not a function would halt, or stop (a task we soon proved was impossible). I generally wouldn't complain that we had proved a problem impossible, intuitively that would mean that we wouldn't have to try to solve it. Unfortunately, for halting problems, we have to prove whether a function is computable or not by attempting to reduce it to a halt function (since halt is not computable, if a halt function can be written using a function f, that function is not computable).

Generalizing Big-Oh Proofs

Note: This post covers Week 10.

This was probably the most hefty lecture of the semester. We took big-Oh proofs, which tend to be somewhat to moderately difficult themselves, and learned how to prove general properties (ie: if f is in big-Oh of g, then g is in big-Omega of f). Basically we were given a statement (ie: f is in O(g)) which provided us with a constant and breaking point, and we had to figure out how to mould those variables to prove the consequent (ie: g is then in Ω(f)).

An interesting example (which was asked on A3) was to prove that for any two functions f and g, f is in O(g) or Ω(g). I originally tried to prove this but then realized that cyclic functions or a simplified Dirichlet function would prove this statement false. Hopefully with a bit more practice these proofs will come easier to me!

Big-Oh

Note: This post covers both Weeks 8 and 9.

Prof. Zhang introduced the formal definitions of big-Oh and big-Omega in Week 8. We learned how to do some simple proofs involving them which were daunting at first but exposed to be quite easy by overestimating (for big-Oh proofs) or underestimating (for big-Omega proofs) the function. I’m glad we’ve had so much practice with proofs, because these were fairly easy to do. The most important part for me was understanding the intuition behind the proofs, which was covered very well in lecture.

We started off week 9 with both a midterm and the A2 due date They were both probably the most challenging pieces of coursework that we’ve done so far. We had quite a few hints in the previous lecture though so they were both fair.

This week we went much more in depth into big-Oh proofs, going over examples of negation and limit-based proofs. We started with a regular proof, but discovered that we could not only overestimate the function, but also underestimate the bound which makes dealing with more complex proofs a bit simpler (but lets the profs ask us to do more complex proofs on tests…). We also learned negations (which were fairly intuitive) and yet again, a proof involving limits. If the ratio of the bound divided by the function approaches infinity as n approaches infinity, we can determine that the bound grows more rapidly than the function and therefore the function is in big-Oh of the bound. We used l’Hopitals rule to simplify the limits and then followed with a regular big-Oh proof. This was a fairly complex proof so much like my classmate Aqib writes here, I had to attend office hours to fully understand how to do it. I like these proofs now though because you don’t have to find appropriate constants or breakpoints, the fact that the variables exist to prove big-Oh are given by the limit.

Algorithm Analysis

Note: This post covers Week 7.

Finally! Some actual more typical computer science material!

We started off the lecture by discussing proofs by cases (useful for proofs involving absolute values or different cases when a variable is odd or even) and then reviewed all the proof structures we had done so far. This was a good synopsis to copy down for the exam aid sheet, Then we moved on to "Algorithm Analysis and Asymptotic Notation."

Prof. Zhang lectured about running time, juxtaposing merge sort (which operates in n log(n) time) and bubble sort (which operates in quadratic time) as an example. Since only the asymptotic behaviour of algorithms is of interest, which is to say only their behaviour as input sizes get very large, we learned that we can place algorithms into separate classes depending on their rate of growth. Thus big-Oh notation was introduced.

Proofs, Proofs and More Proofs

Note: This entry combines both Weeks 5 & 6

Midterm week! This test was fairly easy, as a few minutes spent practicing with last years test would leave you well prepared. We also finished up assignment 1 this week. It was more challenging than any of the other course material, but quite doable in a few hours.

Prof. Zhang started off Week 5's lecture proving how "if you did bad, then it is not bad" which was an entertaining example of a direct proof. We learned several new proof techniques, such as proof by contrapositive (when P => is too hard, try not Q => not P), proof by contradiction (assume not Q and arrive at a contradiction, thereby proving the contrapositive) and how to prove sequences. This was a much more challenging class than the previous ones, and it takes a while to get used to proofs. It's confusing at first when you don't know how to start, but I guess that's just something that goes away with practice.

Week 6 was spent building on what was learned in the previous week and providing us with examples of how to prove non-boolean operators (ie: "floor"), disprove statements (prove the negation), and prove limits

Proofs using the floor function were fairly difficult to do because we had to mold the definition to suit our purposes as opposed to simply applying memorized laws. This was a major part of assignment 2 and one of the hardest parts of the course up till now. Delta epsilon limit proofs were fairly straightforward because I had already learned them in calculus, but we encountered more difficult instances on the assignment.

This was an interesting two weeks learning the basics of proofs and I'm interested to see how we'll apply these techniques to more technical computer science scenarios.

Problem Solving Exercise

I will be using Polya's method to attempt to solve the problem depicted here.

Understand the Problem

The problem at hand is to predict whether creases on a repeatedly folded paper will be hill or valleys.

Devise a Plan

I will try to fold the paper and record the pattern of hills/valleys after each successive fold, in an attempt to uncover a pattern.

Carry Out the Plan

Folds | Hills | Valleys

   1         0           1

   2         1           3

   3         3           8

   4         8          14

It seems to be the number of valleys is the same as the number of hills for the next fold. I can't figure our another pattern after that thought...

Look Back

I tried one method, perhaps I should try again because I don't see a pattern.

Acknowledge When and How You're Stuck

I don't really see a pattern so I'm quite lost...

Finishing up the "Language of Math"

Note: This post covers Week 4

We added to bi-implications and transitivity to our mathematical toolbox this week, and mixed it up with multiple quantifiers. It was a fairly easy lecture, but a good opportunity to practice using the various predicate laws we learned last week (ie: distributive, DeMorgan's).

We started proofs this week. First we were presented with an example limit proof, which was pretty straightforward because it had already been covered in MAT137 (but too déjà vu...bad memories). My friend Isobel is absolutely right here when she writes that taking 137 is very useful for this course, it made this lesson so much easier than if it were the first time I were exposed to these ideas. We were also introduced to the indented Python-like proof structure that is very different (much more organized and symbolic-heavy) from that used in calculus.

Working with Predicates

Note: This post covers Week 3.

This week we practiced some more operations with predicates, specifically conjunctions

and disjunctions. I took a statistics course previously so it was a bit confusing at first as I tried to differentiate between these operations and the union and intersect operations in sets.We then started doing operations with multiple predicates, which because increasingly difficult to show on a Venn diagram, so truth tables were introduced to simplify that matter.

I enjoyed the tutorial this week because it was good to have a chance to practice and apply everything we learned in the long lecture. The problem set was fairly challenging and it was a good opportunity to make sure I understood how to use predicates. Overall, this was a pretty easy, still introductory week.

First Post!

Note: This post covers Week 1 & 2.

My name is Theo and I'm a freshman taking CSC165 with Prof. Zhang. I'll be posting every week about my experience with the class: things I learned/enjoyed, topics that were interesting, particular difficulties with the material, etc. Feel free to comment on my posts to ask questions or provide your own reflections on the class. Since this is my first post I'll be discussing the first two weeks of class.

The first class was an introduction to mathematical logic. It was interesting experiencing my first three-hour lecture (fortunately we have break every now and then). Prof. Zhang started a discussion on how to achieve the right balance between precision (ie: machine language) and ambiguity (ie: human languages). He then introduced mathematical quantifiers, which allowed us to segway to more complex topics in the second class such as negation, predicates and equivalence. It was a bit confusing at first but we went through an exhaustive set of examples and that made the material easier to understand. We also had our first lab this Thursday which was a good way to cement the concepts.

Looking forward to next class!