[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]

Back to Project Discussion. On to More Recursive Algorithms.

**Held** Monday, October 9, 2000

**Summary**

Today we finally consider how to analyze recursive algorithms.

**Notes**

- Homework 3 is due at 5pm today.
- Are there any final questions?
- I'll grade it, but not until break.

- How did Friday's class go?
- For Friday, I'd like to have you have working
*stubs*for the utility classes. Email them to your fellow students. - I should have the next exam ready on Friday.
- I probably won't give you a homework assignment on algorithm analysis; your test will serve that purpose.
- I'll (finally) take questions on Bailey at the start of class tomorrow.

**Overview**

- Analyzing the recursive smallest algorithm
- Recurrence relations
- Binary search

- While you know some techniques for computing the running times of
iterative algorithms, you don't know about ways to compute the
running times of recursive algorithms.
- The iterative technique doesn't work for recursive algorithms because the function call involves the function itself.
- It is possible to rephrase every recursive algorithm iteratively.
- However, it may be easier to directly analyze the running time of a recursive algorithm.

- We'll consider our recursive smallest algorithm first.
- We'll begin by investigating a few recursive algorithms, including
binary search, exponentiation, and various forms of computing values
in the Fibonacci sequence.
- Binary search: find something in a sorted collection
- Exponentiation: compute x
^{n} - Fibonacci: determine the nth element of the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, 21, ...

- How much does it cost to ``split the array in half''?
- It depends on the implementation.

- How do we deal with the recursive call?

- You learned binary search in 151 (or at least I think you did). We'll review it quickly and look at some analysis.
- To find something in a sorted collection:
- Identify the middle element of the collection
- If that's the thing you're looking for, you're done.
- If that thing is larger than what you're looking for, recurse on the subcollection of smaller elements.
- If that thing is smaller than what you're looking for, recurse on the subcollection of larger elements.

- What's the running time? How do you know?

Wednesday, 23 August 2000

- Created as a blank outline.

Thursday, 24 August 2000

- Slight reorganization to page design.

Monday, 9 October 2000

- Filled in the details.

Tuesday, 10 October 2000

- Removed uncovered details (now in the next outline).

Back to Project Discussion. On to More Recursive Algorithms.

[Current] [News] [Glance] [Search] [Instructions] [Links] [Handouts] [Project] [Outlines] [Labs] [Homeworks] [Quizzes] [Exams] [Examples] [EIJ] [API]

**Disclaimer** Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.

This page may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Outlines/outline.26.html

Source text last modified Wed Oct 25 10:05:37 2000.

This page generated on Fri Oct 27 08:19:59 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu