Sorting and Efficiency

   To start with, we should know the definition of algorithm. Basically, algorithm is a step by step procedure for calculation, and it is used for calculation, data processing, and automated reasoning.Different Algorithms provide methods with different thoughts, some will solve a problem in a faster way(best case), but some of them will take more time to figure out(worst case).

   There are various kinds of sorting methods. We will discuss the most common ones in the following text. At first, we need to know what Big O notation is. Big O notation characterizes the function according to its growth rate: different functions with the same growth rate may be represented using the same O notation. Big O notation usually provides an upper bound on the growth rate of the function.The other types of growth are described by using the symbols  o, Ω, ω, and Θ. 

   1) Insertion sort builds the final sorted list one item at a time, however, this method is less efficient on large size lists.The worst case is O(n^2), the best is O(n), and the average is O(n^2). Now let's sort the sequence  {3, 7, 4, 9, 5, 2, 6, 1} from small to big by using insertion sort. We will do the following step:

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 7 4 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 7 9 5 2 6 1

3 4 5 7 9 2 6 1

2 3 4 5 7 9 6 1

2 3 4 5 6 7 9 1

1 2 3 4 5 6 7 9

   2）Selection sort is also inefficient on large lists. The algorithm of selection sort is that it divides the input list into two parts: the sublist of items already sorted, and the sublist of items remaining to be dealt(rest). It proceeds by finding the smallest(or largest) item in the unsorted sublist, exchanging it with the leftmost unsorted element, and move one element to the right. The best, worst, and average cases are the same that is O(n^2). The following image is an example.

3) Bubble sort works by repeatedly stepping through the list, it compares each pair of adjacent elements and swaps them if they are in the wrong order, and it is also not quite efficient on larger size lists. The worst and best cases are O(n^2), and the average is O(n).The following image is an example of bubble sort, and we can notice that it takes lots of time to run.

4) Merge sort divides the unsorted list into n sublists, each containing 1 element, and it repeatedly erge sublists to produce new sorted sublists until there is only 1 sublist remaining. The worst, best , and average cases are the same that is O(n log n).Here comes the example.

5) Quick sort at first picks an element as a pivot from the list, and then reorders the list so that the values less than the pivot come before the pivot, and the greater ones comes after it. At last, it will recursively apply the above steps that is choosing the pivot and comparing the value to put it in the correct order. Unlike the merge sort, the worst case of quick sort is O(n^2). Here is the example.

By learning the sorting and efficiency part of computer science, I can know what computer scientists think about the algorithms, and how they improve the efficiency, and this can extend my ways of thinking about a problem. Also, saving time is the best.

Week 10

   This week, we also focused on sorting, and during the lab, we have finished coding the inorder function which returns the first node in a linked list that contains every value from the binary tree, and its longest path. The first one was easy to think up, but for the second one, we should apply the theory of big-o, and this take me more time to finish. Next week, we will have the midterm II test, so during this weekend, I should work hard to review the past materials. My weaker point is the recursion, I still could not think up a recursion in a natural and easy way by myself, as a result, I need to do more exercises, and read more examples. There are only 2 more weeks, hope everyone can get a ideal result in CSC148. Have a good weekend, but do not forget studying!

Week 9

   During Week 9, we learned about Big-O in class, and solved some BST problems in the lab. At first I had little knowledge of the helper function, but after the lab, I realized that writing a function can make the whole code easier to understand. For example, we want to calculate the factorial of n, we can write the following code:
def _fact(n):
    if n == 0:
        return 1
    return n*_fact(n-1)

def fact(n):
    n0 = int(n)
    if n0 != n:
        raise ValueError
    if n < 0:
        raise ValueError
    return _fact(n)
 
  Big O notation is used to classify algotithms by how they respond to changes in input size, and it usually provides an upper bound on the growth rate of the function. In the runtime problem of python, we call it the worst-case scenario.In CSC240 and CSC165, we have already learned about this concept, so this is easier for me to understand.
  As for the binary search tree(BST), it makes the related sorting algorithms and search algorithms (like in-order traversal) very efficient.

Week 8

  In Week 7 and Week 8, we focused on the topic LinkedList during the lecture and the lab. LinkedList is an interesting data structure, and it is recursively defined. LinkedList is made up of nodes which contain a reference to the next one, and this kind of data is called cargo. During the lab, I have learnt many methods dealing with the LinkedList, like how to add new item to front of the LinkedList, delete item from LinkedList, check whether a LinkedList contains a specific value and find out the position (index) of the value or item in the the LinkedList. The following code is an example of the class LinkedList:

class LinkedList:
    """Linked list class"""

    def __init__(self: 'LinkedList', item: object=None,
                 rest: 'LinkedList'=None) -> None:
        """Create a new LinkedList
        item - The first element of the linked list,
        Not present if self will be the empty linked list.
        rest - The linked list that contains the elements after item.
        Not present if self will be the empty linked list."""
        self.empty = (item is None) and (rest is None)
        if not self.empty:
            self.item = item
            if rest is None:
                self.rest = LinkedList()
            else:
                self.rest = rest
This week's lab is more easier for my partner and I to finish, because we have read and learnt more materials of LinkedList. To learn this stuff well, we should always think carefully about the recursion method. A few weeks are left, I think I should practise more to think up the code much more quickly and correctly.

