Week 7 is such a big week with so many contents that without deep understanding of the lectures in this week directly causes poor marks for my term test 2 QAQ.
In this week we did: binary tree, tree traversal, assignment 2 and binary search tree(posted in slog of week 9). At the beginning of the lecture Danny talked a little bit about assignment 2. I liked this assignment so much that right on the morning of Apr 11th I still feel it's the best one I've ever tried to work on . This assignment, which I think, contains some basic contents and thoughts of AI(artificial intelligence). In this assignment we were asked to design a game called Tippy and try to upgrade our strategy for computer in assignment 1. The new strategy we need to write is called Minimax. Based on the condition that player one will always pick a proper move just like computer, Minimax is a strategy that implicitly go through a game tree by implementing recursive function whose base cases are the ending situation(game states) of the game. As a general strategy, Minimax is supposed to be able to work for any kinds of 2p games. The principle of Minimax is to keep applying moves if there's possible move exists until it reaches the very end of the game (a player wins). The player who wins will be given a base score with value of 1 and the other player -1 as he loses the game. According to the concept of zero-sum game (what is good for one player must be bad for the other) and the same level of intelligence of two players, we can multiply the base score by -1 to get the score for another player in the upper states of the game. We repeat this process until we reach the state for computer to pick a move among possible moves. What we need to pick the correct move is to pick the lowest score for its opponent in all the next game states by using function min(). In this way we realize a very basic extent of AI for computer to pick move smartly. This assignment is so interesting that makes me feel like to focus on AI if I'm enrolled in my program.
After a brief mention and some hints for A2 Danny began to introduce a new data structure for the course called binary tree. A binary tree is just a special case of the general tree. Just like its name, a Binary tree only has two children for each node: self.left and self.right. We need to implement class BTNode for our binary tree to have these special attributes. Danny gave us a vivid example as a representation of the binary tree:
*
+ 6
3 7
As arithmetic binary expressions can be represented by binary tree, if we evaluate this BT we expect the result of 60(10*6).
To lay the background for BST, We need some basic knowledge about tree traversal first. There were 3 kinds of traversals which we did in the lecture: preorder, postorder and inorder. All of these three kind of traversal require the implementation of recursive function. The difference between these three traversals is the order of the nodes being visited. For preorder traversal we visit the root then the left then the right(root -> left -> right); for inorder we go like: left -> root -> right; for the postorder it's: left -> right -> root. On wikipedia it said all these three traversals are depth-first type and there's another type called breath-first search which contains level-order traversal.
After let us know some basic concepts about BT and tree traversal, Danny moved on to the BST( impression posted in the slog of week 9). In general week 7 was a big week with many quite challenging contents. We need to take time to think about all these data structures to completely understand how they work.
Saturday, 11 April 2015
Well, binary search tree again! (week 9)
In week 9 we had our term test 2(which I sucked TAT).The reason I didn't do well in the test was I didn't deeply understand the contents in week 7. In week 9 professor introduced a new data structure called binary search tree(BST)to us. The basic definition for BST is a binary tree with its all larger item on the right hand side and all its smaller item on the left. For example if I have list [1,2,3,4,5,6] and I have 4 as the root of my BST. Then I need to put 3 on the left and 5 on the right because each item on the right hand of the previous node should be larger than the item on the left by definition. In the same way I got 1 left and 2 right for 3; 6 for 5( there's only one item for 5). The diagram will be like this:
4
3 5
1 2 6
（It's not quite good-looking but I hope it can make things clear.)
By building binary search tree we can reach a item in a far quicker way then using bubble search or insertion. The algorithm for BST is quite similar as the one for quick sort. Generally speaking, BST is a sorted binary tree which allow us to reach a certain node in a quicker way so that we can make our modification more efficiently.
As usual we were asked to try to write methods for BST: insert node, delete node, getitem and so on. It's not hard to implement these methods this time by knowing its definition and algorithm.
I looked for BST on wikipedia and it turns out to be a data structure with great
uses. The way it stores data by keys and its structure let it skip over half of the tree at a time, which greatly enhances the efficiency.
4
3 5
1 2 6
（It's not quite good-looking but I hope it can make things clear.)
By building binary search tree we can reach a item in a far quicker way then using bubble search or insertion. The algorithm for BST is quite similar as the one for quick sort. Generally speaking, BST is a sorted binary tree which allow us to reach a certain node in a quicker way so that we can make our modification more efficiently.
As usual we were asked to try to write methods for BST: insert node, delete node, getitem and so on. It's not hard to implement these methods this time by knowing its definition and algorithm.
I looked for BST on wikipedia and it turns out to be a data structure with great
uses. The way it stores data by keys and its structure let it skip over half of the tree at a time, which greatly enhances the efficiency.
llnode linkedlist
In week 7 professor Danny showed us class LLNode and class LinkedList. At first I don't quite understand the point of these two classes because I think class List will be enough for us to implement all the functions needed. After a whole week, these two new classes begin to make sense to me.
Just like binary tree node(BTNode), LLNode is a class that represents each node in a linked list. Class LinkedList is a collection of LLNodes. A LLNode contains two attribute: its value and the next Node it refers to. You may store value in LLNode and it can be a list, tuple, dict... Linkedlist contains 3 attributes which are front, back and size of the Linkedlist.
In lectures and labs we are asked to implement some methods for class LinkedList: make modification to LLNode at a certain index, add or delete LLNode to a LinkedList ,and search for a LLNode in the whole LinkedList. Some of the functions require the implementation of recursion and some not. With these methods LinkedList can behave in a similar way as normal List(array).
Though these two class seem similar to each other, LinkedList do have some advantages over the normal list because it makes the modification of certain items within the list more efficient. Not like the normal list, linked list is like a whole collection of separate objects that is connected in a sequence, which means the computer don't have to get the slice (go through the whole normal list) to make modifications to items. In this way we can achieve higher efficiency by using LinkedList in some situations.
Though by using linked list we reduce the computations need to be done by the computer, I think it may still have some limits comparing to the normal list.
However I'm still ignorant of these limits because I never used linked list in
the assignments(how pathetic!). I'm looking for some further study to gain some deeper insight in this new data structure.
Just like binary tree node(BTNode), LLNode is a class that represents each node in a linked list. Class LinkedList is a collection of LLNodes. A LLNode contains two attribute: its value and the next Node it refers to. You may store value in LLNode and it can be a list, tuple, dict... Linkedlist contains 3 attributes which are front, back and size of the Linkedlist.
In lectures and labs we are asked to implement some methods for class LinkedList: make modification to LLNode at a certain index, add or delete LLNode to a LinkedList ,and search for a LLNode in the whole LinkedList. Some of the functions require the implementation of recursion and some not. With these methods LinkedList can behave in a similar way as normal List(array).
Though these two class seem similar to each other, LinkedList do have some advantages over the normal list because it makes the modification of certain items within the list more efficient. Not like the normal list, linked list is like a whole collection of separate objects that is connected in a sequence, which means the computer don't have to get the slice (go through the whole normal list) to make modifications to items. In this way we can achieve higher efficiency by using LinkedList in some situations.
Though by using linked list we reduce the computations need to be done by the computer, I think it may still have some limits comparing to the normal list.
However I'm still ignorant of these limits because I never used linked list in
the assignments(how pathetic!). I'm looking for some further study to gain some deeper insight in this new data structure.
Friday, 10 April 2015
Object-Oriented Programming
How to define the programming language --- Python --- we've been using all through the course? l looked it up on Wikipedia and it said:"Python is a widely used general-purpose, high-level programming language. It supports multiple programming paradigms, including object-oriented, imperative and functional programming or procedural styles." Though python supports many kinds of programming paradigms, what we've always been using until now is object-oriented programming style.
Object-oriented programming is a specific programming style mainly based on "objects". Basically all the types in python: "int", "str", "list"..., all of these are objects. The functions that can be called on a certain type of object are called methods. Sometimes we create types with certain characteristics to make our programs more efficient. These types are called classes.
By using classes we can maintain our program and test the functions far more convenient than simply using help functions. As professor Danny said in the lecture, if we want to design a program (a game in the lecture), first we write a class with some generic attributes (certain kind of attributes shared by all instances) and we only need to write a subclass for all the different attributes under different considerations. In this way we can avoid maintaining many codes at the same time and achieve a high level of efficiency. If we want to test for different cases, it's also better to use unittest than doctest, especially when it's hard to write down examples in docstring.
Object-oriented programming is a specific programming style mainly based on "objects". Basically all the types in python: "int", "str", "list"..., all of these are objects. The functions that can be called on a certain type of object are called methods. Sometimes we create types with certain characteristics to make our programs more efficient. These types are called classes.
By using classes we can maintain our program and test the functions far more convenient than simply using help functions. As professor Danny said in the lecture, if we want to design a program (a game in the lecture), first we write a class with some generic attributes (certain kind of attributes shared by all instances) and we only need to write a subclass for all the different attributes under different considerations. In this way we can avoid maintaining many codes at the same time and achieve a high level of efficiency. If we want to test for different cases, it's also better to use unittest than doctest, especially when it's hard to write down examples in docstring.
Monday, 6 April 2015
Recursion impression
As mentioned in the previous slog, I think recursion is a quite ingenious algorithm. By using its output as argument, it can solve many complicated function with only a few lines of code. Despite its comparably large O(n), it's still remarkable for its well-constructed idea of computing.
Professor Danny used the example of nested-list to introduce this clever algorithm. What should we do with a general nested-list to count it's depth/length, gather all items, sum up its elements or find the maximum value?
These cases was quite tricky even impossible for us to solve at that time. We need to use recursion for these problems.
Since recursive functions take in its output as its argument, it'll keep computing without a base case, which is the condition for it to jump out of calculating and return a basic result. Take nested-lists as an example, we use method "is_instance" to decide whether an object is a list. If the result is True then we simply implement our function on all of its item. We repeat this process until the base case (the item is no longer list) is reached.
Recursion has a very large range of application. It can be used to construct Fibonacci Sequence, visualize Collartz's problem or even realize AI (artificial intelligence). I think this is an algorithm with tremendous meaning and I am deeply impressed by its beauty.
Professor Danny used the example of nested-list to introduce this clever algorithm. What should we do with a general nested-list to count it's depth/length, gather all items, sum up its elements or find the maximum value?
These cases was quite tricky even impossible for us to solve at that time. We need to use recursion for these problems.
Since recursive functions take in its output as its argument, it'll keep computing without a base case, which is the condition for it to jump out of calculating and return a basic result. Take nested-lists as an example, we use method "is_instance" to decide whether an object is a list. If the result is True then we simply implement our function on all of its item. We repeat this process until the base case (the item is no longer list) is reached.
Recursion has a very large range of application. It can be used to construct Fibonacci Sequence, visualize Collartz's problem or even realize AI (artificial intelligence). I think this is an algorithm with tremendous meaning and I am deeply impressed by its beauty.
It's getting fancy.
Since I'm basically making up for my missing slogs because of the elbow fracture, the impression about the first few weeks may be a little vague for me. However, first few weeks of 148 still gave me some deep impressions: Wow, it's getting fancier and fancier!
I was doing 108 in last semester and basically I was just mimicking the way Tom was coding. Because I didn't know anything about programming before, I had to start from the basic level. I went through many simple functions and followed the instruction and format strictly at most of the time. In 3 assignment, I was told to implement all the functions given rather than writing the main program or some new classes.
Things changed significantly at the very beginning of 148 (everything's opened up!) In the first week, Danny let us explore and examine Class in a so much deeper way than what we did in 108. Many functions (such as __init__) that once were barely understood by us now seemed to have clear meanings. As we were gaining deeper insight into Class and Subclass, we started to take a look at its applications such as creating class Queue and Stack based on built-in class List.
Among all these new stuffs that looked so fancy, Recursion and Turtle are the two that impressed me the most. In 108 we were writing functions all the time and we didn't have any visualizing experience other than shell and call stacks. Turtle seemed so cool to me because it allowed me to draw something on an graphic interface by simply inputting command in shell. You can even add methods to draw more complicated graphs as you want. Though most students were already surprised by turtle, recursion appeared to be even more marvelous. As an cleverly designed algorithm, it's an ingenious function that takes in it's own result as an argument and keeps calculating until base case is reached. Though this algorithm is quite time-taking, it's intriguing idea and wide application (even in AI) should always be highlighted in the history of computer science.
Although some of the course contents appeared to be hard to understand, I found the first few weeks of the course were quite interesting and enlightening. It's also in this period of time that I found the beauty of this subject.
I was doing 108 in last semester and basically I was just mimicking the way Tom was coding. Because I didn't know anything about programming before, I had to start from the basic level. I went through many simple functions and followed the instruction and format strictly at most of the time. In 3 assignment, I was told to implement all the functions given rather than writing the main program or some new classes.
Things changed significantly at the very beginning of 148 (everything's opened up!) In the first week, Danny let us explore and examine Class in a so much deeper way than what we did in 108. Many functions (such as __init__) that once were barely understood by us now seemed to have clear meanings. As we were gaining deeper insight into Class and Subclass, we started to take a look at its applications such as creating class Queue and Stack based on built-in class List.
Among all these new stuffs that looked so fancy, Recursion and Turtle are the two that impressed me the most. In 108 we were writing functions all the time and we didn't have any visualizing experience other than shell and call stacks. Turtle seemed so cool to me because it allowed me to draw something on an graphic interface by simply inputting command in shell. You can even add methods to draw more complicated graphs as you want. Though most students were already surprised by turtle, recursion appeared to be even more marvelous. As an cleverly designed algorithm, it's an ingenious function that takes in it's own result as an argument and keeps calculating until base case is reached. Though this algorithm is quite time-taking, it's intriguing idea and wide application (even in AI) should always be highlighted in the history of computer science.
Although some of the course contents appeared to be hard to understand, I found the first few weeks of the course were quite interesting and enlightening. It's also in this period of time that I found the beauty of this subject.
The importance of writing for computer programmers.
As Joel said, it's crucial for programmers to learn how to write efficiently and understandably because no one will use an extremely complicated code without comments. Sharing ideas is one of the most significant characteristic of computer science. Therefore, the prerequisite for one to share his idea with others is to be able to write clearly in English.
How do programmers let computers do certain jobs/calculations for people? They code! Coding is the process of translating certain algorithm to something that can be recognized by computer. Programmers need to use programming language precisely for computer to operate. What if their code can't be read by computer (may have some errors)? Computer won't be able to function as expected. What this tells us is geeks must make sure that their 'writing'(codes) are extremely precise while doing their jobs. In this way, writing and coding are so tightly related that every programmers should put enough emphasis on how to write clearly.
Noticed that programmers need to 'write' efficiently enough for computer to understand their codes, we have to admit it is also a great concern for programmers to write clearly in English. Just as coding to computer, programmers need to communicate with other programmers, to share ideas with users, to make their codes easy and clear for their codes to be used by others. A complex program without notes and comment definitely won't be accepted by users. To make their codes thrive, programmers need to let people know what their codes can do, how their codes work at first. If a programmer write poorly in English, it'll be so hard for people to grasp the main idea and the algorithm of his code (just as computer can't read poorly written code) that they just turn to other codes instead.
Since computer science is a subject about sharing ideas, efficient writing is one of the basic abilities that every programmer should have.
How do programmers let computers do certain jobs/calculations for people? They code! Coding is the process of translating certain algorithm to something that can be recognized by computer. Programmers need to use programming language precisely for computer to operate. What if their code can't be read by computer (may have some errors)? Computer won't be able to function as expected. What this tells us is geeks must make sure that their 'writing'(codes) are extremely precise while doing their jobs. In this way, writing and coding are so tightly related that every programmers should put enough emphasis on how to write clearly.
Noticed that programmers need to 'write' efficiently enough for computer to understand their codes, we have to admit it is also a great concern for programmers to write clearly in English. Just as coding to computer, programmers need to communicate with other programmers, to share ideas with users, to make their codes easy and clear for their codes to be used by others. A complex program without notes and comment definitely won't be accepted by users. To make their codes thrive, programmers need to let people know what their codes can do, how their codes work at first. If a programmer write poorly in English, it'll be so hard for people to grasp the main idea and the algorithm of his code (just as computer can't read poorly written code) that they just turn to other codes instead.
Since computer science is a subject about sharing ideas, efficient writing is one of the basic abilities that every programmer should have.
Subscribe to:
Comments (Atom)