# 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

- These problems are not cs50 homework. You don't have to do
these, nor by doing them will you get any extra credit. These
questions are for fun only; you
*might* learn something
here that you can apply to cs50, but then again you might not.
These aren't really review questions.

- Challenge problems will be added whenever I feel like it, or
whenever new problems occur to me, whichever comes last.
Check this page every so often; maybe there will be something
new. If you have a problem to suggest, feel free to email it
to me.

- Solutions will
*not* be published, although you can talk
to me about the answers or beg for clues if you so desire.
Some of these problems are quite challenging, although their
answers are all simple- like so many interesting things, many
of these are surprisingly easy to explain and remember but
hard to figure out the first time. Therefore, if I just leave
the answers sitting on a web page, people will just read that
page and be denied forever the joy of solving these problems
themselves.

## 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>