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. 

CSC 148 Python Week 4 Slog: Stack and Sack

This week, we learnt two new abstract data types: stack and sack. A stack contains items of various sorts. New items are usually added on to the top of the stack, items may only be removed from the top of the stack. It’s a LIFO (last in first out) structure. However, sack is different from stack. New items are added on to a random place in the sack, so the order items are removed from the sack is completely unpredictable. 

From my perspective, I find stack a little bit hard to understand. I then use a stack of books as an example of stack in python to help better understand the concepts. Because when we have a stack of books, we add the new book to the top of the old books but remove the most recent added books first. So it is a last in first out order. Also, the order of the books in the stack is important. Here, from this graph, we can know more about the structure of stack using "push" and "pop"：

This concept is different from a queue concept which is first in first out as the people waiting the first in the queue should be removed first. This algorithm of stack can also be used in different places like matching brackets in sentences. From this class, I learnt that linking abstract concepts to real world applications is a good way to learn new concepts.