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.
2014年3月22日土曜日
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.
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.
2014年3月10日月曜日
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.
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.
2014年3月3日月曜日
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.
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.
2014年2月22日土曜日
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.
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.
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.
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.
登録:
投稿 (Atom)