Fin

So, looks like we've reached the end of the course (and the semester). This past 4 months have been very busy and also interesting at the same time. I came to CSC236 from CSC165, expecting it to be hard. However, now that we've covered all the materials, I'm happy to say that Danny is an excellent lecturer who goes above and beyond to make sure that everyone understand the materials. I also think that my TA (Colin) has done a good job explaining things further during the tutorial.

With the final exam looming, I'll focus on understanding NFSA first as this is the last material we covered. Then, I hope to review materials from earlier in the course. I hope I'll do well in the final.

Anyways, happy holiday in advance and I really wish for a white Christmas this year.

Here's something to get the holiday mood going...

Hope you all have a great one!

Almost There

So, tomorrow's lecture will be the last one this semester. Time surely passes quickly; I can still remember my first 236 lecture in September. It's been an exciting ride, especially since this semester has been the most hectic one for me.

About the last assignment: strangely, I find that the first question is the most tricky one. I could understand why we need at least 16 states for the DFSA, but it took me a while to figure out how to structure the proof (using contradiction). I hope the logic I came up with is valid.

As for the rest of the course, I think I should have enough time to get to grip with NFSA. Thank God for large gap between the last day of lecture and our final exam.

Tutorial 7

Just skimmed through the handout of tutorial 7. My thoughts so far:

1. Prove or disprove that if RS == SR => R == S (let this statement be our predicate)
Let S and R be two regular expressions
To disprove, we only need to find a counter example.
Let R = (0 + 1)*
and S = 1*
So, RS = (0 + 1)*1* and SR = 1*(0 + 1)*
Note that the string "01" is accepted by both RS and SR, so RS == SR
But, R != S, so this is a contradiction!
Therefore we've disproved the statement

2. Devise a regex R for all strings of {0, 1}* that start and end with the same bit (e.g. 1001101, 01000, etc.)
R1 = 1(0 + 1)*1 -> a string that starts with 1, followed by 0 or more occurences of {0, 1}, ends with 1
R2 = 0(0 + 1)*0 -> a string that starts with 0, followed by 0 or more occurences of {0, 1}, ends with 0
R = R1 + R2 = (0(0 + 1)*0) + (1(0 + 1)*1) -> R1 or R2

Proof of correctness:
I still don't know how to write a formal proof for this regex. I'll update this post sometime after the tutorial tomorrow.

Catching Up

So, it's been a while since I last posted here. The last few weeks had been incredibly hectic, with midterms, assignments, and interviews I had to attend. Anyway, this is the first time in the past few weeks where I had no midterm or assignment due. Thought I'd use it to start off early with assignment 3. Partly because unlike in assignment 2, I can actually spend more time on this assignment if I start early. I didn't do as well as I would've liked in assignment 2 due to the lack of time to go over it. As a result, the proofs were flawed or incomplete.

After skimming through it, it looks like I need to spend more time to learn more about DFSA. I couldn't attend the lecture & tutorial session where it was discussed, so I need to read up more on the issue to get better understanding of it.

I hope to finish this assignment by the end of this week, which should leave me plenty of time before the due date to go over it as needed. This might seem drastic, but one thing I learn from being in PEY this year is that companies like to call you for interviews at the very last minute. You may think that you have enough time allocated to do your assignments, but if you get the call, then your plans will be thrown into disarray. That happened to me last week, and with the amount of work due at the end of the semester (3 CSC assignments + 1 midterm + 1 presentation, all due between November 30 and December 4), I have to be way more conservative with my time allocation.

Unwinding Woes

It's been almost 2 months since the start of the semester. Time surely flies, doesn't it? It's been one though week for me, with midterms and assignments. It's not going to get any easier next week as I have another midterm and 3 assignments (one of which is from this course) all due on Friday.

Meanwhile in 236, the course is getting harder as I move into uncharted territory: unwinding. At first, I find it challenging to come up with a closed form of an endlessly expanding statement. After working on the tutorial problem set last Thursday, I find it important to write your equation in certain way.

Take Q2 for example, where n = 3^k. On my first attempt, I substituted n for 3^k right from the get go and I ended up with a messy statement with no pattern readily visible. Then I looked at tutorial solution and I hit myself in the head. If we use n, we can come up with a "sigma" to close the expansion, and use the formula for geometric series (not that I know anything about geometric series).

The course has given me no major problem before this, but with unwinding and mergesort, it's going to get more interesting. Especially since unwinding was not covered in 165, IIRC.

Tutorial 3 Recap

Let's recap the solution of tutorial 3 questions.

Q1: We want to prove that for some positive rational number c, P(n): T(n) >= c log(n).

• Case 1: n = 1
• No problem here: log(1) = 0, so c log(1) = 0 for all c
• Then T(1) = 1 >= 0 = c log(1)    # P(1)
  
• Case 2: n > 1
• T(n) = 1 + T(ceiling(n / 2))
         >= 1 + c log(ceiling(n / 2))
         >= 1 + c log(n / 2)
         >= 1 + c log(n) - c log(2)
         >= 1 + c log(n) - c
  
• What we want: turn 1 + c log(n) - c into c log(n)
  Remember that we want to prove P(n) for some c
  Then we can set a value of c such that P(n) holds (set c = 1)
  Then T(n) >= 1 + (1) log(n) - (1)
  T(n) >= (1) log(n)    # P(n) for c = 1
  
• Then there is a rational number c such that T(n) >= c log(n).

Q2: We want to prove that for all natural number k, P(n): T(2^k) = k + 1. (Note: This is actually similar to the quiz given in the tutorial. The only difference is, in the quiz we use T(3^k), but the solution's logic is the same.)

• Base Case (n = 1): T(2) = 2 = (1) + 1    # P(1)
  
• Induction Step: Assume P(n) for an arbitrary natural number n.
• Then T(2^k) = k + 1
  T(2^(k + 1)) = 1 + T(ceiling(2(k + 1) / 2))
                       = 1 + T(2^k)    # we can ignore the ceiling because 2^k is always an integer
                       = 1 + k + 1      # by IH
                       = k + 2            # P(n + 1)!
  
• Then P(n) => P(n + 1)
  
• Then for all natural number n, P(n)

Q3: We have to unwind G(n). Unfortunately, we didn't get the chance to finish this question during the tutorial.

Well Ordering

As I have said in my previous post, I was struggling to understand the principle of well-ordering. Thankfully, someone in Piazza kindly posted a link (go to page 43) that explains it in a very good way.

Basically, what we do in well-ordering is assume that a set of counter-examples to P(n) called C exists and that c is the smallest element of C. In the link I provided, P(n): 1 + 2 + 3 + ... + n = n(n + 1)/2

• Then, for all n < c (e.g. n = c - 1), P(n) holds, since the smallest value of n where P(n) is false is n = c.
  
• With this in mind, we show P(c - 1):
  1 + 2 + 3 + ... + (c - 1) = c(c - 1)/2
  
• Then we modify P(c - 1) to be P(c) and show that P(c) is in fact, true:
  1 + 2 + 3 + ... + (c - 1) + c = c(c - 1)/2 + c    # add c to both sides
                                             = (c^2 - c + 2c)/2
                                             = (c^2 + c)/2
                                             = c(c + 1)/2         # P(c + 1)!
  
• But P(c) is suppose to be false, this is a contradiction!
  
• Then, P(c) should be true and there is no counter-example to P(n).
  
• Therefore for all n, P(n) holds.

Thanks to Alex for the awesome post!