Week 13: Last week of class

December 5th, the last day of class for the fall semester. We had our exam preparation and a handout on Weds from Danny with all the topics that we should be studying for the upcoming exam on Weds. The test today was better than term test 2 for myself and hopefully we'll know where we're standing before our exam as soon as the marks are posted. Before ending my post, I was thinking about this example of context free grammar I came across the other day:

Let L₃ be the set of algebraic expressions involving identifiers x and y, operations + and * and left and right parentheses. Then L₃ is a context-free language. For the following context-free grammar G₃ = <>3 , ₃, S , P₃ > generates L₃ :
V₃ = { S } , ₃ = { x , y , ( , ) , + , * } and P₃ = { S -> ( S + S ) , S -> S*S , S -> x , S -> y }

Reference: http://www.cs.odu.edu/~toida/nerzic/390teched/cfl/cfg.html

I'm just curious how P3 = all that chunk? If Danny is reading this post, please give me some feedback, thanks!

Anyway, just wanted to take the chance here to thank Danny for being such an amazing prof for both of my 165 and 236 course. I wonder what courses will be taught in the winter term by Danny.

Weeks 11-12: NFSAs/Pumping Lemma + Non-regular Language

Again, I'm writing a blog for 2 weeks, which is pretty bad as of the blog requirement. I will definitely write one for the last week of class! Looking back to week 11, we dealt with a lot of problems of NFSA and the new concept of the Cartesian product that was used in dealing with one of the problems for A3. There was indeed some confusion and difficulty when combining the two machines, binary string of odd length and multiples of 5 into one huge machine. If I remember correctly, I had about 16-18 states to list out. But the lecture material really did help in clearing up how to write up the Cartesian product of the delta function, accepting and starting states. Danny also went through a few examples showing how there is a regular expression for every FSA. However, I run into problems of choosing which state to remove first when trying to express the FSA to a regular expression.

We started off week 12 looking into the pumping lemma and proving it. Unforunately, the projector burned out again during lecture and everything was done on board. We were also introduced to grammars that contained productions and states denoting a language. Perhaps more examples can be found in the textbook. If possible, it would be great to see lectures posted from the evening class for revision of the test on Friday.

Week 9-10: Formal Languages and DFSA

It's been 2 weeks since I've writing a blog.. I know we should be writing weekly, but I tend to easily forget with all the assignments in MAT, CSC207 and all. Well, test 2 was handed back in Week 9 and it wasn't as good as I thought it'd be. I lost some marks on Q2 and I really didn't have time to finish up Q3. By the time I thought of an approach, the time was up. I guess I'll be having this test to take the least weight of all assignments and test. More intense studying will be needed for test 3! Formal languages and regular expressions were introduced and both of them are brand new material. I still have to get used to remembering all the possible operations of *, +, ? and this is definitely a problem when it comes to doing A3.

DFSA was the core material learned in week 10 and the drawings of the machine with arrows and circles doesn't seem to complicated at the moment. However, when it comes to submitting assignments in text file without the drawing, that will definitely be an issue for me. If only we could submit the picture somehow, then life would be so much better. We also looked into the intersection of languages, which is quite hard to express using regular expressons. I wonder how the DFSA questions will be on the upcoming test 3.

Week 7-8: Program Correctness and Termination

The use of iterative and recursive functions are widely used, but rarely do we prove that a program is correct and produces the correct output for every passable input by some sound argument. In week 7, we looked into the proofs of how preconditions and executions implies the postconditions. When we assume that a program is correct, some assumptions are made and we believe they must be true for every computation at the end of each iteration. This is known as the loop invariant and by stating this, it certainly helps me in understanding the iterative algorithms as a coder and reader. It's important to establish the loop invariant, as well as maintaining it before we exit the loop. In A2, it was definitely some challenege to prove that m = int(mat.sqrt(b*e)) actually worked for binary search, compared to m as the midpoint of the left and right. If m was correct, then indeed everything else would flow. Otherwise, it would be necessary to disprove by a counter example for its program correctness.

