The last quiz

 I did really bad for the last quiz today, tried so hard to figure out how to devise a DFSA that accepts strings with length which has a reminder of 2 if divided by 3.
 The question gives examples like 2, 5, 8, I can come up with 11 and so on, so a string is accepted as long as it's 3 units longer than the previous one. And empty string is clearly not accepted, in this case, the starting state can not be an accepting state, then whichever way to get to the accepting state needs at least two states, one of which is the accepting state. I just figured out I'm still don't fully understand what a DFSA is (I thought I understand it before this quiz, just a reminder, the key idea of DFSA is : every single state has exactly one transition for each possible input)
  So my actual solution is quiet simple like this:

  In this case, it totally works, and the RegEx for this DFSA is : (1+0)^2((1+0)^3)^* , I was so stupid during the quiz cuz I thought the question might be like devise a DFSA that accepts odd 0s and even 1s, which is similar to the tutorial question(Since this is how the previous quizzes work)
  Anyway, this quiz reminds me that I need to go through all those basic concepts during reviews.

Assignment 3

  Just finished the assignment for another course, now I finally got some time.
  For assignment 3, I'm not that confident with my work, but anyway, q1 took me quiet a lot of time to understand what I'm supposed to do, I figured it out by writing down states that satisfy the expressions and trace them by adding 0 and 1 then I found that they would go to different states at some point which is against the definition of DFSA, so if two strings start in the same state, then adding 0 or 1 to them should drive them to the same state again, otherwise, it would be a NFSA, so I get this contradiction.
   q2 is kinda like the examples used in lecture, all we need is a loop invariant, which is, the value of x and y are strictly decreasing throughout the loop, as long as x and y are natural numbers, then y is always going to hit 0 which means the loop terminates.
   q3 is something I saw in text book, just design a DFSA and then prove it by induction, need to point out the starting state and accepting state, as q1, I can get the idea that this DFSA need at least 3 states (since the starting state and accepting state can be the same).
   q4 confused me a little, the hint wants me to use the approach from lecture notes, but the one in lecture was written recursively, now I have to use a loop, I wrote 3 versions of the design in python, and the runtime of divide-and-conquer solution is indeed fast, the important thing to notice is that the algorithm should return the highest index of the specified value, which means if there's some duplicated values in the list, then the index of the last occurrence of that value should be returned, for divide-and-conquer algorithm, the most important thing is the max and min index, cuz we need them to calculate the middle value, so the loop invariant should be something like, max > min. Then it's just like q2, use induction to prove the loop terminates.

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.

Finally got some time

  So it's been two weeks since the last time I'm here, course went intensive, got 1 midterm, 1 assignment and quiz for every week.
  I found that study the quiz before tutorial is kinda helpful to  get a sense about how the quiz would be like, then read the online text, search for some MI, CI, SI problems on google would help me to get a better understanding of the course material.
  And this week we learned about time complexity, Prof. Heap used merge sort as an example, it reminds me of what we learned in CSC165, basically this example is to analyze the lower and upper bound of the runtime of a sorting algorithm, I assume that we're gonna learn how to prove all the other sorting algorithms, probably by ourselves, in this case, I will start to prove those algorithm runtimes. This runtime analysis can be very helpful for future programming, since the running speed of a program is sometimes crucial in real life.
  Later, I will post my solutions for sorting algorithms.

Week 4: So far as I learned

  So this is the 4th week, and already done 1 assignment plus 1 quiz, pretty intensive.
  Missed out the second quiz on Monday, cuz I thought the tutorial will be  on Wednesday, so I'll go to Thursday's evening section tutorial, hope I can still write the second quiz.
  Assignment 1 seems to be not so hard, all the problems can be solved by reviewing the notes from the lecture, MI and CI were not some new stuff since I took CSC165 last year, and then we learned WO, they are pretty much the same to me.
  Still didn't get back Quiz 1 paper, it's really easy though, so probably shouldn't be worried about that.
  Now I'm preparing for tomorrow's Quiz, the course seems getting harder as time goes by, think I need to put double time to study.