Assignment 3 Blues

DFSA became extremely difficult extremely quickly this week. Even attempting to do question 1 on Assignment 3 was very challenging, and I am still had trouble coming up with a proper proof statement.
I created this diagram to help me understand how the automata in question one works but, I'm still having issues gaining some insight into how to actually tackles the proof that proves this machine needs a minimum of 16 states.... In this diagram the red arrows indicate accepting 0's, and the green accepting of blue. As recommended by Danny Heap the start state is indeed at the state where a string with no 0's resides as this is the only state that doesn't reach an accepting state in three hops. It would be easier to prove question one with this diagram then without, as it can be clearly seen that if two of the four bit string resided in the same state would be impossible as each state has a unique connection to other states...

DFSA

We received test #2 on Friday, a bit relieved that the marks were adjusted, but it also shows me that I need to brush up on proofs of recursive algorithms. So I'm hoping to make some time to review and revisit parts of that material before this week ends. I think, as mentioned earlier that the first question really was a bit off-putting due to not remembering a simplification for the harmonic series. ah well. Another thing about the test the I think my section will miss out on is correctness proofs. I will look to brushing up on that as well.

The new material on deterministic finite state automata, for whatever reason seems much easier to understand, especially the proof, in comparison to correctness proofs of algorithm. I think it has to do with the fact that it's visual. Perhaps even correctness proofs for all code should be presented with a visual version as it seems much easier to understand (esp. for those of us who it takes a little bit longer to process what the code is actually doing). Even reading the proof in 7.3 for correctness were a breeze compared to chapter 2 topics.

The topics of languages is also very interesting too, and I wish more CSC courses would focus on history of computer languages, and construction of computer languages, instead of being force-fed languages such as Java, Python, etc.

I hoping to also start my slog problem/investigation soon. Perhaps it will be on automata :).

Abysmal Test Result

Although the test was, by and large, easy. I mean, you could solve these ones on your own, in your own time, with references etc. But doing this in a time limited situation was a bit off-putting.  The first question really relied on your knowing how to derive a summation into a simpler form. Unfortunately most of my study involved, say, the topic that were suggested, correctness, proving increasing decreasing, master's theorem, etc. The fact that probably about 50% of the mark for the first question rested upon your know how to simplify a summation in order to later prove closed form for T(n) seemed a bit unfair.

For the test my studying mostly involved understanding correctness proof which at first seemed complex but is quite easy to understand once you see how Complete Induction is used in the proof and that (precondition + termination) implies postcondition. I wish that had been featured on the midterm instead. I'm pretty sure I did not do very well on this one. Although I think I will be more prepared now for the final and will just have to be more aware of the possible questions to be encountered...