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 |