stat 579

Homework: week 9

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

In one of the previous homework assignments, 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):

  1. 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]))
    }	
    
  2. 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)}
    
  3. 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 = ""))
    }
    
  4. 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:
  1. 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).
  2. 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).
  3. 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: