Week 12: Eliminating states and deriving Regular Expressions and A3

This week we mainly learned about how to derive a Regular Expression from a DFSA, the process is interesting. It's amazing that after several steps of eliminating states when only the starting state and the final state left, we can easily derive a RE by just doing some combination. That's where I found the magic! The lecture material and the tutorial material are easy to understand this week.

Our final assignment (A3) was submitted this week. It was much harder than the assignments before. Mainly because it involves a lot of proofs and more open to creativity solutions as we were asked to write and prove our own algorithm. I like the creativity work, but I do hate to type all those symbols! And Microsoft Word is really awkward to draw DFSAs!

And this is the last week of our day section, since there are no lecture on the week (the virtual week). I finally realized that time flys so quickly. And I've nearly completed my first term at UofT. Now my opinions are: UofT is a good university, it pushes us so hard that we do learn a lot! And Danny is a really nice professor, so patient and kind!

Thank you professor, and thank you my classmates! Hope all of us will do good in final! Fighting!

Week11: Regular expressions Proof and NFSAs

The week we first studied regular expressions, it looks like an extension of formal languages. Again, it's not hard, just treat them as special sets and do some sets operations. What I found interesting and new is  the process of proving a regular expression. I didn't expect it to be a mutual proof (we need to prove both L is the subset of L(R), and L(R) is a subset of L); I had thought that we only need to prove L(R) is a subset of L. Then I realized that I was wrong, simply proving one way doen't mean L is equal to L(R). But the process seems to be a little bit tricky and made me feel that it's just playing with English in some parts.

Then we started to draw some NFSAs. But by now, I still don't know what is the point of drawing NFSAs, since they can't tell anything meaningful to me. But the professor said there was some magic between DFSAs and NFSAs, but I didn't really catch what the magic is. :(    It seems that we'll discuss more on this magic next week.

Here are my lecture notes:

Week 10: Formal Languages and FSAs

This week, we finally finished dealing with all those abstract concepts and starts to do something easier to understand to me -- the formal languages and FSAs. For the part of formal languages, I regard them as special sets. All we need to do is just some operations on sets. Since I did a lot of sets operations and analysis last term in my previous school, this part is just the second easiest part to me in this course (the easiest part is the early part about simple and complete inductions). Then The DFSAs are very similar to what we are leaning about transition matrix in STA247. It's just a process of drawing the transition matrix into pictures.

As a result of the long weekend, the pace of the day section and the night section switches. Thus we have to do our quizzes on new materials as soon as we finish our lectures since this week. The feeling is not good, we have to really concentrate on the lecture so that we can make it in the quiz. There's no time to review before quiz! (Fortunately, for this week's quiz, we just need to draw a DFSA, which is not hard.)

Here are my lecture and tutorial notes:

Week9: Partial Correctness & Term test 2

As expected, we discussed more on correctness this week. This time, the goal and the point of proving correctness are more clear to me after I studied the past term test 2, and there was a problem asking you to prove that a program terminates and the postconditions will be met (Though later I found out that it is a topic that we hadn't covered before this thursday). It makes sense that we should use some method and find some loop invariants to prove our program will meet the postcondition and terminate. It helps us to make sure that our program is correct and will terminate.

The part I didn't quite understand during the lecture is the process of deriving conditions from pictures. Because I was absent minded for a while, and when my mind came back, I couldn't figure out how the pictures were derived, namely I didn't know what the problem is! Then I asked my friend after lecture and reviewed the slides (I didn't find corresponding part in the textbook), I thin it's just another example of proving an iterative program, but expressing with some pictures to help understand.

