More A3

After about a week of pondering this question, I finally gained some insight into how to solve it. And I am proud to write that I have (at least I think I have) solved it. The way the hint danny posted on the assignment handout was worded didn't really help me, and I was really struggling with it. I ended up finishing all the other questions before taking a look at this question again. Before attempting it again I decided to quickly peruse piazza to see if anyone else was struggling. I noticed a few people had raised concerns about the question. Luckily for me Danny had posted his hint again but reworded it in a way that really helped me think about the problem and eventually led me to working out the solution. The key for me was to think of the problem like "Ok so if the machine has less than 16 states, then two or more strings share a state. Then if this is true, what is the problem with that?" I am now proud to say that I think I am done the assignment. All that is left to do is to type up the solution. I am very thankful that I am done, I have a lot of other projects and tests going on this week and this is one less!

Interesting assignment 3. I am starting early because I also have a CSC209 assignment coming up, and those frequently take a substantial amount of time, not to mention I have a midterm on the Wednesday of the week this assignment is due. Good to start early. Question number one has me stumped. I am probably going to attend office hours tomorrow. Ask a few questions. I have come up with an approach, which I think is headed in the right direction. Question one asks: 

Let L = {x is in {0, 1}* | fourth-last symbol in x is 0}. Prove that any DFSA that accepts L has at least 16 states.

We know if DFSA M, accepts L, then for any string s in L, the first state that s drives M to is necessarily in Q. That is the state that s[0] drives M to is in Q.  Also  every state that s[i] , i=1,2,......,n drives M to is also necessarily in Q, and will transition from state to state according to transition function *Delta*. Finally we know that if M accepts string s then the last character in S causes the machine to half at an accepting state.

Im not quite sure where to go with this. The hint helps somewhat in that by showing that two binary strings of length 4 drive the DFSA to the same state, it implies that the two binary strings are the same and thus further implying that each binary string of length 4 drives the DFSA to a unique state. But I am having difficulties trying to formalize this in a proof.

I am definitely attending office hours tomorrow!

The term test was not what I was expecting. The pre/postcondition question was fair and it was great practice for really learning the material. The rest was straightforward excluding the last part of number two. That question definitely took me the longest to solve and it stumped me for a bit. But eventually I got it and it was a clever solution. Class afterwards was a bit tedious considering we had just written a test, but I stayed and learned some new things about iterative correctness. I am really looking forward to moving into learning about finite state automate and formal languages. It seems like really interesting subject matter.

This past week was a hectic one. Not only was Assignment two for this course due on friday, but I also had my systems programming assignment (CSC209) assignment due that day as well as a macroeconomics midterm. Obviously given all this work, it was important for me to start early. The first question gave me little trouble . The second one however gave me a bit of a headache, specifically proving that the recurrence was monotonic. After attending a helpful office hour with danny however I new exactly what to do. I was glad that the assignment was not too demanding as my systems programming assignment was, I must have worked on it for at least 20+ hrs. I find asking danny questions about the assignment and attending office hours particularly helpful when trying to solve the assignment. Tutorial quizzes these past few weeks were interesting. I particularly enjoyed devising the divide and conquer algorithm and then applying the master theorem to give a tight bound for the time complexity. So far the course is quite enjoyable and I am really learning a lot. I am still finding it somewhat difficult to following along in class. I suspect this may have something to do with the fact that I am in the evening section. Nevertheless I feel like the quizzes assignments and tests are fair given what we have been shown in class, and I sincerely hope this continues. I am going to attempt to blog more frequently now, as these past few weeks have been quite hectic and I have completely forgotten about continuing to blog.

Problem Solving

Doing very well in csc165, I came into CSC236 very confident. The first lecture grabbed me by surprise however in that, there was very little review, and we went straight into the first concept. Having not done summer school I was caught off guard like a deer in the headlights. The first few lectures I had trouble following the last few proofs. But I took them home and looked them over and eventually I was able to following along in class and understand the proofs.

The assignment was challenging but a good challenging in that with careful consideration, insight, time, and a few helpful bits of advice from Danny, I was able to complete it with time and I am confident in my answers. When solving problems of a logical nature such as the ones in assignment one, I think I have a few unique problem solving methods to share and some not so unique methods.

A unique thing I do that I often find helps me at least get a rough solution is I move away from my desk, lie in bed face down and think about the problem, list of facts we are given and facts I need to get to and try and find a logical bridge between the two. Most of the time an idea (ideas) pops into my head and most of the time it really helps.

A not so unique thing I do is I often write down examples of the problem and try to notice a pattern that can be useful to solve the problem.

I am looking forward to perhaps learning some new methods of problem solving methods that work for me.