Creative Programming Assignments

Below are links to a number of creative programming assignments that we've used at Princeton. Some are from COS 126: Introduction to Computer Science; others are from COS 226: Data Structures and Algorithms. The main focus is on scientific, commercial, and recreational applications. The assignments are posed in terms of C or Java, but they could easily be adapted to Python, C++, or C#.

SCIENTIFIC COMPUTING
Assignment	Description	Concepts	Difficulty

Guitar Hero [checklist]	Simulate the plucking of a guitar string using the Karplus-Strong algorithm.	objects, ring buffer data type, simulation	5
Digital Signal Processing [checklist]	Generate sound waves, apply an echo filter to an MP3 file, and plot the waves.	data abstraction, arrays	5
Percolation [checklist]	Monte Carlo simulation to estimate percolation threshold.	union-find, simulation	5
Global Sequence Alignment [checklist]	Compute the similarity between two DNA sequences.	dynamic programming, strings	5
N-Body Simulation [checklist]	Simulate the motion of N bodies, mutually affected by gravitational forces, in a two dimensional space.	simulation, standard input, arrays	3
Barnes-Hut [checklist]	Simulate the motion of N bodies, mutually affected by gravitational forces when N is large.	quad-tree, analysis of algorithms, data abstraction	8
Particle Collision Simulation	Simulate the motion of N colliding particles according to the laws of elastic collision.	priority queue, event-driven simulation	7
Atomic Nature of Matter [checklist]	Estimate Avogadro's number using video microscopy of Brownian motion.	depth-first search, image processing, data abstraction, data analysis	8
Root Finding [checklist]	Compute square roots using Newton's method.	loops, numerical computation	2
Cracking the Genetic Codes [checklist]	Find the genetic encoding of amino acids, given a protein and a genetic sequence known to contain that protein.	strings, file input	5
RECREATION
Mozart Waltz Generator	Create a two-part waltz using Mozart's dice game.	arrays	3
Rogue [checklist]	Given a dungeon of rooms and corridors, and two players (monster and rogue) that alternate moves, devise a strategy for the monster to intercept the rogue, and devise a strategy for the rogue to evade the monster.	graph, breath first search, depth first search, bridges	8
8 Slider Puzzle [checklist]	Solve Sam Loyd's 8 slider puzzle using AI.	priority queue, A* algorithm	5
GRAPHICS AND IMAGE PROCESSING
Mandelbrot Set [checklist]	Plot the Mandelbrot set.	functions, arrays, graphics	3
H-tree [checklist]	Draw recursive patterns.	recursion, graphics	3
Sierpinski Triangle [checklist]	Draw recursive patterns.	recursion, graphics	3
Collinear Points [checklist]	Given a set of Euclidean points, determine any groups of 4 or more that are collinear.	polar sorting, analysis of algorithms	4
Smallest Enclosing Circle [checklist]	Given a set of Euclidean points, determine the smallest enclosing circle.	computational geometry, randomized algorithm	8
Planar Point Location [checklist]	Read in a set of lines and determine whether two query points are separated by any line.	computational geometry, binary tree	6
COMBINATORIAL OPTIMIZATION
Small World Phenomenon	Use the Internet Movie Database to compute Kevin Bacon numbers.	graph, breadth-first search, symbol table	7
Map Routing	Read in a map of the US and repeatedly compute shortest paths between pairs of points.	graph, Dijkstra's algorithm, priority queue, A* algorithm.	7
Bin Packing	Allocate sound files of varying sizes to disks to minimize the number of disks.	priority queue, binary search tree, approximation algorithm	5
Traveling Salesperson Problem	Find the shortest route connecting 13,509 US cities.	linked list, heuristics	5
Open Pit Mining	Given an array of positive and negative expected returns, find a contiguous block that maximizes the expected profit.	divide-and-conquer, analysis of algorithms	5
Baseball Elimination	Given the standings of a sports league, determine which teams are mathematically eliminated.	reduction, max flow, min cut	3
Assignment Problem	Solve the assignment problem by reducing it to min cost flow.	reduction, min cost flow	3
Password Cracking	Crack a subset-sum password authentication scheme.	hashing, space-time tradeoff	7
TEXT PROCESSING
Natural Language Modeling	Create a Markov model of an input text and use it to automatically generate stylized pseudo-random text.	suffix sorting or hashing	6
Natural Language Modeling	Create a Markov model of an input text and use it to automatically generate stylized pseudo-random text.	Markov chains, graph	4
Markovian Candidate [checklist]	Create a Markov model of an input text to perform speech attribution.	artificial intelligence, symbol table	6
Word Searching	Search for words horizontally, vertically and diagonally in a 2D character array	tries	7
Redundancy Detector	Find the longest repeated sequence in a given text.	suffix sorting, strings	4
Text Indexing	Build an inverted index of a text corpus and find the position of query strings in the text.	suffix sorting or binary search tree	4
COMMUNICATION
Linear Feedback Shift Register	Encrypt images using a linear feedback shift register.	objects, encryption	4
Pictures from Space	Detect and fix data errors in transmission using a Hadamard code.	2D arrays, error-correcting codes	3
Prefix Free Codes	Decode a message compressed using Huffman codes.	binary trees, data compression	4
Burrows-Wheeler	Implement a novel text compression scheme that out-compresses PKZIP.	suffix sorting, arrays, data compression	7
RSA Cryptosystem	Implement the RSA cryptosystem.	big integers, repeated squaring, analysis of algorithms	8
DISCRETE MATH
Linked List Sort	Shellsort a linked list.	linked list, shellsort	4
Batcher Sort	Implement Batcher's even-odd mergesort.	divide-and-conquer, parallel sorting hardware	6
Rational Arithmetic	Implement a Rational number data type.	struct, data abstraction, Euclid's algorithm	3
Factoring	Factor large integers using Pollard's rho method.	big integers, Euclid's algorithm	5
Deques and Randomized Queues	Create deque and randomized queue ADTs.	abstract data types, generics	5
Linear Congruential Random Number Generator	Find the cycle length of a pseudo-random number generator using Floyd's algorithm.	loops, mod	2
Stock Market	Predict the performance of a stock using Dilbert's rule.	loops	2
Subset Sum	Partition the square roots of 1 to 100 into two subsets so that their sum is as close as possible to each other.	various	6
Loops and Conditionals	Binary logarithm, checkerboard pattern, random walk, Gaussian distribution.	loops and conditionals	1