Week 11: Recursion revisited

After working out recursive solutions for Assignment 2 and Assignment 3, my fascination with recursion has only increased. Moreso in Assignment 3, I find it amazing that recursive functions can span less than a dozen lines in order to achieve their purpose. However, even while the body of the recursive functions and respective helper functions often totaled no more than a dozen lines, it was often the case that the amount of time spent thinking was tremendous. I often found that I was always thinking way too hard about the implementation of a recursive function and always ended up hitting dead ends and writing very convoluted code. As such, one benefit of dealing with recursion is that I learned to slow down my working process and really think before I code instead typing a few lines thinking "This may or may not work..."

Week 8 SLOG: Binary Trees and Binary Search Trees

In week 8, we learned about Binary Trees and Binary Search Trees.

Binary Trees are simply trees that have a node, and at max have two children under each node.

Binary Search Trees (BST) are a special type of binary tree. They have three distinguishing characteristics:
(1) All data in BSTs are comparable.
(2) The data in the left subtree are less than the root node
(3) The data in the right subtree are greater than the root node.

As such, they are useful when holding information that needs to be compared because the structure of a BST makes it very easy and efficient to traverse.

There are three different ways to traverse a Binary Tree: Preorder, Postorder, and Inorder.
The names of these traversals are very self-explanatory.
In Preorder, the main node is visited first, then the left subtree second, and finally the right subtree.
In Postorder, the left subtree is visited first, then the right subtree, and finally the node itself.
In Inorder, the left subtree is visited first, then the node itself, then finally the right subtree.

Week 7: Abstract Data Types

An abstract data type (ADT) is a functional model of a specific data structure. Example ADTs are Stacks and Queues. It can be said that the implementation of an ADT does not define it, but rather the data held inside it and its associated operations. For example, inside a Stack, one can store sets of objects and push() and pop() items out. As such, abstract data types explicitly have two parts:
(1) a set of operations that can be performed on the specific ADT (2) a name to specify a set of data.

There is also an underlying principle regarding abstract data types, in that they hide information. For example, if I wanted to implement an ADT in the form of a Queue. I can do so by writing:

class Queue:
    ''' Represent a FIFO queue.
    '''

    def __init__(self):
        ''' (Queue) -> NoneType
        '''
        self._data = []

    def enqueue(self, o):
        ''' (Queue, object) -> NoneType
        '''
        self._data.append(o)

    def dequeue(self):
        ''' (Queue) -> object
        '''
        return self._data.pop(0)

    def is_empty(self):
        ''' (Queue) -> bool
        '''
        return self._data == []

And thus I have implemented a Queue for anyone to use. However, when I allow someone to use my implementation of this Queue, I only need to provide the operations and the name so that someone may utilize this fully. In other words, I do not need to let them know the implementation information, but they are still able to use the Queue if I give them the operations like: enqueue, dequeue, and is_empty.


As such, some information is abstracted to the user and hidden (the actual code), but the user is still able to fully utilize the ADT knowing its methods.

Object-Oriented Programming

Object-Oriented Programming is simply the manipulation and interaction of different objects. It has many benefits, including eliminating the need to write duplicate code. A good example of this is the creation and interaction of classes, the blueprints for objects.

If I wanted to emulate the workings of a school, I can create a few classes to represent this. For example I can create separate student, and teacher classes.

class Teacher(object):
 
    def __init__(self, name, subject):
        self.name = name
        self.subject = subject

class Student(object)

    def __init__(self, name):
        self.name = name

Bob = Teacher(Bob, English)
Joey = Student(Joey)

Now I have created (a representation of) a teacher named Bob who teaches English and a student Joey.
But hold on, since both a student and teacher are people, I can create a class named Person and have the Student and Teacher class inherit from that Person class. This way, if I ever wanted new Student and Teacher attributes, like something universal like age, sex or height, I would only need to edit the parent class, Person, instead of editing several different classes.

