Since we are both relatively new to the concepts of
programming computers lets be basic. I am not going to assume that you have
advanced knowledge of mathematics but do have a basic understanding. With
programming it can become very convoluted with obscure mathematics concepts very
quickly. Instead let’s look at the ideas of algorithmic design and data structure
techniques in a more familiar setting. For my classmates, I apologize you may
have heard this before.
If you haven’t seen the movie Inception (Warner Bros., 2010)
you’ll need to see it to grasp this fully. We’ll try to keep it simple as we
can, but with words like algorithmic design and structure techniques this may
be tough. In the movie we are introduced to the abstract concept of entering
another person’s dream to carry out some type of “adventure”. Through the movie
there are scenes of increasing intensity as the characters try to carry out “mind-crimes”
on other people. In the climax sequence they dive deeper than ever before by
entering a dream. Then entering a dream within a dream, and again a dream
within a dream within a dream. They go deeper than ever before and take a chance
on not waking up in time to save themselves (another abstract idea that if you
die in a dream you die for real).
Keeping all of this in mind programming can be very similar.
We take the abstract concept of data on a computer and put it some use. This is
the idea of data structure, and the implementation that we use to manipulate it
is the algorithm based on the algorithmic design desired. So, to be clear, the structure
is what we are working with, and the algorithm is what we use to manipulate it.
In the movie, the data structure would be the idea of a dream and the algorithm
is the people within the dream making the outcome/output what they desired.
So, as with most things computer oriented we start with the
finish, what is our desired output? What do we need the program to “do”? Once we have that output we can decide on the
structure and the algorithms. There are many data structures such as stacks,
lists, queues, and trees. Each of these has its own specific algorithms that it
follows to maintain the data it is given. So, if you think of the structure you
are also thinking of the algorithm. I told you this was a very abstract
concept. So, keeping this in mind why would we have a bunch of different structures?
Why not just use one for simplicity’s sake? Wouldn’t it be simpler and easier
to just use one? Of course not. Each structure has its own advantages depending
on what our desired output is. The main advantage is improved efficiency in
terms of time gained or lost in operations. Well then, which is best you ask? We’ll
just use it all the time and it will be easy/simple. Not so fast. As an example,
we’ll search a list, start with the easy ideas and go up from there. There are
two basic ideas for searching a list, linear and binary. A linear search is what
it sounds like, search each object in order until you find or don’t find what
you are looking for. The binary search is a little more sophisticated. It halves
the list until it finds, or doesn’t find, what you are looking for. So now I ask
you, which is better? The best? Of course, it all depends on how much data you
are searching through. If you did a linear search on Amazon for bicycle tires
it would take forever, but a binary search would be exponentially quicker. We can
say, without getting deep into the math of it, that the amount of time it takes
to search is directly relative to the size of the data being searched, agree?
Great. The algorithm for searching a data structure is directly relative to the
size of the data structure. What does any of this have to do with a movie?
The concepts of algorithmic design and data structures
define how we develop a program and how we get as deep as we need too to complete
a task. We take the desired output and take steps toward it. As we move from
step to step we will implement the different types of algorithms we need to manipulate
the data as we need. Progressively moving closer to our output. The structures are
normally developed inside of their own files and then compiled together to make
a complete program or app. This allows the program to be developed by many
different people or teams of people independently while working toward a common
goal. The result is a finished product. So, the initial dream that we enter is
the first step of designing the data structure and moving one step forward. The
next dream is the progressive step and implementation of algorithms to move toward
our goal. The next dream is to divide the work into files so we can work
together. The climax, final dream and waking up, is to compile the structures
and algorithms together into our final, working product.
