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#.


Assignment Description Concepts Difficulty
SCIENTIFIC COMPUTING
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