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.

Week 4

This week, we're back to the old stuff from last year, but more indepth. Danny taught us about how we can prove recursive functions using induction. This part isn't too difficult to understand because we practiced recursion a lot in 148 last year. I believe most of us understand how it works. Then, there's time complexity and unwinding. Coming up with a function that calculates the time complexity of a recursive function wasn't too hard after learning how to unwind. All it takes to learn how to unwind are just basic math concepts.

-Assignment 1-
Assignment 1... I'd say it's more difficult than last year. I invited my friend over one day to discuss it. After looking through it, we just sat there staring into empty space. I knew how to do question 1 because I've done something very similar many times in high school. The other three were just horrible. Question 2 took me an hour to start off... I had no clue of how to do question 3. I couldn't even understand what question 4 was talking about. So, we decided to go on discussion board. Thank god! Question 4 is postponed to the next assignment. We've also found some hints that Danny and other classmates gave us. However, we still had little idea of how to solve the questions. Therefore, we went to the computer science help center. It was extremely helpful. The TAs tries hard and they don't just tell you the answer, which is great. I will only end up in bad condition for tests and exams if they just tell me the answer. I think understanding the material is more important than getting 100% without knowing what's going on. For question 2, the TAs told me different ways to design the technique. Afterwards, I just proved it by using induction. For question 3, I just had them explaining to me what Danny's hint meant. Then, I immediately knew how to do it. I am expecting a decent grade for this assignment. =D

Week 3

This week, Danny went into details of Principle of Well-Ordering. He showed us how to use it and how to prove the cycle of implication between Complete induction, Simple induction and Principle of Well-Ordering. I actually have no idea of how Danny proved the cycle. The only thing that I understands is what is Principle of Well-Ordering and how to use it. I figured that's probably the most important thing for now. As for the prove, lots of reading is required for me. I feel like csc236 is laughing at me now...

-Problem set 2-
We had our second problem set due this week. There was only one question about complete induction. It was the very famous stamp question in week 2 lecture slides, but with different numbers. It felt great to actually solve it youself. I didn't have a hard time proving it.

Week 2

Danny finally taught us something new this week! Another type of induction was taught, which is called Complete Induction. It is interesting to see how different it is from Simple induction. It proves P(0) to P(n - 1) hold, then use that to prove P(n) also holds. After understanding the basic concept of it, I still don't know when to use which induction. It seems like I will have to do lots of exercises and read the textbook for more details... I really like the stamp and chocolate examples. Without them, I couldn't have understood how complete induction works. Principle of Well-Ordering was also rougly introduced.

-Problem set 1-
Finally, our first course work of the year. It is based on simple induction, which was taught last week. I think Danny is kind enough to give us two questions that are so similar to the examples mentioned in week 1 lecture slides. Question 1 is basically the same, but just with a different base. So, I think problem set 1 is free marks. Thanks Danny =D

Week 1

Another exciting year in Danny's class! Last year was great fun, it certainly was interesting to learn about proofs. Now at least when I see those forall or exists symbols, I won't get tangled up. This week is mostly introduction of the course and some revision from last year. It's good to know that the great grading system is still here. I don't know if it's Danny who decided it, or the faculty. The system is great! It makes all of our lives much easier. There will be no tutorials this year, instead, we are going to have 6 problem sets. I think having an adequate amount of course work such as problem sets is great. It forces lazy people like me to keep up with what's going on and allows us to understand course materials better. There are still assignments. I am expecting them to be as challenging as last year.
To conclude, nothing much went on this week. There were no problem sets or assignments. As for the slides on Simple induction, this is simply revision from last year.