Sorting and efficiency

We learned about sorting algorithms in CSC148 and the topic on their efficiency is worth talking about.

There are many sorting algorithms and they can be classified by different standards. Specifically, there two types of sorting algorithms, one is a comparison sort, which means it examines the data only by comparing two elements with a comparison operator, another is called non-comparison sort. Comparison sort includes quick sort, merge sort, bubble sort, insertion sort and selection sort. Today I will just talk about comparison sort.

I remember the first sorting algorithm I learned might be bubble sort. Bubble sort works by scanning through the list repeatedly, and then compare adjacent items and swapping them if they are in the wrong order. When no swaps are needed, the list is sorted. Its average performance is O(n^2). In the lab, we showed that bubble sort is the slowest among all the sorting algorithms we are testing, which means it is not a practical sorting algorithm for large data.

Selection sort is easy to understand. This algorithm divides the input list into two parts: the sorted part and unsorted part. In the beginning, the sorted part is empty and the unsorted part is the entire input list. Then the algorithm finds the smallest (or largest) element in the unsorted part, swap it with the leftmost unsorted element and puts it in sorted order. The time complexity of selection sort is O(n^2) , for we have to compare the item we got with all other items.

Now let’s take a look at two fast sorting algorithms: quick sort and merge sort. Their average running time are all O(nlogn). Quick sort is a divide and conquer algorithm and it is recursive. It divides the list into two smaller sub-lists and then it recursively sort the sub-lists. The base case of the recursion is lists of size zero or one, which never need to be sorted.

Week 7

Week 7

One of the most important topics in csc148 is about recursion. But sometimes recursion is very hard to track. But I think I have some good ways to understand and to track the recursion process.

One way is to trace the function calls and I learned this in Lab04, where we are asked to trace some functions, greatest common denominator and binary representation. The process helped me lot understand recursive functions. I think it is easy for people to have an ambiguous idea about recursion without tracing it. If you traced it, you will see it’s just a repetitive process of calling the same function until it satisfies some condition and then stops.

My advice about learning and understanding the recursion is to work step by step. The recursion is not so hard if you have a clear thought about what the functions does and what the base case is.

Week 6

Week 6

This week’s lab was pretty easy. I finished all the tasks in 40 minutes! The first task of the lab was writing four functions, which can be easily done using for loops. And the second task is to writing test cases in unittest.

And the binary tree is actually what we did in last week’s lab!

Week 5

Week 5

In this week’s lab, we traced some recursive functions. I think this tracing process helps me understand how the recursive function actually works.

About the tower of Hanoi recursion:

In a 3-stool Hanoi model, the basic recursion process is:

    def threemove(n, source, temp, destination):

        if n == 1:

            model.move(source, destination)

        elif n > 1:

            threemove(n - 1, source, destination, temp)

            threemove(1, source, temp, destination)

            threemove(n - 1, temp, source, destination)

This is not too hard to understand. I traced this code in a 2-cheese and 3-cheese case and it’s all clear. And in a1, we have a 4-stool Hanoi model, the best approach to move all the cheeses from one stool to another stool also uses recursion. To move 10 cheeses, our code takes 49 steps; 15 cheeses, 129 steps. It’s considerably less than , so I think we got that right!

Week 4

Week 4

In this week’s lab, we designed classes motorized and human powered. The main task of this lab is to practice implementing classes, using inheritance and writing test cases. The tasks are pretty easy but the idea is very important. In my opinion, inheritance is the practice of passing on the feature to a child upon a parent. By using inheritance, we can write a new class quickly and it has its parent class’s methods. And it must be noted that choosing test cases is a difficult job, because you have to design some special cases, like an empty collection, a collection with 1 item, smallest interesting case and collection with several items.

For the recursive functions of nested list, I had some a little bit difficulty writing this piece of code:

def rec_max(L):

    return max( # the maximum of

       

        # list of maximums of sublists or plain numbers in L

        [rec_max(x) if isinstance(x, list) else x for x in L])

I can only write a version that is not so succinct:

