Week 7: linked structures

Hello world...
So unfortunately, due to the fact that I was in the Wednesday evening class from 6-8:00 pm on Wed, I was unaware that there was in fact a lecture section on linked structures for this week’s class, given the scheduling of the first term test at the same time as lecture. Nevertheless, the concept of linked data structures (i.e. the “LinkedList” class used in lab) was pretty straightforward, and after reading the lecture slides and one of the readings on “LinkedList” that was posted on the website* (along with a few Google searches on the topic), I feel fairly comfortable with the idea and able to implement a linked data structure should that appear on an assignment or exercise.

LinkedList into Binary Tree?

Even though the lecture slides had clearly pointed out that the example of LinkedList used was a representation of a tree with arity = 1, I’m fairly confident that - with some slight modification to the LinkedList class - it can also be used to represent trees of arity n. The classes LinkedList and TreeList represent more or less the same idea, though how the two implement recursive structures are slightly different. Nevertheless, I found that applying the concepts (i.e. height, branching factor, internal nodes, leaves, etc.) I had learned when we were covering TreeList helped me with understanding LinkedList.

Reflections on the test and other thoughts....

Now, to talk briefly about the test we had: I thought it was fairly straightforward; nothing surprising. The test covered the basic concepts we had learned in class, and there was quite honestly nothing that was out of the ordinary. Yes, there were a couple hard questions on the test that took some time to think about, but in general, I feel fairly confident that I had done well on the test, and I think this was a similar sentiment shared by other students who had attended lectures and labs regularly. For those who didn’t attend lectures and labs, it is to my understanding that it was a “challenging test”, as I was told by one of my friends who didn’t show up for lectures regularly. The cheat sheet we were allowed to bring was sort of unnecessary, since I didn’t use it even once on the exam. However, I found that the time I spent reviewing previous topics in creating my cheat sheet was actually really helpful in preparing for the exam, and made my more prepared in general for the fundamental concepts of CSC148.

*Here’s the link to the article I was talking about. I personally thought it was immensely helpful for understanding LinkedList. 

• http://openbookproject.net/thinkcs/python/english3e/linked_lists.html#the-fundamental-ambiguity-theorem

Week 6: recursive data structures

In this week’s material, we ventured on to the topic of recursive structures with a focus on binary trees (aka the ‘TreeList” class). I thought this week’s lecture was particularly interesting, given that this was my first interaction with ADT with a recursive spin to it.

I found the idea of binary tree’s intuitive and appealing from a functional perspective. I have to admit, it took me a while to wrap my head around the concept, but once I did, I could immediately see the functional aspects of using recursive data structures over traditional methods of organization (i.e. for searching applications).

Binary Tree: a tree made of 0s and 1s?

To my understanding, binary trees are composed of ‘nodes’ and ‘leaves’, where nodes that have children are referred to as internal nodes, and nodes with no children referred to as leaves. The height of a tree is defined as the maximum path length from a root to a leaf. The arity of a tree refers the maximum number of children for any node, which in the case of a binary tree, is 2.

Final Thoughts and Reflections

On a side note, shortly after class, I had a brief discussion with a classmate (who’s been programming in C ++ since he was 13), who told me that when he first learned about recursive data structures, his instructor had used the example of pointers referring to memory address rather than nested lists to explain recursive data structures. This got me thinking some more about recursive ADTs, and made me realize that a binary tree could have just as easily been implemented using pointers pointed at unique memory addresses containing ‘child objects’ rather than using something like a “TreeList”.

Week 5: stools, names, tracing

In week 5 of CSC148, we started this week's material by talking about the concept of "recursive insight". The idea behind recursive insight is to develop an understanding of what our problem is, spot out any patterns, and then figure out how we can break down the problem into subproblems, such that we can develop an recursive solution to solve it.

The Recursive Way...

I found this method of problem solving to be a nice way of figuring out how to develop a recursive solution. In a typical CS fashion, the steps for developing a recursive insight is structured into an algorithm, such that, we as the programmer, can easily spot out when a recursive solution would come in handy when given a programming problem. There is one thing that I would of probably added to the lesson though, and that was the necessity of developing good base cases when creating a recursive function. I found that most of time, when I'm talking to classmates about the use of recursion in programming, many fail to realize how important base cases are in developing a recursive function. 

Tracing

We also covered the topic of tracing a little bit more since last class, which I won't talk about in great detail since I had already blogged about it in my last post. Nevertheless, it doesn't hurt to say that knowing how to trace a program, both mentally and on paper, is a necessary skill in becoming a good programmer. Sometimes its more important to understand how and why a function works than to be simply content with having a working function. This is important because there often come times as a developer when it may become necessary to modify a function to do something different to what the function was initially programmed for, as is often the case in the software development world.

Thoughts or comments for the day?
To fellow CSC148 students: what are your thoughts on recursion? We've definitely have talked about this concept for quite a few times now at this point. What are your thoughts on it? Does it make sense? Leave your comments below!

Also, please let me know if there's something you think I could do to improve this blog; would love to hear some feedback. Thanks.

Week 4: More recursion

I have been meaning to post an update for the materials covered in week 4, but due to numerous exams and assignments that, with my unfortunate luck, crammed all into the period of a single week, this post has been a few days overdue. With that said, time to move on to the topics of week 4!

In this week's CS lecture ("or technically, 'last' week), we went over the topic of recursion once more. Though I personally have a relatively strong grasp on the subject, (due primarily to the fact that I find recursion to be a very elegant way of solving problems, complemented by the fact that I find it to make sense intuitively-speaking) I thought it was nice that we covered some more ground on recursion. On a side note, I found that many of my classmates find the topic of recursion to be somewhat confusing, and that they would use simplifying statements such as "recursion is just a method that calls itself" to describe it, which although is correct, does not necessarily reflect the other facets that makes recursion an elegant solution to solving programming problems (i.e. the concept of breaking a problem down into sub-problems until a base-case solution is reached).

We also covered some ground on the basics of tracing a function, which I think is rather important (as many other programmers would probably agree) in understanding how one's function is supposed to behave and how it behaves in actuality. Before I begin coding any functions in my module, I always have a quick mental side note with myself to quickly run the function in my head to see how I expect my function to be implemented, which I would then compare to how it is actually implemented when I run the module by looking at the results. I find that by quickly mentally tracing the implementation of my function in my head, I become more aware of any potential errors in my code when my program (inevitably) runs into problems during my first trial run. By tracing the implementation of my function, I find myself more "synchronized" with my code, for the lack of a better word, and am able to better understand what my code is doing in my program.

While I'm on this topic, one thing I found to have been particularly useful in my programming endeavours is including a print() statement at the end of functions that I feel "uneasy" about to more clearly see what my program is doing. This little "technique" has been very useful for me when I'm fixing my code due to unexpected errors.

We also briefly went over nameless functions with lambda during lecture. I found the concept to make sense intuitively, and I can easily visualize its practical applications when programming (i.e. reducing time spent creating simple functions that are only used once, as well as reducing the lines of code in a module). However, I must admit that the syntax for creating lambda functions still troubles me in my sleep, as I am very much unfamiliar with the syntax used in creating lambda functions. One of my goals in the next couple weeks is to become more familiar with creating lambda functions, such that I can easily integrate such functions into my code without fear of unexpectedly running into problems due to simple SyntaxErrors.