Algorithms and
Problem Solving
Lecture Objectives
• Revisiting problem solving skills
• Explore the algorithmic approach for problem
solving
• Learn about algorithm development
• Become aware of problem solving process
Problem Solving
• Programming is a process of problem solving
• Problem solving techniques
– Analyze the problem
– Outline the problem requirements
– Design steps (algorithm) to solve the problem
• Algorithm:
– Step-by-step problem-solving process
– Solution achieved in finite amount of time
Problem Solving Process
• Step 1 - Analyze the problem
– Outline the problem and its requirements
– Design steps (algorithm) to solve the
problem
• Step 2 - Implement the algorithm
– Implement the algorithm in code
– Verify that the algorithm works
• Step 3 - Maintenance
– Use and modify the program if the problem
domain changes
Analyze the Problem
• Thoroughly understand the problem
• Understand problem requirements
– Does program require user interaction?
– Does program manipulate data?
– What is the output?
• If the problem is complex, divide it into
subproblems
– Analyze each subproblem as above
What is an algorithm?
• The idea behind the computer program
• Stays the same independent of
– Which kind of hardware it is running on
– Which programming language it is written in
• Solves a well-specified problem in a general
way
• Is specified by
– Describing the set of instances (input) it must
work on
– Describing the desired properties of the output
What is an algorithm? (Cont’d)
• Before a computer can perform a task, it must
have an algorithm that tells it what to do.
• Informally: “An algorithm is a set of steps that
define how a task is performed.”
• Formally: “An algorithm is an ordered set of
unambiguous executable steps, defining a
terminating process.”
– Ordered set of steps: structure!
– Executable steps: doable!
– Unambiguous steps: follow the directions!
– Terminating: must have an end!
What is an algorithm? (Cont’d)
Important Properties of Algorithms
• Correct
– always returns the desired output for all
legal instances of the problem.
• Unambiguous
• Precise
• Efficient
– Can be measured in terms of
• Time
• Space
– Time tends to be more important
Representation of Algorithms
• A single algorithm can be represented in
many ways:
– Formulas: F = (9/5)C + 32
– Words: Multiply the Celsius by 9/5 and add
32.
– Flow Charts.
– Pseudo-code.
• In each case, the algorithm stays the
same; the implementation differs!
Representation of Algorithms (Cont’d)
–A program is a representation of an
algorithm designed for computer
applications.
–Process: Activity of executing a program,
or execute the algorithm represented by
the program
Expressing Algorithms
• English
description
More
easily More
• Pseudo-code
expressed precise
• High-level
programming
language
Pseudocode
• Pseudocode is like a programming
language but its rules are less stringent.
• Written as a combination of English and
programming constructs
– Based on selection (if, switch) and iteration
(while, repeat) constructs in high-level
programming languages
• Design using these high level primitives
– Independent of actual programming
language
Pseudocode (Cont’d)
Example: The sequential search algorithm in
pseudocode
Algorithm Discovery
• The Two Steps of Program Development:
– 1. Discover the algorithm.
– 2. Represent the algorithm as a program.
• Step 2 is the easy step!
• Step 1 can be very difficult!
• To discover an algorithm is to solve the
problem!
Problem Solving: A creative process
• Problem solving techniques are not unique to
Computer Science.
• The CS field has joined with other fields to try
to solve problems better.
• Ideally, there should be an algorithm to
find/develop algorithms.
• However, this is not the case as some problems
do not have algorithmic solutions.
• Problem solving remains an art!
Problem Solving Strategies
• Working backwards
– Reverse-engineer
– Once you know it can be done, it is much easier to do
– What are some examples?
• Look for a related problem that has been solved before
– Java design patterns
– Sort a particular list such as: David, Alice, Carol and Bob to
find a general sorting algorithm
• Stepwise Refinement
– Break the problem into several sub-problems
– Solve each subproblem separately
– Produces a modular structure
• K.I.S.S. = Keep It Simple Stupid!
Stepwise Refinement
• Stepwise refinement is a top-down methodology
in that it progresses from the general to the
specific.
• Bottom-up methodologies progress from the
specific to the general.
– These approaches complement each other
• Solutions produced by stepwise refinement
posses a natural modular structure - hence its
popularity in algorithmic design.
Brainstorming
• A group problem-solving technique that
involves the spontaneous contribution of
ideas from all members of the group
– All ideas are potential good ideas
– Think fast and furiously first, and ponder
later
– A little humor can be a powerful force
• Brainstorming is designed to produce a
list of candidate classes
Computer Example
• Let’s repeat the problem-solving process
for creating an address list
• Brainstorming and filtering
– Circling the nouns and underlining the verbs
Computer Example (Cont’d)
• First pass at a list
Computer Example (Cont’d)
• Filtered list