def rec_max(L):

    result=[]

    for x in L:

        if isinstance(x, list):

            result.append(rec_max(x))

        else:

            result.append(x)

    return max(result)

They basically mean the same thing.

About the permutation function:

The basic idea is to let every element in the string be the first letter and perm(other letters). Fox example: perm(“abc”) = [“a”+perm(“b”+”c”)]+ [“b”+perm(“a”+”c”)]+ [“c”+perm(“a”+”b”)]

Notice that the base case is perm(“a”)=”a”

My OOP Study Log (week1,2,&3)

When this course started, I noticed that this course is called “Introduction to Computer Science”, while CSC108 is called “Introduction to Computer Programming”. Looks similar but a whole lot different. In CSC108, we mainly spent our time learning a programming language. However, in this course, I think we are learning about program design concepts, like object-oriented programming.

In OOP, the focus is on the creation of objects, which contain both data and functionality together. In the first class, we learned how to create a user-defined class: the Point. Although we could just use tuple to store the coordinate of a point but I don’t think that’s a good way, because a point has many properties that a tuple doesn’t have, so why don’t we just create our own class? I find the design process to be easy because we already learned about designing class in CSC108. Nevertheless, it must be noted that I had some problems. Firstly, style. I used to write the type contract below the def line not in the parentheses. Secondly, when designing the __eq__ method, I didn’t know we need to write (isinstance(other, Point) in order to compare whether the two objects that we are going to compare are both Point objects. I then realized that this is necessary and very important. The reason is that Point objects are list-like objects, so if we compare [3,4] with Point([3.0,4.0]) without checking if they are all Point objects, the result will be True. Moreover, I

In Lab01, we designed a class to count the times of appearances of each word in a document. The problem my partner and I had was that how to sort a dictionary by its value when designing top_n method. We tried sorted() and a couple of other methods but it doesn’t work. Then with the help of TA and some python guides, I found that we missed the lambda function, just write sorted(d.items(), key=lambda d:d[1], reverse=True), we can easily sort the dict by its values(d:d[1]) or its keys(d:d[0]) reversely. Here is my top_n:

>>> b=[]

>>> for i in range(n):

            b.append(sorted(a.items(), key=lambda d:d[1], reverse=True)[i])

    return b

It works perfectly.

I feel a little frustrated because it cost me more time than I had thought. I think I need more practice.

     In the second lecture, we designed the stack class, which I found to be easy. But the recursion function confused me, I didn’t understand that we can call a function within its definition. Then I found this answer on Piazza which helped me a lot:

“Well first of all, it doesn't matter that you call a function within its function definition. My understanding of it is that at the beginning of runtime, the code finds all the def statements and makes the function names point to "run the code from line x to line y". So you're not technically calling it in the function definition, because it was already defined and can be called whenever you want now.”

Now I understand how to write a recursion function:

def sum_list(L)

      result = []

      for x in L:

             if isinstance(x,list):

                    result.append(sum_list(x))

             else:

                    result.append(x)

      return result(array)

But I still have some problem writing code like this:

def sum_list(x):

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

This piece of code is very succinct and works just perfectly but it looks kind of ambiguous to me. I may have to write this code several times before I get it right. I think some more practice will help.

In lab02, our task is to using class Stack and Queue. The tasks are pretty simple. And the part about the efficiency is really interesting. The two classes Stack and Queue are similar but their running time are so different. The problem is that in Queue, you pop the first element while in Stack, you pop the last one. To fix this problem, you must not remove the element because it costs too much time.

In week3, we will learn about inheritance, which is an important concept in object oriented programming. I guess we will learn about polymorphisms in this courses also.

In my spare time, I am learning Objective-C. Python and OC are all object-oriented programming language. In my opinion, I think Python’s programming language is more straightforward, easy to read and write. Programming in python is just like writing in English.

For example:

In OC, it takes 20 lines to finish a piece of code. While in Python, we just need to write 10 lines. But fortunately, Xcode is very powerful and it’s free!