Final Words

Contrary to CSC165, I actually enjoyed this course. It laid more emphasis on applications rather than theoretical proofs. The problem solving techniques helped me tackle problems in different ways (specially in physics) and upgraded my problem solving abilities. I learnt that all problems do not need to be solved mathematically but a bit of logic can help a lot; example the binary arithmetic trick for the 4th question for A3.

Although I did run into some medical issues during the semester, I am a bit worried about my marks but I was able to catch up most of the work I missed and Danny was very helpful throughout the term. I am very thankful to him for all his help in CSC165 and CSC236 and to the TA's at the CS Help Center. This course makes me feel more confident that I will actually be able to do the AI specialist without glitches and inspires me to continue in this field.

Happy holidays to everyone!

Bimal

Test 3

Today we had test 3 but I did not do so well in it (I dont know, maybe I did). I have a bad fever and a flu since 5 days and its been bugging me a lot... I cant even study properly... I thought of going to the hospital but the fear of having to take a blood test forced me to take the test no matter what; because last time I took a blood test, the syringe needle broke in my arm and getting that thing out was the most painful experience in my life and since then, has become my greatest fear...

About the test, the first question about the DFSA seemed familiar to Q4 from the third assignment. I think I got all the state declarations right and I think the way to tackle part b of the first question was to count the odd/even number of 1's and their sums and match them to the declaration that suits it.

I think I bombed the second question, I thought about it on my way home and I think I got the wrong answer for it. I proved that if there is a regex for R1 and R2 then there is a subset that can be denoted for L(R1 + R2) and since R1+R2 belongs to R, then the subset (0,1,epsilon) exists...

The third question was easy but I think I used the wrong technique... I made a DFSA that represents L2 and by using minimisation techniques, I got a regular expression that takes from state epsilon to a final accepting state and that regular expression was eqivalent to the L( ... ) expression. I wanted to make a formal proof but my head hurt too much and I couldnt concentrate anymore.

I hope I will get better soon because my finals start next week and I need to study for them.

An interesting example on the Pumping Lemma

I had some problems understanding the Pumping Lemma and while reading a book (Introduction to Automata Theory Languages and Computation 2nd edition page 128) I came across an interesting example of how they described the Pumping Lemma as a game:

The Pumping Lemma as an Adversarial Game

... The pumping lemma is an important example in a theorem that involves several alternations of 'for-all' and 'there-exists' quantifiers that can be thought of as a game between two players, since it in effect involves four different quantifiers: "for all regular languages L there exists n such that for all w in L with /w/ >= n there exists xyz equal to w such that ..." We can see the application of the pumping lemma as a game, in which:

1. Player 1 picks the language L to be proved nonregular.

2. Player 2 picks n, but doesn't reveal to player 1 what n is; player 1 must devise a play for all possible n's.

3. Player 1 picks w, which may depend on n and which must be of length at least n.

4. Player 2 divides w into x, y, and z, obeying the constraints that are stipulated in the pumping lemma; y != epsilon and /xy/ <= n. Again player 2 does not have to tell player 1 what x,y, and z are, although they must obey the constraints.

5. Player 1 "wins" by picking k, which may be a function of n,x,y, and z, such that x(y^k)z is not in L.

Building a DFSA from an NFSA

Suppose we have a Non-Deterministic Finite State Automaton (NFSA) and we want to derive a DFSA from it. Lets take for example, a NFSA that accepts strings containing at least '00' or '11' and can be of even or odd length:
We can see that if we input strings containing at least two zeroes or two ones, those strings are accepted by this machine. To derive a DFSA from this machine, we need to draw the state transition table.

First lets observe the transitions when we input 0's and 1's:

If we input a 0, we remain in q0 and at the same time we go to q1 therefore q0q1
If we input a 1 we remain in q0 and go to q3 therefore q0q3

Now that we have the transitions for q0, we now have new states q0q1 and q0q3 and we now have to deal with them.

if we are in q0q1 and we input a 1, if 0 enters q0 it transits to q1 and if 0 enters q1 it transits to q2. We then get a new state q0q1q2. And when we are in q0q1 and we get a 1, we remain in q0 and it transits to q3 as well. When we get a 1 for q1, there is no state transition for 1 so we don't move anywhere. Then we get state q0q3 which we already found for the transitions for q0.

Now, we have to take care of q0q3. If we get a 0 we remain in q0 and branch to q1 and when we get a zero for q3, we don't move anywhere since there are no state transitions described for a 0 input. Then we get state q0q1. Now when we get a 1 in q0, we remain in q0 and branch to q3. When we get a 1 for q3, we branch to q4. So we geta new trsnaition state q0q3q4 and we have to take care, as always for every new state derived, of it and observe its transitions. If we get a 0 for q0q1q2 we get the same state transition: q0q1q2 and if we get a 1, we get q0q3.

Similarly if we get a 0 for q0q3q4 we get q0q1 and if we get a 1 we get q0q3q4 again. In our NFSA, q2 and q4 were final accepting states so in our DFSA, any state containing q2 or q4 will be accepting states as well. We will highlight them in red and all others in blue. So now we dont have anymore new states and we can start building our DFSA but lets build the transition table first so that we get a clearer picture of what's happening:

-------------------Inputs--------------|
---------------0-------------1---------

q0-----------q0q1---------q0q3

q0q1--------q0q1q2-------q0q3

q0q3--------q0q1---------q0q3q4

q0q1q2------q0q1q2------q0q3

q0q3q4------q0q1--------q0q3q4


And our DFSA looks like this:

Problem 4 Assignment 3

Use the Cartesian Product technique from Section 7.5 of the Course Notes to construct a DFSA that accepts binary strings of odd length, and that are multiples of 5 when interpreted as base two numbers. For example, your machine should accept 101 (5 in base two), but not 1111 (15 in base two). State, without proof, the appropriate state invariants (see Section 7.3).


My teammate and I worked on a solutiona nd came up with the following:

The following is the state invariants of a DFSA that accepts binary strings of
odd length, and that are multiples of 5 when interpreted as base two numbers.

Note: In the expression x%5 = n, n denotes the remainder of x divided by 5.


State invariants of a DFSA that accepts binary strings of odd length.

Q_1 = {q'_0, q'_1}.

Sigma_1 = {0, 1}.

