Transcript n301AlgorithmDevelopment - Department of Computer and

Algorithm Development
CSCI N301: Fundamental Computer
Science Concepts
Copyright ©2004  Department of Computer & Information Science
Goals
By the end of this lecture, you should understand:
• How we develop algorithms
• The Four Concepts of Algorithm Development:
–
–
–
–
Algorithms are language-independent
Algorithm development requires many iterations
Algorithms are best defined using modularity.
Algorithm development requires almost continuous
refinement.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Machine Language
• In the past few weeks, we have figured out
how to encode programming instructions,
and have traced the circuitry that
processes those instructions through the
fetch-execute cycle.
• We saw that machine language is very
error prone and time consuming – after all,
it is comprised only of 0’s and 1’s.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Assembly Language
• To address the “barrier to entry” machine
language posed, programming engineers
developed a higher level language called
assembly.
• Assembly language replaces the binary values
of instruction codes with English mneumonics,
and (typically) the binary values of data and
memory locations with hexidecimal values.
• The last lab required assembly language
programming for solution.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Assembly Language Programming:
Lessons Learned
• We learned that assembly language requires
memory management – we had to insure that
where we stored our program data was not
overwritten by instructions.
• In higher level languages, this memory
management was taken over by the growing
feature content of an operating system.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Assembly Language Programming:
Lessons Learned (cont)
• We also saw an importance of understanding
the specific xComputer simulator programming
instructions, as our problems required use of
specific commands within the specific toolset of
our simulator.
• Similarly, there are are many versions of
assembly languages, each with a slightly
different toolset (or set of commands), each tied
to a specific type of processor chip.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Assembly Language Programming:
Lessons Learned (cont)
• Finally, we learned the programming power of
labeling addresses.
• Once an instruction is given a label, we can write
“relative” code, code that allows us to modify
execution flow to return to specific instructions,
or branch away from others.
• The concept of labeling was so powerful that it
continued to grow – in higher level languages,
labels replaced cell locations to become
variables.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
No Magic, Though
• Keep in mind that as we move up the
ladder of abstraction to look at higher level
languages, nothing has really changed …
• Instead, translation programs have been
developed that take the higher level
languages, and translate them ultimately
into machine language.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Programs as a Toolset
• Before we look at higher level languages,
though, we need to position them as a
toolset.
• The toolset exists to provide an execution
envelope for algorithms.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithms: Revisited
• At the beginning of the semester, we
introduced the concept of an algorithm as
the fundamental business of computer
science.
• We revisit the concept now, given our
developed understanding of computer
processing works.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Development
• Recall what we said about algorithms:
“An algorithm is a well-ordered collection of
unambiguous and effectively computable
operations that, when executed, produces a
result and halts in a finite amount of time.”
• And now we are ready to consider this:
How do we develop algorithms?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Development
• The first thing to understand about
algorithm development is to realize it is
independent of any particular
programming language.
• Theoretically, any given algorithm could be
implemented within any programming
language.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Development
• An algorithm is expressed in high level,
non-technical terms.
• This expression is said to be documented
within “pseudo-code.”
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Development
• The second thing to understand about
algorithm development is to realize that it
best occurs iteratively.
• In the first pass, we should write high
level, pseudo-code statements.
• In subsequent passes, we give these high
level statements more and more detail.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Development
• The process of beginning with high level
statements and successively adding more detail
is called top-down development with stepwise
refinement.
• The third thing to know about algorithm
development is that it best occurs modularly.
• What this means is that key tasks are identified,
and thought about as components.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Development
• This “divide and conquer” approach allows both
development efficiencies and debug focus.
• Modular programming is so important that often
the modular blocks are composed as empty
skeleton code for early execution, while we add
functionality later.
• Modular iterative programming is called stub
programming, since we only create stubs in the
early passes.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Development
• The final thing to realize about algorithm
development is that all algorithms require
refinement.
• Even if an algorithm works correctly on the first
try – and this is unlikely – it could benefit from
performance improvements (working faster, or
with less memory, or on an expanded data set).
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Let’s Try One
• With these four key principles in mind, let’s
try our hand at algorithm development
• Let’s look at a simple problem – a variation
on one we have coded in assembly
language – the problem of asking adding
numbers together and storing their sum …
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Development
• The first step is to document a complete
problem specification. In commercial
applications, this process results in a
functional specification.
• In our lab assignments, we will settle for
disambiguated, non-technical problem
statements.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Specification Development
• What sort of questions would you ask to
disambiguate the problem description?
• Good questions would include:
– How will you get the numbers to be added –
user input, read a file, etc.?
– What kind of numbers will the program add –
integers, decimals, negatives, etc.?
– How many numbers will the program add?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Specification Development
• Now we can re-express our problem:
“Add two integer values from memory and
store their sum.”
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Task Chunking
• In the second phase of algorithm development,
you try to identify the major sub-tasks of the
algorithm.
• One way of modularizing our current problem
might be to call out the following sub-tasks:
– Store numbers to be added into memory
– Add the numbers
– Store the result
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Stepwise Refinement
• During stepwise refinement, the major
sub-tasks are fleshed out with minor subset tasks.
• Here is an example - add the numbers:
– Access first number from memory
– Access second number from memory
– Perform arithmetic addition
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Algorithm Implementation
• Once we have disambiguated the problem statement (as
much as is reasonable), identified key tasks and then
successively detailed our stepwise refinement, we can
implement our algorithm.
• Theoretically, the language doesn’t matter – you could
utilize any language to implement your algorithm.
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science
Questions?
N301: Fundamental Computer Science Concepts
Copyright ©2004  Department of Computer & Information Science