# 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 C++, C#, Python, or Fortran 90.

 SCIENTIFIC COMPUTING RECREATION GRAPHICS AND IMAGE PROCESSING COMBINATORIAL OPTIMIZATION 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 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 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 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 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 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 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

Here are some Nifty Assignments created by instructors at other universities. They are more oriented towards recreational applications, but are fun and creative.