Week 11-Sorting and Efficiency

Sorting and Efficiency

When we need to measure the performance of an algorithm, we usually focus on the size of the input. The size could affect the time required to execute an output.
There are different complexities to consider. Suppose n is the input size, there are different ways to vary n. Here below are the ones we have gone through in class:

Week 7- Linked Structure

A Tiny Review: What is Recursion in Python?

For the past few weeks in CSC148, we did a lot of recursions. Recursion is a method in which the function calls themselves within their definition. They can be used multiple times. Recursion shortens complex codes. It involves breaking the problem into smaller subparts and until it can be solved, which is also the base case. Without it, the program will not work since it would loop infinitely until the maximum recursion depth is reached in Python and returns with a runtime error.

To me, it is like finding the greatest common divisor.

For how to start with recursion, please refer to Week 4 - More Recursions!

Linked Lists!

So this week, we were taught how to design a class for Linked Lists.
Linked lists basically are like the Tree class discussed last week ().

Week 4- More Recursion

Tracing

In class, we used a nested example for recursion. We were expected to define nesting-depth of L as 1 plus the maximum nesting depth of L's elements if L is a list, otherwise 0.

We started off with writing the definition and return statement:

We did tracing in order to understanding how recursion works. In the lecture, we were given a few recursive calls to trace with reference to  nested_depth.

Trace   nested_depth([])
1 + max([] +[0]) -> 1
Trace   nested_depth(17)
Not a list -> 0
Trace   nested_depth([3, 17, 1])
1 + max([0, 0, 0] + [0]) -> 1
Trace   nested_depth([5, [3, 17, 1], [2, 4], 6])
1 + max([0, 1, 1, 0] + [0]) -> 1 + 1 -> 2

Trace   nested_depth([14, 7, [5, [3, 17, 1], [2, 4], 6], 9])
1 + max([0, 0, 1, 2, 2, 2, 2, 2, 1, 0] + [0]) -> 3

For a more complex one, we tried finding the maximum number of a nested list using:

This can further show how recursion works by tracing.
Trace   rec_max([3, 5, 1, 3, 4, 7])
max([3, 5, 1, 3, 4, 7]) -> 7
Trace   rec_max([4, 2, [3, 5, 1, 3, 4, 7], 8])
max([4, 2, 7, 8]) -> 8
Trace   rec_max([6, [4, 2, [3, 5, 1, 3, 4, 7], 8], 5])
max([6, 8, 5]) -> 8

Drawing Turtles

This week, we also looked at the tree_burst function and by using the Python Launcher

If we change our docstring example at the bottom into the following, what will happen?

The Python Launcher has helped me in graphing the first example and I tried by implementing the codes for second example listed above into the graph (in similar colours):

Week 1 -Object Oriented Programming (OOP)

In CSC108, we did if statements, loops, defining functions, calling a function, lists, dictionary etc. Proceeding to the CSC148 lecture, we begin with Object-Oriented Programming (OOP). The programming language we use is Python which is an OOP language. This give me a deeper understanding of Python.

Object-Oriented Programming

OOP uses the concept of objects. Attributes are to describe the objects. Methods are functions inside an object where you pass an attribute. The basic elements in Python are like str, dict, int, different functions etc, which are all examples of objects. An object includes data and functions. Relationships can be created in OOP between one object and another. One advantage of OOP is that the defined objects and functions could correspond to the real-world.

Designing a class

After an object is identified, we could design a class. In python, we can create our own defined class. In the lecture, our professor suggested finding the most important noun which could be a name for a class, the important attributes and operations of the noun as the methods. In class definitions, usually there will be function definitions which starts with def followed by some arguments and methods. 
The form of class definition is as follows:

class ClassName(object):
    """ A class example"""
        def function(self):
            pass

This is the basics of designing a class, in the coming weeks, there will be more implementations of class design and hopefully with these basics I could design better classes.