Last week is about Big-O.
Few things that very import:
(1) When we talking about running time in computer science, we talking about how many steps the code has to go through to give us desired output. Also, we cares when the input n gets really large, and how fast the running time goes up.
(2) We don't care the hardware influence, we only care the mathematical algorithm
(3) We don't care for small input n
(4) We don't care the constant or coefficient because as n goes large, n + a, n, cn(for some number a nd c) are same.
(5) We care the degree of n, because it determines how fast the function goes when n is large.
(6) The rate of change: quadratic> linear > log
(7) If in each iteration, n gets half, then the running complex function is log
Friday, April 3, 2015
SOME RETROSPECTION
I have to say that I didn't expect writing Slog actually could help me at the beginning of the semester. However, due to the TA strikes, weekly Slog actually helps me to keep things up-to-date. Every weekend, when I about to write slog, I have to go through the lecture notes and looking for some topic that I should write about, and also I have to do some coding to make sure what's going on. Below is a list of things that I've looked back during the semester:
I personally never find trace recursion is difficult as long as be patient and organized , but writing a recursive function is still a big problem to me. When I writing recursion, I'm only doing it mechanically (all other examples are doing this at the step, so we should do it too), it basically follows my intuition and when I finish the coding, I run the doc test and few examples. If I'm lucky, I might be right at beginning and never feel fully confident when I finish the code (Always thinking about lets try this code to see if it works, then I may find the problem needed to be fixed it later)
However, I still learned some receipts for writing some specific codes. Such as drawing a diagram to start for recursive codes.Diagram doesn't necessary to be complex examples, but starts with easy one.With the help of diagram, I can break the big coding into small pieces for better analysis. Not only the diagram helps to writing codes but also help me to write better codes with less running time because with the diagram, I can see clearly which steps has been taken during the coding, and what is redundant steps that we can avoid.
I personally never find trace recursion is difficult as long as be patient and organized , but writing a recursive function is still a big problem to me. When I writing recursion, I'm only doing it mechanically (all other examples are doing this at the step, so we should do it too), it basically follows my intuition and when I finish the coding, I run the doc test and few examples. If I'm lucky, I might be right at beginning and never feel fully confident when I finish the code (Always thinking about lets try this code to see if it works, then I may find the problem needed to be fixed it later)
However, I still learned some receipts for writing some specific codes. Such as drawing a diagram to start for recursive codes.Diagram doesn't necessary to be complex examples, but starts with easy one.With the help of diagram, I can break the big coding into small pieces for better analysis. Not only the diagram helps to writing codes but also help me to write better codes with less running time because with the diagram, I can see clearly which steps has been taken during the coding, and what is redundant steps that we can avoid.
Week 10
Last week, we have start to talk little about Unitest. In CSC108, we have learned about test cases. In this topic, we need to check for out outputs meet our expectations in respond to some particular input.
It's very common, that an incorrect code pass our doc test, or even most of the cases that we think about. Therefore, we need to design a good set of tests. One of the common method is assertEqual,
it's a boolean function that takes two arguments (usually one is real output, and another is out expected result) and comparing two arguments to see if they are equal or not; and gives us True or False.
To implement unitest, first, we import unitest, then we define a function that we want it to be tested. Then we need to a class MyTest(unittest.TestCase), and def test(self), finally, self.assertEqual(function(input), expected output).
Doc test is easier, we only need to if __name__ == '__main__': import doctest doctest.testmod()
Some others things we should know
(1) Setup(): This is called at the beginning of the test. It's different than AssertionError, which later one is raise when an assert statement fails while Setup() gives us error rather than test failure when exception raise.
(2) Teardown(): It's called after the test had been implemented regardless whether the test method raises exception
It's very common, that an incorrect code pass our doc test, or even most of the cases that we think about. Therefore, we need to design a good set of tests. One of the common method is assertEqual,
it's a boolean function that takes two arguments (usually one is real output, and another is out expected result) and comparing two arguments to see if they are equal or not; and gives us True or False.
To implement unitest, first, we import unitest, then we define a function that we want it to be tested. Then we need to a class MyTest(unittest.TestCase), and def test(self), finally, self.assertEqual(function(input), expected output).
Doc test is easier, we only need to if __name__ == '__main__': import doctest doctest.testmod()
Some others things we should know
(1) Setup(): This is called at the beginning of the test. It's different than AssertionError, which later one is raise when an assert statement fails while Setup() gives us error rather than test failure when exception raise.
(2) Teardown(): It's called after the test had been implemented regardless whether the test method raises exception
Sunday, March 15, 2015
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
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,
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
Sunday, March 8, 2015
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:
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.
first, we check is the v2 is in the first index of Linked List. My code is
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:
Sunday, March 1, 2015
Week 7 --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
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,
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.
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.
Subscribe to:
Posts (Atom)