- Forward


Algorithms
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Definitions
Back SMYC Forward
  • Algorithm:
    • An unambiguous process (i.e., ordered set of steps) for solving a problem using a finite amount of resources
  • Heuristic:
    • A problem solving process that is not guaranteed to be perfect/exact
History
Back SMYC Forward
  • Algorithm:
    • The Oxford English Dictionary (OED) says it was first used with this meaning in 1811 (but as early as 1658 with similar meanings)
    • Some believe that the word is derived from the name of a Persian mathematics teacher named Muhammad ibn-Musa al-Khowarizm, one of the first people to develop step-by-step procedures for doing computations
  • Heuristic:
    • The OED says it was first used with this meaning in 1957 (but as early as 1770 with similar meanings)
    • It may come from the Latin word meaning "ultimately" or the Greek word meaning "find" (and hence is sometimes used only for processes that learn/discover)
An Example
Back SMYC Forward
  • Taken from a Shampoo Bottle:
    • Wet your hair Apply shampoo Lather Rinse Repeat
  • Questions:
    • Is it a set of steps?
    • Is it an algorithm, a heuristic, or neither?
Where Do Algorithms Come From?
Back SMYC Forward
  • In Some Situations:
    • They are a recording/reporting of what is already known
  • In Other Situations:
    • They must be discovered/invented
Algorithm Development's Place in the Cognitive Domain
Back SMYC Forward
  • Bloom's (Updated) Taxonomy of the Cognitive Domain:
    • Creating
    • Evaluating
    • Analyzing
    • Applying
    • Understanding
    • Remembering
  • Algorithm Development:
    • Is not the regurgitation of memorized processes
    • Is about evaluating existing processes and creating new ones
Science or Engineering?
Back SMYC Forward
  • Science:
    • Involves the use of the scientific method (hypothesize, predict, and experiment)
  • Engineering:
    • The application of science
  • Algorithm Development:
    • Part science, part engineering, and a little art
    • comics/Hackles-CutAndPaste.png
      (Courtesy of Hackles)
Recording/Reporting Algorithms you Already "Know"
Back SMYC Forward
  • Describe what you would do:
    • Think about how you would solve the problem
    • Record the steps in the process you would use
    • Verify that the algorithm works
  • Describe what you do as you do it:
    • Solve the problem recording the steps you use as you perform them
    • Verify that the algorithm works
  • Describe what you did:
    • Solve the problem
    • Record the steps you used
    • Verify that the algorithm works
Developing New Algorithms
Back SMYC Forward
  • Look for related problems/algorithms (i.e., patterns)
    • More general problems/algorithms
    • More specific problems/algorithms
    • Analogous problems/algorithms
  • Look for "subproblems"
    • Partition the data
    • Divide the problem
Commonalities Across Algorithms
Back SMYC Forward
  • Decomposition:
    • Large algorithms are often broken down into a collection of smaller sub-algorithms (using abstraction)
  • Input:
    • Information is often obtained from external "producers" (e.g., users, sensors)
  • Memory/Recall:
    • Information often needs to be stored and recalled
  • Operations:
    • Information is often manipulated (e.g., added, concatenated)
Commonalities Across Algorithms (cont.)
Back SMYC Forward
  • Conditions:
    • Operations are often performed under some circumstances but not others
  • Iterations:
    • Operations are often performed repeatedly/iteratively
  • Output:
    • Information is often presented to external "consumers" (e.g., users, devices)
Abstraction in Algorithm Development
Back SMYC Forward
  • Abstraction Defined:
    • "The act or process of separating in thought, of considering a thing independently..." (OED)
  • Using Abstraction:
    • Focus on what is important
    • Ignore/hide unnecessary details
    • Leads to top-down development (treating some things as "black boxes")
A "High Level" Algorithm for Eggs Benedict
Back SMYC Forward
Prepare Hollandaise sauce Toast English muffin Poach eggs until whites are soft Grill Canadian bacon Plate the completed dish
A "High Level" Algorithm for Hollandaise
Back SMYC Forward
Heat butter until bubbling Combine all other ingredients in blender Pour butter into running blender in a slow stream
A "Lower Level" Algorithm for Hollandaise
Back SMYC Forward
Put butter in pot Turn on burner Put pot on burner While not bubbling, leave pot on burner Remove pot from burner If you like spicy sauce, put tabasco sauce in blender Put all other ingredients in blender Turn on blender While you have butter, pour butter into blender in a slow stream Turn off blender
There's Always More to Learn
Back -