2012年10月27日星期六
Master Theorem
In week 7 we learnt about Master Theorem.
I found Master Theorem was very interesting and it was an easier way to find the upper and lower bound. But one problem (at least it was a problem for me) was that I had to remember the three different cases. I liked to use method in week 6 better than this because I did not like to cram something without knowing how to get the conclusion.
Have a nice week!
2012年10月20日星期六
Time Complexity
Now it is in week 6, half of the fall semester! Wow, time is so fast!
Course topic now is about Time Complexity. This is very similar to what I learnt in CSC165. But since I did not understand time complexity well in CSC165, I listened to the lecture carefully and will go to office hour to ask any questions that pops up in my mind.
We are learning complexity of recursive functions. Unwinding is a mostly used way to find the lower and upper bounds of a function. This is a different approach from how find the lower bound in CSC165. First, develop a special case and then apply for more general case, for example, first suppose n to be the power of 2 and then apply n to arbitrary numbers.
But there was one thing that I did not understand in class this week. Professor drew a picture to prove that a function was non-decreasing. I did not understand how this picture related to the decreasing of a function. So I went to the section on Thursday night. After the lecture, I asked professor Heap what did this graph mean. The professor explained patiently that since at first we supposed n to a power of 2 and this was not a general case, we wanted a more general case to apply to the unwinding. To apply the unwinding to a general case, we used the upper and lower bound of log(n) to get an arbitrary number. First prove T was not decreasing and then used the relationship between n and n nod and the unwinding to develop an inequality that contained T(n) on one side of the unequal sign and n on the other side. In this way, we could find out both the upper bound and lower bound of a function.
After professor's Heap's explanation, I found I got a better understanding of how to develop the upper and lower bound for a function. Asking questions to professor helps a lot. He can always explain things well and he is very patient. ^_^
Course topic now is about Time Complexity. This is very similar to what I learnt in CSC165. But since I did not understand time complexity well in CSC165, I listened to the lecture carefully and will go to office hour to ask any questions that pops up in my mind.
We are learning complexity of recursive functions. Unwinding is a mostly used way to find the lower and upper bounds of a function. This is a different approach from how find the lower bound in CSC165. First, develop a special case and then apply for more general case, for example, first suppose n to be the power of 2 and then apply n to arbitrary numbers.
But there was one thing that I did not understand in class this week. Professor drew a picture to prove that a function was non-decreasing. I did not understand how this picture related to the decreasing of a function. So I went to the section on Thursday night. After the lecture, I asked professor Heap what did this graph mean. The professor explained patiently that since at first we supposed n to a power of 2 and this was not a general case, we wanted a more general case to apply to the unwinding. To apply the unwinding to a general case, we used the upper and lower bound of log(n) to get an arbitrary number. First prove T was not decreasing and then used the relationship between n and n nod and the unwinding to develop an inequality that contained T(n) on one side of the unequal sign and n on the other side. In this way, we could find out both the upper bound and lower bound of a function.
After professor's Heap's explanation, I found I got a better understanding of how to develop the upper and lower bound for a function. Asking questions to professor helps a lot. He can always explain things well and he is very patient. ^_^
2012年10月14日星期日
Feel much better for Structual and Well-ordering Induction
The midterm test made me feel I need more understanding in Structural and Well-ordering Induction.
I googled on line but could not find much useful explanation. But luckily I remembered we have a discussion board. I went to the discussion board and found with no surprise that I was not the only one who did not understand Structural and Well-ordering Induction well. In the specific tag, somebody provided a pdf that explain Structural and Well-ordering Induction. I opened the file and as I read through, I found this file very helpful. It solved my problems that when should I use Well-ordering Induction and also explain the difference between Structual induction and Simple Induction. To my undertstanding, Structural Induction could use Simple Induction as an approach to prove things. If we want to prove something that has a specific structure, we could use Structural Induction.
Well-ordering Induction is more likely to use during a provement. It does not like Simple Induction or Complete Induction that have a certain format, it is used as a part of the provement. I remembered professor Heap said it is more often used in the material we are going to learn in a few weeks.
I googled on line but could not find much useful explanation. But luckily I remembered we have a discussion board. I went to the discussion board and found with no surprise that I was not the only one who did not understand Structural and Well-ordering Induction well. In the specific tag, somebody provided a pdf that explain Structural and Well-ordering Induction. I opened the file and as I read through, I found this file very helpful. It solved my problems that when should I use Well-ordering Induction and also explain the difference between Structual induction and Simple Induction. To my undertstanding, Structural Induction could use Simple Induction as an approach to prove things. If we want to prove something that has a specific structure, we could use Structural Induction.
Well-ordering Induction is more likely to use during a provement. It does not like Simple Induction or Complete Induction that have a certain format, it is used as a part of the provement. I remembered professor Heap said it is more often used in the material we are going to learn in a few weeks.
2012年10月10日星期三
First English Bolg
Let's talk about something else apart from study ^_^
First English blog! Wow~ very interesting!
I am very happy to share my CSC236 learning experience
with everyone here. I wrote blogs before but it was not in English ( it was in
my native language haha~), so actually this is my first English blog and it
sounds like a challenge to me! I will keep wrting up things so that we can exchange
our learning experience here~
I finally finished my first CSC236 term test
this Wednesday. How does everybody feel? I think it was not very hard but I
think I need to go over more about structual induction, since it is very like
simple induction and I was a little bit mixed. I think I am ok with simple and
complete induction but I need to work more on well-ordering. I can understand
the principle but I don't know how to use it to solve problems. What I plan to
do is to read the course textbook and google is always there to help~
Hope I
can get a better understanding soon~
Hope everyone has a nice sleep.
2012年10月6日星期六
Midterm 1 is coming!
Up to now, we have learnt Simple Induction, Complete Induction, Structural Induction and Well-ordering Induction.
Simple Induction and Complete Induction was not so hard for me, actually I found they were easy to understand. But Structual Induction and Well-ordering were not so clear to me. I could understand the class material but I was confused about the application. When and where should I use Structural or Well-ordering Induction?
The first midterm test is coming and I was a little bit nervous since it is the first test in this course. I didn't do well in CSC165 so I was alway careful and tried to understand all the course notes in CSC236 and hope to get a better grade. I think I am going to read through the textbook and try to make every point clearer.
Simple Induction and Complete Induction was not so hard for me, actually I found they were easy to understand. But Structual Induction and Well-ordering were not so clear to me. I could understand the class material but I was confused about the application. When and where should I use Structural or Well-ordering Induction?
The first midterm test is coming and I was a little bit nervous since it is the first test in this course. I didn't do well in CSC165 so I was alway careful and tried to understand all the course notes in CSC236 and hope to get a better grade. I think I am going to read through the textbook and try to make every point clearer.
订阅：
博文 (Atom)