Week 13 - LAST WEEK!

Wow time does fly by fast, 13 weeks passed by like the blink of an eye. This week, we had our very last midterm test. The first question on DFSA took me quiet a while to figure out due to the typos of the question, and also because I kept on making stupid careless mistakes when transiting between the states, which resultted in a different answer every time. Overall, I found the test was relatively easy.

I also took a look at the sample solution of assignment 3, if nothing major came up, I think I should've got a pretty good mark on it! ^_^

In the past 13 weeks, I sure learned alot. I really enjoyed this lecture with Danny, and I truely hope I can have him again as my prof for the coming courses~

Wish me luck for the exams~ =)

Week 12 - Non-regular Languages, Pumping Lemma

After spending weeks on the topic of regular expressions, now it's time to shift our interest to non-regular expressions. In order for a language to be regular, when the DFSA runs out of state, it has to repeat some of them, which is what pumping lemma was all about. Any language that can be shown to lack this "pumping" property is not regular, and to prove this, we use prove by contradiction. I haven't had a chance yet to pratice any of these non-regular expression questions, so I'll focus on this topic when I study for the final exam.


ASSIGNMENT #3

This assignment was okay overall. After spliting the questions with a partner, the work load was not too heavy at all. I went to the TA for help on one of the questions, and it didn't take me long to figure out the solution after given a hint. I am hoping to - and I really need to - get a good mark for this assignment. Other than that, I just need to remember to go through the questions my partner did, so I understand those concepts as well.

Week 11 - NFSAs, equivalence

Proving a design of DFSA is easy to do when breaking down to different cases and using induction. NFSA is more complicated than DFSA in the fact that each transition can take the machine to a set of states, rather than a unique state. So at least one of the states the automation could be in after processing x is an accepting state. For every regular expression, there's an equivalent NFSA, and for every NFSA, there's an equivalent DFSA, so this shows how the machine accepts complement, reversal, and intersection. The cartesian product gives an easier and directer approach for finding the intersection. There is an FSA for every regular expression, and we can also go the other say: there is a regular expression for every FSA. I still have not completely understood the concept of FSA, I will look into this topic further...


PROBLEM SET #6

This problem set took me longer to figure out than usual. The lecture example was quiet similar to this problem, but it wasn't clear to me at the beginning how I can apply the same concept to this problem... Now after I handed in my paper, I realized I only proved one way of the equation and forgot to prove the other way. Sigh, I guess I was over excited after I figured out the solution to half the problem and thought I was done.

Week 10 - Regexes, FSAs

DFSA (Deterministic Finite State Automata) is a machine with transition functions, it shows regular expressions for things like L1 AND L2. Its name scared me for a second, but designing a DFSA was not as hard as it seemed. For the questions we discussed in lecture, the state invariant was pretty easy to figure out, the transition function that moves the machine from the present state to the next state was quiet straight forward, then the sketch of the transition to different states followed with logic. I think I did something similar to this before for circuits.

PROBLEM SET #5

This is a very easy problem set, the question is almost identical to the example given in lecture. But it's good that it got me looking over the slides again to review what I've learned.

Week 9 - Formal Languages

A language is a set of strings, and a string is a finite sequence of symbols. Therefore, we can use set operation and string concatenation on languages. The complement, unions and intersections of two languages, L1 and L2, are all the same as set operations, so that is not too hard to follow. A new term that is introduced is the "Kleene Star", which I've never heard of before. But the concept behind isn't hard, it is just "all possible concatenations of 0 or more strings". Exponentiation and reverse are a bit more complicated, but they are not that hard to master either. The most difficult concept of the lecture came when we were to prove a regular expression. I followed the example in lecture closely, understood most of it, but I still don't get how it came up the conclusion. I will read the lecture slide and course notes over the weekend and try to figure it out by myself.


TERM TEST #2

