In week 11, we learned about Big-Oh. This was a fairly easy concept for me because we spent a fair amount of time on it in CSC165 that I took last semester.
The concept of Big-Oh states that a function is in BigOh(fn) if the function grows no faster than f(n) after a certain point. Or alternatively, f(n) is the upper bound of the function.
Notation wise we can use the following example to illustrate BigOh
O(f) = {g : N → R >0 | ∃c ∈ R + , ∃B ∈ N, ∀n ∈ N, n > B⇒g(n)<= cf(n)
This notation basically explains what I said earlier, which is that then) function g(n) will not grow faster than a constant c times f(n) after the point B.
The fundamental purpose of Big-Oh is to test the running time of a function. If the running time of the function is slower or equal to Big-Oh, we say the function is in Big-Oh, else we say the function is not in Big-Oh.For instance, the function 3x^2 would be in BigOh(x^2) but would not be in BigOh(x).
In this lecture we discussed mainly with linear or quadratic running time. We also touched upon on some ways to solve running time question. For instance, when we solve for while loop running time, we times the running time of the inner loop with the running time of the body loop(of the while loop） to produce a result.
In terms of the application of Big-Oh in reality, I am still very unsure. I suppose it will be used as a way to test the efficiency of a function. For instance, it would likely choose the function that runs with the least amount of running time to increase efficiency.
2015年4月2日星期四
Revisit all previous posts and see if I agree
To do this slog, I had to go back to all my previous slogs and see if my impression has changed or not.
To be honest, I began this course intimidated and scared. I was totally overthrown by the concept of class and sub classes because we didn't touch upon these concepts deeply in CSC108. Therefore, I screwed up really hard on my first test.I made comments on my first few posts to talk about how lost I am in this course. However, when I look back, after completing all the tests and assignments, I began to realize that CSC148 is extremely useful and interesting, and I no longer find it that difficult. This is perhaps the biggest overall change I have made throughout the course.
In week three I commented on my impression of why should geeks write. I still agree with what I wrote. In fact, I now agree more that writing is very important for a computer scientist. It is useful for me to write down my thoughts and come up with ideas, and it is also useful for me to write proper doc string and proper code so my markers can understand.
In week four i made comments about recursion and I said the concept was interesting and challenging. Later in week 5 I made comments on how I am unable to understand the logic behind recursion, as I don't understand how on earth can a function call itself. But as I moved on in the course, and as I did more side research on this subject, I began to realize that the logic or recursion makes sense. I learned that the foundation to build and solve a recursion is to build a base case, and always have the function to go the base case. Once this is comprehended, recursion becomes much more meaningful and I believe I can almost master this concept by now.
I also wrote about Object-oriented Language in week 7. I wrote that slog with a combination of my own idea and some side research. I believe my ideas about Object-oriented Language still holds. This language is basically programming with objects, and making programs by building and interacting different objects.
In terms of my impression of trees and linked list, which I wrote in week 8-9, I believe my impression of trees has drastically changed. When I originally wrote about trees, I thought it is a useless concept that we learn for the sake of learning it. However, as I worked on assignment 3 option A, I realized tree is extremely powerful for programming. This is especially useful when I used tree to solve the MinimaxMemoization class for assignment 3. By think of recursion as nodes and leaves, and drawing the tree structure down on a paper, I was able to clear my mind and provide the solution to the question. My impression of linked-list however remain somewhat the same. I still think the concept is quiet easy but it'as easy to make mistakes when solving a linked-list question. I also haven't studied any practical value of linked-list just yet.
Overall I believe I really enjoyed csc148. It's definitely challenging, but after my hardwork it's becoming much more manageable. Hopefully I do well on the final!
To be honest, I began this course intimidated and scared. I was totally overthrown by the concept of class and sub classes because we didn't touch upon these concepts deeply in CSC108. Therefore, I screwed up really hard on my first test.I made comments on my first few posts to talk about how lost I am in this course. However, when I look back, after completing all the tests and assignments, I began to realize that CSC148 is extremely useful and interesting, and I no longer find it that difficult. This is perhaps the biggest overall change I have made throughout the course.
In week three I commented on my impression of why should geeks write. I still agree with what I wrote. In fact, I now agree more that writing is very important for a computer scientist. It is useful for me to write down my thoughts and come up with ideas, and it is also useful for me to write proper doc string and proper code so my markers can understand.
In week four i made comments about recursion and I said the concept was interesting and challenging. Later in week 5 I made comments on how I am unable to understand the logic behind recursion, as I don't understand how on earth can a function call itself. But as I moved on in the course, and as I did more side research on this subject, I began to realize that the logic or recursion makes sense. I learned that the foundation to build and solve a recursion is to build a base case, and always have the function to go the base case. Once this is comprehended, recursion becomes much more meaningful and I believe I can almost master this concept by now.
I also wrote about Object-oriented Language in week 7. I wrote that slog with a combination of my own idea and some side research. I believe my ideas about Object-oriented Language still holds. This language is basically programming with objects, and making programs by building and interacting different objects.
In terms of my impression of trees and linked list, which I wrote in week 8-9, I believe my impression of trees has drastically changed. When I originally wrote about trees, I thought it is a useless concept that we learn for the sake of learning it. However, as I worked on assignment 3 option A, I realized tree is extremely powerful for programming. This is especially useful when I used tree to solve the MinimaxMemoization class for assignment 3. By think of recursion as nodes and leaves, and drawing the tree structure down on a paper, I was able to clear my mind and provide the solution to the question. My impression of linked-list however remain somewhat the same. I still think the concept is quiet easy but it'as easy to make mistakes when solving a linked-list question. I also haven't studied any practical value of linked-list just yet.
Overall I believe I really enjoyed csc148. It's definitely challenging, but after my hardwork it's becoming much more manageable. Hopefully I do well on the final!
Week 10- Review of week 9
In week 9, we didn't learn much new because we only had a 40 minutes lecture after the test. However, I did have some good experience preparing for the test and I would like to share with the group.
My trick to prepare for the test is to study all tutorial questions and make sure you know how to write them and that they run properly on your computer. I also tried to modify the tutorial questions and solve the modification myself. This was a good practice because the fact that you can solve a modification to the problem shows that you really understands the problem and can deal with whatever way the professor modifies the problem on the test.
The only part that I find difficult was linked list, because it's so easy to make a mistake with it.
Overall I think the test was fairly straightforward. The questions were expected and I think I did very well. The only part that I am not too sure was the linked list part. I am very sure that I have the concept right, but I could have forgotten something there.
The school year is almost over and so far I feel that computer science is so fun. I hope I can keep this up
My trick to prepare for the test is to study all tutorial questions and make sure you know how to write them and that they run properly on your computer. I also tried to modify the tutorial questions and solve the modification myself. This was a good practice because the fact that you can solve a modification to the problem shows that you really understands the problem and can deal with whatever way the professor modifies the problem on the test.
The only part that I find difficult was linked list, because it's so easy to make a mistake with it.
Overall I think the test was fairly straightforward. The questions were expected and I think I did very well. The only part that I am not too sure was the linked list part. I am very sure that I have the concept right, but I could have forgotten something there.
The school year is almost over and so far I feel that computer science is so fun. I hope I can keep this up