Algorithm Exercises

From BenningtonWiki
Jump to: navigation, search

An Algorithm Exercise involves inventing an algorithm to accomplish a given simple task. Some algorithms are short and ingenious while others prove to be more complicated than you’d think.

There are three measures of an algorithm’s worthiness. First obviously is its correctness. That is, does it do what the exercise says it should do? The second measure is its size. This is the length of the algorithm and the amount of workspace the algorithm needs when it runs. When you run the algorithm how much information are you keeping in your head? If you were to write down the algorithm, how many steps would it be? Is it a long or short algorithm? Generally a shorter algorithm is better. The third measure is its speed. If you were to run the algorithm, how many operations does it take? Is it a fast algorithm? In almost all cases a faster algorithm is better.

Often there’s a trade-off between the size of an algorithm and its speed, with faster algorithms typically requiring a greater degree of sophistication and a consequent increase in size. For these exercises you should always try to make your algorithms as fast as possible. In exercises where the length of the task may vary from one run to the next (an unpredictable number or order of items) the performance is averaged over many runs.

For some exercises your algorithm may be specified using only a given set of elementary actions. Other exercises may allow you to create your own vocabulary of actions.

By the way, algorithms rely on logic but they aren’t logic problems. I hate logic problems. “Susan (who made seven history errors) made one less geography error than the girl who made one less history error than Anne. The boy (not Luke) whose sister is Louella made more history errors than Sammy.” Etc. Yuck. What good are these? The logic in most algorithms consists of simple logical and relational expressions like “if A and B” or “if A is less than B.” Nothing more complicated than what you’d say out loud if you were to narrate your day. Try it. “If the sink is full then turn the water off.” “If I’m ready to go and the door is closed then open it and go outside.” Algorithms are about doing. (P.S. order is important: Don’t try walking through the door until you’ve opened it first.)

For a great introduction to what algorithms are and how they apply to computing, read EW Dijkstra's Short Introduction to the Art of Programming. I would like to come up with several dozen simple algorithm excercises to use in my Logic Machines course.

Doing

Troubleshooting

Something is busted. Determining what's wrong and fixing it is an example of an algorithm. It would be cool to create a situation where something isn't working, and let people fix it, taking note of their strategies.

Making art things

There must be a thousand things over in VAPA that are made according to algorithms. Mixing paints, making prints, ceramics, clay, etc.

Trains

How does a train drop off cars, rearrange cars, chainge direction, etc.? Reminds me of Dijkstra's train parable.

Printing photographs

Making test strips in B&W printing is an algorithm. What is it figuring out? What is it optimizing?

Dining Philosophers

http://en.wikipedia.org/wiki/Dining_philosophers

Starting a PS2 game

This one’s easy (or is it?). Select a PS2 game from a library and play it. Handle as many of the exceptional cases as you can think of.

Notes Exceptional cases: the library's empty; there’s already a disk in the PS2; the disk is missing from the case; the machine is unplugged; the machine is already on; the controller is unplugged; the TV’s off; etc.

Line breaking

You’re typing a paragraph on an old-fashioned typewriter. As you get close to the right margin you’ll have to decide when to break and go to the next line.

Making coffee

So you have a coffee maker. What are the steps you use to make coffee? How do the steps change if you're a) out of coffee, b) out of filters, c) out of clean coffee cups, d) dead?

Getting to the dining hall

Ask directions. Follow them. Exceptional cases?

Math

Arabic numerals

Heck, the word "algorithm" comes from a treatise written 1000 years ago about the methods for doing math with arabic numerals. The amazing concept that the digit's place has value: a ones column, a tens column, etc. What is the algorithm for counting using arabic numerals? Can it be extended to other base number systems?

Multiplying

Multiply two integers. Kids often multiply by repeated addition. Long multiplication is a common algorithm taught in elementary school. The snide comment to "use a calculator" is actually a superior algorithm (offload the work to another device).

Dividing

Divide one integer into another. The long division algorithm. I bet there are tons of division algorithms, probably invented thousands of years ago, and then a bunch more invented in the last 50.

Greatest common divisor

Determine the greatest common divisor of two integers.

Notes: Think Euclid.

Square roots

Figure the square root of an integer.

Notes: Think Newton. And ENIAC.

Factorials

Simple example of looping. It's okay to think recursion, but don't implement it that way.

