“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.....