Week 11: Sorting efficiency

A sorting algorithm is an algorithm that puts elements of a list in a certain order. We've learned various sorting methods in this course and CSC108, but what's the fundamental difference between all these methods? And why does it matter?

In my opinion, it is the sorting efficiency.

But why does the sorting efficiency matter?

No matter what sorting algorithm we choose, an expected result will be generated  as long as we choose a correct one. However, a more efficient algorithm will save a lot of running time and  it is important for optimizing the use of other algorithms (such as search and merge algorithms) which require input data to be in sorted lists.

For example, we've learned Bubble sort and  selection sort in csc108. Suppose we are asked to sort [5 6 8 2 14 24 16 1] using these two methods.
Selection Sort:
[{5} 6 8 2 14 24 16 (1)] unsorted array. Find the smallest element () in array and swap with first element {} of unsorted array [].
1 [{6} 8 (2) 14 24 16 5]. Do the same process again.
1 2 [{8} 6 14 24 16 (5)].
1 2 5 [{(6)} 14 24 16 8].
1 2 5 6 [{14} 24 16 (8)].
1 2 5 6 8 [{24} 16 (14)].
1 2 5 6 8 14 [{(16)} 24].
1 2 5 6 8 14 16 [{(24)}].
1 2 5 6 8 14 16 24. Finaly got the Sorted array

Bubble Sort:
In bubble sort elements are compared with just next element if the first {} is greater than second [] then swap.
{5} [6] 8 2 14 24 16 18 [no swapping move forward]
5 {6} [8] 2 14 24 16 18 [no swapping move forward]
5 6 {8} [2] 14 24 16 18 [swapping move forward]
5 6 2 {8} [14] 24 16 18 [no swapping move forward]
5 6 2 8 {14} [24] 16 18 [no swapping move forward]
5 6 2 8 14 {24} [16] 18 [swapping move forward]
5 6 2 8 14 16 {24} [18] [swapping move forward]
5 6 2 8 14 16 18 24 [swapping move forward first phase over again starts with first index]
{5} [6] 2 8 14 16 18 24 [no swapping move forward]
5 {6} [2] 8 14 16 18 24 [swapping move forward]
5 2 {6} [8] 14 16 18 24 [no swapping move forward]
5 2 6 {8} [14] 16 18 24 [no swapping move forward, there is no further swaping in the phase start next phase]
{5} [2] 6 8 14 16 18 24 [swapping move forward]
2 5 6 8 14 16 18 24 Finaly array is arranged in ascending order.

Obviously, selection sort is more efficient. And here, the input size n is small. If we're asked to sort an array of larger size, then the difference will be huge as well.

Talking about sorting a sample of large size, we need to know the big O notation. The first time I learn big O notation was in my CSC240 class, which is a course about computation complexity.  "In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in the input size."(Wikipedia)

 

But essentially, it's a math topic, and it describes the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions.  Here, the argument of the function is the input size and the function describes the corresponding running time. 

Let's show it graphically.

When input size n is small, though the efficiency matters, it is not very important. However, when n is large it matters a lot.  Most real worlds problems we are facing have a very large input size, and that's why we need efficient algorithm. 

Week 7: Recursion

Since the beginning of this semester, recursion has become the most important concept for this course: we are talking about it at class, practicing it in lab and writing codes using it basically for everything.

But what's recursion?

By definition, "recursion is the process of repeating items in a self-similar way" (from Wikipedia). But, in my opinion, I usually just think it as another name for induction (since it works similarly with induction, and I know they are different). we construct the base case (or cases), and then define certain rule on how to construct other cases based on the base case. In my opinion, so far in this course, mostly, we use recursion for two purposes: construct a data type (such as tree) and define a method/ collect data on a recursively-defined class/ data type.

