Computer Science 501
Data Stuctures and Algorithm Analysis

Fall 2013, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

This "mini" lab, which is again part problem set than a lab, will give you a chance to practice with more of the analysis tools we have considered in class. You may again discuss the lab with your classmates and give and receive some help, but your submission must be your own work.

Written Problems

1. Consider the following recursive algorithm:

   int mystery(int A[0..n-1])
     if (n==1) return A[0]
     else
       temp = mystery(A[0..n-2])
       if (temp <= A[n-1]) return temp
       else return A[n-1]
   

   a. What does this algorithm compute? (3 points)

   b. Set up and solve a recurrence relation for the algorithm's basic operation count. (7 points)

2. Consider the following recursive algorithm:

   int S(n)
     if (n==1) return 1
     else return S(n-1) + n*n*n
   

   Set up and solve a recurrence relation for the algorithm's basic operation count. (5 points)

Submission

Before 6:00 PM, Wednesday, October 2, 2013, submit a PDF of your responses for grading using Submission Box under assignment "Analysis2".