Recursion

    The recursion method of python is very interesting, because it will call the function itself when you write the body of the function, and this makes the program much more succinct. For example, we want to write a program that reverses the string '12345' to '54321', with the help of recursion, we can write the following code to implement the request.

   def reverse(n):

    def reversestr(s):

        if s:

            return s[-1] + reversestr(s[:-1])

        else:

            return ''

    return int(reversestr(str(n)))

   

   As we can see, recursion can make a question that seems to have complicated steps easier to solve., and there must be a statement in the code to end the recursion (mainly the if or else statement), in the above example, it is the else statement that ends the recursion. Another classic example is the Fibonacci sequence 0,1,1,2,3,5,8,13,21......:

    def fib(n):

        if n<=1:

           return n

        t=fib(n-1)+fib(n-2)

        return t

   Like we want to find the 7th value of this sequence, and we need to add the 5th and 6th values together, and to get the 6th value, we need to find 4th and 5th, and so on. The two values are 0 and 1, so they are constant and will be the end of this recursion.
   Recursion is very useful, but kind of difficult for me to come up with ,so I need to read more materials and do more exercises to improve this skill.

Week 7 --- Reading Week

    Time flies fast, and the reading week is over. During the reading week, I went to Robarts Library every two days in order to have a quiet environment to prepare for my upcoming midterm, and I have read the materials that we have learnt so far, and also the other study guides of class, stack, recursion, and trees which are written in Chinese to help me understand. I have wrote the two past tests, I thought I should study more since I could not finish them on time, because I thought I lacked of thinking up a program in a faster way. To solve this problem, I should learn more useful examples, and think why the author wrote the code like that. I hope I can do a good job in the midterm.

Week 6

   This week I finished the assignment #1 successfully by myself, and I thought piazza is a good forum for students to discuss questions, and during the process of doing the assignment, I logged into piazza several times every day to check out the new posts of the other classmates, and I could learn from their questions, and came up with my own idea. The lab of this week was about the iteration which we have learnt a lot from CSC108, the for loop, and it was easy to deal with, because I have watched some CSC108 video lectures once more. However, after the reading week, the first term time will be held, thus, I decided to review the lecture slides, reading materials, labs, exercises, and also the assignment during the reading week.

Week 5

   This week, I have learnt more deeper knowledge of recursion in python both in our lectures and lab#4. At first, I think recursion is kind of annoying, because it is a little difficult for me to understand, but when I got used to it, I think it can solve many problems much easier by calling the function itself. CSC148 is quite different with CSC108, because in CSC108, we can write a program by learning from examples, however, in CSC148, we should think carefully to design a program. Therefore, we need to read more notes and examples to enrich our thought. As for myself, I think it is easier to read a code, and understand how it works, but it is difficult for me to think up a code that a question asks me, because so far, we have learnt numerous methods of python, and I do not know how to choose the correct the method to solve the problem. As a result, I know that I should review the knowledge very often both in the current lectures and the past old ones (including CSC108). This weekend, I would like to review the oriented-programming, classes, exceptions, stacks, and recursions to get well-prepared for finishing my assignment 1, and the upcoming midterm test. Also, during the reading week, I think it is necessary to watch the video lectures of CSC108 once more to consolidate the basic but important knowledge.

Python Recursion

   This week we have learned the recursion in Python language, and recursion is a process of repeating subjects in a self-similar way. 

   For example, factorial(N)=N!=N * factorial(N-1)

Then we can write the following code:

def factorial(n):

    if n==0 or n==1:

        return 1

    else: 

        return (n*factorial (n-1))

print factorial(6)

Then we will get factorial(5) is 120. However, there is a maximum limit for the value of the parameter which is related with the memory of the computer. If n is greater than the limit, then there will be an error indicated. RuntimeError: maximum recursion depth exceeded.

Another example is that if we want to calculate the sum of 1,2,3,...,100. We can write the code like this:

def add(n):

   if n<=0:

      return 0

   if n > 0 :

      return n+add(n-1)

Then if we write add(100), we will get 5050 easily.

Every program of recursion always follows the same basic steps:

1) Initial algorithm.--Recursion always needs a seed value to start with.

2) Checking the correctness of the base case.

3) Using smaller or easier subproblems to re-define the answer.

4) Running the algorithm for the sybproblems.

5) Combine the results into the expression of the answer.

6) Return the results.

Week 3 ——Object-Oriented Programming

   During the first three weeks of course CSC148, I learned ways of Object-Oriented Programming like class, and stack. Object-Oriented Programming (OOP) is a programming paradigm using data fields and methods of “objects”-data structures for the design of applications and computer programs. In the class method, we use __init__(two underlines on both sides) to initialize the program and we can also add the initial values after __init__. The specific method is defined after the term “def”, it is not a function, because for every method, “self” is always the first parameter, but when we use it, we do not need to provide it, because the program will automatically bind the first parameter to the corresponding example. The methods and features of python are acquiescently public or common, and if we want to make it private or for our own, we need to use the double underlines before the name of the method. When writing another class name after the “class-method"sentence, and this class name will inherit the specific class. A good example for class-method is:

class Point:
　     """ Point class represents and manipulates x,y coords. """

        
     def __init__(self):

           """ Create a new point at the origin """
           self.x = 0
           self.y = 0
            p = Point()         # Instantiate an object of type Point
            q = Point()         # Make a second point

   print(p.x, p.y, q.x, q.y)  # Each point object has its own x and y
    >>> p.x = 3
    >>> p.y = 4
    >>> print(p.y)
    4
    >>> x = p.x
    >>> print(x)
    3
  As for stack, it is a kind of built-in list of python, and we need to remember the basic methods that are： 
 （1）：__init__  Initialize a new empty stack.
   (2):  push  add a new item to the stack.
   (3) : pop Remove and return an item from the stack. 
   (4) : is_empty Check whether the stack is empty.
　　　

>>> stack = [3,4,5]

>>> stack.append(6)

>>> stack.append(7)

>>> stack

{3,4,5,6,7]

>>> stack.pop()

7

>>>stack

[3,4,5,6]

>>> stack.pop()

6

>>>stack.pop()

5

>>> stack

[3,4]