I spent almost one whole night studying for this term test, but I didn't expect week 8's material to be included in it so I only studied up to week 7. The first two questions were all pretty straight forward, basically after reading it, I had a clue as to how to proceed. But for the last question on proving termination, I had no idea at all! Next time, I better not gamble on it. Should've studied everything up to the lecture before the test just to be on the safe side... =(

Week 8 - Iterative Correctness

This week, we have moved our attention from recursion to iteration (looping), which is also an implementation of repetition. But the difference is, for iteration, we are also checking that the loop eventually terminates with its work done. Termination means that there is some decreasing sequence of natural numbers, , where i is the loop index. Other than this, it contains pretty much nothing new. The proof procedure is still the same: using Simple Induction. I found no problems with this week's materials.

To continue with what Danny left on the Wednesday slides for the counter example:
Show that 7a(i+1) + b(i+1) = 7ai + bi - 1

Case 1: If bi != 0, then from line 5: b(i+1) = bi - 1 and a(i+1) = ai since a it is not modified anywhere. Therefore, 7a(i+1) + b(i+1) = 7ai + bi - 1

Case 2: If b = 0, so a != 0, then from line 8: a(i+1) = ai - 1, and from line 7: b(i+1) = 6. Therefore, 7a(i+1) + b(i+1) = 7(ai - 1) + 6 = 7ai - 7 + 6 = 7ai - 1 = 7ai + bi -1 (since bi = 0).


ASSIGNMENT #2

I wouldn't consider this assignment to be very hard, but due to the amount of workload from other courses (midterms, projects, etc.), I was not able to start on this assignment until one day before the due date. With help from the TAs, I solved all the questions with no problem. However, I couldn't finish typing out the final copy before 10pm. I left out question #4 unfinished, and this is really going to kill my mark. I assume at least 20% will be deducted... Now, I regret so much on how I wasted my time earlier. Even half an hour more would be enough to save this 20%. =(

Week 7 - Program Correctness

Recursion can get me very confused at times, it usually takes me long to figure out how it works. The theory of it isn't hard, it's just when it's applied in a function, I sometimes can't get myself out. I know this means that I need more practice on it. When writing a recursive function, I often can't see how the problem can be broken down into smaller problems to use for base cases, but I'm much better with its proofs since it's basically 'proving by Simple Induction'. Now, I feel like this course is going to help me alot when I write programs... it's not just about proofs afterall.


PROBLEM SET #4

I didn't have any problems doing this week's problem set at all. This problem was an easy one. All it needed was using logics and breaking the problem into smaller problems so that it can be proved using induction.

Week 6 - Complexity of Merge Sort Master Theorem

I was never good with sorting in first year, especially merge sort. Now that it's being touched on again, I think I should spend more time on it this time. Merge sort is an instance of a general strategy: divide up a problem into subproblems of the same type, and then combine the solutions to the subproblems. The "smallest" instances of the problem can be solved directly. This is a useful strategy, and it sounds similiar to the principle of induction. But overall, I was quite lost during this lecture, it's time again to do some studies at home.

I also received my test back this week... very shocked by the speed of marking. I was VERY disappointed with my test result however, I thought I did pretty well. But it turns out that my careless mistakes killed me hard. I lost tons of marks on what I thought was the easiest question... This test has definitely rang a bell: be more conscientious next time! Though I think I will be asking for a remark, the almost 30% deduction was too harsh for a careless mistake.


PROBLEM SET #3

After unwinding the function, I couldn't find a pattern to make a conjecture about a closed-form for it. This question seemed very hard until my friend gave me a hint as to what the pattern is. It wasn't obvious to me at all. What if the same question comes up on the test and I don't have all that time to look for a pattern? Or what if I get totally stuck like this time? Maybe doing more practice problems will help.

Week 5 - Closed Form of Recurrence, Structural Induction, Gcd

The closed form of recurrence seems really confusing at the beginning due to all the complicated symbols, it took me quiet a while to figure out. But once I got the hang of it, the technique was not too hard to apply at all. The next topic, defining sets with induction, is not that hard either. The definition itself gives a hint as to what base case to use and what assumptions to make when doing induction proves.


