Week 12
Constant time access and review
We studied constant time access and reviewed all materials which we leaned in this course. 
Python dictionaries can insert, find item in constant time. The references to elements of the list are stored in consecutive memory locations. 
Python lists are accessed by index. A string, or a tuple, can be converted into an integer, using a hash function. Python has a built_in function called that converts immutable object to 32 or 64 bit integers.

After I learned Constant time access, I reviewed lectures from week 1 to week 11. I found that I still did not understand the structure of LinkedList. I will review it carefully to prepare for Final exam.
 
 

Week 11
Sorting and Efficiency 
I leaned sorting and efficiency in the class. We had to measure algorithm performance, which means that we leaned how to measure the running time. If input gets bigger, programs take more time to run it. We focused on size of the input and it is called n.
There are many types of input:
constant: c, logarithmic: c log n, linear: cn, cubic: cn^3, exponential: c2^n,,,

There are many types of sorting and some of them have different running time.

quick sort: O(n^2)
Quick sort chooses a pivot element in a list. It moves everything smaller than the pivot to one list (left sublist) and everything larger than the pivot to another list (right sublist). Then, quicksort the left sublists and right sublists. Then sorted list is made of left subtree, pivot, and right subtree. n steps are required to choose a pivot and n steps are required to compare each item in a list with the pivot.

merge sort: O(n log n)
Merge sort divides the list in half and mergesort the two divided list. Then merge the two sorted sorted halves in linear time. Merge sort divides a list log n steps and compare the each item in a list n times.
 


 

Week10:
Sorting big-Oh
In this week, I leaned some techniques to make codes of A2 during the lecture, and some sorting methods and their running time.  I thought I completed the A2, but I found a huge mistake in regex_match. It is that I processed a regular expressions of Regex (e.g. '(1|0)') to find if it matches a String. I had to process RegexTree instead of the regular expression. I rewrote every code in regex_match.

Searching linear takes more time to find a data because we must research every element in the list. There are some methods which find a value faster than linear search. 

Quick sort: First, pick up one item from the list and compare it with each item in the list. If item in the list is greater than the item picked,put it on left side of the picked item. If item in the list is less than the item picked, put it on right side of the picked item. Then, use quick sort to the items in left side of the picked item and items in right side of picked item.

Merge sort: First, divide a list into two list. Then compare last items of each list and append bigger items to the empty list and pop the item from formal list. Continue this work until two list become empty. Finally, reverse the new list which contains every item.  
 

Week9 
BSTs and big-Oh
This week I leaned binary search tree and big-Oh. Also I finished is_regex and all_regexpermutations and build_regex of A2 in this week. However, regex_match was harder than the other cases, because I must consider special cases for StarTree and Leaf epsilon. StarTree and Leaf of Epsilon match empty string therefore I have to make more if statements.

I think the definition of binary tree is that each node of tree has 0 or 1 or 2 nodes, and the data in left subtree is less than the data in right subtree. This structure makes it easier to find a value in the tree and delete a value from the tree. For example, if data to delete is less than at node, it deletes from left and return it's node. If data to delete is mode than at node, it deletes from right and return it's node.

Searching a value in binary tree is more efficient than searching linear list. If I research linear list, we must investigate every element in the list. However, if I research binary tree, I am allowed o ignore half the list. If the data I want to get is less than the node, I can ignore the right subclass and search only left subtree.

Running time means time to run the code. We can find the running time of each code and find the best code to solve questions faster than the other codes. If an algorithm runs in number of steps no more than cg(n), we say the algorithm is O(g(n)). This means that running time of the algorithm faster than cg(n) as the size of input grows.


 

Week 8
Linked List

I learned Linked List this week. I did difficult excercise during lab and I could not finish the tasks. It is difficult to describe the relationships between each values of linked list. The lectures of this week helped me to understand the Linked list deeper.

There are two ways to understand the Linked List.
1.  The linked list is made up of a value and the remaining list. This means that a value, such as list,  has a sublist. And the sublist has more sublist.
2. Objects has a value and a reference to other similar objects. This means that a value refers to the other value, furthermore it refers to the other value.

Week 7:
Recursion and Linked Structures

 Recursion is defined as "defining something in terms of itself". The recursion function calls itself in its function body therefore we don't have to make duplicate codes. For example, if we want to find the number of objects in nested list, we must check each nesting list. Then we can utilize the recursion function. If the element in the list is an object, the function counts it as 1 object. If it is a smaller list in the list, the function calls itself and check the inside of the smaller list. Every recursion function has a base case, which checks if the function has to call itself in function body, therefore it automatically solves the problem and we do not have to check a condition for each sub problems.

 In my opinion, the recursion is very useful for programmers because it omits duplicate codes and makes function body shorter. However, the recursion functions sometimes are difficult to read and understand what they do. Tracing the recursion functions precisely is very difficult. In conclusion, if we want to write the codes efficiently, we should write recursion.

Week 6
Recursive Structures.
In this week, I learned some terminologies and structures of Trees. 
Tree is constructed by nodes. One node is distinguished as root, which is the biggest parent, and each non_root node has exactly one parent. 
Node with no children is called as leaf, and node with one or more children is called as internal node.

