Week 10

    This week in CSC148, we learned about big-oh notation and some various sorting algorithms. In addition to this, the second part of assignment II was due. Going to class was very helpful because the professor give us lots of really good hints as to how to approach the problems. For me, the toughest function in the assignment was regex_match(r, s), which returns True if the string s matches the RegexTree rooted at r, and False otherwise. It seemed like the more I tested, the more bugs I kept finding in my program. For example, even when I had '.' working and '*' working, putting them together in the form (r1.r2)* required even more thinking and coding. I think I got a solid program submitted by the deadline, though, so now it's on to studying for the midterm!

Week 9

    This week, we were assigned our third exercise in the course. In the first part, we had to make a function that takes the pre-order and in-order traversals of a binary search tree and reconstructs the tree. I found that this was kind of tricky at first, but after playing around with it a bit, I was able to figure it out. Recursion is my friend. Recursion is my friend. Recursion is my friend. In the second part, we had to make a function that takes a BST and returns the sum of the nodes along the tree's deepest branch. I am working on this right now - haven't finished yet. I'm trying to figure out how to record and compare each of the tree's branches. Hopefully I'll be able to figure it out by the due date at the end of the day!

Week 8

    This week in CSC148, we focused mainly on linked structures. In the lab, we had to make methods for a LinkedList class including __len__, __setitem__, __delitem__, and insert. The trouble was that the only two helpful methods already built were prepend and decapitate, so we were required to use recursion. This was a bit different than the recursion I have been exposed to so far. We had to kind of count down through the indices i of the LinkedList until 0 was reached, calling the function on i - 1 each time, in order to reach the recursion depth that we wanted to insert at, or set, or delete. Here is the method __getitem__, which demonstrates what I'm trying to say:

  def __getitem__(self: 'LinkedList', ind: int) -> object:
        """Return the item at position ind.
        Raise exception if ind is out-of-range

        >>> lnk = LinkedList(5, LinkedList(7, LinkedList(11, LinkedList())))
        >>> lnk[1]
        7
        """
        if self.empty or ind < 0:
            raise IndexError
        elif ind > 0:
            return self.rest.__getitem__(ind - 1)
        else:
            return self.item

Week 7: Recursion

    If you're confused as to why I included the picture above (and what it has to do with recursion - the mandatory topic this week), look at the picture on the cereal box. Then look at the picture on the cereal box on the picture of the cereal box. Then look at the picture of the cereal box on the picture of the cereal box on the the picture of the cereal box... You probably get the idea now.

    Recursion can definitely be a little overwhelming to think about at first. For me, the greatest mental barrier I had to overcome was figuring out how a function can be defined when what it does depends on what it does... when what it does hasn't been defined yet. Regardless of how involved this sounds, I found that once I went through a couple clear examples of recursive functions, there was really nothing so daunting about the concept at all.

   And  in some cases, a recursive function can truly be the simplest, most elegant, and most efficient way to tackle a problem. Take this example we did in class, that returns the nested depth of a list:

def nested_depth(L):
    """
    Return nested depth of list L.

    Nested depth is:
    0                                   --- if L is a non-list
    1 + maximum nested of elements of L --- if L is a list

    >>> nested_depth(3)
    0
    >>> nested_depth([1, 2, 3])
    1
    >>> nested_depth([1, [2, 3], 4])
    2
    """
    return (1 + 

            # maximum nested depths of elements of L, concatenated with 0
            # to deal with possibility that L is empty
            max([nested_depth(x) for x in L] + [0])

            # 0 if L is a non-list
            if isinstance(L, list) else 0)

Any iterative function that returns the same result would certainly be much longer and more complex, not to mention trickier to build and understand.

    Recursion is fun. Yay.

Week 6

    This week, assignment 1 was due. Luckily, I ended up finishing the project a few days prior to the due date, so I had a good amount of time to go over my code and make sure everything was clear and efficient. I also made an attempt at the bonus problem. My function passed the test case in the doc-string, so hopefully I'll get the extra credit!
    In class, we focused mainly on leaves and trees. I was a little confused at first, because I didn't really understand what the point of it was. It took me some time to really realize that  a tree is just an abstract data type like any other, with its own characteristics and features. I feel good about class this week; I feel like I have a good grasp on the material. Now time to study for the midterm!

Week 5

This week, we spent some time in class discussing Assignment II, "Towers of Anne Hoy". I decided to work on this project alone, so the extra help was certainly welcome. So far, I'm about half-way through. I'm having fun with it. I'm finding that my progress isn't really continuous, but sort of jolting, stop-start. I'm stuck; I figure it out; I work a little; then I'm stuck again. With this sort of assignment that requires so much intensive and constant problem solving, I think it really takes time to deeply understand what has to be done and how to approach it. I also found that it was really worth the effort to read through the starter code and make sure to fully understand it before going on and doing any actual coding. So hopefully the rest will go smoothly enough, and it won't be too much of a rush to meet the deadline.

Week 4

    This week, we delved deeper into recursion. We looked at it  mostly in terms of lists, creating a recursive function "nested_depth" that calculated the nested depth of a list. For example, the nested depth of [1] is 1, and the nested depth of [1, [2, [3, 4], 5], 6] is 3. The return statement for this example is as follows:
return (1 + max([nested_depth(x) for x in L] + [0]) if isinstance(L, list) else 0)
This, at first, was a little tough to comprehend. It definitely took a bit of mental wrestling with the fact that a function could make a call on itself before it was even fully defined. However, I think I made a bit of a personal breakthrough this week. I did some extra research on the internet and found that the more I looked at different examples of recursive functions the more sense the concept made to me.
So, this was a good week in CSC148. I feel comfortable with the material so far. Eager to learn more.