Week 9 - Complexity

Well, we just finished the 9th week of the course, and started a not so complex topic called complexity. This topic deals with the efficiency of functions, methods, and thus programs.

I found this topic quite interesting, especially observing the different run-times of different functions, and finding out the reasons for their difference even though they have identical inputs and outputs. I would probably say this is the most interesting topic I came across in this course so far.

The following is the maximum_segment function and an image of a lecture slide which shows how the different terms in T(n) grow for the function, as the number of elements n in the list L increases:

def max_segment_sum(L):
   '''(list of int) -> int
   Return maximum segment sum of L.
   '''
   max_so_far = 0
   for lower in range(len(L)):
      for upper in range(lower, len(L)):
         sum = 0
         for i in range(lower, upper+1):
            sum = sum + L[i]
         max_so_far = max(max_so_far, sum)
    return max_so_far

This was particularly an interesting observation, as even though I came across this function before in CSC108, I never thought about its behavior or run-time for different numbers of elements in the list.

Overall, this week went pretty well for me. There wasn't much challenge I had to face. However, the lab was not that easy; we had to deal with some nested functions and recursion. (If you are a freshman in Computer Science, this should sound scary.)

There is more one more positive I can take from this week; I successfully completed and submitted part 1 for Assignment 2. It was actually super-easy. I just tended to think in a too complicated way at the beginning, and thus confused myself. I must say, it was a great idea to include a part of the assignment solely for design; we often spend hours to make a program working, but we rarely think of our design of the code. This part of the assignment definitely helped me in learning to think and come up with design which has fewer lines of code. Thanks to inheritance.

Okay, I guess I have said everything I had in my mind for this week. Hoping for a wonderful weekend and a great coming week!

Week 8 - Binary Search Trees

This is the end of week 8, and we just got introduced to a new kind of trees, known as binary search trees. I like trees, and probably Dan knows it, and that's why he is teaching us more trees!

On a more serious note, we just finished a wonderful week where we learned the structure and use of this particular kind of trees. To be honest, there isn't much to learn about their structure. The main learning is in making useful functions or methods to perform particular tasks on/with these trees.

I am really enjoying dealing with these trees! I know some people are really hating it (but I guess I am eco-friendly). Some of the functions that were solved in class were quite interesting. Finding the height of a BST, and finding whether a value is in a BST are two which I enjoyed learning. However, I found the method for deleting a node quite tricky, and can't solve it by myself yet. I seemed to understand it during the lecture, but soon forgot when I came back home. Write before writing this slog, I did some searching on Google and found an algorithm which looks similar to the one that Dan showed us. I hope this will work once I code it. I reviewed the algorithm on the lecture slide, but for some odd reason that seemed quite confusing.

Overall this week was not a bad one. I experimented a lot of things this week with trees in general (not just BSTs). I even made a method which returns the number of leaves in a tree:

def num_leaves(t: Tree) -> int:
    if t is None:
        return 0
   
    if t.children == []:
        return 1

    count = 0
    for child in t.children:
        count += leaf_count(child)

    return count

I am also trying to implement a method which will find and return the average of the values of whole binary tree. But, I am still struggling with that.

Okay, on a different note, I just saw that the handout for Assignment 2 got posted. After reading it for around 10 times, I am yet to understand what we exactly have to do in part 1. I probably have to go Dan's office hours for this.

As we wait for the results of Assignment 1, it's already time to get started with Assignment 2.

Hope the coming week will treat me well.

Week 7 - Linked Lists

We are back to work after the reading week. It was a nice and relaxing break. Now its time to get back to studying againg as we already started a new topic - Linked Lists.

Like last week, this week's topic was quite easy as well. I have been keeping up with the readings, so I am not facing much difficulty in understanding the lectures. Dan showed us two ways of representing the Linked List ADT; using list of lists, and by creating classes (nodes and references). I personally prefer using the nodes and references representation because it is simpler to use, and looks nicer in the shell.

I enjoyed attending the lectures this week; they were fun. I particularly enjoyed the append method that Dan solved in lecture using recursion. There is also an iterative solution to this method, which I will try to solve by myself over the weekend.

Our first test was held this Wednesday in lecture, however, I was extremely unwell and therefore could not attend it. Many of my friends later said it was not too hard, so I can consider myself unlucky.

I believe this week was okay in terms of difficulty of the topic. The lab was not too complex as the last one. In fact, it was fun! I enjoyed doing it.

That's all I had for this week. Now looking forward and hoping for a wonderful coming week!

Week 6 - Trees

We are into week 6 of the course, and this week we have been introduced to a completely new topic - Trees! Nope, not the ones that we see around us. These trees are upside down. They have their root at the top, and the leaves at the bottom! Sounds interesting, right? -- Yes it is!

This tree data structure is relatively easy to understand, and does not require much deep thinking. It just took me around 15 minutes to understand the basic features of a tree. I must say, the reading that was posted for this week was very well designed, and was to the point. The lecture and lecture slides complemented the readings nicely as well.

This week was not a very challenging one. The readings and the lecture material all were quite easy to understand. However, the lab was a bit tricky/confusing. I did not like the way of using comprehensions for coding. Though sometimes it may be efficient and require less lines of code, I found it quite challenging to interpret and use. I would therefore prefer the way we have learned so far using loops.

As I said, apart from the lab everything went pretty smooth this week. The only other thing which seemed a bit tricky were the tree traversals. I seem to get lost while traversing by myself, and have to start all over again. However, I believe this is because I am still very new to the topic. A bit more of practice is all I need to get a strong grip of this topic.

Oh, and finally I am done with Assignment 1. I am extremely happy that I finally finished it! It's a feeling of great relief and contentment.

Following is a screenshot of the output from my tour module, for eight cheeses. As Dan showed in lecture, 33 is the minimum number of moves for eight cheeses. So I am right!

Woohoo!

Week 5 - More Recursion

Well, week 5 has just ended, and we are almost half way through the course. As I discussed in my last post, recursion has not been going good for me. To be honest, I'm not liking it at all. I know, it is amazing to watch the results the recursive functions output, but it is equally (or even more) complicated to write these functions.

My experience from this week of classes is very similar to the last weeks. It was not that I lacked confidence, but it was just that I couldn't come up with any recursive solutions of my own unless and until Dan showed us the solutions. However, it was not all bad; I did enjoy understanding the implementations of some of the functions Dan showed us in lectures. One of them was the guessing_numbers functions, which I particularly found very interesting. (This may be because I could actually figure out what to do after Dan just finished writing the first two lines of the function!). Poor me. The binary_search function also was not too difficult to understand once I saw the code. However, I do still have trouble understanding the binary search function that returns the index of the given element. This seems way too complicated.

I know, the way I am progressing with recursion will not take me long. So far, this is the only topic which I found difficult. Sorry, extremely difficult. This might even be the reason for me missing out an A in this course. However, I am working hard, and started to look at some past years' question papers. So far, I did solve few of the questions from these papers, which involve recursion, but only after several attempts.

Oh, I almost forgot to mention but I did achieve something great at the end of this week! I actually figured out how to solve the final part of Assignment 1! Thanks to Dan, for his tips in the lecture and providing us with the Towers of Hanoi function. It helped incredibly! However, after some modification, this function only helps partly in solving the problem. So, after doing a fair bit of research on the Internet, I found an algorithm for writing the other recursive function required to solve the problem. Hope I will be able code it without too much difficulty!

Well, the weekend has just started, and I look forward to finish the assignment before the next week of classes.

Wishing myself and everyone a happy weekend!