Impression of Week 9

The biggest challenge we have for this week is the second term test. My strategy for the test was going through all the lecture slides since the first term tests. Also, I redid all the labs and quiz again. I don't know how well have I done for the test, because after the test, I've run the code I wrote on python, and it doesn't work the way as I expected during the test; I just looking for as many partial marks as possible for that questions.

Due to the test, we didn't talk too much about new materials except for delete algorithm for BTNode. This is quite complex since it involves many cases. First, if the targeted item is a nodes with no children( leaves), or the nodes with children. The point of deleting a parental node is that once you delete it, the structure of the node has been changed. For example,

we can see, when 4 is been deleted, not only was it removed, but also did its children node become a parental node and replaced the old node's position. One thing to keep in the mind is that we always move the left side nodes up to replace the former parental nodes. Why? Due to the definition of BTNode, we always want the smaller value on the left side while greater value on the other. So when we making a new node, we have to make sure that, once the new node has been placed, its right side is larger than its own value.

Here is my thoughts of thinking how the code actaully works for the above examples(please correct me if I'm wrong):

We want to delete 4, and, node is not None, and  4 is smaller than 8, so we going to left side by applying delete function recursively on the left side. This time, the node value is equal to target value 4. At same time, neither its left nor right is None. So we going to else part.

In the part, first, we want to know its left side's biggest value, and we know it must be 2, so we replace value 4 as value 2. But we still have its left side value 2 exists and we need to delete it.

So we applying delete function recursively again to its left side and changing the target_delete value from 4 to 2.

And this time we going to third elif part. We know that value 2's right is None and left is None, so we return its left which is  None, and this None has been assgined to value 2's left.

So we delete value 4, and at same time, we move up the value 2 to its supposed position

Impression of Week 8

We have started to discuss Linked List last week.  It takes me a little while to understand the linked list. It's a little confusing because there are two different class defined for Linked List. First is Linked List class and second is LLNode class. LinkedList class has attributes front, back, size. LLNode class has attributes value, nxt. When I writing the codes, I often mixed up those two classes and their attributes. To summary the characteristics of LinkedList, LinkedList is a list contains LLNodes, and with each node containing both data and a reference to the next node in the list. What is the advantage of using Linked List ? From the lecture codes, I notice that we can very easily append, add, delete, and insert any data into the list. In another words, when we create a data structure and beginning, linked list allows us many flexibility for future data rearrangement.

As I said, the Linked List contains Nodes, and each node has a data. In the lecture we apply self.value to call the data. To get the next Nodes, we use self.nxt. However, LLNode doesn't have attribute that give us the value of previous one, this why I find a great difficulty of doing lab 7. In one question, we need to insert a data before some specific position.

My strategy is that

first, we check is the v2 is in the first index of Linked List. My code is

if not, I start to check check every value in the list until we reach v2, but the point is once we reach v2, we know the index of v2, let say its index is i, and we want to add v1 at index i-1, but LLNode doesn't have the attribute of looking for its previous value (it only have the attribute of looking next value).

In that case, I have to keep tracking two values. Every time when we check if the current node value equals to v2, we have to also remember the previous node value and make is keep moving along so that we don't lose the track of it

Here is my final solution:

 

Week 7 --Recursion

 Writing recursion is quite challenging for beginners like myself. For many time when I doing lab question, my code doesn't work, I don't know why; and sometimes my code works and I don't know why. I read a very interesting definition of recursion once. It states "The main point of it is that it is defined in terms of itself: "Recursion: ... for more information, see Recursion.""

First question: what kind of problem can be well solved by using recursion ? General speaking, problems are defined in term of themselves. This abstract answer tells me nothing. We need a more solid example. A good example I've find is factorial function. 5! = 5*4*3*2*1 = 5*(4*3*2*1) = 5*4! = 5*4*(3*2*1)= 5*4*3!. When n is arbitrarily large,  n! = n*(n - 1)! still holds for all n! 

Second question: how do we solve it? first, we need a base case, where it's so simple that can be solved without using recursion. Why is it so important ? Because it's a haling condition, tells the function when to stop, (stop once reaches base condition). 

for example, 

what would it return ? If n = 3, then our recursion trace would be 

3 * factorial(3-1)---> 3 * 2 * factorial(2-1)---> 3* 2 * 1 * factorial(1-1)--> 3*2*1*0*factorial(0-1)

we have meet an absurd situation. first if n is NOT restricted to natural numbers, then this would go negative infinite and never halts. but if we restricted n to natural numbers, there would be no such
factorial(0-1) exists at all !. Either case, we can't have our promising result. Therefore, the base is required !

We want to define the base so that this absurd situation would happened to us and factorial(3) gives us the reasonable answer (which is 6). 

We first, need to thinking about what happen if the input n is negative ? It should give us error. If n is give as 0 it should give us 1.

therefore, we need have
if n < 0, returns
 if  0 <=n <= 1, return 1, 

Here is how we think of defining a recursion function

Week 6 ---Summary of Object-Oriented Programming Concepts

Object-oriented programming is based on the concept of object. This definition is taken from Wikipedia and tells me almost nothing at first when I google it. It can't be clear without some solid example. Here is some of my personal thoughts on OOP.  For example, python classes have all features of OOP. In python, class defines what is common for a whole class of objects. If we define a class 'Point'(like we did in the lecture), this doesn't imply we create an arbitrary point, but implies we create a kind of manual instruction of constructing 'Point' objects, and this manual instruction is completely up to us to decide. For example , '(3,4) is a point' in python language is '(3,4) is an instance of Point class'. We need to initialize 'Point' and creating attributes like coordinate(its distance from original point (0,0)).

Creating 'Point' class, we haven't create any point. We only create a sort of rules for what it means to be a point. No point exists until we call Point(). For example, >>> p = Point(3.0, 4.0). This implies that we use Point class rules to create a new object, this object is referred as p.

There are many methods we can use to make our class more practical. For example, __str__, __eq__, __repr__  .

One very powerful concept is inheritance. The concept itself is very self-explanatory. The idea is that subclass inherited the method and data from superclass.

For example, if we run a bookstore, we sell many types of books from fiction to non-fiction. We want to record the sales of each type books; we want to apart the fiction from non-fiction books. We create a super class Book, and we write a function sales() in the function with 'NotImplementedError'. Then we create subclass for each type of books. One sub for fiction, one for non-fiction, etc. In each subclass, we again write the function sales() with some specific instructions.