Algorithmic Design and Data Structures

Do you remember learning to tie your shoes? It is a simple task that we do twice every time we put on shoes with laces. You probably do not think about tying shoes while doing it.  In this post, I will use the simple task of learning to tie shoes to demonstrate two complicated-sounding concepts:  algorithmic design and data structures. 

Data Structures

First, let's discuss the shoe. Before we learn to tie a shoe, we must learn what a shoe is. Shoes come in many shapes and sizes, to say the least. It would be a lengthy task to list every type and style of shoe, so let's focus on what makes something a tie-able shoe. It must have laces, or there would be nothing to tie, but it also should be designed to cover a foot. For now, we will use that description for a shoe--it has laces and covers a foot. The point is that we can't tie a shoe unless we agree on what a tie-able shoe is. It is the same with data structures in computer programming. At the beginning of designing an algorithm, we have to agree on the pieces of information the program will process and the things that can be done to each piece of information. In our shoe example, we must know that the shoes will be used to walk around, so they should be tied tight enough to stay on. We must also know that a foot needs to be inside the shoe, so it can't be tied too tightly. Finally, we would like to tie them once and have them stay tied all day, but they must be able to be loosened just as easily. Now that we have our data structures, it is time to develop the algorithm.

Algorithmic Design

An algorithm is a finite sequence of tasks that accomplishes something. It might sound complicated, but the concept is simple. In our shoe example, the instructions passed down to us might have been something like the following:

1. Cross the two laces and circle one back under the other
2. Pull tightly on each lace to tighten
3. Make loops with the two ends
4. Cross the two loops and circle one back under the other
5. Pull tightly on each loop

The instructions above are an algorithm to tie shoes. It is not the only algorithm. Some people do the second cross backward to get a tighter knot, and some people double-knot their shoes. Notice how the first instruction assumes that you have laces? It also assumes that you have shoes. The point is that the data structures (shoes) are an integral part of the algorithm (tying shoes). 

When programming computers, the process of algorithmic design is similar to learning to tie your shoes. You must first understand the data structures. What pieces of data will be processed, and what things will be done to them? Shaffer describes a data structure as "Any data representation and its associated operations" (2013). We deal with many types of structures in programming, including numbers, strings, dates, times, and other data types. We also operate on structures built from other structures. For example, we might need to work with customer accounts, which might have an ID together with a name, address, and phone number. 

Once we have established the data structures involved in solving a problem, the next step is to create a solution or algorithm. An algorithm should meet all of the requirements of the task at hand. For the task of shoe-tying, the basic needs would be that the shoe stays on and that tying them is a quick operation. For a program, the requirements might be to retrieve customer accounts by ID or by name, and both searches should be quick. It is important to establish the requirements as completely as possible before settling on an algorithm. 

Tying the Knot

The key to algorithmic design and data structures is to understand the problem domain. There is no single data structure that works for all data types, and there is no single algorithm that works for all situations. If you create a solution that uses really neat structures and your favorite algorithms but does not solve the problem, it is like decorating shoelaces with art--the laces are pretty, but the shoes fall off. 

References

Shaffer, C.A. (2013). Data Structures and Algorithm Analysis. (Edition 3.2 Java Version). [Ebook]. Retrieved from http://people.cs.vt.edu/~shaffer/Book