Help me come up with an interesting data structures project?
August 4, 2015 11:16 AM Subscribe
I'm teaching a college data structures class this fall, for 2nd year game design students. Can you help me think of cool projects?
In the past, I've assigned a series of projects based on creating/modifying/deleting bank accounts. The first project built the entire functionality from scratch, and then each successive project swapped out the type of data structure used. The idea was that we started with less-efficient data structures like arrays, and ended with more efficient ones like binary search trees. Another learning objective is the swapping out part, since they need to practice building code in interchangeable modules.
But bank accounts are BORING. Can you help me think of any other projects that might be a little more interesting? They're all game students, but it doesn't have to be a game. In fact, I want to focus on processing lots of data, not on game functionality necessarily.
I thought about an game inventory system, but that's pretty much just the bank account program in disguise. Not out of the question, but I was hoping to do something really different for a change. I thought about some kind of animated project, where the coordinates and objects to draw are stored in various data structures, but none of my kids have much experience with the Java or C++ graphics/windows libraries, and this class is not meant to teach those topics, although I could probably do it with some pre-built code that we just added the data structures to.
I'm just fresh out of ideas. Anyone? All my students will have at least two programming courses under their belt, including C++ and Java, both with OOP. (They can pick which language to use for the semester.)
In the past, I've assigned a series of projects based on creating/modifying/deleting bank accounts. The first project built the entire functionality from scratch, and then each successive project swapped out the type of data structure used. The idea was that we started with less-efficient data structures like arrays, and ended with more efficient ones like binary search trees. Another learning objective is the swapping out part, since they need to practice building code in interchangeable modules.
But bank accounts are BORING. Can you help me think of any other projects that might be a little more interesting? They're all game students, but it doesn't have to be a game. In fact, I want to focus on processing lots of data, not on game functionality necessarily.
I thought about an game inventory system, but that's pretty much just the bank account program in disguise. Not out of the question, but I was hoping to do something really different for a change. I thought about some kind of animated project, where the coordinates and objects to draw are stored in various data structures, but none of my kids have much experience with the Java or C++ graphics/windows libraries, and this class is not meant to teach those topics, although I could probably do it with some pre-built code that we just added the data structures to.
I'm just fresh out of ideas. Anyone? All my students will have at least two programming courses under their belt, including C++ and Java, both with OOP. (They can pick which language to use for the semester.)
Spatial partitioning, particularly for collision detection? There are multiple different data structures that could be studied, with very different tradeoffs making them each useful for different situations. And the topic is very relevant to games but not strictly to games.
posted by solitary dancer at 11:33 AM on August 4, 2015 [2 favorites]
posted by solitary dancer at 11:33 AM on August 4, 2015 [2 favorites]
Maybe you could model the scoreboard for a popular online game. Often there are various ranking factors and different levels and the scoreboards may be split in different ways, e.g. by country, by all players within a specific rank, by points, by cash etc.
posted by Gomez_in_the_South at 12:03 PM on August 4, 2015
posted by Gomez_in_the_South at 12:03 PM on August 4, 2015
OOP + Data Structures...
How about some composed types...say, aircraft. aircraft have engines of differing types, which have parts of different types. aircraft have fuel containers, wheels, payloads, passengers, crew. some of which will nicely fit trees. crew have logs (lists) Send 'em off on multi-stop trips ( graphs, yo). See who is too close to restricted airspace (r-tree). a fare could use a state machine ( available, booked, paid, checked-in, cancelled, boarded...).
You could use generics/templates for some data structures and show reuse. Alternatively, abstractions (interfaces & abstract types) can do the same thing.
Not quite FPS, but not a bank, either. But now that you mention it...you could pretty easily do a character construction the same way. Then make em find the quickest path to The City of Treasure (edges weighted with both distance and threat) with their lawful evil elf ranger, carrying a backpack full of charms, with a list of enemies (sorted by hat size), and the Royal family tree (tree).
i enjoyed that way too much
posted by j_curiouser at 12:48 PM on August 4, 2015
How about some composed types...say, aircraft. aircraft have engines of differing types, which have parts of different types. aircraft have fuel containers, wheels, payloads, passengers, crew. some of which will nicely fit trees. crew have logs (lists) Send 'em off on multi-stop trips ( graphs, yo). See who is too close to restricted airspace (r-tree). a fare could use a state machine ( available, booked, paid, checked-in, cancelled, boarded...).
You could use generics/templates for some data structures and show reuse. Alternatively, abstractions (interfaces & abstract types) can do the same thing.
Not quite FPS, but not a bank, either. But now that you mention it...you could pretty easily do a character construction the same way. Then make em find the quickest path to The City of Treasure (edges weighted with both distance and threat) with their lawful evil elf ranger, carrying a backpack full of charms, with a list of enemies (sorted by hat size), and the Royal family tree (tree).
i enjoyed that way too much
posted by j_curiouser at 12:48 PM on August 4, 2015
If you want to draw, I can recommend p5.js (Javascript) or Processing (Java). Both libraries abstract out shapes and draw loops that are called each tick. The basic shapes just take coordinates, so I think you could get them up and running reasonably quickly. p5 has an IDE as well.
posted by dame at 12:56 PM on August 4, 2015
posted by dame at 12:56 PM on August 4, 2015
Would poker be too hard? Modelling the deck & various hands etc, maybe within a specific type that isn't too crazy weird to build.
posted by symphonicknot at 2:04 PM on August 4, 2015
posted by symphonicknot at 2:04 PM on August 4, 2015
What about social media?
You could create mock user accounts that can message each other, post statuses, maybe share things, etc. I'm thinking along the lines of Facebook here, so there's things to model like different relationships between accounts (family, friends, no relationship), "groups" that control access to different information on user accounts, and that sort of thing. There's functionality that requires sorting accounts, adding and deleting accounts, and performing high-level analytics.
If you really want to get the students interested in it, maybe see if you can get access to a REAL social media site's API and have them work with the actual data. Bonus points if the class' work ultimately undercovers interesting or surprising trends in social media that they use every day.
posted by ABCApplePie at 4:18 PM on August 4, 2015
You could create mock user accounts that can message each other, post statuses, maybe share things, etc. I'm thinking along the lines of Facebook here, so there's things to model like different relationships between accounts (family, friends, no relationship), "groups" that control access to different information on user accounts, and that sort of thing. There's functionality that requires sorting accounts, adding and deleting accounts, and performing high-level analytics.
If you really want to get the students interested in it, maybe see if you can get access to a REAL social media site's API and have them work with the actual data. Bonus points if the class' work ultimately undercovers interesting or surprising trends in social media that they use every day.
posted by ABCApplePie at 4:18 PM on August 4, 2015
Collectible card game model?
I just built an assignment around this collection of Magic: The Gathering card data. You can also get Cards Against Humanity in JSON format, which is a bit less specialist-nerdy at the risk of being possibly evil (or just telling you way more about your students than you actually wanted to know). Your students might be into categorizing Steam trading cards?
posted by yarntheory at 5:44 PM on August 4, 2015
I just built an assignment around this collection of Magic: The Gathering card data. You can also get Cards Against Humanity in JSON format, which is a bit less specialist-nerdy at the risk of being possibly evil (or just telling you way more about your students than you actually wanted to know). Your students might be into categorizing Steam trading cards?
posted by yarntheory at 5:44 PM on August 4, 2015
What about online "exchange" order books? I've worked with it in the financial space, but you could easily do it for exchanges of in-game items.
The different algorithms for matching really impact the optimal data structure; You almost always have to store by price, but if you're a FIFO matching algorithm you're going to have a different structure than a "preferential" matching algorithm (maybe certain people pay extra in-game money to move to the head of the queue) or "pro-rata" matching where the amount of things people are willing to exchange affects their priority.
If you want to get REALLY complicated for your better students you can ask them to model a data structure that supports "all or none" trading, or "market" orders that match at the best price available, etc.
posted by true at 7:33 PM on August 4, 2015
The different algorithms for matching really impact the optimal data structure; You almost always have to store by price, but if you're a FIFO matching algorithm you're going to have a different structure than a "preferential" matching algorithm (maybe certain people pay extra in-game money to move to the head of the queue) or "pro-rata" matching where the amount of things people are willing to exchange affects their priority.
If you want to get REALLY complicated for your better students you can ask them to model a data structure that supports "all or none" trading, or "market" orders that match at the best price available, etc.
posted by true at 7:33 PM on August 4, 2015
Maze traversal? You can tie a frontend (or make it a different project) of graphics for the maze and their paths, then have them work on different methods of solving it.
posted by nickggully at 8:35 PM on August 4, 2015
posted by nickggully at 8:35 PM on August 4, 2015
forgive me if i'm wrong here, the op seems to be looking for a domain where these types of things are integral to the design & development task.
posted by j_curiouser at 10:18 PM on August 4, 2015
posted by j_curiouser at 10:18 PM on August 4, 2015
Any way you could make it competitive? Two or more teams - either all of them attempting to do the same thing, or (harder but potentially more interesting) they're trying to 'hack' the other team? Maybe some kind of stuxnet-like scenario? (you have a centrifuge emulator, and they have to figure out how to inject their code, and you drop hints and over time the more sophisticated data structures are required to succeed). Kinda hand-wavy, I know, but it could be engaging.
posted by doctor tough love at 9:37 AM on August 5, 2015
posted by doctor tough love at 9:37 AM on August 5, 2015
I recall my beginning CS classes using discrete event simulation for a few projects. I always found simulations fun because your code can do something unexpected (without it being a bug). It has plenty of potential for exploring data structures, both in the framework of the simulation and in the domain being simulated.
posted by eruonna at 10:50 AM on August 5, 2015
posted by eruonna at 10:50 AM on August 5, 2015
My db class had us build an NCAA football db from scratch.
posted by wwartorff at 9:19 PM on August 5, 2015
posted by wwartorff at 9:19 PM on August 5, 2015
Response by poster: You guys are awesome. So many great ideas here. Gonna spend some time working out possible logistics of a few of them, and see what I end up with.
posted by SuperSquirrel at 1:08 PM on August 7, 2015
posted by SuperSquirrel at 1:08 PM on August 7, 2015
« Older Advice for building a back yard cabin... | Which researcher was shocked by gay rams? Newer »
This thread is closed to new comments.
posted by strangecargo at 11:30 AM on August 4, 2015 [1 favorite]