CS 101 – Algorithms

Programs are essentially computer recipes – a series of steps and “ingredients” (variables) which produces a result. However, when dealing with large problems, we have to create larger and larger “recipes”. This is why we break down individual solutions into processes we call algorithms.

Algorithm – An Overview

An algorithm is a step-by-step solution to a problem. In that sense, it is a very small program (or very small programs are algorithms). Each algorithm takes some input data, transforms it in a particular way, and produces output data.

The difference between a particular program and an algorithm is in the generality of the solution.

For example, we could have an algorithm that takes two integer inputs (x and y), adds them, and produces one integer output (z). We could then create a program which adds 4 and 8 to produce 12, using this same algorithm.

An Algorithm Example – Sort

Suppose we have the following set of unsorted numbers:

12  5  11  3  9

For one reason or another, we decide to sort these numbers. In this example, we will use the simple “selection sort” algorithm, which goes through all the data and selects the smallest value first.

The steps for this algorithm could look like this:

Set A is the starting set

Set B is the final set

While there are still numbers in Set A:

For each number in Set A:

The first element in the list is “smallest”

If the next number is smaller than “smallest”, make that number “smallest”

After we test all the numbers, put “smallest” in Set B

Then, remove “smallest” from Set A

Print out Set B

That may be a bit hard to read, so let’s see how it plays out:

Set A: 12  5  11  3  9

Set B: NOTHING

12 is smallest

12:5   – 5 is smallest

5:11   –  5 is smallest

5:3   –   3 is smallest

3:9   –   3 is smallest

Set B: 3

Set A: 12  5  11  9

12 is smallest

12:5   – 5 is smallest

5:11   –  5 is smallest

5:9   –   5 is smallest

Set B: 3  5

Set A: 12  11  9

12 is smallest

12:11   – 11 is smallest

11:9   –  9 is smallest

Set B: 3  5  9

Set A: 12 11

12 is smallest

12:11   – 11 is smallest

Set B: 3  5  9  11

Set A: 12

12 is smallest

Set B: 3  5  9  11  12

Set A: NOTHING

(PRINT) >>  3  5  9  11  12

The more savvy reader might realize that there are many better ways to implement this sort, as well as better ways to implement sorts in general, but this gives you an idea about how algorithms work.

Homework

Figure out an algorithm that sorts the same kind of inputs using ONLY ONE set.

Rules:

• You can use any kind of loops (FOR, WHILE, etc)
• If you aren’t a programmer, you can just explain what’s happening in your own words.
• I still need to be able to understand it.
• You can use “holder” variables (like “smallest” in the example)

Hint: Try to sort a set of five playing cards by hand. Your solution should make a good algorithm.