Be sure to do a Team…Pull to update your repositories.
It may help to review this example from lecture. It may take a while for the link to resolve to the slide; be patient please.
Write your proofs as text in the studio4.text file of the studiowriteups folder.
Consider each of the following recurrences and initial values:
Problem Number |
Recurrence | Initial value | Solution If you need it Ask the TA for the password |
---|---|---|---|
1. | T(n) = T(n-1) + 2n - 1 | T(0) = 10 | [ solution ] |
2. | T(n) = T(n-1) + 4n - 5 | T(0) = 5 | [ solution ] |
3. | T(n) = T(n/5) + 7 | T(0) = 21 | [ solution ] |
4. | T(n) = 4T(n/2) + 2n | T(0) = 0 | [ solution ] |
For each recurrence:
Here is what you will see in the sheet (using Prob1.xlsx as our example):
- Column A is n, the parameter for the recurrence.
- Column B is the location of the recurrent term. This will change from sheet to sheet, depending on the recurrence formula.
- Column C is the value computed by the recurrence itself. This involves referencing the value of the recurren term and evaluating the right-hand side of the recurrence formula.
- You should not change any of the above columns' contents!
- Column D is where you will do your work, comparing the results you get there with Column C. They should agree exactly (in some rows, but maybe not all) when you have the right answer.
Initially, there is some function in Column D that is certainly not the right answer, but whose values are plotted.
- The plot shows Columns C and D as a function of Column A. As you change Column D, the plot will change too.
- It may help to review these slides from lecture on recursion trees.
- The example of this I did in class can be found in the PersianRecursion.xlsx file in the lecture4 package of your lectures source folder.
Document your findings in the studio4.txt file of the studiowriteups folder of your repository.
If you need help with lab 3, please use time in studio to get help once you have worked on the above problems to the satisfaction of your TA.
When you done with this studio, you must be cleared by the TA to receive credit.
- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click OK while the TA watches
- If you request propagation, it does not happen immediately, but should be posted in the next day or so
This demo box is for studio 4