class Person(object):

    def __init__(self, name, age):
        self.name = name
        self.age = age 
    
class Teacher(Person):
   
    def __init__(self, name, age, subject):
        Person.__init__(self, name, age)
        self.subject = subject
       
class Student(Person):

    def __init__(self, name, age, grade):
        Person.__init__(self, name, age)
        self.grade = grade


Since a teacher and a student are both people, I can simply construct a parent class called Person with attributes that are common among all people, like age and name. Then, in the Teacher class, we need to know what subject that teacher teaches, but also by inheriting from the Person superclass, we can ensure that the teacher has a name and an age. And for students, a unique attribute may be what grade that student is in. So we first simply inherit from the superclass to ensure the student has a name and age, and then create a new attribute called grade in the constructor of the Student class.

Object-Oriented Programming is very intuitive and saves a programmer a lot of work in terms of writing efficient code.

Week 5 SLOG: Recursion

I find recursion to be really fascinating. There are three principles for a recursive function:

1. There must be a base case.
2. The function algorithm must tend towards that base case.
3. The function must call itself.

An example of a recursive function is a function that calculates factorials.

def factorial(n):

    if n == 1:
        return n
    else:
        return n * factorial(n-1)

>>> print(factorial(5))
120

As one can observe in this function, the base case is when n is equal to 1, in which case it will return n, or else it will move towards that base case by multiplying n when it's not 1 with the factorial of n-1.

Recursion looks like it is a staple of computer science and problem solving in general.

My Impression of the First Weeks of CSC148

In these first few weeks of class, we reviewed basic concepts from CSC108 and covered new subjects; the major ones that I believe are: list comprehension and stacks

List Comprehension
List comprehension is a fantastically efficient way to create a list in Python. It encompasses the simplicity, efficiency, and readability one would expect in Python.

For example, if we needed a list of the powers of 2^n, from n = 0 to n = 9, we can construct the list with list comprehension, instead of writing a function for it.

List Comprehension
>>> [2 ** n for n in range(10)]
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

Function (Doing the same thing)
def powers_of_two(n):
    lst = []
    for x in range(n):
        lst.append(2**x)
    return lst

>>> powers_of_two(10)
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512]

Stacks
Stacks are a type of abstract data type in which the last item in is the first item out. An example of this is a Python list, in which when you call append on it, you add the item you want to append to the end of the list. And then when you call pop() on the list, the last item of that list will be removed.

>>> stack = [1, 2, 3]
>>> stack.append(4)
>>> stack
[1, 2, 3, 4]
>>> stack.pop()
4
>>> stack
[1, 2, 3]

Of course, this is only one example of stack. One can even construct a stack as a Python class and then manually implement the methods of pop and push.

The Importance of Writing as a Geek

    When writing is mentioned, thoughts of late night essays on The Catcher In The Rye and trauma induced from mile long research papers resurface in one's mind. So why would it ever be useful for a geek, or more specifically, a computer programmer? I mean, in accordance with Hollywood depictions, all they have to do is sit in a dimly lit room and type in code on a computer right? Well, if it were only that easy.
    As it turns out, writing is especially important for even someone who works with technical things like programs and codes. The reason being that writing forces one to explicate in detail about a problem that may occur, thereby helping you recognize what needs to be done and get closer to a solution. Writing in relatively coherent manner about a more technical subject helps you to understand what is happening. If you are able to explain recursion in layman terms to your 10 year old niece and then explain it to your more knowledgable professor, chances are that you have great, or at least, sufficient knowledge of the matter.
    I also claim that writing helps to improve communication skills. This is especially important in the corporate world. When you interview for big companies like Amazon, Google, or Facebook, the interviewer may ask you a difficult puzzle problem. Chances are that they do not expect you to entirely solve it on the spot, but instead expect you to narrate your thought process in a coherent, logical manner. Doing so proves to your interviewer that you are capable of individual thought, and reveals more of your character to them then a piece of code that, for all the interviewer knows, could have been copied off github or stackoverflow.