There are three ways to visit root and subtrees.
Pre-order traversal - visit root, then pre-order left subtree, then preorder right subtree.
In-order traversal - visit in-order left subtree, then root, the in-order right subtree.
Post-order traversal - visit post-order left subtree, then post-order right subtree, then root.

After the lecture, I played with the examples of Tree which the professor posted on the website and I understood the structures of the above three methods. Also I found the best method to move cheeses from first stool to the fourth stool with minimum moves and completed the Assignment 1.

Week 5 
Recursive continued
 In this week, professor explained us more recursions and gave us hints of Assignment 1. The concept of A1 is based on Tower of Hanoi, it is an interesting topic of mathematics. He provided us a function that shows moves of n cheeses from stoo1 to stool 3, meaning , and it was really helpful for me because that function included recursion and I utilized the function in A1!.


And he taught us name and value this week. Every name contains a value(object) in python and value is a reference to the address of an object. And there are different types of scopes in the function body. Innermost scope is local, enclosing scopes are nonlocal, and the largest scope is global. During the lecture, we practiced to find the names in different scopes.

In this week, I spent most time in A1. I utilized the technique which the professor taught us during the lecture to complete the Tower of Hanoi of four stools.

Week4 
The main purpose of this week is to learn recursion. The recursion is defined as "defining something in terms of itself" multiple times to achieve our objectives. 

'Nesting depth of list' is an example of the recursion. The nesting depth of list is the number of nested list in the list. For example:
nesting-depth of [1, 2, 3] -> 1
: because a list doesn't include any list. Therefore the depth is 1.
nesting-depth of [1, 3, 5, [3, 4, 3]] -> 2
: because a list include one list. Therefore the depth is 2.

The recursion is difficult for me because this is a new topic for me. The recursion function calls itself in its function body, and all recursion include the base case which tells me when/how to stop the function. Tracing the each step of recursive calls increases complexity therefore it is hard for me. 



 

Week 3 -csc148-

Object oriented programming
Python is an object oriented programming. This means that a powerful style pf programming in which data and the operations that are relevant for that kind of data. In object oriented programming the focus in on the creation of objects which contain  both data and functionality together. Each object definition corresponds to some object or concept in the real world, and the functions that operate on that object correspond to the ways real world objects interact. 

When programmer represents numeric value by python, he can defines a new class. Class definitions are near the beginning after the import statements. The header begins with the keyword, class, followed by the name of the class, and ending with a colon. Every class must have a special method __init__, called initializer. Object instances have attribute, it means that one of the named data items that makes up and instance. 

Subclass and Superclass
Stack - It is an example used in Week 2.

• We decided to extend the features of Stack. eg. Create new Stack that only accepts integers. This means that modifying the existing class.

1. We must break the existing clients to create new methods.
2. Cut and Paste to modify Stack. This process is hard to maintain. 
3. New class has attributes of Stack. 

  We can avoid recursion, such as writing same codes twice, by creating a subclass. A subclass inherits all the features of a Superclass. This means that the Superclass is a parent and the Subclass is an offspring. >class Newclass(Oldclass):
  In this case, Newclass is a subclass and Oldclass is a superclass.
  We create subclasses to specialize the features of a new class by adding and modifying behaviors. We don't need to create __init__ method in subclass.
  We can access to Superclass methods by:
>OldClass.method(self,,,) 

New method isinstance(object, classinfo)
          Return true if object argument is an instance of the classinfo argument.
          Example : >isinstance(4, int)
                          True
                        >isinstance('Hello', str)
                          True

Exception 
Whenever a runtime error occurs, it creates and exception object. The program stops running if it occurs and Python describes the exception. Python programmer can create Exception class to raise exception. 

example:

def pop(self: 'IntStack') -> int:
    if self.is_empty():
        raise PopEmptyStackException   
    else:
         Stack.pop(self)

class PopNonIntegerException(Exception):
    pass

If pop(self) causes an error, then PopNonIntegerException appears. 

There are superclass and subclass of Exeptions. For example:

class SpecialException(Exception):
    pass
class ExtremeException(SpecialException):
    pass

In this case, Exception is a superclass and ExtremeException is a subclass of Exception. ExtremeException is a superclass and ExtremeException is a superclass of ExtremeException. And ExtremeException is a subclass of ExtremeException. 

__eq__
When some objects are created by initializer methods, they are different objects and their memories are different. For example:

>>>S1 = Stack()
>>>S2 = Stack()
>>>S1 == S2
     False
>>>S1.push(3)
>>>S2.push(3)
>>>S1 == S2
     False

S1 and S2 are created by class methods and their memories are different. S1 and S2 includes same numerical value. However, their memories are different. 
Then a special method is required. After I make __eq__, memories are still different. 

def __eq__(self, other):
    return is_instance(object, Stack) and self._data = other._data

__repr__
__repr__ is a special methods to represent class as a string. 
def __repr__(self: 'Stack') -> str:
    return 'Stack({ })'.format(self._data)