stat 579

Homework: week 9

Due in class, Tuesday/Thursday Oct 26/28.

Reading assignment: read Yihui's blog entry on the last homework assignment.

In homework assignment 7, you were asked to implement a function, that allowed you to find the number of occurrences of a specified binary pattern y in a binary sequence x. There are a lot of different ways to solve this. Below we have listed four different solutions (not necessarily actual answers):

pattern_a <- function(y, x) {
# find binary pattern y in sequence x
	if (!all(y %in% c(0,1))) stop("y is not a binary pattern")
	if (!all(x %in% c(0,1))) stop("x is not a binary sequence")

	# check that y isn't longer than x:
	if (length(y) > length(x)) return(0)

	# does x start with pattern y?
	found <- all(y==x[1:length(y)])

	# check the rest
	return( found + pattern_a(y,x[-1]))
}

pattern_b <- function(y,x) { result <- 0
if (!all(y %in% c(0,1))) stop("y is not a binary pattern")
if (!all(x %in% c(0,1))) stop("x is not a binary sequence")
if (length(y) > length(x)) return(0)
for (i in 0:(length(x)-length(y))) result <- result + all(y == x[i + (1:length(y))])
return(result)}

break_vec = function(x, M) {
    n <- length(x)
    if (M > n)
        stop("the block size M = ", M, " is greater than length of x (", n, ")")
    x0 = 1:(n - M + 1)
    substring(paste(x, collapse = ""), x0, x0 + M - 1)
}

pattern_c <- function(y,x) {
	sum(break_vec(x, length(y)) == paste(y, collapse = ""))
}

pattern_d <- function(y,x) {
	result=0
	n=length(x)
	k=length(y)
	for (i in 1:(n-k+1)) {
		j=0
		stop=FALSE
		while ((j < k) & !stop) {
			if (x[i+j] != y[j+1]) stop=TRUE
			j=j+1
		}
		if (!stop) result=result+1
	}
	result
}

For the four different solutions above:

Discuss, how you can test, whether the functions do what they claim to do. Come up with a set of examples, that tests each function (in a function, preferrably).
Run each of the functions above through your test set. Try to 'break' each function (at least one of the functions above is breakable - see whether you find its weak spot, and describe it).
Discuss, which of the solutions above you 'like' - try to think of at least five different criteria of what, in your opinion, makes good code.

Deliverables:

Submit a write-up with your discussions and an R script with the test routines.

Sample Solution:

Coming up