Fog Creek Software
Discussion Board




C Programming exercises

Hi Joel,

I've been teaching a C programming course for several times now but I've run out of interesting pointer programming exercises for my students.

So far I've asked students to implement Lists (single/doubly linked), B-trees, Bags, Collections, Hashtables, etc but that category is almost exhausted without falling into repetition.

There are plenty of other programming examples that involve pointers but they almost always require the use of API's of some sort. I'd like to prevent that as the course is about pointers not about API's

Any suggestions for something in plain ANSI-C?

Teacher in VN
Friday, April 09, 2004

I always liked Red Black trees, myself.

But seriously, why do you have so much time? If you don't have enough material to fill a 1 semester course it's better to teach something altogether different rather than endless pointer-based data structures. May I suggest something like doing integer division using bitwise operators in assembler (WITHOUT using DIV instructions, of course).

Joel Spolsky
Fog Creek Software
Monday, April 12, 2004

Joel, I think the teacher was trying to not repeat material in subsequent runs of the course, not fill up the semester. I assume part of the idea is to prevent students from 're-using' code from previous years.

I'd personally say that the right thing to do IS to repeat the exercises (after a suitable number of semesters). The thing to do is to vary the trappings you put around the doubly-linked list project, rather than to try to vary the underlying project. This will help prevent 'code re-use', while giving the teacher a good idea of what to expect from the students.

I also just had the idea that you might want to make the students do a bunch of string manipulation without using the C standard library primitives. You could phrase it as 'write me a set of primitives' (although, don't ask for the standard ones), or you could just assign a project that involved lots of text, but forbid use of str* or *printf functions. This would serve a multi-fold purpose:
1) It would give them the pointer manipulation experience you desire, with the bonus of not making you in a data structures instructor as well.
2) It would give them a solid understanding of how C really does strings. This will help them in understanding the str* functions and will help when they eventually try to use C++ and run into all the wierdness that surrounds string objects which interact with C style strings.
3) It may get the desire to write their own string handling routines out of their systems. Then someone like me won't have to come clean up after them later.

Michael Kohne
Monday, April 12, 2004

To actually answer your question -- take a look through Intro To Algorithms by Cormen/Lieserson/Rivest and you'll have no end of abstract data types to assign students.

More generally: it's a huge help to understand how to implement basic data structures in order to make use of them later.  But there's the rub -- it's hard to understand them when you don't know what they're going to be used for. 

I often felt that way when I was taking second-year algebra -- I'd understand how to find the Jordan Normal Form of a matrix, but until I actually saw how it was useful as a problem solving technique, it didn't make much sense to me. 

Perhaps you can take your students "to the next level", as it were.  Have them implement a really solid string walker, queue, hash table, set and arbitrary tree.  Then put 'em together -- those five things are the basic building blocks of a lexer/parser/code generator.  Or come up with some other example that USES these tools they've just built.

Eric Lippert
Monday, April 12, 2004

I always found writing a memory manager a good open ended excercise for this type of thing.

Just me (Sir to you)
Friday, April 16, 2004

What about using a online judge type site?

ie http://acm.uva.es/problemset/

Heaps of problems.

Aussie Chick
Saturday, April 17, 2004

Oops, didn't see the 'pointer' specification, still its a good site.

Aussie Chick
Saturday, April 17, 2004

I'm studying Comp Sci at University, and we use the Intro to Algorithms Book (MIT Press) by the 'Four authors' ( I think that it is the one mentioned above).
We've done some kick-ass stuff, but normally we have partially written applications and we have to do the data structures or the essential algorithm.
A few examples:
1) Djikstra's algorithm (we had a map of the UK so we could pick cities and get the route between them, and then we had a map with a few million nodes and ran the app again)
2) tries. They're cool. We used it to index a file -- great fun! We searched the bible for God ;) hehe
3) Have you heard of countdown? Well, in countdown you have 7 letters, a mixture of vowels and consonants, and from this you have to make the longest (English) word. Get your students to do a data structure for that (you'd need to use a basic dictionary or something to help them out. Also conundrums would be cool too.... just use some hash tables) If you want to push your students hard then get them to do the number side of count-down too.

There's loads of really cool stuff that you can do. Good Luck!!

Edward Bateman
Sunday, April 25, 2004

*  Recent Topics

*  Fog Creek Home