Comments

I wasn't sure whether we had to put up a different post for the comments we have made on our other mates' slogs, but following the trend, I'm hereby pasting few of the comments I did make on my friends' wonderful slogs:

Anam Alvi:
I loved the way you presented, 'Adidas, you might want to re-brand your campaign because impossible definitely is NOT nothing.' It is definitely NOT wrong to say that after this course. Good luck for the exam!

Jahid Ahmed:
Your problem seems fairly interesting. The way you have clearly mentioned it out is easy to understand and does the job of explaining it pretty well. I followed a slightly similar process, but the general outline was pretty much the same. Well done!

Quinn Daneyko:
The first time I saw the Big O proofs, I also had a similar feeling like yours. I now believe I have grasped the idea behind it, and hope you too also would have. I found a valid point you mentioned about the difference in the proofs we do in MAT137. Both courses circle around proofs, but slightly in a different manner.

Qasim Iqbal:
Firstly, I really like the theme you adopted for the Slog. It's really appealing the way you have put up the information throughout. Computing and halting are confusing for sure. Computerphile have a really good video on the topic here: https://www.youtube.com/watch?feature=player_embedded&v=macM_MtS_w4 I posted the link in my slog also. I hope it helps you out a little bit.


Signing off again,
Abhinav

Goodluck everybody!

Week 12

Finally, a final class as we approach closer than ever to the final exam. (Too much of final, yeah?)

Last class, so nothing that important was covered. Larry gave us a few tips about the a3. Then we briefly looked over induction (Domino effect) and discussed our format for the final exam (or we can say three term tests back-to-back)

Overall, I liked the course, and feel glad that Computer Science has such Mathematical Logic courses going on side by side to the hardcore programming as these proofs seriously a side of brain, rather a new aspect through which you look at the programming world. These 3 months have been worth, learning new concepts and visualizing things with a better angle.

This course has made be able to speak in terms of Mathematics which is fascinating (and was promised by Larry in the first week of class.)

Good luck everyone for finals,
Signing off,
Abhinav.

Week 11

No Class!

Week 10

Halt? Computable?

The class focused on the topic of halting and computability. At first, it seemed weird when you come across the fact that when a program halts, it doesn't halts and when a program doesn't halts, it halts. Though, later I realized it wasn't that bad as it seemed at the first look. This video made it a lot simpler for me:

We also covered some more over the Big O and Big Omega proofs, followed by some proofs involving theta, which weren't too bad to be frank. I guess, this weeks tutorial made it a lot clearer to me about these proofs.

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.