(Renamed: Revisit, Week 11) And here we are.....

What started as an exciting lecture in WB116 turned out to be one of the most intriguing course of my first year. It was tough and rough, yet the only course which gave me a feeling of 'Like-a-Boss!' after solving the basics of the problems. This class has definitely opened my views about the Computer Science and given me a wider perspective to look at the core logic of a certain problem. No one can deny the fact, that this course gave me something new to work over week-by-week (For me atleast).

The one thing that made the course easier was 'The Friend Community'. We all sat, ate, cried and coded. I would like to mention few of their viewpoints I really liked below:

Nagee Elhgassein: It's starting to link:
I love the way Nagee brought a nice taste of humor to the otherwise monotonous SLOG writing. Moreover, the reason I particularly liked this post was that he mentioned the amount of work he was going through that week. It has happened to me as well, few weeks are as easy as you're having vacations in Bahamas, and then a couple of weeks come with work piled to the top roof.
Nagee and I have been constantly discussing our ideas over the CS, and I feel really happy to go upon discussing some good ideas with him. Way to go, Nagee!

Anam Alvi: My Problem Solving Biceps Are Growing:
Now that's some engaging title, 'My Problem Solving Biceps Are Growing'. This post of her perfectly reflects what we, as a group of three, faced during the assignment 2. It was tough as I mentioned in my post 'Mission Minimax'. Yet, we all worked over it and enjoyed implementing it. The number of (wrong) ideas that followed were pretty high, still we felt happy to atleast come with something rather than nothing. I shouldn't feel ashamed to say this, but yes Anam, even I feel 'My problem solving biceps are growing' ;)

Jahid Ahmed: Debugging Logs
You write a code. Run it. 2 Errors. You fix the errors. Re-run it. 13 Errors!
This has been my Wing IDE usage for the last 2 months. Debugging has been a very important part, though it wasn't very easy as it may sound. Finding a mistake is way more difficult than correcting it for most of the times. I liked the way Jahid mentioned to set breakpoints and maintain a journal over the time. We had spent a lot of time working over the problems in the labs, and we know the time we had to spent on few of the errors especially in the last couple of labs. It was fun whatsoever.

There have been really interesting slogs on the board, and really appreciate the time people have devoted on writing some fabulous mini-articles.
Goodluck everyone!

Complexity. Big O(h)!

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.

Without digging deep into the Big O problems tackled in the class, I would like to about something that I find very interesting which suits the present topic perfectly.

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.

                             

(A linear approach. Counting one by one)

(Using the approach explained above)

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

Midterm 2 arrives

We had our second midterm of the course this week. It focused on recursion, and I wasn't very comfortable after learning from that most of the students came almost crying after the recursion midterm previous term. Yet, I feel Danny showed some mercy and gave us a doable test. I put good use my aid-sheet in second question after quickly working out the first one on my own. Third question was the trickiest one, but I spent some time before I figured it out as well. I used the approach of drawing the illustration of a linked list, and analyzing the problem. It worked pretty well and overall, I was happy with the exam.

The Monday before the exam, we went through Binary Search trees in class. I liked the way of gathering data such that we can have certain comparable conditions applied on the child nodes which makes it easier to traverse to the required point. In our work, we ensured the left child has a value less than the parent node, and the right child has a value greater than the parent node itself.

A Binary Search Tree

So now if we consider the example above, and we need to find the number 13, starting from 15, we know that 13 is less than 15, so it will lie somewhere in the left sub-tree, and further 13 being greater than 11, would lie to the right sub-tree of 11, which specifically is the leaf. This way, we reduce the steps the program would have otherwise taken to reach the required 13.  

This week, 4 Midterms in 3 Days, wish for me. Please do!

Mission Minimax

I ended my previous Slog with a hope to 'conquer Minimax'. I feel elated to say, that finally after sweating for days, my team was able to complete it. I felt that this was the start of Computer Science. This was the first 'hard' assignment I'll never forget. It made me think. I made me sweat. It made me work. Yet, I was finally able to code it down in the end. We had already completed other parts of the assignment before touching down Minimax, and hence were able to submit the assignment on time.
(I hope the TA Strike get's over soon, because I'm eager to know how well I did on this assignment, for once!)

In class, we discussed over Linked Lists. The diagrammatic representation made it fairly easy to grasp the idea behind it. With playing over few methods this week, and solving out the lab problems at home, I seemed to be confident about it. The other good think I liked about it was that I was able to find different logics to solve one single problem as compared to few previous weeks, where finding even one recursive call sometimes was a big deal.

Binary Tree: One Parent, Two Childs!

This week of class focused on the binary trees to start with. (Actually, it wouldn't be fair not to tell that we did spent starting halves of the both the lectures discussing A2.) The idea behind binary trees was pretty easy to grasp, and so that wasn't much of a problem.

Jokes aside, Danny showed us few methods working over the trees. Still, recursion was needed to be swept in by the brain. This weeks lab was one of the harder ones for me, as few of the recursive calls took some heavy amount of time. None-the-less, it was a good practice and learning experience. Also, we did the three traversal ways: Pre-Order, In-Order and Post-Order in the class. These weren't tough, just had a slight variation.

Everything seemed going well, until I started working on Minimax. I have spent a lot of hours figuring out the problem, as I feel I have got it, some sort of an error pops up. I hope I can get over this challenge soon. Catch you next week after 'conquering' Minimax!