Week5 - More Recursion and Time Control

Hi Everyone,

This week we handed in our assignment1, which takes three of us a whole weekend to do. We found the recursive functions are the most difficult part. We reviewed many recursive functions from lectures and labs when we're writing our codes. There are three interesting codes which I think mostly improved my programming skills. In this week's post, I am going to share these three recursive functions with you. At the end of this post, I am going to talk about how to control program running time in Python. Thank you for reading :)

Binary Represent:

This is the function that uses recursion to build a program converting numbers into binary numbers, even more surprising, we can do for ternary numbers, quaternary numbers, and even k-nary numbers!

We develop our k-nary numbers by first solving the problem for binary numbers. Here we used the programming skill that we mentioned in Week3's post, solving a big programming problem by solving a simpler case first.

def bin_rep(n: int) -> str:

    """Return binary representation of n in base 2

    n --- non-negative integer

    >>> bin_rep(0) == "0"

    True

    >>> bin_rep(1) == "1"

    True

    >>> bin_rep(5) == "101"

    True

    """

    return bin_rep(n // 2) + bin_rep(n % 2) if n > 1 else str(n)

Note:

# The binary representation of n is the binary representation of

# n // 2 concatenated with the binary representation of n’s last bit

# provided n > 1, otherwise it’s just n as a string

def bin_rep(n: int, k: int) -> str:

    """Return binary representation of n in base 2

    n --- non-negative integer

    >>> bin_rep(0, 10) == "0"

    True

    >>> bin_rep(1, 2) == "1"

    True

    >>> bin_rep(5, 3) == "12"

    True

    """

    return bin_rep(n // k, k) + bin_rep(n % k, k) if n > k - 1 else str(n)

Note: 
# The binary representation of n is the binary representation of
# n // k concatenated with the binary representation of n’s last bit
# provided n > k - 1, otherwise it’s just n as a string

Nested Depth:

The second example is "nested_depth", which is a typical recursion-use function, and there's a small trick that we should be careful of: when we use a built-in method (such as 'max' in this example) applied to a list, we should make the list is not empty. The easy way to control a non-empty is by adding [0] (as highlighted in the code below).

def nested_depth(L):

    """

    Return if L is non-list, or 1 + maximum of depths of elements list L.

    Not defined for infinitely nested lists.

    >>> nested_depth(3)

    0

    >>> nested_depth([1, 2, 3])

    1

    >>> nested_depth([1, [2, 3], 4])

    2

    """

    return (1 + max([nested_depth(x) for x in L] +[0]) if isinstance(L,list) else 0)

 #Note: the [0] is in case we have an empty list

Tower of Hanoi (three stools, seq_of_move):

The last function I am going to talk about is from our Assignment. All the recursive functions we see so far only call themselves once; in this part of Hanoi function, we call the Hanoi function twice within itself. So we learned that the recursive function can happens several times. 

The following code is the sample code provided by Prof. Heap, I am not supposed to post our code here but we use the exactly same strategy.

def move_cheeses(n: int, source: int, intermediate: int, destination: int) -> None:

    """Print moves to get n cheeses from source to destination, possibly using intermediate"""

    if n > 1:

        move_cheeses(n - 1, source, destination, intermediate)

        move_cheeses(1, source, intermediate, destination)

        move_cheeses(n -1, intermediate, source, destination)

    else: # just one cheese --- no recursion required!

        print("Move top cheese from {} to {}".format(source, destination))

Control Program Running Time (with Time module):

We studied too hard to figure this out, even though it's simple haha. If someday you're asked to control your programming running time, there is a built-in model in Python called "time". The thinking here is set the init time first, then the second time, if the time difference is smaller than the one we want, let the program keep running, time2 continuously increase, until (time2 - time1) = time_difference, other codes will run after.

The sample code is as following:

time1 = time.time()

time2 = time.time()

while (time2 - time1) < time_difference:

      time2 = time.time()

#other codes

I am going to talk about scopes and tree class in next week's post. Come back soon~

Week4 - Inheritance and Recursion

Hi Everyone! 

In this week's post I am going to talk about Inheritance and Recursion in Python.

Inheritance and Recursion are two very important process in computer programming. I was also confused when I first learn it. The example function tree_burst(), which I gave in Recursion part, is the one that I found most trouble with. Our prof taught it in class, but it's not very clear. I traced back every step of the recursion, wrote it out in my scrap paper and drew the turtle lines, but I am still confused with turtle_list.append(turtle.clone()).

Turtle module open a new world for me to realize that we can also use python to draw graphs, and this turns the scalar quantities to vector quantities. Furthermore, in this way, I guess we can also create any finite dimensional vector space using computer!

tree_burst() function is not a very good example for beginners to understand recursion, but I still decided to post it out because it is indeed a very impressive function. If anyone feel confused about it, please just skip and move to the next part. (If you have some good idea about the turtle_list.append(), please feel free to communicate! )

A. Inheritance

Literally, inheritance is the practice of passing on the feature to a child upon a parent. Well, in python, inheritance means the subclass(child) get most or all its method(feature) from its superclass (parent). 

There are three ways of inheritance:

1. Implicitly Inheritance

which means some or all the features that the child gets from his father didn't show off (we don't necessarily write it out in our subclass)

class Parent(object):

    def a(self):

        print "PARENT implicit()"

class Child(Parent):

    pass

*Here the method "a" is a implicit inheritance of the Child.

2. Override Explicitly

A child is not as same as their parent, same in the Python, sometimes a subclass behaves differently. We are going to override the function in the child, replacing the functionality inherited from its superclass. 

class Parent(object):

    def override(self):

        print "PARENT override()"

class Child(Parent):

    def override(self):

        print "CHILD override()"

3. Alter Before or After

A child can act completely different without their parent, but once their parent show up, they will behave like an angel. 

In python, we can add a parent version of the function runs among the child versions. 

class Parent(object):

    def altered(self):

        print "PARENT altered()"

class Child(Parent):

    def altered(self):

        print "CHILD, BEFORE PARENT altered()"

        Parent.altered(self)

        print "CHILD, AFTER PARENT altered()"

*These three inheritance we can use them separately or together

*Child(Parent): the Child class is a subclass of Parent class

*Parent(object), because every class is a subclass of the object class

B. Recursion

Recursion means "defining something in terms of itself", e.g. A cat is a kind of animal whose mother is a cat. In python, recursion means a function can call themselves to solve smaller subproblems. 

Note a finite recursive a function must have a base case, in order to indicate the function where to stop, otherwise the function will run forever and it will become an infinite recursive function.

def tree_burst(level, base, turtle):

    """Draw a symmetrical ternary tree of height level with initial edges

    of length base.

    """

    if not level: # Pythonese for level == 0

        pass

    else:

        turtle_list = []

        for h in range(3):

            turtle_list.append(turtle.clone())

            turtle_list[h].color(COLORS[h])

            turtle_list[h].setheading(120 * h)

            turtle_list[h].forward(base)

            tree_burst(level - 1, base/2, turtle_list[h])

* Note in this example, the italic format indicates the base case. Specifically, when level == 0, the recursion stops.

That's all for this week, thank you for reading! Next week I am going to talk about unittest, see you next week! :)

Week3 - Objected-Orientated Programming (OPP)

Hi Everyone!

This is  Azura. I am a first year math student in U of T, taking CSC148 this term. This is my first time writing a blog, and it's even in English! There may be some language errors, so please free to point it out~~

Besides CSC108, I have no programming experience before, when Danny's talking about 148 will focus on object-orientated programming, I have no idea what's going on. I don't know what does it mean by that, but the person sits besides me seems like she knows everything! 

What's the difference between the program I wrote in 108 and the program that I am going to face in this class?? I go back and try to read those supplemental pages on our website. Those kinds of programming we did in CSC108 are considered as procedural programming in formal definition, it is about writing functions that operate on data. 148 is about object-oriented programming, it is focus on the creation of objects contains functions and datas together. 

Class is analogous to a "factory" to produce instances and also "a template for the objects that are instances of it" on the website. I then more understand what a class is and why we need to use class. Then when it comes to my lab session, when I am actually doing it, I am more familiar with the way I learned about how to handle a object-orientated project. I worked with my partner and we think of how handle the whole object at first , then we focus on doing every small parts and finally review and check the whole object. I am more confident now, and know the algorithm to construct a class.

The python style we learned in 148 is different from CSC108, so I was also confused about the different ways of constructing a class. Then I found examples from both classes and compare both, I think the thinking to construct a class is the same, the difference is the writing style. 

The similarity that I figure out is:

1. Define a __init__ function at first to initialize the class

2. Every function needs a self default parameter

3. Can use built-in functions to help out

 The difference that I figure out is:

1. A class can also has a description which right below the class header and above the __init__ function

2. Contract type goes right after the parameter, whereas it was wrote independently below function header. 

3. Besides those built-in functions, we can also use list comprehensions with the following format [(expression) for (name) in  (iterable)], here () indicates the variable that we can change to make our desired comprehension.

Also, there is another very useful list comprehension, especially when we write our return statement. Instead of write 

if a > b:

return "Hi"

else:

return "Hello"

we can write 

return "Hi" if a > b else "Hello"

This week's lecture also talks about recursion and inheritance, which can also be used to create a class. I will talk about these two terms next week. :)