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.
Sunday, February 8, 2015
Week 5
At very beginning of this semester, I talked to one of my friends who already took csc148 in 2014. When I asked her that how did she thinking of csc148, is it difficult? She said the recursion is very hard. Of course, I had no idea what recursion really stands for except that I think it a very cool name. Not until the last week, we finally been introduced to recursion. The starting introduction is very friendly because the example is dealing with the simple question--addition of numbers. we are given a problem at first, to sum a given list. The build-in function could easily solve it for us if the nest contains only integers. However, if the given list contains more than just integers, but a nested list, the build-in function 'sum' doesn't work for us anymore. I remember back to csc108, I used to encounter a similar problem that I need to sum a list where the list itself contains lists. for example, S = [ [5,6], [3,4], [1,2] ]. I remember what I did was to create a new list.
Apparently, this is very inefficient way of doing it, first it requires that each vector in the list much have same length 2, second it doesn't solve the case if the given list contains integers mixed with list, or list of list of list etc. Also, thinking about the running time, it's not the good way of solving such problems if we take the consideration of any of above we mentioned.
I don't who comes up with the idea -recursion, but when I first time saw it, I was very impressed that defining a new method in term of the method itself, functions can call themselves to solve smaller sub-problems.
So far, we haven't taught how to write a proper recursive function. All we do is trace each step. This part requires attentiveness and calmness so that we don't get upset and messed up when the given input is too complex.
I don't who comes up with the idea -recursion, but when I first time saw it, I was very impressed that defining a new method in term of the method itself, functions can call themselves to solve smaller sub-problems.
So far, we haven't taught how to write a proper recursive function. All we do is trace each step. This part requires attentiveness and calmness so that we don't get upset and messed up when the given input is too complex.
Sunday, February 1, 2015
Week 4
This is a very busy week. Particularly due to the first assignment. From assignment, more than just learning the difference between __str__ and __repr__, how to use subclass After the first assignment, I start to realize how easy CSC108 was last year because 148 is completely a new level of programming. In CSC108, when we write program, we were almost given anything that we need. We were given the program outlines, starting codes, what kind of function we need, doc-string, examples, and instructors even completed all the programs codes. Basically, in CSC108, we don' need to think how to start a task, or where to start. We don't need to think what is needed for this program to be successful, or learning how to carefully plan step by step to solve the problems. All we need to do in 108 is just finish the uncompleted codes for most time, I myself without even thinking why is it needed or what is it related to the other functions or overall program. In 148, everything changes. For the first assignment, we are only given a instruction of program, without any starting codes, plan, examples, functions provided. I felt overwhelmed at first after been spoiled so much in 108. I spent much more time on thinking overall and planning than the time I spent on actually writing the codes. I can't remember how many times I've completely delete what I've done and re-start just because something I didn't think carefully at beginning. In CSC108, I barely read assignment instruction, I just download the starting codes and mechanically completed the codes, In 148, it involves more creativity, and our own way of planning and thinking. More challenging thing is that, this assignment is merely a starting for the next two assignments, which means that we have to make sure that when we continue next time, the additional class or codes must comfort with the one we are writing right now, we need to make the code to be as flexible as possible and meanwhile, it must be easy amend in future time. We need to build a structure that we might use in the next two assignment. Some nights, I even thinking about the assignment even when I'm sleeping. Of course, when I finish the program finally, it yields more satisfaction and I'm very looking forward to the next assignment as well.
Sunday, January 25, 2015
Why Geeks Should Know How to Write
It's not the first time I took Mr.Danny Heap's course, nor it's the first time I write slog for his class. The first topic for this class is "Why Geeks Should Know How to Write." I take grant that 'write' means regular writing, like stuff that most of non-computer science write or read daily. Apparently, everybody who is capable, should know how to write regardless of his jobs, education, social background. Mostly, for better communication. When comes to Computer science geeks, knows how to write serves the same purpose-communication. A little different here is that, instead of communicate with real life people, geeks communicate with nonhuman objects. Communicating with nonhuman objects is weird, geeks write codes to instruct computers in an abstract way (logic, mathematical). The codes are written in such way that most non-computer science people don't know what's going on. Since regular writing and geek writing are so different, why geeks know regular writing anyway. One thing is that, though, code writing is different than regular writing, but it comes out of regular writing. There would be no code writing without regular writing. I don't think it's possible for a human to learn mathematical or logic language without even knowing any sort of regular language. If this is not true, we might have computer programing courses when we were in kindergarten. It's necessary to know how to write regular things for computer science geeks. Regular writing involves generating ideas, planning, organization. These are all fundamental for coding. Geeks should know how to communicate with human before they communicate with inhuman objects .
Subscribe to:
Posts (Atom)