Regular expressions

  Got my test 2 back, it's pretty good as expected :)
  We just encountered regular expressions in CSC236, it also appears in 207, so it's good for me to learn it in both courses, but actually I've heard it in CSC148 or 108 can't remember exactly.
  For CSC236, it's more focused on binary strings, in that case, we can simply connect RegEx with finite state automata, but I'm pretty sure that in future we are gonna face some problems that involve letter and number combined cases, can't just be this simple.
  And the next tutorial is about how to devise and prove a regular expression that satisfies the given conditions, of course, the base case comes first which should pass the empty case, empty string case, and one-symbol string case, then for the induction step, we need to show that if R and S belongs to a set, then (R+S), RS and R* should all belong to the set.

Test 2 and new stuff

It's been a long time since the last blog, courses been busy.

So we had our test 2, I felt it kinda easy, because the questions were similar to the ones in A2, so I just used the same strategy to solve them. Missed out last Wednesday lecture, so I took Thursday's lectures instead, but I still need to get my test paper back.

Last week we covered some new stuff like automata, it's quiet interesting, we're like designing some sort of process, I think the automata graph can actually be described in programming languages only by using if statements. And the automata thing is filled with logic,
eg.           1                    0                           1
 state1 -------> state2 ------->  state3 -------> state1 with condition that if state1 or state3 receives a 0, then it shall go to a dead state, so if you are in some random state, you can actually tell which states you must have been to, and which state you must never have been to, and which state you can go. This kinda of process can come in handy in future courses I believe (like you design a machine etc)

Assignment 2

So the second assignment is just two questions.

  I found it's easy to solve the first question by simply looking at the examples given, evaluate several other examples for different ns according to conditions given, then I'm able to write out the pattern, which is like a recursive call as we did for merge sort.

  Unwind it and then it's not difficult to find that it acts quiet like a Fibonacci sequence, so unwind it like a Fibonacci sequence in course notes, the most important thing to know is that the closed form of a Fibonacci sequence, without it, there's no way to start the induction proof.
 
  As for question two, since we want T(n) to be non-decreasing, then obviously the max between T(ceiling(n)) and T((floor(n))) has to be T(ceiling(n)), but we still need to use complete induction like the one shown in course notes to prove it's non-decreasing first, then unwind the pattern to get a closed form, and the last step is to prove the closed form in the way we did in CSC165, since it's a big-theta proof, we need to prove both big-oh and big-omega.