Help me design a class project!

This is a discussion on Help me design a class project! within the A Brief History of Cprogramming.com forums, part of the Community Boards category; Hey guys, I have to design a difficult, two-week project on recursion for the first semester programming class I'm teaching. ...

  1. #1
    Registered User codegirl's Avatar
    Join Date
    Jun 2003
    Posts
    76

    Help me design a class project!

    Hey guys, I have to design a difficult, two-week project on recursion for the first semester programming class I'm teaching. But I'm having a hard time finding something that's difficult yet doesn't require any data structures except for linked lists (which is all they would have learned at this point).

    For an example, last semester they had to decrypt a message, where the encrypted message was made by substituting letters, e.g. substituting every "a" for a "c". They were given an encrypted message and a dictionary of words that could appear in the solution. They had to take one encrypted word and figure out a substitution that would yield a valid word. Using that substitution (e.g. maybe they decided that all a's were substituted with c's) they had to solve the rest of the message. If they reached a point where they had a word that was not in the dictionary, then they must have made an invalid substitution and had to back out of the recursion and try again. (Maybe the c's in the encrypted message were actually e's, not a's.) We gave them no skeleton code for this project; they had to do it all themselves. But I can give them some skeleton code for this project if necessary.

    If you have an idea, please do not post a solution in case a student stumbles upon this site. Just state the problem as if you were assigning it to your students and I'll figure out the solution. It just has to be something a lot more complicated than the standard write a recursive function to calculate n! -- it needs to take them a full 2 weeks.

    Thank you!
    My programs don't have bugs, they just develop random features.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >something that's difficult yet doesn't require any data structures except for linked lists
    Implement a linked list library with recursive internals. To make it more difficult, require them to maintain a free store of nodes (usually implemented as linked list) as an optimization for memory management.
    My best code is written with the delete key.

  3. #3
    ...
    ... is offline
    Registered User
    Join Date
    Feb 2002
    Posts
    465
    2 weeks for recursion? eesh... my programming class gave us a day, at most, to learn it. of course, its not a semester long class either :-\

    i dont know if this is a 2-week worthy assignment, but how about implimenting quicksort? i wrote a quicksort algorithm that would sort a linked list where the next pointers get rearranged to order the list in the way specified by the user (by passing in a compare function). maybe have this as part of the link list library mentioned by prelude...
    I came up with a cool phrase to put down here, but i forgot it...

  4. #4
    Banned nickname_changed's Avatar
    Join Date
    Feb 2003
    Location
    Australia
    Posts
    986
    Difficult and with linked lists... maybe their own version of a string class with simple operators etc?

    Although there might not be much recursion in that... hm.... what about the towers of Hanoi I spent an hour or so today playing out with pieces of paper how that could be done. Lots of fun!!

  5. #5
    Registered User codegirl's Avatar
    Join Date
    Jun 2003
    Posts
    76
    Thanks for the suggestions!

    Prelude, may I ask what recursive internals are? I don't think I've heard that term before.

    quicksort would definitely be too easy for a project, that would be something they might whip up in lab. I wish they knew trees or something so I could think of something really nasty!

    Towers of Hanoi is a possibility, but I would be worried that they might find the algorithm or even some code online for such a well-known problem.... sigh ... this may be a harder project to design than I thought!

    Any other suggestions? Thanks!
    My programs don't have bugs, they just develop random features.

  6. #6
    Registered User
    Join Date
    Apr 2002
    Posts
    1,571
    What about the 8-queens problem? Or if you want to mix it up, the knight's tour. Those are pretty good.

    Edit: You can easily extend it to an n-queens problem.
    "...the results are undefined, and we all know what "undefined" means: it means it works during development, it works during testing, and it blows up in your most important customers' faces." --Scott Meyers

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Prelude, may I ask what recursive internals are? I don't think I've heard that term before.
    Instead of using loops to implement operations like insertion and deletion, use recursion.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Input class project (again)
    By Elysia in forum C++ Programming
    Replies: 41
    Last Post: 02-13-2009, 10:52 AM
  2. Design guidelines advice - IRC Bot class
    By IceDane in forum C# Programming
    Replies: 2
    Last Post: 12-05-2008, 01:21 AM
  3. Game Independent Anti-cheat Project Needs Programmers
    By GIA Project Lea in forum Projects and Job Recruitment
    Replies: 3
    Last Post: 09-15-2005, 08:41 PM
  4. problems in with design of a server project.
    By codec in forum C++ Programming
    Replies: 4
    Last Post: 02-28-2003, 09:11 AM
  5. gcc problem
    By bjdea1 in forum Linux Programming
    Replies: 13
    Last Post: 04-29-2002, 07:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21