Program Concepts for
CS280, Programming Language Paradigms

Lee Spector

The following are the program concepts, submitted by students, that are to serve as the basis for assignments 2-6. These are of mixed difficulty and of mixed specificity. In some cases you will be able to implement only a part of the idea in the time provided for the assignment, while in other cases you will be able to implement the complete idea and several extensions. (I have listed some possible extensions, but you may want to develop some of your own.) In some cases the idea is fully spelled-out below, while in other cases you will have to fill in several of the details.

What I expect for assignments 2-6: For assignment 2 (C/Pascal -- languages in which you are already fluent) I expect you to spend approximately 1 hour writing code. For each of the later assignments I expect you to spend approximately 3 or 4 hours programming. I am not looking for a large volume of code or for programs that "merely" meet one of the listed specifications. Rather, I am looking for evidence that you have applied yourself and that you appreciate the features of each programming paradigm.

Because I edited and otherwise transformed several of these concepts, I've removed author names from all of them.

Anagram Finder

This program would be useful for games such as 'Jumbles' (the unscrambling game in the newspaper), and for a game in which you try to find more words hidden inside another word than your opponent.

Input would be random words or letters typed in by the user. The output would be all the possible words or combination of words that could be produced from the input.

For example:

A dictionary would be needed so that letter combinations could be compared to it and be checked to see if they qualify as words.

Random Quote Picker

This program randomly picks predefined strings from a file. (This could be used, for example, to add a random quote to a .signature file every time you log in, although this would require additional interaction with the operating system.)

Input: a text file containing a list of quotes. Each quote can be multiple lines; it must be separated from quotes before and after it with a "###" symbol placed on a line by itself.

Output: One of the quotes, defined as all text between two '###' separator lines, not including the separator lines. This quote should be chosen at random from the available input.

sample file:

Spam, spam, spam, spam....
Interesting website of the day: 
    CNN Online,          
Renee Landrum, Smith College, Northampton, MA


Force Calculator

This program involves objects under constant acceleration. Given the force, you can solve Newton's Second Law (F=ma) and find the equations of motion for an object. In the case of constant acceleration these equations are fairly straightforward. The input would be the force, the object's mass, some set of initial conditions, and a length of time. The output would be the state of the object (position and velocity) at arbitrary intervals during the specified time period. To keep things simple I would do it for one-dimensional motion only, but I'm not sure how difficult it would really be to simply extend it to three dimensions. Being able to deal with more complicated forces would also be interesting, but that would definitely take me much more than an hour to do.

Compatibility Screening Test

Let's face it, sometimes you meet someone, and get to know them, and later decide you wish you had never met them. This program finds out whether or not you will get along by simulating a conversation with you.

It will ask the user a series of questions, and keep track of how many answers correspond to yours.

For example, if you really love the color purple, you might have the program ask "What is your favorite color". The user might answer "purple." If the users answer, purple, matches up to your answer purple, then that's one thing you have in common. The computer keeps track of how many things you have in common. If the user's answers correspond to yours quite frequently, like if you ask 10 questions and 9 times the user's answer is the same as yours, the program can say something like "Hey, we have a lot in common! We should definitely meet sometime."

On the other hand, the user could be someone you never, ever want to meet. For example, if you are gay, you might ask. "How do you feel about gay people? Do you think they should be burned at the stake?" If the person answers "Yes", chances are that this isn't someone you want to meet. In which case you would have your program say "I'm sorry, we just can't get along" and exit quickly. You could also have keywords that make the program end. Like, if you're an evangelical Christian, and you ask the user what religion they prescribe to, and they answer "Satanist", that might be the program's cue to end.

Basically, talking to the program is much like talking to you. This lets the user figure out whether or not they like you, and lets you screen out any undesirables who don't meet up to your standards of personality.


This would be a game either of two players on one computer or a one player game against the computer. The interesting part comes when it is a one player game because the computer can either move randomly or it can be programmed with a plan to win or rules for movement. The user could select if she wanted to be X or O. So the input would be a one or two player game, unless you just wanted to do one or the other. And then you would put in where you wanted the X's or O's. The output would be the displayed board and eventually who the winner is if in fact there is a winner.

