Edit the RMarkdown source file for this assignment in RStudio. When you finish, Knit the file to HTML and upload the .html output to Canvas.

The world-famous La Xurrería churrería in the central district of Querétaro, Mexico, sells the best churros you can buy, and offers them in various integer lengths (measured in inches). The price of a churro depends on its length, according to the following table (prices have been converted to US cents). Click on the play button to see the results in the source pane, or knit to see the results in HTML.

##        [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## length    1    2    3    4    5    6    7    8    9    10
## price     1    5    8    9   10   17   17   20   24    30

When the churros come out of the churro-maker, they are \(n\) inches long, but they can be cut into smaller pieces before they are sold. (Here we will consider \(n \leq 10\), but rumor has it that their equipment is being upgraded.) The question is, what is the optimal way to cut an \(n\)-inch churro to maximize the total price of all the pieces?

  1. Consider the case \(n=4\). List all the possible ways to cut a 4-inch churro, and give the total price of each. What is the maximum total price?

Recursive Churro Cutting

Consider the following recursive algorithm for finding the maximum total price among all the ways to cut an \(n\)-inch churro into pieces.

Let price[1..n] be a constant array of prices.
So price[i] is the cost of a churro of length i.

CutChurro(n):
    if n = 0
        return 0
    maxTotPrice <- -1
    for i <- 1 to n
        totPriceTry <- price[i] + CutChurro(n-i)
        if totPriceTry > maxTotPrice
            maxTotPrice <- totPriceTry 
    return maxTotPrice
  1. Determine the number of CutChurro calls made by CutChurro(n) as a function of \(n\), for \(n \geq 0\). You don’t need to give a formal proof (though a formal proof would certainly be sufficient), but if you don’t, you still need to justify your answer in a way that is convincing.

CutChurro in R

Here is an implementation of CutChurro in R. Press the play button to load this function into the current environment.

price <- c(1,5,8,9,10,17,17,20,24,30,34,34,38,40,45,46,47,50,52,55)
CutChurro <- function(n) {
  if (n == 0)
    return(0)
  maxTotPrice <- -1
  for(i in 1:n) {
    totPriceTry <- price[i] + CutChurro(n-i)
    if(totPriceTry > maxTotPrice)
            maxTotPrice <- totPriceTry 
  }
  return(maxTotPrice)
}

Execute the following code chunk to check your answer from #1.

CutChurro(4)
## [1] 10

In R, you can check the running time of an algorithm using the system.time command:

system.time(CutChurro(20))
##    user  system elapsed 
##   1.804   0.016   1.832
  1. Compute the elapsed system time for CutChurro(n) for values of \(n\) from 10 to 20. What do you notice about this sequence of numbers? Does it seem consistent with your answer to #2?