Personally, I wouldn't say recursion is hard. In my opinion, it sometimes becomes a problem is because that it is a comparatively new concept and we are still learning it. But, in fact, it is not a new concept. However, we did not learn it from CSC108. We were exposed to this concept in different mathematics classes (calculus, math concept) and CS courses which focus on computation complexity. In my opinion, induction, structural proof and recursion are essentially same. All we need to consider is that find out what's the base case (or cases) and rules to construct cases. And to solve these two questions, there are a few methods.

The first one is drawing a processing diagram. The only path that lead to the output is the simplest case. If it's not, we call recursion on it to simplify it until it reaches the base case. The diagram is very useful tool when you start working on recursion (in my opinion), since it's straightforward and simple. But, it takes time to finish the picture. The second way is better than the first one, since it's more abstract and it saves time. It's to write down the mathematical function, which is the essence of the code (sometimes the math function is same with the code). We've met an example, which appeared on the handout of A1 (for Hanoi tower).

As I mentioned above, recursion is used everywhere in this course, for example, A2. In my opinion, tree is a perfect example to demonstrate recursion, because we construct tree by recursion (base case: root node) and almost every tree method needs recursion (since tree is recursively constructed). More specifically speaking, the basic element of a tree is a node, and everything is based on the node. For example, if we are asked to define a tree method, first we need to ensure it works for the root node.

These are what I think about recursion.

Week 6: Tree

So this week we learned what's tree, how to construct a tree recursively and how to use tree to store data.

Generally speaking, tree is an abstract data type that simulates a hierarchical tree structure, with a root value and sub-trees of children, represented as a set of linked nodes. Also, a tree can be defined recursively as a collection of nodes (starting at a root node), where each node has a value, together with a list of "children" nodes. Tree is very useful and convenient, since a tree can be analyzed mathematically both by nodes and as a whole.

