Last Week

This term seems past so quickly that all the lectures are done, and we completed all the assignments and labs. The final exam would be the only task left for us to do. It is obvious that this term was really tough since the strike of CUPE 3902 Unit 1, the labs were cancelled for nearly a month, and tests and assignment were graded for a long time. All  these things affected us in different ways, however, we all got through these things.

In my opinion, we learned a great deal of recursion on python for CSC148 course this term, from the simplest tree to linked list. In the last several weeks, we also learned about efficiency(sort) and the big-O difinition.

 For recursion, we learned it through tree, binary tree, linked lists and so on. And most of three assignments were closely associated to this. I think the functions were simplified by this, and easier to be understood.

For the efficiency part, different sort methods (bubble, insertion and selection) as well as big-O definition has been taught.  

Other sort method:
Break a list up (partition) into the part smaller than some value
(pivot) and not smaller than that value, sort those parts, then
recombine the list:
def qs(L):
    ''' (list) -> list'''
    if len(L) < 2:
        # copy of L
        return L[:]
    else:
        return (qs([i for i in L if i < L[0]]) + [L[0]] +
                     qs([i for i in L[1:] if i >= L[0]]))

Big-O definition:
Suppose the number of \steps" (operations that don't depend
on n, the input size) can be expressed as t (n). We say that
t 2 O(g) if:
there are positive constants c and B so that for
every natural number n no smaller than B,
t (n) cg(n)


Overall, I learned a lot through this term's CSC148 course. All the tough assignments and labs gave me an opportunity to challenge myself.

Week#10 Revisit Slogs

Revisiting Slogs

In this term's csc148 course, we have developed our skills in python, and the most important thing we learned is recursion.

In past several weeks, I wrote slogs about impression every week. In my opinion, I agree with most of what I write especially the concepts and examples used in the class.

At first, we learned the recursion through simple examples for lists of lists. These examples aimed at create a basic impression of recursion.

However, we mainly learned the recursion through tree and linked lists. As far as I concerned, the most efficiency way to think a recursion method is draw this specific tree, and figure out what nodes(or parents) and leaves(or children) are. What's more, we must ensure that every instance used in the class is understood before we write any method in class.

__init__ method for BTNode which represents a binary tree.

Compare with my friends' experience, I prefer to write codes after drawing the picture of a tree or linked lists on paper. Because this could help  me figure out each steps of each method, I can easily write codes through that specific tree.

Week#10

There are only two weeks left to complete our courses in 2015 winter term. In this week's csc148, we analyzed our codes written in assignment 2, and learned some methods to strength our ability in python.

In assignment 2, we wrote a specific class called Minimax Strategy, which is a strong strategy for computer to choose the best possible move in current situation. As this method seems to be difficult to thought of, Danny gave us a possible way to get the solution.

one possible solution for minimax

The best way for us to come up with the idea and understand the solution is to draw a tree to represent every possible moves and all the winning position for a specific player. However, the tippy game seems to be so complex, so we will consider the examples in the subtract square game.

Subtract square example

On the other hand, we also learned a new method called assert to simplify our 'if not' statement.

Week#9

For CSC148,  this week we started the topic of mutation (eg. LLNode and LinkedList) and we took term test 2 on Wednesday.

Class Tree, BTNode and LinkedList were tested in midterm 2. As far as I'm concerned, the methods written in the test for BTNode and LinkedList were similar to what we wrote in the lab. As long as we understand the recursion and basic methods written in the classes, the methods for the test would be easily completed.

On the other hand, LinkedList would be the first class that we encountered with mutation. 

LinkedList init

The nodes in the LinkedList are the nodes in LLNode class. As a result, self.front would be continued changing while value and nxt change. (insert_before would be a good example to explain this.)

 

Week#8 Impression of Week 7 and Assignment 2

After reading week, our CSC148 course seems to be more difficult than before, especially the assignment two. However, our lectures continued the topics on recursion and mutation.

For week 7 and week 8, we learned two different classes called BTNode and LLNode, which can been seen as a tree and a linked list, respectively. Both classes can be closely associated with the recursion steps. We can take LLNode in week 8 as an example. 