Probabilistic Text Garbler

A probabilistic text garbler like CONX or emacs's "Dissociated Press." The program's input is a text file, presumably of sentences in English or another language. Its output is another text file, produced by first picking a word (or letter) from the source file at random, then picking a word (or letter) to follow it based on the probability of such a sequence in the source file, then picking another word (or letter) based on the probability of that one following the last one picked, and so on for some predetermined amount of time. So, for instance, if the input contains "spiny porcupine" twice and "spiny cactus" once, then the program (if it's working on words, not letters) gives "porcupine" a two-thirds chance of following "spiny."


The program will have a story in it with some words omitted. As an extension, there might be a couple stories to choose from.

The program will request certain parts of speak from the user.

The program will output the finished non-sense story.

Mix Maker

Input: database of CDs with song titles and times.

Output: 90 minute mix of various songs divided into two 45 minute sides.

Ideally, the program will find an optimal "packing" of songs; that is, it will find a mix that minimizes the wasted (blank) space at the end of each side.

Possible extension: annotate songs with descriptive keywords and produce mixes that take these into account. For example, you might ask for a slow mix, or a blues mix, or a mix that alternates slow and fast songs.

Spell Check

Simple spell check program (one word at a time).

Data: Small Dictionary (words only in alphabetical order)

Input: Word to be spell-checked

Output: If word exists in dictionary, then output: correct; else, output: No such word.

Possible extension: List possible corrections for misspelled words.

Possible enhancement: To save space, most spell check programs store their dictionaries in a tree structure (e.g. a B-tree) rather than in a linear list. Implement a tree-structured dictionary for your spell check program.

Spinning Cube

Produce a list of coordinates for a cube that is moving and spinning around the screen in 3D.

Input: Coordinates for several positions through which cube will move. These should be given by the coordinates (in 3D) of two opposite corners. The cube will move through each of these positions, in order, taking the shortest route each time.

Output: The complete list of coordinates for cool looking cube that moves in 3D.

Possible enhancement: Find a rendering/animation package that can produce the actual 3D images and have your program produce output in a format that this package can read. (Although most of the languages we'll be using have graphics libraries, we will only be covering text input/output in the class.)

Name Letter Scrambler

(Related to "Anagram Finder".)

Input: Dictionary

User input: his or her name



Input: Dictionary (with numbers of syllables for each word)

User Input: a certain noun that they would like to see in the poem

Output: a Haiku in the format of three lines containing 5, 7, and 5 syllables, using the user's word.

Horoscope for the year

Input: dates for all the astrological signs, years for all the Chinese signs. Little paragraphs for all.

User Input: a birthday

Output: two paragraphs describing a horoscope for the astrological and Chinese of the particular birthday. (Maybe you could add the cycle of the moon as well.)

Image Matcher

This program covers the area of computer vision. There are two sets of inputs, both of which are two-dimensional arrays. Firstly, the program will be presented with a two-dimensional array of `0's and `1's, like the following:
This represents the letter 'S'. This is called the tested array. The second set of input is a set of 3 two-dimensional arrays of exactly the same sizes. They might represent the letters 'E', 'B', and 'H', or they might not represent anything meaningful to us at all. The program is required to analyze the tested array with the other set of 3 two-dimensional arrays, and output which one of the second set 'looks' like the tested array most. That is, which one looks like the character 'S' most.

Text Reverser/Palindrome Finder

1. Reverse user-supplied text. Example:

2. Determine whether user-supplied text is or is not a palindrome (the same backwards as forwards).

3. Given a dictionary (word list) find palindromes consisting of words from the dictionary.

Letter/Word Counter

Count of all occurrences of each letter in the alphabet from the reading of a file

Input: A text file.

Output: A list of the alphabet and the number of times that each letter appears in the file, next to that letter.

Possible extensions:

Bias Finder

Read in text files containing articles from different newspapers/magazines and analyze them for their use of code words/phrases that

Grade Calculator

Input: A list of courses and their grades.


Student Employee Database

Supervisors input: hours worked by student assistants on campus.

Students input: name.

Output: balance of financial aid.

Foreign Language Flash Cards

This program would have a dictionary of pairs of words, one from each of two languages. The user could select which language was to be presented, and which was to be used for responses. The program would then randomly present words and the user would try to provide the corresponding word from the other language. The program should keep track of the user's progress and tailor subsequent presentations to the areas in which the student needs improvement.


This program would randomly select a word from an internal word list and would present the user with a sequence of blanks, one for each letter in the word. For example, if the selected word was "aardvark" then the program would present the user with:


The user would then be asked to guess a letter. If the letter occurs in the word then the program would show the user where the letter and all previously guessed letters occur. For example, if the user guesses "a" then the program would output:


If, on the other hand, the letter does not occur in the word, then this counts as a point against the user. This may be presented to the user by adding a body part to a stick figure hanging from a gallows (hence the name "hangman"). If the user acquires 6 points (that is, the stick figure is complete: head, body, leg, leg, arm, arm... or some people allow for more points and include feet, face parts, etc.) before completing the word then the user loses. When this happens the system outputs "you lose" and the complete word.

Text Judger

Input: a text file.

Output: various judgements of the text's quality. These may include simple measures like word count (see above), intermediate measures like "reading level" (for which there are several standard algorithms), and much more complex measures like aesthetics of rhythm, rhyme, and meaning (very big open research problems lurk herein!).

Date Calculator

This program will, using today's date entered from the keyboard, output tomorrow's date. Both the input and output will be a month, a day, and a year. So for instance, if the input is Feb 28 1998 the output would be Mar 1 1998. If the input is Jan 13 1998, the output would be Jan 14 1998.

Possible extension: Allow for a variety of date calculations. For example, allow the user to find the date of the day that is 90 days after Feb 15, 1998.

Another possible extension: Given a month and year, print a calendar for that month.

Wall Structure Assistant

You have a square wall made up of small squares all the same length. You need to find out the minimum number of diagonals needed to keep the wall rigid.

Input: number of squares in the wall

Output: number of diagonals needed

Museum Organizer

You need to organize paintings on the walls of a museum. Each painting must have enough "personal space," and you want to fit as many paintings as possible.

Input: number of paintings, each painting's "personal space," number of walls, dimensions on each wall that can be used

Output: location for each painting

Scissors, Paper, Rock

This program will simulate the fun childhood game of scissors paper rocks. It is a two player game. To play, each player picks either scissors, paper, or rock. The rules are as follows: The winner gets the bigger piece of cake or gets the good chair or has to taste the food to test for poison or whatever.

The simple i/o of the program would be, of course, that the player tells the computer their choice, the computer (either randomly or through an algorithm) will compare it's choice with the human players, announce the winners, and loop till the human gets sick of the whole deal. Alternate i/o would be to play over a network with another human player (having each player enter in their guesses in front of each other would sort of defeat the point) or have the computer play itself, perhaps with two different programs within. More fun would be to pick the method that the computer uses (human input, pick a position randomly, or choose an algorithm to use) and see which way works best. The basic structure of the program:

Number Guessing Game

The user chooses the number and the computer tries to figure it out using cues from the user.


Output "Choose a number between 1-100, and I will guess it"
Input "" (to signal she chose a number)
Output "is it 50?"
Input "no"
Output "is it higher or lower?"
Input "lower"
Output "is it 25?"
Input "no"
Output" is it higher or lower?"
Input "higher"
Output "Is it 37?"
....and so on until it guesses it.

Possible (difficult!) extension: The user picks a numerical property, like "multiple of 3," "factor of 100," or even "one more than a prime," and the computer tries to guess this.

Poker Hand Computer

Input: a description of the cards in a hand of poker.

Output: a description of the best way to "call" the hand -- for example, "3 Aces" or "Flush Hearts."

Possible extensions: allow for wild cards, games with many cards per hand (e.g. 7-card stud), high/low games, games in which "up" cards of other players are known, etc.