The above elements only checks for partial correctness of a program. To further develop a solution, we must also show that the loop terminates at a certain point of the loop. This is known as termination, which we looked at in week 8. I have a feeling it's going to be something big on the upcoming test and I should review more on the material of termination and correctness in the textbook and other examples online.

Week 5-6: Closed Form, Merge Sort

Just got my test back on Friday morning and it was definitely lower than what I had expected. But the class average was actually pretty solid, in the low 70s range? I was really satisfied with my assignment and thought I'd go in to the term test doing alright. Looks like I'll be needing to do more induction problems and solve quickly within a time limit. The subset question sort of threw me off. It was similar to the question we had in class of 2^n subsets, but to me, I thought this one required much more thinking. The base case was rather easy to develop and show how if n was equal to 2, the subset {1,2} would omit either one of the elements or both. However, in the induction step, it didn't come to mind of using partition and the constraint of n+1>2. Luckily I had some partial marks for the base case and the general structure. Although I still lost marks on the the other 2 test questions, I found them pretty fair.

Starting into Week 5 and 6 with closed form problems and merge sort, I kind of struggled with problem set 4. In the unwinding progress, I ended up with 3^n + 3^n-1 + 3. I had problems figuring out what the constant would be because in my case, it always varied. Will more problems be posted on unwinding? I'd like a lot more practice in preparation for the 2nd midterm. Exploring mergeSort was what we focused the past week and the logic again seemed pretty straight forward. However, I'd probably need to enhance my algebra skills to prepare for more upcoming divide and conquer concepts.

Time to start writing on paper for A2! The 4th question from A1 still remains unsolved, since the drawings of the trees are just getting more and more messy..will there be any hints on this problem?

Week 3-4 Fibonacci and RecBinSearch

It's been almost 2 weeks since I've written on this page with all the assignments and projects going on in other classes and in CSC 207. I just checked the mark for assignment 1 with my partner and we're both very satisfied with the mark. It really does reflect the effort we've put in and much thanks to the TA's at the TA centre and Danny for clarifying several parts of the proof structures. Hopefully I continue to remain confident and study hard for the upcoming test this Friday. There are indeed a few worries on my mind right now, especially the material from week 4. On the surface, the concepts of Fibonacci numbers aren't hard to grasp. We've explored it before in CSC 165. But, the unwinging zpf problem that we did together in class is a question I don't understand completely at the moment. I'm not exactly sure how the coefficients are calculated in each of the rows of T(n). Do we have to guess the general equation of the function for the unwind zpf(n) as well as the RecBinSearch question?

Week 1 and 2- Simple and Complete Induction

The first week of lectures on simple induction was pretty much a review of CSC 165 for myself. Again, we had to work around the problem and search for solution insights in order to move on with the proof structure. The base case of P(0) was revisited and the induction steps were further explored with different cases. I'm glad to hear that the proof structure is much more relaxed as to CSC 165, where the indentations had to be clear and the lines had to match with one another. Despite of that, the course seems to be much more loaded with 3 assignments and problem sets on top of that. The problem sets is really a revision of what was learned and is more of a modification of problems that were done in class. With them done in advance, I believe it helps in tackling the problems in the assignments. Hopefully the TA's won't be too harsh on the marking scheme for both.

Problem set 2 was quite similar to a problem that was done in CSC 165, with the difference that it now had to be proved by complete induction for the postage stamps. Although part a took me a while to write down quite a few of the possibilities of n>k, it was pretty doable. As for part b, I'm thinking to use contradiction as a solution to the problem. I have yet to flip through the pages of the textbook to refresh my memory of a contradiction proof structure.

Assignment 1 is due in just around 7 days and I've been thinking on all of the problems. Problems 1 and 2 makes a lot of sense to me and it's the proof structure that I'm struggling to write up with. Even if I'm able to come up with a differnet menu for the eight combinations, how do I put it into a proof structure? The TA hours on Mondays and the CSC help centre will defintely be a great aid for me to clear up the questions that I have right now. It's also good to hear that the assignment can be done in pairs and not alone because it really helps to have someone to work with. I'm looking forward to meet Danny again at the office, when there's less people outside the door.