My office phone number is 496-6246 (8am-5pm), and my home phone number is 643-9644 (6pm-10pm). Please do not call me after 10pm, or before 10am on weekends.
By far the best way to reach me (or anyone on the course staff) is via email. My email address is ellard@deas. The email address of the course account is lib50@fas.
email is also the easiest way for me to get information to you. Please check your mail at once a day or so.
int *i;This defines i to be a pointer to an integer. It does not specify what integer i points to, nor has it allocated memory somewhere for i to point to.
You must never dereference a pointer variable unless you have assigned a valid address to that pointer.
On the last pages of this handout, I've included a printout of a few binary tree functions. These are different from the functions in the lecture notes; I thought it might be interesting to see another approach to the same problems, so I wrote these routines based on slightly different algorithms.
The last function, tree_display, can be very useful for debugging binary tree structures.
Note: writing the animals program consists of several steps, which must be done in the order described in the assignment in order to get full credit.
Draw pictures; walk through the algorithm step by step. If you can't play the animals game on paper (or a chalk board), your efforts to explain the game to the computer will probably be in vain.
Good design is essential to effective programming. Once you have a good design, writing the code will be quick and painless.
In general, a better design will result in less time spent coding and debugging. This program may seem complicated at first, but once you have decomposed the program into smaller pieces, you'll see that it is actually relatively small and simple.
Note that if you complete this part of the assignment before 6:00pm Monday night and email a copy to me, I will review your design and offer suggestions (and let you know if you're headed in the right direction). If you take advantage of this opportunity, you will almost certainly do better on this assignment (and with less pain) than if you do not.
Note that I cannot read pine attachments with my mail reader, which is not pine. When you email your design to me, please do so as plaintext. Use mail if you can't find another way, i.e.
cat design.txt | mail ellard@deas
Note that for this assignment, you should organize your program up into separate source files (i.e. .c and .h files). The Roberts book discusses how to do this in chapter 10 (and later chapters).
Analyze the success of your design. Did it work out the way you planned? What would you change if you could start over from scratch? What have you learned about program design? (pay particular attention to the questions in the assignment)
Note that we're not asking you to comment, edit, or change these functions in any way. There's no need to even compile them and run them (the work of setting up a test program for each would be a lot of work all by itself). Instead, all we ask is that you read through them and figure out what they do and what algorithm they use to do so.
Each recursive algorithm has two cases:
Note that the recursive case must move towards the base, by reducing the ``size'' of the problem. If it doesn't, then the base case will never be reached, and the algorithm will not terminate.
For example, consider the problem of doing an inorder traversal of an ordered binary tree. This can be done using purely iterative constructs, but is far from trivial to code- give it a try, if you like! (hint- a stack or two will come in handy. I may be able to avoid using stacks through extreme cleverness, but I can't remember exactly how, so it's probably a little on the obscure side.)
As another example, consider the quicksort algorithm (a sorting algorithm we will cover later in the semester). When it was first invented (by C. A. R. Hoare), programming languages that supported recursion were not widely used, so it was initially described and implemented using only iterative constructs. Unfortunately, it is quite complicated to correctly state the quicksort algorithm without recursion. In fact, the original implementations were so complex and hard to follow that there was some debate over whether or not they actually really worked! Once the algorithm was restated in a recursive form, however, the algorithm was quickly proven to be correct.
/* The NULL test must come first! */ if (cell == NULL) { return (NULL); } else if (cell->value == value) { return (cell); }
return (llist_llookup (cell->next));
llist_lookup (llist_t *cell, int value) { if (cell == NULL) { return (NULL); } else if (cell->value == value) { return (cell); } else { return (llist_llookup (cell->next)); } }
Now, let's try an algorithm that puts together a few more concepts, playing with both recursion and pointer arithmetic: an algorithm for finding the sum of the elements in an array of integers. For reference, here's an iterative solution:
int array_sum (int length, int *array) { int i; int sum = 0; for (i = 0; i < length; i++) { sum += array [i]; } return (sum); }
As an aside, unrelated to recursion, note the use of pointer notation to represent the array. By using pointer notation instead of array notation, we can eliminate the requirement that we specify the length of the array as part of its type, but instead can pass this as a separate parameter. Therefore, this function will work properly with arrays of any length, not just some fixed length.
To restate this recursively, we need to identify the base case and the recursive case (or cases).
For this problem, we have a choice of base cases, depending on what sorts of assumptions we dare to make about the array. If we know that the array will always be at least one element long, then the base case can be that the sum of the elements of an array of length 1 is the value of the first element. However, let's be more general, and allow the user to enter arrays with length zero. So, our base case will be that the sum of an array of zero elements is zero. This translates into the following C:
if (length == 0) { return (0); }
To be more defensive, however, we might find it useful to consider the case when the user (or the calling function) goes berserk and enters a negative value for length. To guard against that, we'll modify this to say that the sum of an array of zero or fewer elements is zero:
if (length <= 0) { return (0); }
Note: we could also prevent the possibility of a negative length by saying that length is an unsigned integer, and therefore can never be negative. (We haven't talked about unsigned numbers much yet, but you can read about them in K+R or Roberts.)
Now, we need a recursive case. Here's one: the sum of the elements is the sum of the first element in the array and the sum of the rest of the elements. This translates into the following C:
return (array [0] + array_sum (length - 1, array + 1));
Note the address arithmetic used here: array+1 is the address of the "rest" of the array past the first element.
Putting the pieces together:
int array_sum (int length, int *array) { if (length <= 0) { return (0); } else { return (array [0] + array_sum (length - 1, array + 1)); } }Attached to this handout are several examples of recursive algorithms.
Examples of an algorithm with this order include linear search, and searching through a linked list.
Examples of an algorithm with this order are binary search, or searching through a balanced binary tree.
Quicksort and mergesort are examples of this. (We haven't studied these yet, but we will.)
A list of TF and their topics of interest can be found in: http://www.deas.harvard.edu/cs/academics/courses/cs50/final-project/proj.html. If your interests don't match up with mine, then feel free to contact a TF whose interests do seem like a better match (although of course you'll need to talk to me about your proposal eventually!). The most important thing is to pick a project that you will enjoy; you'll be spending a lot of time working on it, so you might as well be having a good time doing so!
Your project proposal should look something like a combination of a problem set and a design document (although not necessarily as detailed as the design document for animals). It must describe what the goals of your project are, and how you will achieve them. The design should be detailed enough so that it is clear to me that you understand how to accomplish your project goals. Keep in mind that your project will be graded based on how well you meet your own goals, so it is in your best interest to clearly state your goals and how you will demonstrate that you have met them!
In the past, the most common problems students have had with their final projects were that either they couldn't think of anything interesting (if this is the case for you, talk to me; I've got a hundred ideas that you might find interesting), or they thought of something far too complex or time-consuming to implement (it should be about twice as complex or time-consuming as an ordinary homework, like assignment 6, but not more).
In past years, students who thought through their proposals and let me review them once or twice before the deadline generally found the final project to be the most fun and rewarding part of the course. Students who waited until the last minute, however, deeply regretted it later; several were killed by rhinos.
Dan Ellard - (ellard@deas.harvard.edu)