Test3 and Final Words on CSC236

Test3 was a fair assessment of our knowledge of regular expressions and DFSAs,and I except a decent mark on it,although i feel i might have underwritten in terms of content for some of my proofs,but these mistakes will benefit me in the sense that i now know not to repeat them on the all important final exam.Finally,my last impressions of this course were that it was a very interesting,thoroughly enjoyable course,with an equally enthusiastic lecturer and some very unique and essential course content,which was all very surprising for me as i had heard really awful stories about other people's past experiences with CSC236,but am happy to admit,i found it be a very worthwhile and educational experience.I wish you all the best of luck on the final,and hoepfully will see you in CSC263 next semester.Take Care!!

My Polya Problem

For my problem solving session,i have decided to go back and answer Question 2(b)
of our 236 Assignment #3, using the Polya Problem Solving Techniques:

Step1:Understanding the Problem:

Firstly,i look at what the question has stated as given information,that the language L can be defined over a finite alphabet of {0,1},and any string that is represented in the language L has to have a even number of ones.Then,i examine the claim,which states that the Regular Expression R2 = (0 + (10*1))* can represent or denote the Language L.Now,my objective is to derive a proof that can substantiate this claim,or come up with a counter-example to disprove it.

Step2:Devising a Plan:

Once what has been given and what is to be proven is established,the first step I take would be to see if any counter-examples could be created,which would render the claim false.In this particular regular expressions case,there is no counter-example that would falsify the claim that R2 could represent L,since either 0 or 10*1,no matter how many Kleene-Star expansions are made(Kleene Star is a 0 or more repetitions of a character or string),both have an even number of ones,but that just means,the job is half done.Now,I have to examine a way in which to prove that this regular expression is capable of denoting L.One way to do this would be to show that if an arbitrary string is contained in R2,then it should be contained in L,and conversly,if it is contained in L,it should be contained in R2.This would show that R2 is capable of representing L.

Step3:Implementing the Plan:

Since I need to prove double implication,i.e x in R2=> x in L and x in L => x in R2,
a direction is needed to from which to begin the proof.For the sake of the problem,I chose to go in the forward implication direction first.
Forward:There,x is assumed to be aribitrary string derived from the regular expression R2=(0 + (10*1))*.Now,this string x can be broken up into 2 elements x[1]=0* and x[2]=(10*1)*.In each substrings case,they contain an even number of one characters,therefore when added back together,the sum of 2 even numbers get another even number,therefore the union of x[1] and x[2] would produce an even number of ones,which would allow x to be a member of the language L,Hence the Forward Implication is proven.

Backward:Here,x is assumed to be an aribtrary string in the language L,which means x must contain an even number of ones.Therefore,to form the x+1th string,the xth string can be concatenated with either the empty set,the set containing {0},the set containing {10*1}and the set containing {11} and the set containing {1},by the finite language over which L is defined.

Case1:If the xth string is concatenated with the empty string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since the xth string is assumed to contain an even number of one characters,and the empty set contains no elements.

Case2:If the xth string is concatenated with the {0} string to form the x+th string,then the x+1th substring would contain an even number of one characters,since
the xth string is assumed to contain an even number of one characters,and the {0} string contains zero 1 characters.

Case3:If the xth string is concatenated with the {10*1} string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since
the xth substring is assumed to contain an even number of one characters,and {10*1} contains 2 one characters,an even number of characters,which would hold true for any number of Kleene Star Expansions.

Case4:If the xth string is concatenated with the {11} string to form the x+1th string,then the x+1th substring would contain an even number of one characters,since
the xth substring is assumed to contain an even number of one characters,and {11} contains 2 one characters,an even number of characters,which would hold true for any number of Kleene Star Expansions.

Therefore,the x+1th string would always contain an even number of ones,and when any combinations of these Cases were made to form a new string,they would also contain an even number of ones since the sum of 2 evens is always even.Hence,The x+1th string can be represented in R2 since each one of these cases in representable by the definition of R2 itself.

Hence,since both the Forward and Backward Implications have been satisfied,R2 can represent the language L

Step4:Conclusion:

This thought-process represents structural induction,and the methidology behind which
most problems of this nature are solved.

Assignment #3,The last 2 problem sets and CFG(Context Free Grammars)

As we near the end of the semester,I have surprised myself to no end with my performance in this
course,which at the beginning of the semester was the one i was most reluctant to take,having heard nightmarish stories about its absurd difficulty,but through consistent work and with good instruction being provided by Danny,its proving to be my best course this semester in terms of grades and educational value.Hopefully,i will continue to ride this streak of good luck towards the end of the semester.Anyway,we completed assignment #3 this week,and while i was working without my regular partner on this one,I found the questions to be very gripping and a good test of essential concepts such as Program Correctness and Introduction to Regular Expressions.All in all, i expect a good grade on this one,and welcome any feedback.With regard to the last 2 problem sets,on which i scored 7/10 each,i felt i was less rigorous in my proofs then i have been in the past,and left a lot of small but essential arguments up to the marker to figure out,and that accounted for 3 very easily attainable marks.Oh well,you cant make an omelette without breaking some eggs!!:P.Both these problem sets dealt with manipulations of regular expressions,which have become my favorite part of this course,since they are very interesting when first glanced upon,and I'm sure that wherever they are applied,they must serve a greater purpose.Finally,this week we began CFG's(Context Free Grammars),which are an extension of Regular Expressions and formal Language,as in just as any language requires rules of syntax and grammar,formal languages and Finite State Automata require some sort of structure and regulation.Danny began his explanation with an example of a sandwich and how each element,when added in a certain order,makes a completely different meal every time,but still maintains the sense of being a sandwich.Looking forward to elaborate on this more as soon as i have caught up on lecture readings(since I've been coming habitually late to class this week!!).

