Week 9

Big O Proofs are here. The lecture focused more clearly on the detailed proof of Big O. A couple of complexities were added to make it a thorough proof. The disproving seemed to be more challenging as always. The choice of  'n' seemed to a little strange at first glance due to usage of slice, but it did made sense by the end of the explanation.

Basically, we need to choose 'c' and 'B' intelligently and follow a predefined procedure to prove it. For sure, it has confused me, but I guess, if I'll spend some time on it, it won't be that tough to grasp the concept properly. It was interesting to use it on non-polynomial functions wherein we needed to use our Calculus skills to solve the function. Afterwards, we had to shift it to a Big O form.

Not to forget, I had my second midterm. It seemed to a challenging with the time constraint imposed, but I guess I did well on it. Let's hope for the best!

Week 8

Complexity. The week took to topic that has a vital role in a computer programmer's life. How different algorithms can do the same thing. Exactly same. But, still a lot different. It's not just about the expected outcome, but also the quickest and the least expensive method.

Problem Solving aspect mixed with a topic learnt in class:

I had watched a lecture of Harvard's CS50x course by David Malan which had something very intriguing to the same topic. I'll like to brief it out here, as it left a great impression on me about run-times.

He did a practical experiment in a class of 700-odd students. The aim was to calculate the number of students present in the class as quickly and efficiently as possible. So, one way was to go to each student one by one and count. Or, count taking two students at a time (2 + 2 + 2 + ...........).

Then, he proposed an algorithm. It showed up on the big screen and was the following:
1) Stand Up.
2) Think to yourself, 'I am #1'.
3) Pair up with someone; add your numbers together; take the sum as your new numbers.
4) One of you should sit down.
5) GOTO step 3 if still standing.

The video:  https://www.youtube.com/watch?v=79gAss0K1TI&list=PLhQjrBD2T382Lqs7bsMl6WRDA9anaEzBe#t=1226

So, all the 700-odd students stood up. In first round, half of them sat down, with everybody standing with number 2 with them. This continued, and next half of remaining sat down. And it continued. Till only one student was left, with the number of students with him. The amazing thing was, it took less than 10 steps as from ~700 we had ~350, followed ~175 and so on. Rather than going through all the 700 students, it was done in just 10 steps. Isn't it awesome? It was to me when I first saw it for sure. From a linear counting, it showed an easy way to calculate it exponentially.

This is a great example that presents that there are various methods in which you can solve a problem, but it comes down to the fact that your solution must not only be efficient enough to give the desired results, but also fast enough to solve it. As I mentioned, the most simplistic idea that comes to the mind is to count the number of students one-by-one, but sadly it is one the most inefficient way to solve our problem. Dealing more into it, the method proposed by Prof. Malan opened a new thinking approach that the simplistic answer may not be the one you're looking for. Moreover, the perfect (or nearly perfect) answer must not be a very complicated or hard-to-grasp, as we see in this problem, the algorithm was fairly intuitive.

An example of a class full of students

  

 Counting class one-by-one (Linear Approach)

 

Counting it by the method discussed above

I hope this illustration makes easier to understand what's actually happening in these two different approaches. 

Week 7

Proofs...And some more Proofs.


The lecture started with covering some more intense forms of solving a proof. Till now, the basic structuring of the proofs were pretty much understood by me, and I was trying to compile some more information for how to write the main content of the proof. We were taught proofs by cases. This was a fairly intuitive method to look at complex proofs. We did few examples on it, followed by proof based on uniqueness.

Later, we revised all the proof patterns and introduction rules. It made me realize that it's only practice that would help me out to harden my concepts of writing a thorough proof. Before shifting on to the algorithmic portion of the lecture, we had a small fun session over the Fermat theorem.

I liked the animations based on the different sorts. In this lecture we covered bubble and merge sort. This paved to the idea of run-time, which me as a CS student have always pondered upon. Overall, the session was really interesting, and something different from what we had been doing in the past few weeks.

Week 6

38/38
Woah! 100% in your first ever university test. A happy start. None-the-less, it's happy ending that matters the most. Moreover, many students got a perfect score, and overall average was pretty high. I'm more afraid of the upcoming tests, as they seem to more harder, simply after the results of test 1 being high.


The lecture was shortened to two hours, because of the Thanksgiving holiday the day before forced a cancellation of other tutor's lecture. For me, the main content hovered around the floor. I had done greatest integer function in school, so, the conceptualisation wasn't that difficult, rather understanding the written definition in symbols was the complicating part. This was followed by disproving something, by taking the negation, which wasn't new, and latter limits were proved. The limit portion of the class seemed helpful as the same was going on in MAT137 class. 

Week 5

Freaked Out!

First ever university Mid-Term. First big exam at University. I prepared well, according to me. I solved a couple of last year's paper, and class notes, though, I didn't pay much attention to the sample paper that had been uploaded. Finally, it the clock ticked 6:10, and my paper started. To my very unpleasant surprise, the test was entirely based on the lines of the sample paper. I cursed myself for a minute, but recollected myself and went forward with the test. It went well asI was satisfied with my performance.


Further, the class continued, and Prof. Larry was up with his another well prepared joke to chill down the confused bunch of students after the exam - 'Keep Calm and Carry On'. The lecture continued with more on proofs. This lecture was based upon proving via Contrapositive and Contradiction, and writing proofs for existence and a sequence. Proofs are not my love for sure, but I believe I'll need to spent some time towards it to grasp it properly. 

Week 4

The week started with the announcement of the due assignment 1. This followed by a scarier announcement of the first term test. The lecture focused on bi-implications, and various equivalencies associated with it. The breaking up of a bi-implication into disjunction of two conjunctions and vice-versa was tricky, but at the same fun.

Larry gave us a view about how to structure of a proof, and ended with a few good examples. He gave few good real-life English examples, to justify the point he was making.

The tutorial was comparatively very easy this week, but the next day, we had to submit our assignment. Assignment 1 was really brainy. It was challenging, and required a great amount of time, and discussion with the partner. In the end, writing down the answers in LaTeX was rather more tough than anything. In the end, we (my partner and me) finally figured it out, and submitted the assignment before time.

Week 3

The class was based about some more elements of the language of Math. It started with conjunctions and disjunctions, which was fairly easy to grasp. Larry made sure that we don't get confused with the English meaning, and gave a laughable example of a pen-phone! Then, followed this:

A logician’s wife is having a baby. The

doctor immediately hands the newborn to

the dad.

His wife asks impatiently: “So, is it a boy or

a girl?”

The logician replies: “Yes.”

I couldn't believe, that such a mathematical joke could bring a smile on your face. Welcome to Computer Science! Welcome to UofT!

This was followed by discussing the steps of negation, which we were already aware off by now. But points made on scope were helpful. Truth tables were next in turn. He explained why we need truth tables with simple but effective example. We worked over few of the truth tables, and concluded at the meanings of satisfiable, contradiction and tautology. The most important concept of the day was the De Morgan's law.

The second tutorial was nice brain-exercise. The class was loud with discussion and different view-points. This lead to a better understanding of the concept, and was good to tackle something challenging.