LLNode consists value (the current node) and nxt (the node linked with current node) which can be treated as the child of value. The recursion steps happen since the nxt could also be the value of other nodes. The difference between we learned in week 7 and week 8 could be the way we imagine the  diagram of these two classes. For BTNode, we should see the values as leaves in a tree, appending the values in left or right leaves in that tree and calculating the values by a distinct symbol. On the other hand,  LLNode is a class that represents a linked list, each node has its own child, and child can also be the parents of other children. However, the essence of these two classes should be same. They both include the thoughts of recursion and mutation.

BTNode

LLNode

Assignment two seems to be more difficult than the assignment 1, especially  winner in tippy game state and minimax strategy. In winner, we must containing all four possible states of forming a tippy. What's more, minimax could be consider as the most difficult problem we countered. However, once we figure out the recursion steps, and  body of the method can be written easily. In this step, a tree diagram and written score for every steps in the corresponding position on the diagram.

Week#7 Recursion II

Continue on Recursion

Tree

After reading week, we continued the lectures about recursion, however, the lecture focused on a different class named BTNode, a generic Tree design. In my opinion, Tree enables us to learn the recursion method more visualizable. We can trace the steps in a specific diagram.

Initialize of the BTNode

Compared with the lectures before reading week, the codes we wrote in this week’s lecture seem to be more complicated. The reason is that parents and leaves should not only be run, but also be evaluated whether it is valid and the codes should be calculated in a specific order. All these requirements needs more specific methods to be written in one class.

evaluate method

In evaluate method, the return result is the value after being calculated by the int and str provided in the tree. And the simplest situation is when the node is a leaf, which would involve another method in the class. However, the recursion steps are similar with before. But the calculation in the recursion steps would make us confused and lost in the position of tracing steps.

WEEK#6 Object-oriented Programming Concepts

WEEK#6 Object-oriented Programming Concepts

Stack: in a stack, you remove items in reverse order you insert them, so the first item removed is the most recently-added.

ADT(abstract data type): An ADT describes how it stores data, and what operations(methods) one can perform on this data.

This is abstract because there is no code required to understand an ADT.

Class

Class: A user-defined prototype for an object that defines a set of attributes that characterize any object of the class. The attributes are data members(class variables and instance variables) and methods, accessed via dot notation.

Class variable: A variable that that is shared by all instances of a class. Class variables are defined within a class but outside any of the class’s methods. Class variables aren’t used as frequently as instance variables are.

Instance variable: A variable that is defined inside a method and belongs only to the current instance of a class.

Inheritance: The transfer of the characteristics of a class to other classes that are derived from it.

Method: A special kind of function that is defined in a class definition.

Object: A unique instance of a data structure that’s defined by its class. An object comprises both data members (class variables and instance variables) and method.

Operator overloading: The assignment of more than one function to particular operator.

Exception: the purpose of the Exceptin is to stop the program woth a meaningful message if there is an advertent executin path that would return NoneType.

Recursion

Recursion means “defining something in terms of itself” usually at some smaller scale, perhaps multiple times, to achieve your objective.

Data Structure:The organization of data for the purpose of making it easier to use is called a data structure

 recursive call : The statement inside the function definition in which the function calls itself is known as the recursive call.

base case: It does not lead to a recursive call: the case where the element is not a (sub-) list. Without a base case, you’ll have infinite recursion, and your program will not work.

## base case: A branch of the conditional statement in a recursive function that does not give rise to further recursive calls.

## infinite recursion: A function that calls itself recursively without ever reaching any base case. Eventually, infinite recursion causes a runtime error.

## recursion: The process of calling a function that is already executing.

##recursive call: The statement that calls an already executing function. Recursion can also be indirect — function f can call g which calls h, and h could make a call back to f.

## recursive definition: A definition which defines something in terms of itself. To be useful it must include base cases which are not recursive. In this way it differs from acircular definition. Recursive definitions often provide an elegant way to express complex data structures, like a directory that can contain other directories, or a menu that can contain other menus.