CSC 148 Python Week 11 Slog: Revisit of the application of Recursion

This week, I am going to revisit my Week 7 slog talking about Recursion and its efficiency. I think I understand more about recursion especially after learning about Binary Tree Traversal and Efficiency. Also, I know more about the advantages and disadvantages of using recursion.

Recursion means "defining something in terms of itself”. The graph below I think can best describe the concept of recursion as it seems that it is always in a circle algorithm. Last time, I did not realize the broad applications and extensions of recursion. I only focused on its relationship with iterative loop as some of the problems will be solved more efficiently using recursion. After a few weeks, I find out its application in Tree traversal as there are many of the methods inside the tree algorithm require the use of recursion like "Insertion", "Binary Searching" and "Deletion". Also, in our assignment, we also use recursion when using "Depth First Search" and "Bread First Search". I believe recursion can be used in more fields and we will discover that in our future study.

However, in terms of "efficiency", we always find that recursion is not always efficient comparing with "iterative" methods. For example, in terms of writing "Fibonacci" algorithm, while using iterative method, it will only take O(n) time. However, if we use recursive method, we can see that it will take O(2 to the power of n) times. Also, recursive method takes larger memory than iterative method.

In summary, we can get the following conclusion. Sometimes a recursive method has more to do following a recursive call. It gets done only after the recursive call (and all calls it makes) finishes. In addition, recursion is often simple and elegant, but could be less efficient when we apply it to the wrong problem as it may also takes a lot longer time than iterative method. Thus, we need to consider whether using iterative method or using recursion when solving a problem!

CSC 148 Python Week 10 Slog: Efficiency of Algorithms

Today in class, we learnt more about Efficiency of Algorithms. Because we can solve Binary Search Tree insertion in both iterative and recursive way, the professor today want to show us which is a more efficient way. Basically, we will consider two factors in analyzing the efficiency here. The first one is how large is the extra memory of these two algorithm and the time it takes to do two algorithms. We can find out that in doing iterative way, we do not need much extra memory as the for loop will always have a constant extra memory to store. However, for recursive way, we can see that if the tree is balanced, which means that the right and left side have similar amount of children, there will still be O(lgn) larger amount of extra time than iterative way. For the time they spend, we can see that for iterative way, there will be n number of time but for recursive way it will take 2 to the power of n number of time. This means that in a Binary Search Tree inserting new value algorithm, recursive algorithm is not efficient. However, recursion is a very powerful technique for problems that are naturally recursive. So different methods will work better for different problems. 

Here is a graph of the comparison between Recursive and Iteration and I find it very helpful.

CSC 148 Python Week 9 Slog: Binary Search Tree How to Delete

Last week, we have already learnt the structure of Binary Tree. A binary tree consists of a finite set of nodes that is either empty, or consists of one specially designated node called the root of the binary tree, and the elements of two disjoint binary trees called the left subtree and right subtree of the root. We know that when inserting a new node to a tree, we first need to make comparison with the root of each node. If the new node is smaller than the root, it will be placed to its left subtree. Otherwise, it will be placed to its right subtree. It will continue this comparison until the new node find an empty place to be placed. This kind of structure is easy to trace in an "Insert" algorithm. However, from my perspective, it is hard to think about how deletion work in Binary Search Tree. After the class, I find out that there are three possible cases to consider and according to the Professor， there are three ways to solve deletion problems. 

• Deleting a node with no children: simply remove the node from the tree.
• Deleting a node with one child: remove the node and replace it with its child.
• Deleting a node with two children: call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Copy the value of R to N, then recursively call delete on R until reaching one of the first two cases. If you choose in-order successor of a node, as right sub tree is not NIL (Our present case is node has 2 children), then its in-order successor is node with least value in its right sub tree, which will have at a maximum of 1 sub tree, so deleting it would fall in one of first 2 cases.

Here, we can see that using this picture, we can understand this algorithm better. 

From this example, we can see that when we are dealing with more complicated binary tree deletion like deleting node with two subtrees, we can either use the largest node in left subtree or use the smallest node in right subtree. From this lesson, I find out that using tree diagram and tracing will help us better learn this subject. Because binary tree is an ordered tree, we can use this to apply to other data set so that it will save us a lot of time to search for a certain number. Also, in class, we also learnt about the importance of a balanced tree. A balanced tree, which have similar number of right and left trees will be the best and most efficient in doing searching.

CSC 148 Python Week 8 Slog: Tree Traversals vs Linked List

