More about A3

After taking a look at the sample solution for the A3, I find some mistakes in my own answer. For the first one, i didn't make my contradiction clear as it showed in the sample solution. And it is kind of tricky to come up the idea that add i's 0 at the end of the two strings whose ith bit are different.

For the A3

Although the handout A3 had been posted since last week, i am not working on it until yesterday. Unfortunately, this one is much more challenging than the previous 2, maybe because the professor didn't talk about much examples in RE and correctness, the proof for these four question is longer and harder. But if i read the course note before i doing this assignment, it would become much easier. Anyway, it is my first to read the course note,because i don't know how to find it before this assignment . The problem is when i saw these questions, "Holy crap, How should i know the proof for the state invariant, and what does the first question talk about."

Anyway, I finished this assignment before it was due, but I don't trust my own answer to these four question.

About Test2

I got my test2 paper back last Friday, the mark is much better than I expect. Actually I think this one is pretty easy,since these two question in the test had appeared in the handout of tutorial and the assignment2. However, it seems that the whole class did not do well in this test and the professor decided to add 3.5 point on our original mark, which is more than 20% of the test. How kind it is!
The instruction for Assignment 3 had been posted, I will  do these questions in this week,and post some of my solution later.

Keep going

On Monday of this week, we had the term test2 for this course.There are only two questions in this test.In my opinion, it is supposed to be an easy task. However, I spent nearly all of my time doing the first question, because I made a mistake when I unwind the formula to find a close form.Of course i got a wrong answer but didn't realize it until the test was end. There must be something wrong with my mind during this test, how can i make mistake on the question which is almost similar to the one we have in the tutorial.
For the question1:
When we deal with the situation that n = 2^k, T(n) can be written as T(2^k) = 4T(2^(k-1)) + 2^k, and keep unwinding we have T(2^k) = 4^k + 2^k(2^k - 1) so T(n) is obviously equal to 2n^2 - n, and this form can be proved by induction.
For the question2:
When we got the upper bound and lower bound for the formula it is easy to find a B when m>B,the inequality is true,but i don't sure whether we need to prove the result by induction.
Anyway, this course is not hard for me, i think i can get a good mark on the final exam.

More complexity

From last week, the course materials began to concentrate to the sort method, figure out the upper and lower bound for each sort method. After attending the tutorial on Monday, I know how to deal with this kind of problem now. N is supposed to be a product of 2 or 3, so we can rewrite the function and unwind it for a more clear version rather than a recursive method.

Time Complexity

Last week, we have the first term test of the CSC236 course. It was easier than I though, or because i am comfortable with the induction proof which i have learned a lot in the MAT137 course last year. Then after the test, we come to a new part: time complexity. Although the induction is still the tool to prove this kind of the problem, i didn't catch the professor's idea.How could we figure out that the time complexity of the binary search is O(log n) ? The python code is also confused, what "e" and "b" stand for? Moreover, what is the "unwinding"?

Tomorrow i will have a tutorial, and TA will talks about the exercise questions on the handout,so it is a good time to learn how to deal with these kind of problems. And a new week starts again.- -

CSC236 SLOG

This blog is used to record my academic life in UTSG, as well as a course blog for CSC236 in 2012 fall.