Strong Induction and run-time complexity for recursive functions

        Hi, it’s nice to be back. In my previous slog, I mentioned about analyzing the run-time complexity of recursive function and the master theorem. So I will spend most of the time on it today by using merge sort as an example.

        At the very beginning, I would like to introduce a digression here – The effectiveness of strong induction in writing recursive function. The idea of strong induction is by having a functional base case and assuming the function works for all the smaller cases, the function will eventually solve a bigger problem. Like the inorder traversal we did in Lab9, I simply put

So I have a functional base case -  if a binary tree does not have left and right sub-tree, simply return the linked list with the root of the tree. Then there are three difference cases – A tree without left sub-tree, a tree without right sub-tree, and a complete tree. For the first two different cases, by strong induction, I assume my function works for smaller cases so I just changed where I prepend the root of the tree and simply call the function on sub-trees. Then for the last case, also by strong induction, I called the function on right sub-tree, prepend the root, then prepend the linked-list generated by calling ‘inorder’ on the left sub-tree. And then I’m done. By assuming the function works for smaller cases, I eventually solved a larger case. Note you need to change the prepend method a bit for prepending linked-lists. So through strong induction, all I need to do is to find out the base case and use smaller cases to construct a larger case and it will provide much ease when writing recursive function.

    It’s a huge digression actually ha-ha! Now I’m back on track. I’ll take the merge sort we did in class as an example.