Smallest circle

Given a set of points on a plane, your goal is to find the smallest circle that encloses those points.

Communicating

Secret communications

You want to send a message to a friend and you want to make sure that no one who intercepts the message can read it. How can you do this?

Notes Codes. Public key encrption.

Languages

The reason for parts of grammar. What purpose do they serve? What kinds of "How" questions do the parts of grammar address?

Mailboxes

A common carrier is responsible for picking up and delivering mail to everyone's mailboxes. Let's think about the performance of the carrier. He wants to get done as soon as possible, and the people all want their mail as soon as possible. What are algorithmic ways to optimize the carrier's performance? What is the "data" (location of mailboxes, mail carrier location, mail destined for each mailbox, mail waiting to be picked up at each mailbox)? What are the "actions" (go to a mailbox, deliver mail to a mailbox, pick up mail from mailbox, calculate best route)?

Notes There are cases when the carrier doesn't need to stop at a mailbox. The order of delivery may be a factor.

Mental poker

http://en.wikipedia.org/wiki/Mental_poker

Debouncing

Pushbuttons have this annoying property of bouncing mechanically when they're switched. These bounces generate additional and unwanted pulses, especially noticeable when the switch is hooked up to a fast electronic circuit that's counting the button presses. This is a classic problem in electrical engineering that also has similarities to other electronic interactive devices that are triggered in mechanical ways. The solution is known as "debouncing" or "adding hysteresis".

Elevator action

Describe the algorithm for an elevator. How many floors are there? Is there a "home" floor the elevator goes to when it doesn't have anything to do? What are you optimizing for? What's the "data" (number of floors, destination(s) of occupant(s), floor locations with people waiting for the elevator)? What are the "actions" (open door, close door, wait, go to floor)?

Exchanging phone numbers

When you meet someone and you want to exchange phone numbers, what's the best way to do it? (How do you define "best"?)

Contour lines

Playing

ALL games are algorithms. Let's play.

Also, think about how there are algorithms for playing the game correctly (ie, following the rules) and algorithms for winning (ie, strategies). It reminds me of a seminal computer science article that I read as a teenager that discussed how a computer chess playing program worked (Sargon article from Byte magazine). The process was divided into two halves. The first half of the program concerned itself with the implementation of the rules of chess: the size of the board and the kinds of pieces, generating legal moves for each piece, etc. The second half concerned itself with picking the best move -- winning. The article only went into detail about the first half.

Should we use Monopoly money?

Dots and Squares

You know that game where you connect dots arranged in a grid with short lines, and you put your name in each completed square? There must be a few different strategies for playing that well.

Minesweeper