Recursion is what we use to construct a tree. Since every tree is constructed by nodes (or sub-trees), we can set the root node as the base case of the tree. Thus we define what a node is in the __init__ function. And when we build a tree, we can keep add new nodes as children to the root node. Since the tee is constructed by recursion, when we need to get all data from the tree, we need to use recursion to get the data, and thus we have pre-order, in-order and post-order (we get data node by node). Similarly, when we define tree methods, recursion is used (since every method is supposed to work on a tree which's built recursively).

In my opinion, tree its self is not a challenging concept, but the recursion under it is. It's not easy to point out what's the base case and how to build recursion step when I first met the concept. However, I found it very helpful to use structural proof (what I learned from CSC240) when I work on recursion problems. Root node is the base case, and the children are constructed by induction ( recursion) steps. And tree methods are supposed to work on the whole tree (both root and children). This is super similar with the structural proof ( Prove a proposition works both for the base case and the induction), but the difference is that this time we are not asked to prove certain arguments, instead, we are asked to find a method which works for the entire. However, the idea is same.

  

Assignment 1

First, I'd like to say thanks to the 33 viewers of my past two posts! I mean you guys are now my motivation to update this "SLOG"!

So if I was asked to summarize my week 5 of CSC148, I would like to say Assignment 1.
I started working on A1 on Monday Feb 3rd  and completed my job on Wednesday Feb 5th after kept working 3 nights at  a CS lab (I have to finish A1 before Friday because I need to save time for my 2 midterms in this coming week.)

I am co-working with two of my friends, and my job is writing all the codes while they are human debuggers and doc-string writers. To be honest, it's not easy to write all the codes and minimize the number of possible bugs, and it feels so bad to work in the lab alone at night. But, anyway, we've done and our programs work well!

In my opinion, A1 is a very good test on everything we have learned by the end of week 5. I used everything I learned from class in A1, including "different scopes", which was taught on Wed Feb 5th. As I said in former posts, I enjoy this course and coding. So it feels so good to code with the fresh techniques I learned. Recursion is a super important technique I used in A1, and I also got a better understanding of it by using it frequently.

Talking about recursion, I am also learning it in another course I am taking: CSC240. But in that course, we learn it in a more mathematical way. However, the stuff I learned from CSC240 helps me a lot in 148, and also the other way around. And this really inspired me on planning my next year's schedule. I mean right now I really understand how important math is to CS, and I have decided to take more math courses concerning about mathematical logics in the future, probably MAT309.

Plus, as I said in the post last week, I did pair up with someone in my last week's lab, and he was my first lab partner for CSC148! And working with a partner feels totally different from working alone. It's fun! Although I would not say that we are friends now (I am too shy to talk more other than lab work), we did have nice conversation and the lab went well. And my goal this week is to make new friends at class, since I realized that to some extent, computer science is always "group work", and it's super important to learn how to cooperate with your colleagues. Also, more importantly, it's so boring to work at the CS lab alone!

Well, at the end of week 5 of winter 2014, I would say so far so good.

Csc148 Week4: What? We've done 1/3 of the course?

I was surprised when I noticed that 4 weeks have already passed and we have done 1/3 of the semester! (If there are 12 weeks for this semester as I remember.)

For me, the past 4th week is the most difficult one compared with the other 3. We started learning recursion, which is not easy. It is something totally new to me, not like stuff we did in the first 3 weeks to which I was exposed in CSC108. To be honest, I was totally lost at class and I could not follow at all. I found it very hard for me to understand the purpose of the codes quickly and point out where should I use recursion. But, after reading the slides and the recommended online text, I found a little trick to help me get a better understanding about recursion, that is drawing the process flow diagram. So what I did was drawing the diagram corresponding to the instruction and then turning the picture into codes. Though it takes extra time, it helps me figure out where to put the recursion sentence and understand the whole operation process. And thanks to this little trick, I would say that so far recursion is not a problem for me any more.

Although it's a bit depressing that I hardly followed the lectures, there were some little delightful things. I did the lab by myself this week (I switched the lab section and most of my lab mates have already been paired up), and surprisingly, it went pretty well and I finished everything! The most beautiful point I find about programming is the time that all codes run properly and no bugs show up! Working alone is harder than having a good coding buddy, but it could bring more satisfaction if everything goes well. However, I do wish to have a coding partner for the coming lab. I am confident in my coding ability, but it's always better to make new friends! 

So, at the very end of week4 (Okay right now is Sunday night), here is the question: what did I learn and what have I gained in the past 4 weeks (or the first 1/3 of the semester)?
Answer:
Useful programming techniques (Object-oriented programming, recursion, class and subclass and how to choose appropriate test cases), problem solving skills and most importantly, a better understanding towards computer science and desire to learn more about it!

Object Oriented Programming?!

Hello, world! 

It's been two weeks since the first CSC148 lecture, and so far I really enjoy this course.

In fact, I was pretty worried before the course started, because I took CSC108 last winter and I didn't really use Python after last April. However, I stopped worrying after the first week, especially after taking the "ramp-up". Luckily, I still obtain the ability to use Python, though there're things which I've forgotten or I haven't seen before, like "Wing".

The main topic for first two weeks' lectures is "Object-oriented Programming". I have to say, this topic is very interesting and I really like it. For me, a game  player, object-oriented programming is like a great new game, and it feels awesome when my code works and actually solves some real problems. But, on the other hand, I did meet some problems when I was doing the first lab questions. Since it's objected-oriented programming, it requires us to manage everything. It's hard to give the overall structure or the big picture of the code, and decision-making did take us (my lab partner and I) a lot of time. However, it feels so great when we finally solved the problems. Also the lab is a good preparation for exercise 1. I did the exercise 1 after the lab, and since I got enough preparation from lab 1, it didn't take a long time to finish exercise 1.

I am also doing mathematics and statistics, I found that object-oriented programing very useful for my other courses. It's a very useful tool in solving mathematics questions, because as long as you know the way to solve the question, you can translate it into codes and then the computer will help you get the answer, which means that you can leave the tedious calculation to the computer and save a lot of time. Also, it helped me learn that how to interpret and solve real world questions. Although I have not tried to apply what I've learned in 148 to my study in statistics and mathematics, I can tell that it would be a very helpful tool in data processing and real world question solving. 

So far I really like this course and enjoy learning, and everything is good.