Week 11, 12, 13

I am combining these three weeks because I haven't been catching up with lectures due to the work load from 207 and some commerce courses. I've looked through all the lectures and realized that I don't understand a single thing except for NFSA. Pumping lemma seems very abstract. I really want to read the textbook regarding theese topics... but unfortunately, I lost my textbook in the aid center. Hopefully, I can get some help from my classmates.
Thank you very much for another wonderful year, Danny! You are one of my favorite professors who care so much about students. You have dedicated a lot of time to help us on discussion board, during office hours and lectures. You also try hard to give us the best grades we can get. I really appreciate it.

-Problem set 6-
The question was very similar to the lecture example. I just used the exact same format with some changes in the numbers.

-Assignment 3-
I was assigned to do question 2 and 4 by my partner. Question 4 was really straightforward because there's a similar example in lecture. As for question 2, it took me a while to figure out which one has a counter example and which one does not. I asked a few people and they all had different answers. In the end, I confirmed with TAs in the help center. Proving the two correct ones was annoying, the Kleene stars in the end really bothered me. The stars made the proves so different from the lecture example. I am going to read the solution to a3 later on to make sure that I also understand question 1 and 3.

-Test 3-
Test 3 was by far my worst test. I think the question on DFSA was easy. Danny didn't even ask us to construct the whole thing ourselves, therefore, it cannot get any easier. The two proves on regular expression were difficult, especially the one about L being an infinite language if it's not a subset of {epsilon, 1, 0}. I had no clue of what it's saying. So, I just wrote "I do not know how to answer this question." For the other prove, it took me a while to figure out. I was trying really hard to recall Danny's solution to a3. Although I wasn't too comfortable with my answer, I believe I earned more than 50% for that question.

Week 10

I find this week's topic very interesting. The DFSA is like a handwritten program to verify whether a binary string is of the form that the user wants. I never thought that something like this can work. It's quite neat to come up with a machine yourself. It will be great to know in what situations can this be used though.

-Problem set 5-
In order to prove this, you need to understand that whenever you add a new string to the language, you can add the regular expression that denotes the new string to the regular expression that denotes the language (R_L + R_newstring).

Week 9

This week is all about regular expression, teaching this right after we completed our 207 assignment is perfect timing. I find regular expression to be a very useful tool for string operations. It can be used to restrict strings very precisely. Since we've learned the application of it in 207, now we have to know how to prove its correctness. The example in the slides showed us a general format of proving a regular expression. I think the structure can be very different depending on where the Kleene Star is located.

-Test 2-
The test wasn't too challenging. It was based on proving correctness of programs with loops and proving recursive funciton (need to use unwinding to come up with a closed form).

Week 8

This week, there's more on program correctness. But this time, we have to know how to prove program correctness involving loops (for loops, while loops and recursion). After reading through the examples, it seems like the approach is to assume precondition to prove termination and post condition. I believe I can prove a program with only one loop. However, with nested loop, it is way too confusing. It gives me a headache by just looking at the example in the end of the slides. Further reading of the textbook is required.

-Assignment 2-
This assignment wasn't too bad. I'd say question 1 was the hardest. It took me half of the total time to do it. I am just bad with finding patterns. The way that I completed question 1 was mostly due to TA's help. Again, they've been extremely helpful. Question 2 and 4 were very similar to examples in the lecture slides. For question 3, as long as you see the similarity between Fibonacci sequence and the sequence generated by G(n), proving it wasn't hard. Another reason why I think this assignment was easier is because I had a partner this time. =D

Week 7

It's already week 7... Time is just going by so fast. I feel like the course materials are getting harder and I am starting to have a hard time to keep up with them. This week's lecture was on program correctness, which really sounds like something that will come in handy when you can't run the code. The main point is tracing through the program. You have to pretend to be a computer and imagine how the code will be ran. It is not something that everyone can do. I think I am quite good at it. Therefore, proving the correctness isn't too hard for me. (I remember doing something similar last year.)

-Problem set 4-
I feel like I did a question that's almost the same last year... So, I won't comment too much on it. The trick is to insert the new character to the begining of the string of length n instead of the end to prove for P(n + 1). Giving us a problem set about program correctness right after it's been taught, Danny is quick. =D

Week 6

Yay! A week free of intense course work! Anyways, there's nothing special about this week. There's more unwinding and more merge sort, which I've been studying since grade 11. They weren't particularly hard to understand. However, the master theorem of divide and conquer was confusing. Although it may seem like proving it is just another time complexity problem, it is just strange to prove the time complexity of something that's not a function.

-Problem set 3-
We finally get to do a problem on unwinding. The function was a bit tricky to unwind because it involved the use of geometric series, which I didn't realize until someone told me. As long as you get the idea of using geometric series to unwind, proving it is very straightforward. We need to use our all time favorite - induction.

Week 5

This week has been horrible for me. I can dare say that I don't understand anything in the slides. I can't even define my problems for the materials. They are just extremely confusing. (To be honest, the notes are a bit messy. Sorry Danny) I think I will have to read the textbook instead. I will pay extra attention to how to define sets by induction. The example looks very similar to question 4 of assignment 1. I believe it will be useful.

-Term test 1-
I was completely freaked out before the test because there were too many things that I didn't fully understand especially week 3. Fortunately, the test was composed of straightforward induction proves and proving recursive functions. Most of them were either mentioned during lecture or done in problem set. Therefore, I think I did well. Thanks to Danny who's kind enough not to put week 5 materials on the test.