Lecture 14: Due Oct. 25, 9:00pm. Email ShaloshBEKhad@gmail.com an attachment
hw14FirstLast.txt
OK to Post

	1)Use a procedure CountRuns(L,k) that inputs a list L of numbers (or for that matter, any objects) and outputs the number of "runs" of length k in L
	  [A run of length k is a string L is an occurence of an i such that L[i]=L[i+1]=...=L[i+k-1]
	  For example
		CountRuns([1,2,2,2,1,1,1,1,2,2,2],3) is 4 for the runs starting at i=2, i=5, i=6, i=9. Note that it can be part of a longer run.
	  [Hint: a quick way to find whether location i is the beginning of a run of length k (where i is between 1 and nops(L)-k+1, is to see if nope({op(i..i+k-1,L)})=1]

		A:
			CountRuns:=proc(L,k)local i,j,counter, count:
			counter := 0:
			for i from 1 to nops(L)-k do
			 for i from i to (i+k) do
			  if L[i] = L[j] then 
			   count:=count+1:
			  else
			   break:
			  fi:
			  if count = k then
			   counter := counter + 1:
			  fi:
			 od:
			 count := 0:
			od:
			return counter:
			end:



	2) Use the above CountRuns(L,k) that you just wrote, combined with procedure RPath in M14.txt to write a procedure AvePathRuns(m,n,k,N) That inputs 
	   positive inetgers m,n,k, and a LARGE positive integer N, generated N random paths, for each of them records the number of runs, and finds the sample average and
	   standard-deviation (the squre-root of the variance) Run AvePathRuns(200,200,5,3000) ten times and see what you get. Are they close to each other?
		
		A:
			AvePathRuns:=proc(m,n,k,N) local Sum, temp, l, dev, i, together:
			l := []:
			dev:= 0:
			Sum := 0:
			for i from 1 to N do
			 temp := RPath(m,n):
			l:=[op(l), CountRuns(temp,k)]:
			#print(l):
			 Sum := Sum + l[i]:
			od:
			Sum := Sum / N:
			for i from 1 to N do
			 dev := dev + (Sum - l[i])^2:
			od:
			dev := dev / N:
			together:=[evalf(Sum), evalf(sqrt(dev))]:
			return together
			end:

			#Since 3000 was too large, here is:
			seq(AvePathRuns(200,200,5,300), i=1..10)= 
			[23.7233333300, 7.6932950590], [23.2566666700, 7.4456333190], 
			[24.1733333300, 7.8151533720], [24.2266666700, 7.5882775070], 
			[24.2400000000, 6.6464827800], [23.7633333300, 7.4476386990], 
			[24.0766666700, 7.3324022130], [24.4700000000, 7.5083797630], 
			[24.2766666700, 7.6937283260], [24.0233333300, 7.8185328260]


			#The outputs for the average and standard-deviation are vey similar

	3) Do the analogous thing for Good paths, writing AveGPathRuns(m,n,k,N)
	   [Hint: you only have to change one word in the code]
	   Run AvePathGRuns(200,200,5,3000) ten times. How does it compare with the previous output for all paths?
		
		A:
			AveGPathRuns:=proc(m,n,k,N) local Sum, temp, l, dev, i, together:
			l := []:
			dev:= 0:
			Sum := 0:
			for i from 1 to N do
			 temp := GPaths(m,n):
			l:=[op(l), CountRuns(temp,k)]:
			#print(l):
			 Sum := Sum + l[i]:
			od:
			Sum := Sum / N:
			for i from 1 to N do
			 dev := dev + (Sum - l[i])^2:
			od:
			dev := dev / N:
			together:=[eval(Sum), eval(sqrt(dev))]:
			return together
			end:

			seq(AvePathRuns(200,200,5,300), i=1..10)

	4) A maximal run is a run L[i]=L[i+1]=...L[i+k-1] AND L[i-1]<> L[i] and L[i+k]<>L[i]
	   [Hint: a quick way to find whether location i is the beginning of a MAXIMAL run of length k (where i is between 1 and nops(L)-k+1, 
           is to see if nope({op(i..i+k-1,L)})=1 and L[i-1]<>L[i] and L[i+k]<>L[i]]
	   Write procedures CountMaximalRuns(L,k), AvePathMaximalRuns(m,n,k,N), and AveGPathMaximalRuns(m,n,k,N) and do the analogous thing for the above two problems,
	   (that you did for Runs) for Maximal Runs.

		A:
			CountMaximalRuns := proc(L, k) local i, count, ans:
			ans := 0:
			count := 0:
			for i from 2 to nops(L) do 
			    if L[i] = L[i - 1] then 
				count := count + 1: 
			    elif L[i] <> L[i - 1] then
				if k < count then 
				     count := 1: 
			  	elif count = k then 
				     ans := ans + 1: 
				     count := 1: 
			   	elif count < k then 
				     count := 1: 
				fi:
			    fi:
			od:
			if count = k then 
			    ans := ans + 1: 
			fi:
			ans:
			end:

			with(Statistics):
			AvePathMaximalRuns := proc(m, n, k, N) local S:
			S := [seq(CountMaximalRuns(RPath(m, n), k), i = 1 .. N)]:
			[Mean(S), StandardDeviation(S)]:
			end:

`			seq(AvePathMaximalRuns(200,200,5,300), i=1..10)

	5) Write a procedure GoodBrother(L) that inputs an arbitrary list of ODD length that adds up to 1 (so if the length is 2*n+1 it must have n+1 1's and n -1's), 
	   and outputs the UNIQUE cyclic shift that is a so-called Dyck path of length 2*n with 1 appended at the end.
	   For example GoodBrother([[1,-1,-1,1,1,1,1,-1,-1,-1,1]=[1,1,1,-1,-1,-1,1,1,-1,-1,1]

		A:
			helper := proc(L) local i, count, ans:
			count := 0:
			for i from 1 to nops(L) do
			   if L[i] = 1 then 
				sum = sum + 1: 
			   else
				sum = sum - 1:
			   fi:
			   if count < - then
			        return false:
	   		fi:		
			od:
			return true:
			end:
			
			GoodBrother := proc(L) local i, S, A:
			S := CycShi(K):
			A := []:
			for i in S do 
			 if  helper(s) = true then
			   if s[nops(s)] = 1 then
			      A := [op(A), s]:
			   fi:
			 fi:
			od:
			A:
			end: