“I define nothing. Not beauty, not patriotism. I take each thing as it is, without prior rules about what it should be.” Bob Dylan

This week we had our last test before the final. I missed the post regarding the absence of chapters 6 and 7 on the test and found myself trying desperately to grasp the concepts running time of programs and numerical systems. Running time of programs is fairly straight forward. Although it is annoying and tedious its nice to see the computer programming finally start to blend in to the 165 material. On the other hand although also bringing in an element of programming I found the numerical systems chapter very hard to grasp. To my surprise and relief the test did not cover that material. Learning it for the final without ever working on it on an assignment or exercise is going to be quite a challenge but hopefully within the next two weeks I'll be able to grasp the material.

As for some final words, 165 was quite an eye opener. This course has reviled to me a passion I never knew I had and I look forward to diving deeper in to the material on the future.

Professor Heap could not have done a better job teaching this course.

Many Thanks ;)

G. Polya, "How to Solve It"....Subsequence part II

I'm running out of time on this one so reluctantly I'm posting my results so far.

Unfortunately the last test case I wrote is failing. After taking a little break and revisiting the problem and being unable to get the last test case to work I'm almost certain this algorithm is very wrong and I would most likely start from scratch on this one.

But as the process of problem solving goes this is where I'm at at the moment, and the moment is slowly running out.

def sub_seq(s, sub):

'''Return the number of times the string sub if found (not necisarly

adjacently) in the string s.

'''

return _sub_seq(s, sub)

def _sub_seq(s, sub, index=0, count=0):

'''Helper for Seb_seq

'''

if sub:

index = s.find(sub[0])

if sub[0] != sub[-1]:

count += 1

return _sub_seq(s,sub[1:], index, count)

else:

while index <>

count += 1

index = s.find(sub[0], index + 1)

return count - 1

else:

return

if __name__=='__main__':

# a substring with the first character in the 0th index

s = '12'

sub = '12'

assert sub_seq(s, sub) == 1

s = '123232'

sub = '12'

assert sub_seq(s, sub) == 3

# a substring with the first character in a random index

s = '8888188882'

sub = '12'

sub_seq(s, sub)

assert sub_seq(s, sub) == 1

# a substring with the first character in a random index

s = '8888188882888882'

sub = '12'

sub_seq(s, sub)

assert sub_seq(s, sub) == 2

# This is Failing

# a substring with the first indices repeating

s = '1212'

sub = '12'

sub_seq(s, sub)

assert sub_seq(s, sub) == 3, 'got %d' %sub_seq(s, sub)

G. Polya, "How to Solve It"....Subsequence part I

So I took some time over the week to think though my previous suggested solution. I couldn't get it to work and it seemed that the idea was wrong so I decided to drop it.

While checking up on the website this week I came across the requirements for this SOLG and came across the the article name in the title. Well, I figured considering my situation this would be a good time to use it, and I think It actually helped.

Here it is...

UNDERSTANDING THE PROBLEM

I drew out various possible test cases for the sub sequence problem and determined at each step what I know about the data, condition and variable.

DEVISING A PLAN

The plan I came up with is very simple.

Search for the first occurrence in the string of the first character in the sub string.

Once found call a recursive function that returns the number of times the next letter in the substring occurs after the current index. This creates a recursive function that returns the number of times that the substring occurs for that first letter. Do this on every time the first letter is seen and the result should be the number of times that substring occurs in the string.

CARRYING OUT THE PLAN

To be continued.....

"Understanding how DNA transmits all it knows about cancer, physics, dreaming and love will keep man searching for some time." David R. Brower

The subsequence teaser question that was given out in class on friday kept me thinking for a while about it. I guess it was the fact that the natural solution was one thats implementation was extremely long that kept me thinking. I guess I never really thought about the fact that there are problems that need solving all around us that may be hard to solve just because of their size.