Regular Expressions Continued(and Introduction to Finite State Automata)

This week,we began constructing Finite State machines,which are a very visual and extremely useful way of representing a Language.Firstly,we have the set of finite alphabet,normally denoted by sigma,and the transition function,which enables a Regular Expression or String to travel from one state to the next,denoted by delta,we have the starting state,where the machine itself gets inputted with the string,denoted by s,and a set F,which denotes the set of accepting states,which represent the output of the machine.Since we started with building a Deterministic Finite State Machine,there can only be a specific number of accepting states in F.Then,once all of this notation is established,we pass in strings that we think should be included in the language,and through tracing of the machines transition paths,we can determine whether the string belongs to an accepting state,and consequently the language.Also,the idea of efficiency was brought up,as there may be dead states,i.e non accepting states,or states that do not even lie on the path to accepting states,and these unnecessarily clutter and complicate the machine,so we get rid of them and the paths leading to them.We received our midterms back,and i was satisfied with my performance,but a note to myself for the future,i need to make my Precondition/Postcondition proofs a lot more formal.

Introduction to Regular Expressions and Midterm#2

This week,we had our 2nd midterm.I actually studied less for this midterm than the first one,and surprisingly,i feel i will fare much better on this one,Since the concepts covered in the midterm(closed form,precondition=>postcondition,loop invariant) have been ingrained into my head through countless iterations of the Assignment and problem sets.Also,in lecture this week,we began regular expressions,which entail creating a unique language consisting of certain characters(certain string,binary numbers etc),and using it in a program context to define certain algorithims.In my next post,i will go into more detail about this,as i am still no very clear on the subject yet.

Assignment #2 and beginning of Loop Invariant

Assignment 2 was due this Monday,and boy was it ever challenging.The question about the recursive formula for the number of ternary trees took me for ever to figure out,however by a combination of knowledge from STA247(at last some use from the course),and help from the T.A's at the aid center,We were able to finish it quite satisfactorily.Otherwise,in lecture this week,we began talking about loop-invariants,which are sort of relational tools in that they help you more fully understand the functioning of a particular loop.Personally,i am finding them a little bit strange to deal with right now,but i guess in due course,i will grow to understand them.

Midterm and introduction to correctness of a program

 The midterm was quite good,however i screwed up royally on one of the questions,while doing quite well on the remaining two.An overall estimation of my performance was that i knew what i was doing for the most part,i just did not follow through.hopefully,this will enable me to do better on the 2nd test.We began doing the correctness of a program this week,which was confined to two important properties,the precondtion which states what sort of input is needed for the program to be 'correct',and the postcondition,which states what sort of output stipulates a 'correct'program.Very interesting stuff.The other order of buisness is Assignment 2.Having done exceptionally well on A1, i now have to emulate the standard i have set myself on this assignment.

Recursion and Introduction to Closed Form.

Now into weeks 4/5, We have began discussing recursion, which i was first exposed to in CSC148 last year, and actually did not have too difficult a time understanding (barring the Huffman Code incident).We began unwinding some sample recursive functions and a sorting algorithm Binary Sort, (i.e simplifying each run of the code into a recursive call),Then coming up with an inductive proof to substantiate our claims.Our first midterm is this Friday, and i am not as nervous as i normally am come midterm season ,because of the methodical strategy i have adapted this year with regards to the material covered in class as well as the assignments/problem sets.Finally, we began closed forms today, which in essence relates a recursive function to a closed(i.e some sort of power or simpler) definition and use induction yet again.Good luck on the midterm everyone:)

Principle of Well-Ordering

Well we are 3/4 weeks into CSC236, and we have already had 2 problem sets and the assignment due date is due soon.So far, i have been keeping up with the work by doing over the material the same day it was covered in class, contrary to what i used to do in 1st/2nd year(which contributed to sub-par grades).Coming back to new material being covered, we have learnt a new principle of sets known as the Well-Ordering Principle which states that any non-empty set has a smallest element,and have used in several examples such as a round-robin domino tournament.So all in all, things are still smooth sailing at this point, let's hope for more of the same:)

Week 2(Problem Set and Assignment#1)

We are now 2 weeks into the csc236 course, and are now covering more techniques of induction,and writing up proofs for problems that utilize these rules. Complete Induction uses the fact that it is assumed to be true for a set of elements ranging until n-1,and using that Inductive Hypothesis to show by virtue of implication that P(n) is true,thereby concluding the P(n) holds for all n.Problem set 1 was a review of simple induction, and was relatively easy to finish.Assignment #1 still looms, although i have developed a proof for the 1st question, so i'm getting there slowly.The fear i have with respect to these assignments is that i will miss some small detail,seemingly insignificant at the time, but ultimately crucial when push comes to shove.So wish me luck,and good luck to all of you on the Assignment/Problem Set.

Beginning CSC236

Since i took two very math intensive courses during the summer break, Calculus 2 and Linear Algebra, my grasp of the mathematical notions is still quite fresh, so when i stepped into the classroom for CSC236, i anticipated a substantial jump from CSC165,but i would be able to cope with it. So far, my premonition has not been falsified.The course began with an introduction to simple induction proofs, utilizing quite basic,but essential mathematical ideas such as partitioning of sets into subsets, multiplicative axioms,and algebra.The proof structure from 165 remains in use thus far, but the rigidity has so far not been as stern as it was then.We have recieved our first 2 homework assignments of the semester, and i am eager to sink my teeth into both to determine the exact nature of my understanding of early 165 concepts.