We had out term test 2 this week. I had been worrying about writing Python code in the exam (because I didn't learn Python before), but it turned out that the test was easier than I had expected and didn't involve programming.

The lecture note for this week are as follows:

Week 8: (Precondition + Termination) => Postcondition

I had a strange feeling after finishing this week's lecture: I did followed up with the pace of the lecture and understand what the profesor was proving, but when I think back of the lecture, I can't speak out what I learned. It's like that we first use our common sense to find some preconditions of a code, then we figure out what the code is doing and that would be our postcondition. Then the process of proving the correctness of the program just seems like we first assume the postcondition, then we just go through the program again while applying some induction to analyze the program.
But I just don't know what is the point of doing this, it seems like that we first analyze the program and get to know what it does, then we analyze the program again but using a more complicated method.

Maybe I need a discussion with someone or wait to see if the professor will tell more next week.

This week's tutorial seems different to me. We did some practice on writing divide and conquer algorithms, as I haven't learned Python before, my code just looked like a combination of C and Python :(  Fortunately, the grammer doen't matter. Then we did more practice on Time Complexity and Master Theorem, a little bit hard but was very helpful to understand the lecture materials.

Week 7: Divide and Conquer & Master Theorem

Just as I guessed last week, we did go into further details of Master Theorem. But as I didn't review the lecture notes and the textbook this week, I fount it still hard for me to really understand the Master Theorem. But this time it is the TA that helped me a lot. I asked him about the master theorem after the tutorial, and he really caught my points and make me understand the master theorem in words! I was just confused about those abstract parameters for Master Theorem.

We also studied more on the divide and conquer method. At first I was confused again about the meaning of the term, thinking that it would be something new. But later I just realized that we have already used this method a lot. It just the philosophy of using method like recurrence to divide a big problem into several small problems and solve them separately then recombine the results.

By now, we have practiced a lot on time complicity, and I'm now quite familiar with the terms like upper bounds, big-oh etc,     :)

Practice makes perfect!

The lecture notes for this week is not well organized, thus I decide not to post it.

Week 6 : More Time Complexity, Unwinding and Master Theorem

We covered a lot of things in this week's lecture. But as I've made up the background knowledge that I was missing. I managed to catch up with the pace of the lecture (Again, thanks to Jason and Harry!).

First of all, we discussed more on Time Complexity on trying to calculate the upper bounds of recursive binary search. As we encountered trouble using the method we did to calculate lower bound, we applied another method, which to me is very similar to the former method, but just more tricky.

Then we learned to use Unwinding to analyze questions involving recursive definitions. Since I have done this a lot in my previous school (like analyzing Fibonacci Sequence), this is not hard to me. But I didn't quite catch up with how to prove the recurrence of binary search is non-decreasing. Then I read Lemma 3.6 in the textbook, it explains very clearly.

Later, we were introduced the Master Theorem, I found it really abstract and hard to understand. But since the professor didn't go into much detail, maybe this topic isn't that importan or we may go for the details later.

This week's lecture notes are as follows:

Week 5: Time Complexity & First Test

This week we studied Time Complexity, mainly about the method to estimate how much time a program would take to do a job. This lecture seems to be a disaster to me, because the methods involved some techniques and terms that I had never heard of while all my classmates have learned them in CSC165! I even didn't know what the terms "lower bounds", "upper bounds", "big-oh" and "big-omega" mean! I just tried my best to follow the lecture.

 I do need to thank a lot to two of my new friends Jason and Harry! Jason is my classmate in CSC236, and he taught me about the concepts of those terms after class. Harry sent me some lecture notes of CSC165, so that I can refer to when I found some background knowledge missing. Just as the old Chinese saying goes: "You have to depend on your parents when at home, and you have to depends on your friends when away from home!"

We also had out first term test this week. And it was my first term test in UofT. The difficulty of the term test is appropriate. Again, if you attend all the classed and do some exercises, this won't be a problem.:)

I didn't take much note on this week's lecture, because it was already hard for me to catch up with the pace. But I did set down the meaning of Big-Oh and Big-Omega in my note. :)

Week 4: Structural Induction & Assignment 1

I feel really guilty that I fell asleep during this week's lecture. So I learned this week's material mainly by self study, reading the annotated slides and the textbook.

Through the process of self study, I find a tip that I'd like to share with you guys: read both the annotated slides for Thursday and Friday. I found that the first part of the annotation of Thursday's slides are of higher quality than Wednesday's slides, but the second part is of lower quality than Friday's.

Also, I did talk to someone and made some friends this week -- some other guys who are also from China. I found that it does help if we discuss questions in our mother language, though I know that I need to speak English as more as I can. But this seems to be an issue that I need to balance some time.

What's more, we handed in out first assignment this week. The questions were mainly on proving statements using Simple Induction or Complete Induction, not hard. And I just realized that if I attend all the lectures and tutorials and do some exercises, then the quizzes and assignments won't be a big problem.

At this point, my fear of this course has already gone.  :)

