Time to wrap up

Time flies so fast! Three months has passed and it is time say goodbye!

Before leaving I just want to check what I have learned in that course:

Induction (mathematical, complete, structural and WOP)

Time Complexity for recursion (involving closed form, Master Theorem, etc)

Correctness proof of a program (formally check whether an algorithm is correct)

Automata theory (regex, DFSA, NFSA)

So far I can know lots of things about an algorithm by using what I have learned

from this course. Also the formal language section guides me to know the very

basic concepts about a programming language.



Regards

Problem-solving episode

I found an interesting math problem to share.

This problem is a fundamental illustration of mathematical induction, but it is still a bit tricky.

"tromino" is an L-shaped object consisting of three squares of the same size.
Consider a 2ⁿ X 2ⁿ square. If one of the smaller squares is removed from a corner of the large square, the the resulting region can be completely covered by trominos.

I will try to use Polya's method.

Understanding the problem
Known: the square (size, shape) need to be covered
Unknown: I must discover whether trominos can cover that square

Devising a plan
It seems a bit difficult at first glance, but I notice that the problem deals with a natural number n, so the idea of induction may help.


Proof
I carry out my plan using mathematical induction.
Base Case: when n = 1, the region after removal is exactly a tromino. So the theorem holds when n = 1

Induction Step: suppose when n = k, the theorem holds, so the 2^k X 2^k square region after removing the corner can be covered by trominos. Let me examine the 2^k+1 X 2^k+1 square. It should be like this:

Then we can put a tromino in the middle


















And we can obverse the region can be divided into four 2^k X 2^k medium-sized regions as illustrated:
















By induction hypothesis, those four regions can be covered by trominos, and the three small blank squares can be covered by one tromino, so the whole region can be covered by trominos as well. so the theorem holds for n = k + 1. By MI, we know the resulting region can always be covered by trominos.

Looking back
After looking back, we find that without a plan of using induction, it will be very difficult to come up with a good idea to strictly solve this problem. So it is a good idea to use Polya's method when solving tricky problems.

Formal Language and Automata

Formal language is largely different from the previous chapters, except the frequent use of induction. DFSA is a way to describe a language, and it is also of great fun because it reminds me of the puzzles I solved when I was in primary school. I think devising a DFSA is not difficult, because what you need to do is simply draw "0" lines and "1" lines and connect circles with those lines. But proving DFSA is a different story, for you must follow the format in the course notes like finding state invariants. Also problems related to DFSA can be very hard sometimes, the question 1 in Assignment 3 is not funny at all. I spent almost a whole week on that problem and finally got a right answer before the due time. I think automata will be a important part for the final exam, so I must work hard on that section. And no matter how hard the final exam would be, I must stay calm (just as the guy below) and try my best to conquer that.

Correctness--the most tedious part

I have to say proving correctness is the most tedious part among this course. It involves lots of formats and conventions, and we have to remember and even recite those stuffs in order not to lose marks.

I have already read the textbook and made a summary about how to cope with questions concerning proving correctness.

There are two types of questions according to the textbook and the lecture notes: correctness on recursion and correctness on iteration.

For the first type of question(example: binary search), we need to state the precondition and postcondition at the beginning, and then i> prove partial correctness of BinSearch ii> prove termination of BinSearch.

For the second type of question(example: integer power of x), we also need to state the precondition and postcondition at the beginning, and then i> prove partial correctness of intPower ii> prove termination of intPower iii> derive the invariant in intPower.

I think knowing an outline of the whole solution can help us deal with those problems quicker and better.


But when I was trying to finish Assignment 3, I found my outline for solving the second type of problems did not work properly. So I had to derive a new guideline for solving the assignment problems.

When you get an algorithm and figure out what precondition and postcondition are, the next thing you must do is trying to figure out (largely by observing) the loop invariant after ith of the loop, and then using induction to prove it is correct.

After that, you must prove partial correctness, that is, assuming the program terminates, the final state (simply call it state after kth iteration) exactly meets the postcondition. In other words, It means if the program halts, the output is exactly what it is supposed to be.

Then you need to prove termination by proving the sequence of a certain variable (usually the variable determining the halt condition) is decreasing, then by WOP the whole program terminates.

Finally you can simply state that putting them together we get correctness (cheers!)

That is a better outline, and I think any correctness proof should follow those steps. I will remember it and use it adroitly in the exam.

Term Test

I did not do well on my term test because I did not find the correct close form for T(n) in the first question. The first question states that we only need to consider n = 2(k), so I just did the unwinding for T(2(k)) instead of T(n), and forgot to modify that n for split and recombine. Because of that mistake, I finally got a n-cube closed form and could not go on my induction proof. In a word, I got totally wrong in the first question and there are only two questions in the test. What a pity!

 Anyway, I should not be sad because there are still an assignment, a slog and a final test ahead of me. I have to work harder and harder afterwards. Also my review strategy needs to improve since I focused mostly on course notes but did not work on tutorial problems that much.

 I also went to the office hour this afternoon to ask some questions encountered in the review, for example, I did not quite understand how to solve the closest pair of dots problem.

Now I know that I should check all the dots in the neighborhood of the vertical partition line and compare those with the minimum of the left region and right region (those have already found by recursion). Moreover I got a better understanding on the multiple binary string problem.

 This week the course will be all about correctness, so I will work hard to learn it well.

Review of Big O notation using Wiki

I have to admit that I didn't learn well in csc165 course, so as the course going on, I found it necessary to do some reviews on the 165 stuff. When the professor mentioned Master Theorem, I thought Big Theta was lower bound, so I was totally confused about the stuff derived from that Theorem. So after class I looked up that concept using Wiki and found that Big Theta is both the upper and lower bound, namely tight bound. Then I suddenly came to understand the idea of Master Theorem: using that theorem you can know exactly the time complexity of Merge sort or other divide-and-conquer problems. Also I reviewed other stuffs such as Big Omega so that I could understand the course material better.

 Wikipedia is a good reference for students. Since I am interested in computing  discipline and algorithm, I often browse on Wiki to get something useful. For instance, when I looked up Big O notation on Wiki, I noticed a sentence in the introduction: "In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size." Initially I thought why people need algorithm was because people need to handle very very large input n by using a very very advanced billion-calculation-per-millisecond computer, but now I realized that very basic thing about computing algorithm. I have already done the review of 165 stuff, but I will definitely do some preview or optional reading using Wiki.

Time Complexity

I still do not quite understand time complexity stuff in Friday's lecture, especially the slides below. I will try to figure out as soon as possible on weekdays.

Now I understand all those stuffs after finishing Assignment 2. First, n stands for the input size, and we need to use divide-and-conquer method to find the time complexity of this algorithm. For simplicity, we assume n = 2^k,and we can easily get the time complexity for that certain input. The calculation for n != 2^k needs more work and we must use other tricks (like sandwich theorem) to figure it out.