Dan's cs50 Challenge Problem Page

A few problems that you might find interesting or amusing. All of them are related to topics that we've studied in cs50 this year.


Rules of the Game


Challenge Problems

1. The Order of Fib

Consider the following recursive implementation of the Fibonacci function:
	int	fib (int n)
	{
		if (n <= 1)
			return (1);
		else
			return (fib (n - 1) + fib (n - 2));
	}

This function is not particularly efficient; in fact it's awful. This one is particularly natural to write, however. We've seen better ways to compute the same function, but that's not the point.

Challenge: Exactly how many times is this function called (including recursive calls to itself) when it is used to compute fib(n) for any n greater than 0?

Possible Hint: Any binary tree that has the property that all of its nodes have either two or zero children also has the property that if it has x leaf nodes, then it has exactly x-1 internal nodes.

2. Doubly-Linked Lists (With Only One Link)

In assignment 6, you explored how to implement doubly-linked lists using two pointers- a pointer to the previous element of the list and a pointer to the next. However, it turns out that this is not necessary; with some cleverness, you can devise a doubly-linked list data structure that only has one link, and yet allows traversal along the list in either direction (in effect, all the generality of a doubly-linked list).

Challenge: Describe (in sufficient detail that someone could implement something according to your description) a linked list data structure that allows traversal in both directions, but only requires one "link" instead of two.

Possible Hint: Consider the following interesting property of the bitwise XOR operator (written as ^ in C): for any A and B, it turns out that if C = A^B, then A = C^B and B = A^C as well.


Please bring any errors or inconsistencies in this document to the attention of the author.

Dan Ellard <ellard@deas.harvard.edu>