s_1 = {q'_0)}

F_1 = {q'_1}
q'_0 if the length of x is even
P_1(x): delta*(s_1, x) = q'_1 if the length of x is odd


State invariants of a DFSA that accepts binary strings that are multiples
of 5 when interpreted as base two numbers:

Q_2 = {q_(epsilon), q_0, q_1, q_2, q_3, q_4}.

Sigma_2 = {0, 1}.

s_2 = {q_(epsilon)}

F_2 = {q_0}

--------------q_(epsilon) if x is an exmpty string
--------------q_0 if x%5 = 0 when interpreted as a base two number
--------------q_1 if x%5 = 1 when interpreted as a base two number
P_2(x): delta*(s_2, x) = q_2 if x%5 = 2 when interpreted as a base two number
--------------q_3 if x%5 = 3 when interpreted as a base two number
--------------q_4 if x%5 = 4 when interpreted as a base two number


State invariants of a DFSA that accepts binary strings of odd length, and
that are multiples of 5 when interpreted as base two numbers.

Q = {q_(epsilon), q_0, q_1, q_2, q_3, q_4, q'_0, q'_1}.

Sigma = {0, 1}.

s = {(q_(epsilon), q'_0)}

F = {(q_0, q'_1)}

------------(q_(epsilon), q'_0) if x is an empty string
------------(q_0, q'_0) if length of x is even and x%5 = 0
------------(q_0, q'_1) if length of x is odd and x%5 = 0
------------(q_1, q'_0) if length of x is even and x%5 = 1
------------(q_1, q'_1) if length of x is odd and x%5 = 1
P(x): delta*(s, x) = (q_2, q'_0) if length of x is even and x%5 = 2
------------(q_2, q'_1) if length of x is odd and x%5 = 2
------------(q_3, q'_0) if length of x is even and x%5 = 3
------------(q_3, q'_1) if length of x is odd and x%5 = 3
------------(q_4, q'_0) if length of x is even and x%5 = 4
------------(q_4, q'_1) if length of x is odd and x%5 = 4

How to nail an assignment

Image Courtesy: Jared - MAT237 Assignment 2

I just discovered one of the major problems I had when doing assignments (Whether it was for CSC165 or CSc236 or any other subject) while working on Assignment 3. I found that I was thinking too hard and most of the time, I misread the question. While working on A3, the first thing I noticed about question 1 was a proof on an iterative program. Immediately I put in some values and calculated the output and I noticed that q returned the number of times the while loop executed and r would give the GCD() of the two numbers n,m. I wrote a 1.5 page proof on it...

Well it sure was ugly and when I showed it to my assignment partner, he was surprised and he simply asked me:

"Why?"

I was surprised and when he told me what the function exactly does and the fact that it was already described, I felt stupid and I felt that I wasted a lot of time writing the unnecessary proof. It was so simple that after sometime I asked myself:

"Why didn't I think of that in the first place? and what made me think of GCD()?!!"

The second mistake I made was on question 4. I actually thought we had to hand in a complete DFSA. Well it turned out that we simply had to submit the state invariants and that would give the TA's a clear idea of how the machine worked. It shows that I didnt even read the question properly and thought too much on it when it was simple. Maybe I panicked and tried designing a DFSA and used a series of inputs to test it. But when I did so, I found that I was going round and round and that trial-and-error may not be effective in solving this kind of problem.

I did have some problems understanding how to develop a technique to count multiples of 5. Thats when I went to Danny and he explained to me how to tackle this sort of problem. Well everything went well after that but the only thing bothering me is that I feel being careless can be very dangerous and can account for most mistakes. Simple misinterpretations can lead to disaster and working with a partner really helped me find my faults.

I hope any student that reads this post will learn something about my experiences and will be careful when tackling assignments. Anyways I have made it a habit now that for any subject, if I dont understand something in the assignment, I would go and ask the TA's at the help center or the instructor.

The Koch Curve

I know its slightly off topic but still, there is some connection to CSC236 -- Paterns. The Koch Curve is sort of a fractal, we can use the equations and change it to make interesting shapes. Here is the python code for a Koch Curve (got it from wikipedia) that will model a snowflake:

import turtle
set="F"
for i in range(5): set=set.replace("F","FLFRFLF")
set=set+"R"+set+"R"+set
turtle.down()
for move in set:

#Get rid of the underscores, replace by a sinlge tab as blogspot doesn't like leading blank spaces.
____if move is "F": turtle.forward(100.0/3**i)
____if move is "L": turtle.left(60)
____if move is "R": turtle.right(120)
input ()

And we get this image:

Now what if we try and modify the equations?

Lets try:

import turtle

import math

set="F"

c = 2f

for i in range(5): set=set.replace("F","FLFRFLF")

set=set+"R"+set+"R"+set

turtle.down()

for move in set:

____if move is "F": turtle.forward((100/c**i))

____if move is "L": turtle.left(60/c**(c-i*i))

____if move is "R": turtle.right(math.cos(45*(i/i**2))*i**4)

input ()

And we get a more interesting pattern:

Looks fun, now lets terribly screw it over and see what happens :)

Lets try:

import turtle

import math

set="F"

c = 2

for i in range(5): set=set.replace("F","FLFRFLF")

set=set+"R"+set+"R"+set

turtle.down()

for move in set:

____if move is "F": turtle.forward((100/c**i))

____if move is "L": turtle.left(60/c**(c-i*i))

____if move is "R": turtle.right(math.cos(45*(i/i**2))*i**4)

____set=set+"L"+set+"L"+set

____for move in set:

________if move is "F": turtle.forward((100/c**i))

________if move is "L": turtle.left(60/c**(c-i*i))

________if move is "R": turtle.right(math.cos(45*(i/i**2))*i**4) #set=set+"R"+set+"R"+set

input ()

After a couple of minutes of computation, we get this:

Now if we let the computation continue for a while (7mins) we get this:

And finally after 21 minutes, we get this beautiful image:

God knows what it is but I like it. Now there's something worrying me a bit, its still drawing! I dont know when it will stop drawing but i think i'll let it draw till tomorrow morning and see what the final image is like.

DFSA

I had some problems understanding how to create the state transition table for a given DFSA. I knew how to form transition tables using circuits but this one is a bit different. I read this great book: "Introduction to automata theory languages and computation 2nd edition by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman" and the bank-store-customer example they used made it clear to me.

I used an example from the book and tried to solve it.

Problem 1: Design a DFSA that accepts a string that has the sequence "01" somewhere in the string

Solution: Let L be the language where:

{x01y where x and y are any strings of 0's and 1's}

So that means "01", "11010", "100011" ε L
but "100", 110000", "000", "111" is not contained in L.

Let q0 be the starting state. Now since we need to find string "01" we need a 'variable' to store the previous character so that we can compare. Let q1 be the state when we see a zero. So when we are in q1 and we see a "1", we can move to a final state q2 which is the accepting state. Now, if we are in q1 and we still encounter a "0" character, we shall stay in the same state. Similarly if we are in q0 and find a "1", its useless since the string desired should start with "01".

Finally once we step into q2, we dont have to worry if we encounter a "0" or "1" anymore since we will remain in q2 no matter what. (By the way, if i remember, in a JK flip-flop system, this is denoted by capital X which means 'dont care' state).

So our transition table looks as follows:

∂(q0, 1) = q0

∂(q0, 0) = q1
∂(q1, 0) = q1
∂(q1, 1) = q2
∂(q2, 0) = q2
∂(q2, 1) = q2

and our state diagram looks like:

Now what if we try and modify it and say we want it to accept any string containing the string "0101"

Problem 2: Design a DFSA that accepts a string that has the sequence "0101" somewhere in the string

So our state transition table will change and we have to introduce new states q3 and a final accepting state q4. So if we start at q0 and find a "1", its pretty useless and we remain in the same state q0. but if we find a "0" means that it is the start of the substring we are looking for. So we jump to state q1. Now from q1, if we find a "0" as the next character, we are back to square 1 so we jump back to q0. But if we find a 1, we jump to q2. Similarly, if we get a "0" while being in state q3, its useless since its not forming the substring we are looking for and we jump back to q0. But if we find a "1", then we jump to the final accepting state q4. Once we are in state q4, we 'dont care' about the incoming characters since we have already found our substring and we remain in state q4.

So our transition table becomes:

∂(q0, 1) = q0 ---------- ∂(q0, 0) = q1

∂(q1, 0) = q0 ---------- ∂(q1, 1) = q2

∂(q2, 0) = q3 ---------- ∂(q2, 1) = q0

∂(q3, 0) = q0 ---------- ∂(q3, 1) = q4

∂(q4, 0) = q4 ---------- ∂(q4, 1) = q4

And our state diagram would look like this:

I must thank Danny for showing us jFlap. Its a great tool to analyse state diagrams and find flaws.

Problem Set 5

Problem: Prove that if language L has a finite number of strings, then there is is some regular expression that denotes L.

The first thing i noticed is that since L has a finite number of strings, there exists a Regular Expression (RE) that denotes L.

//This roof resembles a proof we did in linear algebra (MAT223) where we had to prove that a vector v = (v1,v2,v3,..,vm) belongs to a vector space.

Let L = {L1, L2, L3, ... ,Lm} over Ʃ

Any substring from L can be denoted as L_a where a should at least be 1 and at most be m. Given that strings are a concatenation of characters, we can define a string:

L_a = (L_a1, L_a2, L_a3, ... ,L_an), since L_a belongs to L and L_a belongs to Ʃ

Then L_a1 is a regex for Ʃ ==> L_a1L_a2 is also a regex;
Then L_a1L_a2...L_an is a regex for Ʃ

RE(L_a1L_a2...L_an) is a regex for Ʃ and given that L_a = (L_a1, L_a2, ... L_an), L_a defines the string.

Then RE(L_a1L_a2...L_an) is the String L_a.

All substrings in L have regular expressions RE_1, RE_2, RE_3, ... ,RE_n
RE_1 is a regex for Ʃ
(RE_1 + RE_2) is also a regex for Ʃ
.
. Concatenating the regexes
.
(RE_1 + RE_2 + RE_3 + ... + RE_n) is also a regex for Ʃ

The sum of all regexes is equivalent to the language L.

n
Ʃ RE _i <=> (RE_1 + RE_2 + RE_3 + ... + RE_n) <=> L
i=0

Then if L has a finite number of strings, there exists a regular expression RE that denotes L;

Problem set 4

Problem set 4 was OK, i missed a perfect score because I did not use the induction hypothesis but here is my solution: (Please note that blogspot does not like spaces so indentation is a problem; sorry about that)

def revString(s):
if len(s) <>
else: return revString(s[1:]+s[0])

(1) Define our P(n)
{
____P(n) = /forall s /in Strings+ { if len(s) == 1: revString(s)
____else if len(s) > 1: revString(s[1:]+s[0])
}

Lets assume that the program does not take empty strings (strings with length 0) and lets denot all strings with positive lengths but Strings+. i.e: /forall x /in Strings+, len(x) > 0.

Proof:
Base case:
len(s) = 1

Assume s /in Strings+
{

__Then s is a string with at least 1 element
__Then len(s) = 1 and 'if' condition is satisfied
__Then revString() executes line: 'if len(s) is less than 2: return s
__Then revString() is correct.

}
Then /forall s /in Strings+, len(s) < 2 =""> revString() is correct and our base case passes=> Post condition is true.

Inductive case:

Assume n /in N #Generic natural number
_Assume s /in Strings+
__Assume i=0_V^n P(i) (*) (Want to prove P(n+1))
___Assume len(s) >= 2

{
____Then 'if' condition is false and line 'if len(s) <>
____Then line 'else: return revString(s[1:] + s[0])' is executed.
____Then len(s[0])=1 && (len(s[0]) <= len(s[1:]).
____Since len(s[0]) = 1, from our base case we know that len(s) == 1 ==> return s.
____So return revString(s[1:]) + s[0] # *1 = s[0] part is then true.
____Then revString(s[1:]) is called.

____Case 1: len(s[1:]) == 1:
_____by base case, if len(s) == 1: then return s
_____Then s[1:] is returned and revString() is correct.
_____s[1:] + s[0] means string returned is reversed ==> Post condition is true.

____Case 2: len(s[1:]) >= 2:
_____Then line 'else: return revString(s[1:] + s[0])' is called.
_____# s[0] by *1 is true
_____Then by (*), revString() is correct.
_____==> Post condition is true
}

___Then revString() is correct # proof by cases
__Then P(n+1)
_Then i=0_V^n P(i) => P(n+1) # intro =>
Then /forall s /in Strings+, i=0_V^n P(i) => P(n+1) #intro
/forallThen /forall n /in N, /forall s /in Strings+, i=0_V^n P(i) => P(n+1) #intro /forall

Then Post condition holds and revString() is correct

Test 2

Unfortunately, I had a lot of problems to look after (some related to school and some not) and I did not have enough time to study for any subject... :( As a result I did find test 2 difficult but i still gave it a shot from what I followed in lectures.

The first question was a bit confusing, I think I got the wrong idea... I stated unwinding G(n) and tried to prove that T(n) can be derived and exists in G(n). I used the same unwinding technique from problem set 3 but I dont know if that was the solution to it...

The second question was fine, we had done something similar in lecture and in CSC165 during summer. The third question was a bit tricky, i had trouble finding an appropriate invariant but I knew that we had to show that the loop terminates. We know that n keeps on getting smaller after each iteration and at some point, the condition would be false and the loop would terminate.

To summarize, i knew part of the solutions but i'm not sure whether they are correct... I will have to catch up on the forthcoming problem sets/assignemnts and tests.

State machines... we meet again

On Wednesday, we were introduced to state diagrams and how to draw a circuit from given states and state transitions... I did FSMs back home when I was studying electronics... They are very useful for designing sequential circuits using JK flip-flops. I was surprised and happy to learn that we are learning how to use state machines in CSC236 but this time, we are not lighting leds or making a vending machine... instead we are building "circuits" to analyse strings.

Professor Danny used a very interesting software called jKFLAP (? not sure) where he made the circuit simply by drag-and-drop. I was also amazed that it can even test the circuit.. Now, how I wished I knew back then that there was such a software...

Unfortunately because of some personal problems, I missed two lectures (the ones dealing with formal languages) but it was pretty easy to catch up on the slides. I found that the laws for the equivalent REs on the slides were similar to the laws whether a vector belongs to a vector space from linear algebra (MAT223).

For example, there has to be the zero element or empty string such that:

( R + Ø ) = R # Ø is the empty string.

Theres only one thing I'm not too sure about and that is the "Idempotence of Kleene start" where:


( R** = R* )

I missed that lecture, unfortunately, but i'm wondering whether there is a typo and if it should have been: Kleen star (thats what google says)

Wikipedia states that: http://en.wikipedia.org/wiki/Kleene_star

1) If V is a set of strings then V* is defined as the smallest superset of V that contains λ (the empty string) and is closed under the string concatenation operation. This set can also be described as the set of strings that can be made by concatenating zero or more strings from V.


2) If V is a set of symbols or characters then V* is the set of all strings over symbols in V, including the empty string.

So for example:

{'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", ...}

Applying the Kleene star would mean it contains the zero element λ and all the elements 'a', 'b', 'c'

And then it would looke like:




We can notice a pattern in the number of elements that form after every "step" as shown in the image below:

Problem Set 3

One thing I noticed with CSC236 is that you cannot sit down and try and get the answer in a couple of hours... I was actually confused by the notion of a closed form. I wondered how to use repeated substitution, I thought hard about it but couldn't get a hint. Then I said to myself, "lets take a break!"

So I played a bit of unreal tournament 3 online with my friends while a small part of my brain was concentrating on the problem set. Suddenly out of the blue, I shouted "AHA!". All of a sudden, at random, a clue came to my head. I immediately exited the game and went back to the problem set.

After playing around with the numbers and continuosly re substituting onto itself, I came up with a sequence which could be easily written with summation symbols etc. The sequence was :

3^3 + 3^2 + 3^1 + ... I played around with the summation and found that it actually converged to P(n+1). That was the clue! After re arranging and some factorisation, I spent about half an hour trial-and-error and found the final equation that would be a closed form for the problem!

Then I said to myself, frequent breaks are really useful! Random hints might fall in when the brain is not fully concentrating on the subject. The human brain surprises us all the time...

A mathematical problem

As a scientist, although I got a transfer credit for the first year calculus, I dont know much about real world calculus! And i am happy that I dont know anything much about it because thats the best result you can get: Know Nothing! This proves that there still much to learn ahead and excitement to come!

Here's the problem that got me stuck for ages:

My friend owns a roller shade company and he need to make boxes for them. He makes the barrels himself and they come in various diameters. Now he has to roll a shade of length L onto in and after each turn, the total diameter increases exponentially (because it is a spiral and spirals grow exponentially, not linearly). Then we can obtain the total diameter of the barrel and the shade rolled onto. Once we have that, we can order boxes of correct dimensions.

Here is a picture of the situation:

Now, the only way i tried to solve this problem is by rolling and counting the number of turns made first.

So lets denote:

Length of shade: L

Width of shade: W

Thickness of shade: h

diameter of barrel : D

3.1412 : pi

n = number of rolls

Now lets roll the first turn: we can do that by subtracting the circumference of the diameter++ from the sheet of shade.

n = 1 => So 1st turn: [L - pi(D)] cm left to roll onto

n = 2 => 2nd turn: [(L - pi(D)) - pi(D+h)]

<=> [(L - pi(2D + h)] cm left to roll onto. pi(D+h) means that the new circumference has increased by the thickness of the shade, which also varies in size.

n = 3 => 3rd turn: [(L - pi(D)) - pi(D+h) - pi(D+2h)]

<=> [(L - pi(D)) - pi((D+h) + (D+2h))]

<=> [(L - pi(D)) - pi(2D + 3h)]

<=> [(L - pi(3D + 3h)] cm left to roll onto.

n = 4 => 4th turn yields: [L - pi(4D + 6h)] cm left to roll onto

n = 5 => 5th roll yields: [L - pi(5D+10h)] cm left to roll onto

n = 6 => 6th roll yields: [L - pi(6D + 15h)] cm left to roll onto

... nth roll

So for n>1 rolls:

We can observe a pattern. If we look at the last digit in each equation, we see 1, 3, 6, 10, 15, ...

And this pattern is best described as triangular numbers: http://en.wikipedia.org/wiki/Triangular_numbers

So we can actually write a program that can generate a list/range of numbers from

2 -> m # {2,3,4,5,......,(m-1)}, lets call this list m

then we create a regular list starting from 1 -> p # {1,2,3,4,.........,p}, lets call this list p

Assume m and p are natural numbers. Then we add each number in a specific way:

for i in range(0,m):

p[i+1] = p[i] + m[i]

Then list p will have elements: {1,3,6,10,15,...}

and save it in an ordered list named Q. Then, if we can start with our base case, n = 1, we can substitute each number from this ordered list to the last digit in our n+1 equation corresponding to the proper index. So we will have an ordered list Q of triangular numbers. That would solve the problem creating the pattern.

Now for the coefficient of D, we can see a similar pattern but it seems to be related to the number of rolls. So for every new equation for (n+1) turns, we can form a formula:

Assume that n > 0:

Length remaining to roll =

if n = 1, [ ( L - pi( (n)D ) ]

else if n > 1, [ ( L - pi( (n)D + Q[n-2]*h ) ) ]

Q[n-2] indicates the index of the element in Q

So now we have a general formula to calculate the number of turns possible given a length of a shade and the diameter of the barrel. We dont care much about the width of the barrel and shade as it does not affect our calculations.

Now since we can predict the length of any nth roll, we can write some code to check if the length remaining is smaller than the length required for the next (n+1) roll and if it is smaller, we can stop there and return 'N', the number of rolls possible.

We now have the number of turns possible but I still cannot find a way to find the diameter at that Nth point. I am still working on it but if anyone has any hints, please let me know, that would be great!

I hope you enjoyed this problem as much as I did.

Assignment 1 and the symmetric pattern

For assignment 1, problem 2, i noticed something fishy... Something playing around with my mind..

I could sense a pattern going on but couldn't trace it down. The problem is that we are given 2 meals, L and S. A suitable cycle for the meals in which the meal for the next day differs by exactly one would be: {}, {S}, [L,S}, {L},

So when we add a new meal and manually compute the set, we get this:

{}, {S}, [L,S}, {L}, {L,P}, [L,S,P}, {S,P}, {P} which is correct.

But I noticed something interesting. Starting from the first element {}, lets make a copy of this list. If we take the region after the last element and before the "," [i.e: {}, {S}, [L,S}, {L} (THIS REGION HERE) ,] and use it as a vertical symmetry axis, we can rotate the list by 180 degrees and we would obtain an image of our original list.




Then if we add the new meal 'P' in each set in our newly rotated list, we get this:
{}, {S}, [L,S}, {L}, {L,P}, [L,S,P}, {S,P}, {P}

And this corresponds to what we would get by manually verifying it:
{}, {S}, [L,S}, {L}, {L,P}, [L,S,P}, {S,P}, {P}

So, could there be a pattern? Lets check by adding a new meal 'Q'. We repeat the same stesp. Lets create an imaginary vertical symmetry axis at the point labelled 'here': ...{P} (HERE) ,

Lets make a copy of the list and rotate it. We would get this:
{}, {S}, {L,S}, {L}, {L,P}, {L,S,P}, {S,P}, {P} ( Symmetry Axis here) , {P}, {S,P}, {L,S,P}, {L,P}, {L}, {L,S}, {S}, {}

So if we add the new meal 'Q' in each set of our newly rotated list, we would get:
{}, {S}, {L,S}, {L}, {L,P}, {L,S,P}, {S,P}, {P}, {P,Q}, {S,P,Q}, {L,S,P,Q}, {L,P,Q}, {L,Q}, {L,S,Q}, {S,Q}, {Q}

And if we verify manually, we would get the same! So there exists a pattern to solve this question! In a programming language, we can achieve this by copying the list, reversing the elements, add the new element in each array, appending the modified copy to our original list and voila!

Maybe the law of supersymmetry in physics (which states that for any object, there exists its symmetric twin somewhere else in the universe) could explain this but this technique works for any length of the list!

Now we can also observe that the length of the list is equal to 2 ^ (number of meals)
Inductively we can prove that when new meal is added, the length of the new list of meals is double that of the original list.

n>2

We need to rpove P(n) => P(n+1)

<=> 2^(n+1) = 2^n x 2^1
<=> P(n) x 2 # Which means P(n) was actually 2^n

So inductively we can show that the length of the new list is double the size of the original list.

Hope it helped!

First

Welcome everybody to my blog! This is my first post and I will be posting very frequently about my experience with CSc236. Just as a short recap, I had a nightmarish time with CSC165 - Maths reasoning for computer scientists. I cannot understand why but i feel that I like CSC236! Its more like applying the proof techniques in CSC165 to real world problems. Well, we will see how it goes... Stay tuned for more posts.

-Bimal