Notice this is not the complete version since I don’t include merge function here due to space limit. So for merge sort, by strong induction, this should work as it has a valid base case and uses smaller cases to construct a larger case. But its run-time complexity is not easy to find out. Since the run-time complexity depends only on worst cases, I’ll ignore the condition when length of L is smaller than 2 but analyze the else part. The very first thing we need to do is to assume the total steps merge sort takes are M(n) steps for a list of length n. Then by our assumption, both merge_sort(L[:len(L)//2]) and merge_sort(L[len(L)//2:]) will take approximately M(n/2) steps by ignoring the constants because of the nature of big-Oh. For merge, since it’s a procedural function, we can easily analyze its total steps for merging two lists of n/2 length is c*n where c is a constant. So

M(n) = M(n/2) + M(n/2) + cn = 2M(n/2) + cn = 2(2M(n/4)+cn/2) + cn/4 = …. So by telescoping this equation , 

we can see M(n)/n  = logn eventually, so M(n) ∈ o(nlogn). For more information on proving this, I suggest you check this powerpoint ( http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/04MergeQuick.pdf ). So the idea is to firstly find the recurrence for run-time complexity and then telescoping it. Eventually the recurrence could be solve and the big-Oh notation will come through.

    That’s it and good luck on term test2.

Introduction to Runtime Complexity

   Hey, sorry that this slog is a bit late since I was quite sick last week but now since I’ve come back, I can write down some of my own reflective on run-time complexity.

               First of all, what is the run-time complexity for a program? Basically it’s the total steps a program would take given the size of input n, and we formally use O(f(n)) to describe the asymptotic behavior of the program and here O(f(n)) is defined as ‘There exists a natural number c, and there exists a natural number b, such that for all n bigger than b, the total steps of the program would be less than or equal to c*f(n)’. Quite obscure and doesn’t seem to make sense at the first glance so here I am going to introduce my own interpretation: For a run-time complexity of a program to be in O(f(n)), the growth rate of the total steps of the program with respect to the size of input is less than or equal to f(n). So if the total steps a program takes is n^2 given the size of input n, then we will say the run-time complexity of the program belongs to O(n^2).

               Next, why should we even care about the run-time complexity of a program? Some may claim that as long as the program works, it is a good program. This makes sense when the input is relatively small but suppose here we are given the size 1 million, and one program has a run-time complexity of log(n) while the other has n^2. Log of one million is about 20 while the square of one million is one times ten to the 12^th and this is a huge difference since computers nowadays, though fast, still have limits and it’s obvious 20 steps takes much less time. So correctness differentiate bad and good programs while efficiency differentiate good and better programs.

               As I have told about the interpretation of run-time complexity and the reason why we should care about run-time complexity. I would like to go a bit further by telling you how to analyze the run-time complexity of a program. There’s a small trick I found: The depth of a for loop depends on the input size usually determines the power of n in O(n^x). Take the following program as an example.

This program has a nested for loop so its depth is 2 and since both for loop depends on the size of input x. Thus the inner loop runs x times and the outer loop runs the inner loop x times and the run-time complexity of this program is, obviously O(n^2). Also, always remember that constants normally would be ignored when calculating the run-time complexity because of the definition of O(f(n)).

              Though my trick works for many programs, it has a limitation that such trick could only be applied in procedural programs while for recursion, more work needs to be done. I was stuck on how to calculate the run-time complexity for recursive programs until this week in CSC240’s lecture. I was told the master theorem (check http://en.wikipedia.org/wiki/Master_theorem for more info.) and then I have the weapon to tackle the run-time complexity of recursive programs. I’m still on the way of learning and I’ll come back later this week to write more on analyzing recursive programs.

What is linked list and when to use linked list

        During the last two week, we spent most of the time dealing with linked lists and I am always wondering why I should use linked lists. Now that I finally have a week without midterms, I can write down some thoughts.

First of all, what is a linked list? In my own viewpoint, linked list contains elements with two inner attributes and the first attribute points to an object while the second attribute referenced the element behind it. This might be a bit abstract but if you look the following graph, I am sure you can easily grasp the idea of a linked list.

        Like what I just said before, the first attribute points to a value while the second attribute serves as a pointer pointing to the next element so if you want to get the second element of the linked list, you need to follow the references from the first element to reach the second element and same for the third element, and the fourth element, etc. This idea of extracting the element from the previous element is the idea of recursion where the solution to one task depends on the solution to the previous task and the code is as follows. (Check http://siyangcsc148w3.blogspot.ca/2014/02/what-is-recursion.html for more on recursion if interested)

        However, when I was doing the lab on week 6, I found there is a serious problem associated with this way of getting elements. As I stated before, most languages have a maximum recursion limit to prevent the program from getting stuck in infinite loops, so suppose we have a linked list of 10,000 elements and we want to know the 5,000-th element, then due to the recursion limit, we cannot get the 5000-th element since it requires 4999 recursion which is far beyond the maximum stack limit which inevitably resulted in an error. So the only way to access an element is through step by step, find the previous element, then to the next element and this might seem quite inefficient compared with lists where we can just use the index of an element to reach that element. Thus someone may say, there is no need to have linked list and list is enough. I will, under most cases, agree with that statement but there are some cases where linked list is much more efficient since linked list allows for constant-time(O(1)) insertion and deletion of an element since during insertion of one element, all we did is to get to that position and change the pointer of the previous element to the element we want to insert and set the pointer of the newly added element to the original element in that position while not affecting other element. However, if we want to insert an element to the middle of a list, we had to move every element after it to the right to leave space for inserting the element we wanted.  As the length of lists increased, the time it takes to move all elements to the right gets longer and longer which is, obviously, quite inefficient. So for random elements, yes, we should use list since it allows for random indexing but if for sorted elements where we know exactly which place to insert an element, we definitely should use linked list. This idea is applied in binary-tree search in which a tree is built with nodes placed in order, and we could easily insert a node, changing the pointers or access that element from the root under the order we designed without concerning too much about the length of the linked list.

To sum up, when we want to place different object without any order, a list is a better approach to store these objects since list allows for random indexing, but if we want to place objects in an order, then linked list is a better approach since it allows for constant-time insertion and deletion.

What is Recursion

It’s the seventh week of CSC148 and I took the midterm for CSC148 as well as CSC240 and I don't have much time to sit down and think about what is recursion, but since I’ve survived the week, I finally had some time to write down my thoughts on recursion.

Recursion, in my own viewpoint, is to divide a problem into several smaller problems which are easier to solve and the solutions of these smaller problems, when combined together, formed the complete solution to the original problem. Here I take a quite simple example: the Fibonacci sequence (see http://siyangcsc148w3.blogspot.ca/2014/01/some-thoughts-on-recursion.html for detail). Suppose we want to know the nth element in the sequence, then we need to know the (n-1)th and (n-2)th element in the sequence since all elements in the Fibonacci sequence is the sum of two elements that are immediately precede it and to know the two elements, same process will be applied until we reach the first two elements which are defined to both be 1. So the process is actually breaking bigger problems down to smaller problems until a solution is reached and then the solution is passed back and combined to form the complete solution. Here the solution to the smallest problem is called the base case and the process of reaching complete solution is called recursive steps or constructor cases.

But then comes the question: why should we use recursion? I’ll say that the use of recursion could significantly reduce the length and complexity of the program when used properly. (Check my previous post http://siyangcsc148w3.blogspot.ca/2014/01/some-thoughts-on-recursion.html for detail). Like the function we use in assignment1 for moving cheeses among four stools. A recursively defined process only requires 3 lines to reach the goal while it would be quite lengthy to write a procedural function since there are so many cases that one could easily miss something and even one does consider all cases, the code could be quite lengthy and became harder to understand than the 3-line recursive function. However when can we say is a good time for recursion? Certainly, many recursion could be written in for loops like the problem 1 in the extra section of lab 4 – write a recursion function that reverses string s and it could be easily written in for loops as we learned in CSC108, and it only requires 3 lines. So reverse a string might not be a good time for us to use recursion since recursion neither reduces the length of the code nor makes it easier to understand. Nevertheless, there is someplace that recursion could play an important role – when a program requires consideration of many different cases in for loops, recursion could be quite useful as the assignment1 I mentioned earlier. So, when thinking about using recursion, first consider the for-loop version of the program, and if the for-loop version doesn’t require considering too many cases and is not hard to understand, then use for loops instead of recursion. Also, if we want different solutions from the same problem, then recursion is, I’ll say, useless since recursion is based on the assumption that smaller problem only has one unique solution which can be used to construct the solution for bigger problems. One more thing, recursion couldn’t be used on particularly large problems since most programming languages limit the recursion depth to a certain level to avoid crashing of the whole system so when encountering particularly large problems, either use specially designed recursion or find another way without recursion.

In the end, I want to discuss a bit about debugging recursion. Basically a recursion needs a base case and recursive steps that lead to the base case or at least, smaller cases. You can find more on my previous slog http://siyangcsc148w3.blogspot.ca/2014/02/at-end-of-this-slog-httptracycsc148.html.

Debugging recursion in a systematic way

At the end of this slog http://tracycsc148.blogspot.ca/2014/02/csc148-slog-object-oriented-programming.html, the author mentioned “a recursive function will not stop running until the condition in the 'else' part is met” which sounds easy to understand but actually hard to recognize such an error when actually coding. So here I am about to talk about how I debug for recursive functions.

               First of all, the most obvious one – syntax error. It’s obvious doesn’t mean it’s always easy to recognize. Like the preorder function for Trees,

(This is not quite right. Please refer to CSC148 website for the correct version)

When brackets and parenthesis get mixed up, it became much harder to detect where we missed a right parenthesis or a bracket at a glimpse and it’s very likely that we need spend quite a while reading line by line if coding larger projects. Such thing is inevitable but we can always try to avoid it by splitting them into different blocks – instead of writing ternary if, writing in different blocks as we did in CSC108 makes such ‘silly’ error more apparent and may save much time.

               Then comes to the run-time error where under most circumstances problems occur. Most people trying to write recursive function must have experienced error message like ‘Maximum recursion depth exceeded’ which indicated the program falls into an infinite loop. To fix such an error, the very first thing, to me, is to test the base case – an infinite loop always mean the program can’t get to the base case or the base case is in an infinite loop. So it is essential to trace the base case and make sure it’s functioning. For instance of the Fibonacci sequence I wrote in my previous slog (http://siyangcsc148w3.blogspot.ca/2014/01/some-thoughts-on-recursion.html), a functioning base case is essential for keeping the program getting into infinite loop. After the base case, check the constructor cases. Starting from small cases, like the third element in Fibonacci sequence and print out things returned by every recursive step. Still, I will take my fib function as an example.

What I did is to print tuples made up of the fib result and its associated number.

Suppose I type fib(4), it will print (1,2) and (1,1) ,(2,3)and return 2. So I will know fib(2) , fib(1) and fib(3) are all working and if it’s not working, I could quickly find out at which point the recursion failed and fix it.

I used this method in Assignment 1 where Tour module worked for 8,9,10 and 11 cheeses but not for 12 cheeses. As I print out all the recursion steps, I found my initial set up for 2 cheeses is wrong where I set i=0 for 2 cheeses instead of 1. And it saves huge amount of time than tracing by hand or wondering around.

Coding style

    This slog http://slogslogslogslog.blogspot.ca/2014/01/week-4-inheritance-exceptions-and.html is quite intriguing to me. It talks mostly about the importance of writing syntactically correct programs, and I believe this plays a huge role in writing programs. Different programming languages have their own syntax so it is essential to learn the correct syntax at the very beginning and then apply the correct syntax. Otherwise, obviously, ‘Syntax Error’ will prevent any program from running and the logic behind it could never be implemented. In addition to syntax, I would like to talk more on coding style. A good coding style is something that makes codes easier to read, easier to follow, and easier to understand. Think about the following example.

    Both function return the power three of x and syntactically correct but the first function is, under most circumstances, prohibited. There are two reasons: First: the function header shows nothing about what the function will do. (Who knows what will ‘dosomething’ do). Second: Writing function body just after the function header does not show the block of the function which makes it harder to read when the function body became longer and longer. So the second function, clearly has a better coding style: clear header, apparent blocks and is taught as a standard way by almost all teachers. So like assignment1, when my group and I start working on that, the very first thing is to set up a consistent coding style, so that everyone could understand what others are writing more efficiently and can add codes without too much modification. Like the initialization of TOAHModel, we set the names of the attributes of the objects as ‘stools, cheeses, etc.’ So when other members of the group and TA wants to read it, it is obviously much more understandable than simply putting ‘a,b,c’ as attributes.

To sum up, a good coding style saves a lot of time and makes both programmer and debugger easier to understand and trace the program, so it is important to have correct syntax but more important to have a good coding style.

Some thoughts on recursion

It’s the fourth week of CSC148 and just a brief summary of what I have learnt: First week, object-oriented programming, the second week, inheritance and recursion, the third week, exception, and this week, more on recursion. Also, assignment 1 came out and it’s basically about the Hanoi tower with more than three pegs. Today, I am going to talk something about recursion. The most well-known recursive thinking, I believe, is the Fibonacci sequence – 1, 1, 2, 3, 5, 8…… Starting from the third number, each number is the sum of the two numbers before it.(5=2+3, 8 = 3+5) Every time we want a number, we need to know the two numbers before it, and to know the two numbers, we need to know the two numbers before themselves.  This may sound confusing, but it would be clearer when put into code.

The base case returns 1 when n equals 1 or 2 and if n is greater than 2, the program would firstly calculate the sum of the (n-1)th number and (n-2)th number, and to calculate the (n-1)th number, the program would calculate the sum of the (n-2) and (n-3)th number, and same for all the numbers until the program reaches base cases and return 1. Starting from 1, the program adds these numbers together and produces the nth number we want. As Danny said in class, tracing a recursive function could be too complex to handle, so my way of tracing the code is to use abstraction – Find patterns of the code for the first or two cases, then apply these patterns to more complex cases based on the assumption that the code could work properly.

As seen from the Fibonacci sequence program, through recursion, we can significantly reduce the length of the code. Through abstraction, recursion would be much easier to understand than writing in for loops or other loops. However, recursion, for most of the times, actually lowers the efficiency of the program. Thus, when using recursion, we need to find a balance between efficiency and code length – if the code could be converted into for loops while not extending much length, it is better not to use recursion. So analyze at the very beginning, and decide which way we are about to use.