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
- 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
1. The Order of Fib
Consider the following recursive implementation of the Fibonacci
int fib (int n)
if (n <= 1)
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
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 <firstname.lastname@example.org>