Again, think of the two-fold chess breakdown. You need code that implements the playing field and the rules of the game. How big is the playing field? What are the possible values of each square? How do you enforce legal moves (eg, not picking the same square twice, not picking a square that's off the board)? What are the winning condition(s)? Once you have that code, you can start on the code that plays the game. If it's to be played by a human, the code would prompt for the next square to pick, and then apply the rules to the choice, ensuring that it's a legal move and checking for end-game conditions and modifying the playing field. But in my opinion what's really fun is implementing code that plays the game itself. You can still use the two-fold breakdown of code. The second half -- the strategic code -- can use whatever algorithms you think of. A simple but completely legit version could just pick random squares, paying no attention to the state of the playing field. It might even win once in a rare while. A better algorithm would recognize simple patterns and avoid squares that it's able to deduce must contain a bomb. You can get increasingly complex with your Minesweeper-playing algorithm.

Jigsaw puzzles

My dad loves to work jigsaw puzzles. When he sets to work on one there's no disturbing him until it's done. He has a methodical system for doing them that in my kids' opinion takes all the fun out of it. They just want to find pieces and put them where they go. He works the edges first, finding all the edge pieces and making the frame. In fact, he'll measure how big the puzzle should be (based on the stated dimensions on the box) and place the corners exactly where they go. When he finds pieces to particular obvious parts of the puzzle he'll set them aside, and work them as mini-puzzles. If there are big areas of the same color (skies, water, etc.) he'll put those pieces aside and work those areas last, going primarily by the shapes of the pieces.

His algorithm could be described on several levels. The above description works well for someone who knows jigsaw puzzles and is familiar with the vocabulary and the typical things you do when working them. You probably understood it well enough. If you were describing his process to someone new to jigsaw puzzles you'd certainly need to use more detail. A machine definitely need a much more precise description.

Nertz

Multiplayer card game, with multiple decks. Solitaire-like.

Old maid

Avoid ending up with the old maid as you pair cards.

War

Each player is dealt half the deck, and both players play simultaneously. Each player shows one card, and whoever has the higher card takes both cards shown and places them at the bottom of his deck. In case of a tie, both players play three face-down cards and one face-up card, and these face-up cards decide who will receive all the cards. If there is another tie, the process is repeated, etc. (From War; also Egyptian Rat Screw).

This is easy to visualize in algorithm terms.

High / low guessing

Someone picks a number from 1 to 100 and you try to guess it. The person can only answer “too high,” “too low” or “you got it.” Try to guess it in as few tries as possible.

Notes The fastest algorithm to do this will require an average of six or seven guesses. Why?

Twenty questions

The classic game of twenty questions. Someone thinks of an object and you try to guess what it is by asking yes or no questions. What's your strategy for narrowing the possibilities down until you finally have the answer?

Gambling for candy

I used to play a devious gambling game with my kids. When they wanted candy (or just about anything that could be counted), I told them they could have as many pieces as the number I was thinking of, provided they didn't want more than that number. This is how it worked: I'd think of a number from one to ten and not tell them. They'd start at "one" and ask, "May I have one piece of candy?" I'd always say yes. If they wanted to, they could then up the stakes and ask, "May I have two pieces of candy?" and so on. They could keep asking for more and stop at any time and take as many pieces they stopped at, but if they pass the number I was thinking of they'd lose and not get any candy. At every step they'd need to evaluate the diminishing chance of getting one more, and the increasing likelihood of losing them all.

Bzz

Yesterday Alexander and Soley played a game he called "Bzz". It's a math counting game. The object is to count as high as you can starting with 1 and replacing every number that contains a '3' or is divisible by 3 with "bzz". The players alternate saying the next number. The beginning goes "1, 2, bzz, 4, 5, bzz, 7, 8, bzz, 10, 11, bzz, bzz, 14 ...". If a player makes a mistake they're out and play continues until there's only one player left, who is annointed the winner.

Chess

Sargon article.

Searching

Finding a word in the dictionary

Someone picks a word at random from the dictionary. Another person finds the same word. An efficient algorithm should depend on the ordered aspect of the data (alphabetically sorted words in a dictionary). One way of doing this is similar to the high / low guessing game algorithm. How would this task change if the words weren't sorted?

Finding the aces

Find all four aces in a shuffled deck of cards. How long on average will it take?

Finding anagrams

Take a word and find every possible anagram. How can you be certain you’ve found every one?

Decide on a dictionary to use as the authority on valid words.

Two-letter words

Find all the two-letter words in English.

Seems there are two opposite approaches to this. Do you look in the dictionary for every two letter word? Or do you try every possible two letter combination and look them up in the dictionary to see if they're valid?

Caching

How can you speed up a search with a "cheat sheet"? How do you implement the cheat sheet, and how can you know that using the cheat sheet improves performance?

Navigating a maze

You're a rat in a maze superimposed on an NxN square grid. There's one entrance and one exit, and every square in the grid has at least one opening to an adjacent square. What are your strategies for finding your way through the maze?

Organizing

Separating cards into suits

Separate a shuffled deck of cards into its four suits.

Arranging people alphabetically

Sort people in a line alphabetically by name. The first person in the line needs to be the lowest in the alphabet. The people are initially in a random order.

Actions

A person can be addressed by name (Paul) or count from the beginning of the line (position 5) or count to the left or right of another person (third person to the left of Paul).

  • Swap (Paul swap places with the first person to your left)
  • Move (Paul move to position number 5)
  • Compare (Is the person at position 5 higher in the alphabet than the person at position 6?)

Notes

I wonder what it would be like to give the people in the line their own algorithms and let the solution run in parallel. For example, tell each person to look to their left and swap places if they're out of order.

Adding a person to a sorted line

Add one more person to the proper place in a line of already sorted people.

How is this different than sorting a random line of people? One way of doing this is similar to the high / low guessing game algorithm.

Eight queens

Arrange eight queens on a chessboard such that no queen is attacking another. There are 4 billion possible arrangements of queens of which 92 satisfy this condition.