TERM TEST #1

Overall, I think this is a very reasonable test. It was similar to what I have expected based on the past midterm. All three questions were about induction, and I don't think they are too difficult to solve. After finding out about the base case, the prove seemed very straight forward to me. I think I can expect an A from this test.

Week 4 - Recursive Definitions

In short, recursion is just a special case of naming. When a definition includes the name we give to the entire definition itself, we have recursion. This topic is not a hard one, though sometimes it is not easy to find the pattern when unwinding. Other than that, I just have to be extra careful when defining a function, not to miss out on any cases and make sure it is a recursion based on previous elements. The topic on time complexity is the one that caused most trouble for me this week. After reading the slides over and over again, I still can't seem to understand how to calculate the time complexity of a function. For this, I am going to ask for help from some friends, and if that doesn't work, I will go talk to the TAs next week.


ASSIGNMENT #1

Also, this is the week that assignment 1 is due. I was expecting the assignment questions to be on the same level of difficulty as the problem sets, but I was wrong. The first question was ok, but the second and third question took me quiet a while to figure out. I was stuck on figuring out a general technique for making the lunch menus for a long time. The TAs at the Help Center were a great help. They made the question look so easy. I guess I was just thinking too much.... Oh, one other thing, I didn't start looking at the assignment sheet until the weekend, and I found it pretty rushed to get all of the questions done. I didn't hand in the assignment until the very last minute. For next time, I'll know to start working on assignments early, not going to leave it to the last minute again.

Week 3 - More Principle of Well-Ordering Equivalence of Induciton Flavours Traps and Tricks

This week's lecture started off with the comparison and connection between Principle of Simple Induction, Principle of Complete Induction, and Pricinple of Well-Ordering. It could be seen from the proofs that there was a cycle of implication between these three principles- if you believe one, you must believe the other two. Before the lecture, I didn't know how PWO was connected with the other two, but now I clearly see a connection between them. It was nice to note these connections, as now we could refer to all three principles when doing proofs. The next topic, bases larger than zero, I didn't have any trouble with. It was similar to the material from the previous two weeks except that the base case could be changed to any number. The induction step still remained the same.


PROBLEM SET #2

This week's problem set is bit harder than last week's, but still manageable. The lecture slides weren't a big help this time, but the textbook was. There was a similiar example on the textbook, and after consulting the book, the problem didn't take me long to solve. It just took me a while to realize that we are supposed to substitute in a specific number for N before proving it. The try and error part of this problem to find N took me the longest time.

Week 2 - More Induction Flavours

Complete induction is very similiar to simple induction, except that for simple induction, we assume p(n) is true to show p(n+1) is true; whereas in complete induction, we assume p(0)... p(n-1) is true to show that p(n) is true. However, I find complete induction more challenging than simple induction, this might be due to the fact that I was exposed to simple induction more and complete induction is still a new concept. The theory behind the two method is the same, they both require base cases and an induction step. I guess one other challenge at this step right now is trying to figure out which method to use (either complete or simple). To get used to it, I will look more into complete induction, read the textbook pages for this topic, and do some exercises on both methods to see in which case should use what.


PROBLEM SET #1

I find the first problem set not that challenging to solve. Both questions are similiar to the examples given in class. After reading over the lecture slides, it didn't take me long to crack the problems. I think I'm getting more comfortable at simple inductions now. Just hope I can always pick up the materials of the course this fast.

Week 1 - woohoo~

Here comes another exciting school year with computer science. woohoo~! As the course code gets larger, the course is got to be harder as well. But I'm glad to have Danny as my prof again, he makes everything so much easier to understand. =)

Looks like this course is a continuation of 165, it's mostly about writing proofs. First week's lecture is not too deep yet, it's more like a review of last year's materials on simple induction. Instead that this time around, we don't have to follow that annoying format anymore. This is such a big relief for me, I remember last year, I spent so long writing everything following the strictly defined structure.