Any way I thought about a possible solution and I don't even know if I'm on the right track or not nut I figured I would jot down my thoughts and maybe latter try to code it up and see if im on the right track.

Here it is.

Scan the list once. While doing so create a dictionary with the items of the list as keys and there index placements in the list as values. in addition to that create a binary search tree from the list in order to cut down search time when retrieving a certain element from a list.

given a a case that the main string was 'xyxayxya' and you were looking for the number of occurrences of 'xya' instead of looking at the string you can refer to the dictionary that would look like this

{'a': [3, 6], 'x': [0, 2, 5], 'y': [1, 4]}

then for every character of the sub string 'xya' you check recursively how many times the next character happens at an index that is strictly larger.

looking at x[0] would return y[1] would return a[3, 6] would return y[4] would return a[6]

looking at x[2] would return y[4] would return a[6]

looking at x[5] would return nothing because there is no y at a bigger index.

I'll try to code this up and see where it goes.

Thanks for reading

"Everything is vague to a degree you do not realize till you have tried to make it precise." Bertrand Russell

Since test 1 is done with it seems that the course is turning the corner and we have now started working with proofs. I find proofs very interesting especial given the new found knowledge of the different techniques in approaching logical statements. I feel that in the past when dealing with proofs unless I had a clear path to follow I could stare at a the problem without knowing where to begin. 165 has given me a new perspective on problem solving and I can feel how my mental tool box is slowly growing and enabling me to structure proofs on my own without knowing where the result will lead me to.

In spite of all this rambling, I found the last assignment a little bit tricky. I generally try to do to get started on the assignment relatively close to the date we get them and go over them to correct any mistakes closer to the due date. When going back to review my work this time, after a week of going over proofs I discovered that my approach was all wrong and consequently so were all my answers. For some reason while trying to prove

∀ n ∈ N, U(n) => U(n2)

Where U(n) is defined as,

∀ n ∈ N, U(N) ⇔ ∃K ∈ N, N = 5K + 1

I'm not sure if it was the way the definition of U(n) was given but something about the ∀ n ∈ N, coming before the U(n) itself made me think that all I had to do was prove existence. When going back to review my work (at around 9:15pm the day it was due) I realized my mistake and franticly tried to figure out the right way to fix it. I hope it when't well and I'm pretty sure I got it right in the end.

The current topic that is blowing my mind is proving the obvious, who would have imagined.....

“Logic is the art of going wrong with confidence” Joseph Wood Krutch

Here It goes, my first 165 blog. In fact this is my first blog ever so I figure this is a good opportunity to contribute to a rapidly growing world of idea sharers. My thoughts on the course so far have been mostly an overall notion of excitement mixed with frustration. I'll start with the frustration since I am currently stuck on some questions in assignment one. With the course falling under the general umbrella of logic and reasoning you would think that there would be some logical flow to the reasoning behind the concepts in the course. Or at least what I thought was logical reasoning. It turns out that through years of practicing logic through the ambiguity of language what seems like logical reasoning can be quite far from it. It seems like the courses first goal is to break down the idea that In my head " I know what logical reasoning is, its common sense, I've been doing it my whole life". Well it turns out to be not so common and often to not make much sense. I admit what seems to be the first goal of the course is working on me. But as you know, old habits die hard, hence the frustration.

Moving on to the excitement, I took a pause from my everyday scrambling through the day trying to get my work done to take a pause and look at the power that lies behind the ideas of logic and reasoning. What I discovered a wonderful world I can't wait to start exploring. It just so happens that mathematical logic, although being the core of this course, is just one out of the many applications of logic. Logic spills over into fields such as Philosophical Logic, Formal and Informal Logic of Language, Inductive and Deductive Reasoning, Argumentation Theory and many many more.If jumping head first in to topics like that with a skill set enabling you to immerse yourself with the content doesn't excite you, your not on the same page as I am. With that said, I'm going back to work …. ;)

Thanks for reading

¬øThoughts