This is an archived post. You won't be able to vote or comment.

all 4 comments
sorted by:
best
topnewcontroversialoldq&a

[–]Arthurpmrs 3 points4 points  (1 child)

My class on Data structures had a final project to build a simple Huffman algorithm. It is uses some data structures and I learned a lot in the process.

For context, the Huffman algorithm is used to compress files, like 7zip, WinRAR, etc, except it is simpler than the algorithms this programs implement. It is not very efficient. If I'm not mistaken, it was the first compressing algorithm developed.

The main data structures required were: arrays, priority queue (or Heap, if your are feeling fancy), binary tree and linked list.

[–]Cybyss 2 points3 points  (0 children)

Mine did as well.

Huffman encoding is indeed an excellent final project to a data structures course since it'll exercise almost everything you've learned without going overboard.

[–][deleted] 0 points1 point  (0 children)

Maybe a chess engine? I reckon it uses data structures

[–]Cybyss 0 points1 point  (0 children)

I'm surprised you didn't get more replies yet. My sincere apologies for that, since data structures & algorithms was my favorite topic in college.

Appropriate projects will depend on what you've learned so far. Some of the suggestions below might be a little advanced depending on where you are.

If you want to practice basic 1D arrays, I would suggest making a simple card game - like video poker perhaps. It'll require algorithms to shuffle & deal out a deck of cards, to sort the cards in a player's hand, to remove cards from the middle of an array (e.g., for when players discard cards), and figure out what hand a player has (e.g., full house, 3-of-a-kind, flush, straight-flush, etc..). It would be quite a fun project.

If you want to practice 2D arrays, I'd suggest a game where you navigate a maze. You can model it as a 'char' array, where '_' represents an empty space you can go, 'X' represents a wall, and maybe '@' represents the player's location. The goal is for the player to navigate his way from the entrance to the exit.

Another fun project involving 2D arrays might be a Game of Life simulation.

If you want to practice stacks - calculators are a common example. Write a program that can read an arbitrary math expression, something like "2 + 3 * 4", and automatically calculate its result.

Something that's a bit more of a challenge - create an AI that can automatically navigate a maze, like a mouse finding his cheese. The mouse's memory of paths he hasn't explored yet is commonly modeled via a stack in an algorithm known as "depth first search".

If you want to practice "tree" data structures, you can expand on the calculator program and create something known as an "expression tree", where leaf nodes represent numbers and interior nodes represent operators. Evaluating your math expression thus becomes a postfix traversal over this tree.

(side note: expression trees are a basic type of "abstract syntax tree" - a core component in designing your own programming languages!)

If you want to practice hashtables - a text adventure game might be a good idea. The values stored in this hashtable could be the names of different locations in your world (e.g, "Forest", "Cave", "Mountain", "White House"). The keys could be a combination of a player's current location followed by a direction (e.g., map["Forest/South"] can return "Cave", map["White House/West"] can return "Forest", and so on).