Since I fell asleep during the lecture, I have no notes to post here. :(

Week3: Well Ordering

This week's topic was focused on well-ordering. First of all, the concept of well-ordering was introduced and proved. Then we had some examples on proving some statements using well-ordering.

The concept of well-ordering was new to me. And I was a little bit confused about the concept at the lecture. Though I can understand all the examples, It wasn't clear to me what exactly the concept of well-ordering is. Furthermore, I didn't know for which part of the examples, the principle of well-ordering was applied.

My approach to find out the answer was to read the text book and lecture notes. After doing the reading and looking back at all the examples. I just realized that all I need to remember about the principle of well-ordering is that "Every none empty subset of N has a smallest element." Just that!

Also I wanted to ask some of my classmates. But at that time, I simply didn't know and hadn't talked to anybody. So I realized that maybe the first step that I should do was try to be brave and speak out and make more friends.

This week's tutorial was focused on Complete Induction. Though the questions on the hand out were not hard. I had difficulty to finish the quiz in time, because I wanted to add some creativity and try a new method rather than the one presented by the TA. But later I regretted that I should try my creativity work after class, not during the quiz!

Quiz 1 was returned this week. Though I got full mark, I made a mistake in the predicate.
My predicate looked like this:
P(n): For all n belongs to N, blah blah....
Here I shouldn't use "for all", it made the predicate too strong.

My lecture notes are as follows:

Week2: Complete Induction

Week 2's material was mainly focused on Complete Induction (Or we can call it Structure Induction). This topic was as expected as we discussed about Simple Induction in week 1.

This week's material was also not hard, and it made me feel more confident in this course. But there're still something new and interesting to me that we leaned to apply induction to prove problems with trees. I just learned the tree data type before I came to UofT (we learned to deal with trees using Haskell) and it's fun that we can use induction to analyze trees. Furthermore I leaned a new concept "full binary tree" that every internal nodes of the binary tree has exactly 2 children. And we did an example to prove that every full binary tree, except the zero tree, has an odd number of nodes (I set down the proving process on the second page of my notes).

Also we had our first tutorial and first quiz this week. The tutorial and quiz were practices on Simple Induction. The questions were very relavent to the lecture materials and not hard.

Week1 Introdcution and Simple Induction

The first class of CSC236 was taken on the fourth day that I start to study in UofT (I'm a newly admitted transfer student). Frankly speaking, I was a bit nervous to attend the first class, afraid of missing some basic background information because I didn't take the CSC165 courses. And the course information sheet did scare me because of the marking scheme and the amount of tests and assignments. I didn't expect that the workload would be that heavy. However, fortunately, the first class came as a relief to me. The materials covered in the first class were mainly focused on Simple Induction (we mainly called it Mathematical Induction in high school), which is not hard.
The following is my lecture notes taken to prove some problems:

Sorry for the late starting of my SLOG

Hi all,

I'm really sorry for starting my SLOG this late!
I'll update my SLOG regularly from now on!

Hope to make more friends in the class.

All the best:)

Hengwei Guo (Jerry)