Programming Languages (CS302 2007S)

[Skip to Body]

**Admin:**
[Front Door]
[Glance]
[Handouts]
[Honesty]

**Current:**
[Current Outline]
[Current EBoard]
[Current Homework]

**Groupings:**
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Outlines]
[Readings]
[Reference]
[HOG]

**Misc:**
[SamR]
[CSC302 1999S]
[CSC302 2006S]

Assigned: Friday, February 2, 2007

Due: Friday, February 9, 2007

*No extensions!*

This homework is also available in PDF.

**Summary:** In this assignment, you will reimplement two classic recursive algorithms without recursion.

**Purposes:** To give you more experience understanding recursion. To help you think about the design of languages.

**Expected Time:** Two to three hours.

**Collaboration:** You may work alone or you may work in a group
of size two or three. I encourage you to work in groups on this assignment.
You may discuss the assignment with anyone you'd like, provided you cite
such discussions in your assignment.

**Submitting:** Email
me your answer. More details below.

**Warning:** So that this exercise is a learning assignment
for everyone, I may spend class time publicly critiquing your work.

As Hoare mentions (and as you'll see in some followup readings), the addition of recursive functions to programming languages was a great advance. Of course, it is certainly possible to translate every recursive function into a corresponding iterative function. In some cases, you'll need to use a stack to simulate the recursion. In others, you will need to simulate the stack.

As you may recall from CSC151, there is an elegant, logarithmic algorithm
for computing x^{n}, for integer n. Here, I express it in Scheme.

(define expo (let ((square (lambda (val) (* val val)))) (lambda (x n) (cond ((zero? n) 1) ((odd? n) (* x (expo x (- n 1)))) (else (square (expo x (/ n 2))))))))

Rewrite this algorithm without recursion. Note that your solution
must still be O(log_{2}*n*). You may not use a stack.

You can solve this problem in C, Java, or Scheme.

Hoare, who seems to be providing an initial focus to this course, is also the author of Quicksort. As you likely know, the Quicksort algorithm, like most divide and conquer algorithms, is naturally recursive. It also involves a more complex type of recursion than the previous problem, in that there are two recursive calls at each level, rather than one.

Rewrite Quicksort without using recursion.

You can solve this problem in C, Java, or Scheme.

Correct, working, solutions will earn a check.

Particularly elegant solutions, or solutions that include an analysis of the principles you used to rewrite the algorithms are likely to receive a higher grade.

Non-working or incorrect solutions will earn a lower grade.

Please submit this via email, using a title of CSC302 HW3.

Attach the files that you've created to that email message.

[Skip to Body]

**Admin:**
[Front Door]
[Glance]
[Handouts]
[Honesty]

**Current:**
[Current Outline]
[Current EBoard]
[Current Homework]

**Groupings:**
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Outlines]
[Readings]
[Reference]
[HOG]

**Misc:**
[SamR]
[CSC302 1999S]
[CSC302 2006S]

**Disclaimer**:
I usually create these pages on the fly

, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.

This document was generated by
Siteweaver on Sun Apr 29 11:25:29 2007.

The source to the document was last modified on Thu Feb 8 21:04:30 2007.

This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS302/2007S/Homework/hw.03.html`

.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu