Last impression about this course

Looking over this course, it is different from a pure programming teaching course which focus on grammar and programming technique. Instead, it focus more on programming thinking. Most of the time, we are not learning how to write code, but how to solve, how to arrange the structure of the program. I remember there was a impressed demo. Professor Heap wanted to explain how binary tree search work. He asked all of the students to be one on the node, and each line of student represent a level in the tree. He as the root of the tree asked question to his sons which are the first lines of the student, and the first line asked next line until someone found the answer. This demo clearly explained how binary search tree works and demonstrates how efficient it is.

Another important concept I learned in this course is recursion. If we want to solve a problem, we can divide it into smaller problems and combine them together to solve a bigger problem. The easy-to-code nature of python provide a easy to understand and easy to design structure of recursion. Since we can use a list to contains the result of previous recursions, we can simply use + to combine these results. For example, we search a binary tree, we can put all the number by calling left subtree into a list, and put all the number by calling right subtree into another list. Now we have all the values in the tree in a single list and we can find the value of the tree easily. 

revisit topic about why geeks should write

Why geeks should write is a topic that raised very early this semester. I remember in my previous blog, I recall the experience I have for programming and try to combine that with writing blog. I briefly mentioned that writing a blog is important and convenient for us to record bugs we made. After several weeks' study, I have something new to say about it.

In terms of the language geeks (properly us) use, these languages are mostly machine based language. It might be easy to read for experienced programmer, but for most of the people, machine language is not friendly and easy to understand. Geeks need a platform to communicate. The content of the platform should not just limit to codes.  We want to share information that can be understood by most of the people, because the idea behind a problem is much more important than the language itself. For example, some computer science professor who is studying computing theory might not familiar with practical language but their programming design ability should not be ignored. If geeks can write normal language and share their idea in a blog, that means it open a door to communicate with a whole bunch of people such as theory professor who might not familiar with codes.

Impression about week 7

This week, we finish assignment 2 which is a interesting game computation design. Actually, I did bad at Assignment 1 because I did not realize that this game design is a objected-oriented design. What I mean for the objected-oriented is basically the design frame of this assignment should be applied to any other similar games. For example, we have a general game state function which contains general game states and function such as whose turn it is, which move this player chose. What we write for this general function should not design for a particular game state, meaning, we should not use any parameter and function from a particular game class. The reason we do this is to build a frame of all the game so that every time we build a new game, we just follow this frame and design a subclass under this total class. This is quite useful and time saving in a real life design project.

Fortunately,  I don't need to use my messy Assignment 1 to do the Assignment 2. In this assignment, we have a different object which is to build a new strategy - minimax. General idea of this strategy is simply, whatever is good for the opponent is a bad thing for me. It is kind of like game theorem that every move before choosing the move, we have to compare each legal move so that we can get a move that benefits us mostly. To do this, algorithm minimax is a recursive function that kind of computes each move alternatively starting from current player, and return the best move. With this algorithm, we can get a move that relatively good.

LinkedList impression

This week we learned LinkedList. Actually, I was wondering why we need this kind of data structure. Its drawback is obviously, that if you want to find the value of a item, you have to search the whole list and the worst case is the value exits at the back of the list. Also, if you want to use a item, you also need to travel the whole list. But after the lecture, I know that it also has some good implementations. For example, if you want to cut a list at a specific point, and concatenate it with another list, LinkedList data type can do this task easily. Consider a normal array, if we want to do the task above, we need to copy the first part into a new array and copy the second part into another array and then add them together, which is a little bit tedious.

With LinkedList, if we want to do this, we simply use one while loop to find the point we want to cut and link it to the beginning of the other list and it becomes a new LinkedList, easy and fast. Another application of LinkedList i think, is to optimize the use of memory and avoid data overwrite. We know what LinkedList stores is just a pointer that stores address information of the data, which means we can manipulate these data without changing its real memory address. The good thing about that is we dont need to reserve a memory spot for all these data since they can locate at any address with the link of address pointer. With that, we can kind of maximize the usage of the memory and achieve dynamic memory allocation.  

A little taste about quick sort

This week, Professor used a algorithm called quick sort to demonstrate the usage of recursion. The idea of quick sort is basically a divide and conquer algorithm. Basically, it requires us to find a pivot point in an array. And then, we loop for the whole array and compare its value to this pivot point. If it is less or equal to the pivot value, we put it to the left of the pivot point, else we put it to its right side. Note that we maintain the original order when we compare each value because we loop from left to the right. So after this first step we can say the part in the left of the pivot is surely less or equal to the pivot and the right part is greater than the pivot.

Now, we have divide the whole array into three parts, left part of the pivot, pivot and the right part of the pivot. We know that at this level, this three part is already sorted. I mean the values in each area is sorted in a macro level. But within each part, the values might not be sorted. For this reason, we notice that the left part and the right part can be treated as a new array and we can use the same method to keep dividing it into smaller parts until we reach the bottom of the array. That is where we can apply recursion.

# simple quick sort


def quick_sort(L):
    ''' (list) -> list

    Return a list containing the same elements as L in ascending order.

    >>> quick_sort([])
    []
    >>> quick_sort([5])
    [5]
    >>> import random
    >>> L = [1, 2, 3, 4, 5, 6, 7]
    >>> random.shuffle(L)
    >>> quick_sort(L)
    [1, 2, 3, 4, 5, 6, 7]
    '''
    if len(L) < 2: # there's nothing to sort
        return L
    else:
        return (quick_sort([x for x in L if x < L[0]]) + 
                [L[0]] + 
                quick_sort([x for x in L[1:] if x >= L[0]]))

here is the code from professor's lecture note. Note the recursion part 
return (quick_sort([x for x in L if x < L[0]]) + 
                [L[0]] + 
                quick_sort([x for x in L[1:] if x >= L[0]]))

we keep calling function quick_sort recursively to get the sorted list. But here, 

we always choose the first element of the array as the pivot point. If we encounter

a sorted list which means the first element is the smallest one, then we have a 

very unbalanced pivot list and this algorithm will be very slow.  

Topic to be graded : recursion

This week, we learned recursion. Basically, recursion is a technique that using the function itself as a helping function and call itself. With this method, we can dive into many sub problem and solve each of them by the similar technique and finally solve the bigger problem.

Recursion is like doing a puzzle. Whenever you get into a cross road, you choose one first, and when you touch the bottom, the program start to backtracking and try the other possibility. So we can traverse all the possibility with recursion because we tried all the path from top to bottom. To be more precise, let's say we want to find the sum of a list, for example [1,[1,2],3,4]. Using the normal method sum function will give us a error because the element [1,2] is also a list in the whole list. To solve this problem, we can use recursion.

def Sum( L):

        if isinstance(L,list) :
                 return sum([Sum(x) for x in L])
        else:
                 return L

This function is easy to understand, whenever we meet a list, we call Sum again to put all the sub element in to a list, and finally return all the sum and get the answer. However, I met a problem that require us to find the longest length of a list. For example, [1,[1,2,3]] will return 3, because the sub list [1,2,3] has length 3 which is the longest. If we use the same method as before

def  length(L):

        if isinstance(L, list):
               return max([length(x) for x in L])
       else :
               return 0

we will have two problems. Firstly, we did not add the length of the most outside list in the comparing list. Secondly, what we put into the comparing list is all the sub element instead of the length of the list. So we change it to

def length (L):
    if isinstance(L, list):
         l = []
         for x in L:
             if isinstance (x,list):
                 l.append(len(x))
         l.append(len(L))
         maxLength = max(l)
         print(l)
         for x in L:
            maxLength = max (maxLength,length(x))
         return maxLength
    else:
      return 0

will solve the problem because it get maxLength in a level and compare it with sub list leave *maxLength.

some thinking about the learning of python as a c/c++ programmer

Wow, to be honest, I did not take CSC108, so I have no python experience before CSC148. But I have used c/c++ for two years, basically, use it for computer programming contest. I used to do a lot of programming contest problems. Usually, most of my time is spent on debugging.

When I use c/c++, it is much easier to read the program and see the logic inside every loop and condition. But when I go into python, things start to mess up. I am not comfortable about not declaring variables before using it. Sometimes, when I am reading a python program, I get lost and confusing about the meaning of the variables. Compare to c/c++, python is a much easier language because it is more similar to human language and many complicated concepts like points, arrays are replaced with higher level functions. However, it is hard to balance convenience and making thing clear.

For example, since python does not require define variable before its usage, to make program readable, it requires python programmer to write doctest to clarify input variable type and output variable type. And when a python code is translated into machine language, it usually cost more time and memory to " understand " the code since everything in python is kind of auto type.

For these reasons, it tells me that it is very important to write a clear doctest  and follow professional python coding style to make a good python program. Also, keep writing a blog to record your learning experience and debugging process is a helpful way to make out programming skill better.