Today in the class, we learnt tree traversal. In computer science tree traversal (also known as tree search) is a form of graph traversal and refers to the process of visiting each node in a tree data structure exactly once. There are many similarity and difference between Tree and Linked List. Like linked lists, trees are made up of nodes. A common kind of tree is a binary tree, in which each node contains a reference to two other nodes and we also learnt deeply in class. These references are referred to as the left and right subtrees. Like list nodes, tree nodes also contain cargo. However, compared to linked lists and other one-dimensional arrays, which have a linear order, tree structures can be traversed in many different ways. In class, we learnt inorder, preorder and postorder for depth-first searching, as well as level order for breadth first searching. Here are the graphs for these models:

Inorder 

                                                                           

Postorder

Preorder

Level Order

From these examples, we know more about how tree traversal works. In terms of how to write the code for binary tree search and tree traversal, I find that most of the parts are using recursion algorithm to solve the problems. Traversing a tree involves iterating over all nodes in some manner. Because from a given node there is more than one possible next node as it is not a linear data structure. This is often done via a stack (LIFO) or queue (FIFO). As a tree is a recursive data structure, traversal is usually defined by recursion. Thus, I find out that the knowledge are all inter-related and we need to learn all of these methods to understand each other. 

CSC 148 Python Week 7 Slog: Recursion for efficiency?

This week, we got introduced to Recursion algorithm and the professor gave us some real world examples and explained the tracing inside of the recursion functions. Recursion means “defining something in terms of itself” usually at some smaller scale, perhaps multiple times, to achieve your objective. For example, we might say “An egg is something who gives birth to a chicken and then gives birth to an egg again”. When we use this algorithm in python programming language, we can find out that in order to solve a problem, functions can call themselves to solve smaller sub-problems. This kind of algorithm is more efficient to some extent comparing to using for loop and while loop for this kind of problems as it will be more complicated to use loops. From the following graph, we can see the difference between recursion and loops.

During the class time, in order for us to better understand this term, the professor gave us some examples which I find it really useful. The professor tried to help us understand more about the recursion algorithm by using tracing the inside of the algorithm step by step. He gave us many examples and explained very patiently and I understand more after his explanation. We also do some in-class exercises about tracing recursion and this really helps us understand deeper about the inside algorithm of it. Thus, in the future study, I will try to understand more about the internal algorithm of different functions and methods and do more exercise to enhance my study.

During the class, the professor asked us whether Recursion is a method for efficiency. I am surprising find out that the professor explain why it is not a way for efficiency. He explained that because there are different methods to solve problems other than loops and recursions, different methods are suitable to solve different problems and thus we should use different methods at different times. In this way, we cannot say that Recursion is created for efficiency. 

CSC 148 Python Week 6 Slog: Reflection on Linked List

Because it is reading week this week, we did not have class and I then have time to review the concept of linked list.  Linked List is a data structure consisting of a group of nodes which together represent a sequence. Thus, each element in the Linked Lists is actually a LinkedListNode. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. One of the advantages of this structure is that it allows for efficient insertion or removal of elements from any position in the sequence. However, when I try to write methods for this structure, the TA told us that the nodes in a linked list must be read in order from the beginning as linked lists are sequential access. Thus, we need to remember this algorithm when writing its methods. Here is an example of a Linked List and we can see that the whole list is connected.

When I did the exercise of writing LinkedList method, I find that there are 5 basic methods of a LinkedList structure: append, prepend, contain, delete, get item. We can also write other methods in the future to expand its function. During the reading week, I review these concepts and find that I understand more about them and we need to review more often in the future. 

CSC 148 Python Week 5 Slog: List and Linked List, which one is better?

This week, we got introduced to Linked List and the professor gave us some real world examples about the difference between List and Linked List. Basically, Regular Python Lists have some advantages like can efficiently be accessed. But they allocate large blocks of contiguous memory, which becomes increasing difficult as memory is in use. For Linked Lists, they have the Linked List Nodes which reserve just enough memory for the object value they want to refer to, and the linked lists can efficiently grow and shrink as needed. Here, this image is a good example of Linked List. From the following graph, we can see that each linked list contains a node which indicate the next number it should refer to:

In class, in order for us to better understand this term, the professor gave us some examples which I find it really useful. First, the professor asked a list of volunteers to remember their seat location and stand as a list. Then a new volunteer add into the list, which makes the whole list of volunteers move. This is an example to show the disadvantages of list. Later, the professor asked the volunteers to ask the sitting location of the volunteer that is after them. Then after the volunteers went back to their original seats, the professor can recall the list of volunteers according to the information that the volunteer record about the person after them. Also, it will be easy to add a people in the middle of the Linked List as we just need to change two people's location. This example helps us to understand the pros and cons of list and the concept of Linked List and Linked List Node.