Problem Solving Concepts*
* This lecture is based on slides by Dr. Awad Khalil
Problem Solving Methods
◼ There is no perfect method for solving all problems.
◼ There is no problem-solving computer to which we could
simply describe a problem and wait for a solution.
◼ Problem solving is a creative process and cannot be
completely specified.
◼ However, we can still use well-accepted procedures to
structure our thinking and help us solve problems.
◼ Three methods of problem solving are prominent:
1. Analytical Method.
2. Algorithmic Method.
3. Software Engineering Method.
CSCE 1001 – Fundamentals of
2
Computing I
Problem Solving Steps
◼ Each method has four basic components:
1. Problem statement: the problem presents the
situation that requires a solution.
2. Reasoning (Analyzing the problem): this implies a
true comprehension of the problem.
3. Solution approach: this is the process that we
develop to solve the problem.
4. Testing: this is the checking process we use to
confirm that the solution is correct.
CSCE 1001 – Fundamentals of
3
Computing I
I. The Analytical Method
◼ Analytical problem solving has roots in
mathematics, physics, engineering, chemistry,
and other areas in science and technology.
◼ Example:
1. Problem statement
Find the two numbers whose sum is s and product is p.
2. Reasoning (Analyzing the problem)
Let us call the first number x and the second one y.
Therefore, x + y = s and x * y = p.
From the first equation we get: y = s - x.
Substituting y from the first equation into the second
equation, we get: x * (s - x) = p or x2 - sx + p = 0.
CSCE 1001 – Fundamentals of
4
Computing I
I. The Analytical Method
3. Solution approach
The solution to this problem is the solution to the
quadratic equation: x2 - sx + p = 0, provided that
s2 – 4p 0.
This solution is known from the field of mathematics.
4. Testing
To check the correctness of the above solution we calculate
x + y and x * y.
CSCE 1001 – Fundamentals of
5
Computing I
I. The Analytical Method
Limitations of the Analytical Method
◼ Some problems cannot be solved analytically even with the most
sophisticated techniques.
◆ Example: mathematicians have proven that no analytical method can find
the roots of a fifth-order polynomial equation of the form:
ax5 + bx4 + cx3 + dx2 + ex + f = 0, for arbitrary coefficients.
◼ This does not contradict that in special cases, an analytical solution is
possible.
5 4 3 2
◆ Example: x - 1 = 0 can be factored as (x - 1)(x + x + x + x + 1) = 0
leading to one answer x = 1, that can be easily verified.
◼ Likewise, there are numerous problems in science and mathematics
where analytical solutions are not tractable.
◼ Algorithms are often used to solve such problems and the answers that
result are accurate enough to be accepted as solutions.
CSCE 1001 – Fundamentals of
6
Computing I
II. The Algorithmic Approach
Algorithmic Problem:
◼ is any problem whose solution can be expressed as a list
of executable instructions.
◆ By executable, we mean that an independent executor (human or
machine) should be able to carry out the instructions in a step-by-
step manner.
Examples of Algorithmic Problems
1. Baking a cake.
2. Knitting a sweater.
3. Computing the sum of a finite list of numbers.
4. Sorting a finite list of names.
5. Playing Tic-Tac-Toe.
CSCE 1001 – Fundamentals of
7
Computing I
Algorithm
◼ An algorithm is a sequence of executable
instructions with the following properties:
1. There is no ambiguity in any instruction.
2. There is no ambiguity about which instruction is
executed next.
3. The description of the algorithm is finite.
4. Execution of the algorithm concludes after a finite
number of steps.
◼ Algorithms are not unique to the field of computing.
◆ An algorithm is a recipe, i.e. a sequence of steps that
leads from a starting point to a result.
CSCE 1001 – Fundamentals of
8
Computing I
II. The Algorithmic Approach
◼ Non-Algorithmic Problems
Example: Consider the following instructions:
Step1: Make a list of all odd positive integers.
Step2: Compute their sum.
Step3: Compute their average.
Step4: Print the average.
◼ This is not an algorithm because it is impossible to
make an infinite list of numbers, and the problem of
finding the sum (or average) of all odd positive
integers is not algorithmic.
CSCE 1001 – Fundamentals of
9
Computing I
Phases of Algorithmic Problem Solving
◼ Ultimately, one would like to reduce the process of
problem solving to an algorithm in itself, but this
has been shown to be impossible.
◼ The following, loosely-defined, problem-solving
phases were presented by the mathematician G.
Poyla in the late 1940s.
Phase1: Understand the problem.
Phase2: Devise a plan for solving the problem.
Phase3: Carry out the plan.
Phase4: Evaluate the solution for accuracy and for its
potential as a tool for solving other problems.
CSCE 1001 – Fundamentals of
10
Computing I
An Algorithm
CSCE 1001 – Fundamentals of
11
Computing I
Algorithm Representation
◼ There are several methods to represent
an algorithm:
◆ Pseudocode
◆ Flow Chart
◆ Programming Languages
CSCE 1001 – Fundamentals of
12
Computing I
Algorithm Representation
◼ The artificial language we are using to describe an
algorithm is called pseudocode.
◆ Pseudocode is a notation that can be used to express
ideas informally during the algorithm development
process.
◼ The pseudocode used during the early stages of
algorithm development resembles, but is less
formal than, a programming language.
Pseudocode cannot be compiled and executed
by a computer!
CSCE 1001 – Fundamentals of
13
Computing I
Algorithmic Structure
◼ An algorithm is written as a step-by-step
procedure (sequence) in which choices can be
made where necessary (selection), and all or
part of the algorithm can be repeated
(repetition).
◼ Thus, the basic structures of an algorithm are:
1- sequence
2- selection
3- repetition
CSCE 1001 – Fundamentals of
14
Computing I
1. Sequence
◼ An algorithm is based on the notion of
sequence, which is the ordering of statements.
◼ Step n cannot be started until step n-1 is
completed.
◼ Problem 1: Develop an algorithm that calculates
and prints the area of a trapezoid when the
values of the bases and height are given as
input.
Input: base1, base2, height
Output: area
Algorithm 1:
step1: INPUT base1, base2, height
step2: area := (base1+base2)*height/2
step3: OUTPUT area
step4: STOP
CSCE 1001 – Fundamentals of
15
Computing I
2. Selection (branching)
◼ Selection is the choice of alternate paths (branches) depending on a
condition that may arise in the logical flow of the algorithm.
CSCI 106 - Introduction to
16
Computers
3. Repetition (looping)
◼ The third structure used for the development of an algorithm is called
repetition or looping, which supports the repeated execution of part of the
algorithm.
CSCI 106 - Introduction to
17
Computers
III. Software Engineering Method
◼ Software engineering
◆ The area of computing is concerned with
building scalable software systems
◼ Challenge
◆ Tremendous advances in hardware have
not been matched by comparable advances
in software
CSCE 1001 – Fundamentals of
18
Computing I
Software Engineering Phases
◼ Problem Definition/Analysis - (Correct Problem)
◆ Identify data objects
◆ Model properties
◆ Determine Input / Output data
◆ Constraints on the problem
◼ Algorithm Design
◆ Decompose into smaller problems
◆ Top-down design (divide and conquer)
◆ Develop Algorithm (Desk check)
CSCE 1001 – Fundamentals of
19
Computing I
Software Engineering Phases cont.
◼ Implementation/Coding
◆ Writing the algorithm (programming language)
◼ Testing & Debugging
◆ Verify the program meets requirements
◆ System and Unit test
◼ Documentation
◆ Key part of the development process
CSCE 1001 – Fundamentals of
20
Computing I
Software Engineering Goals
◼ Reliability
◆ An unreliable life-critical system can be fatal
◼ Understandability
◆ Future development becomes challenging if the
software is hard to understand
◼ Cost Effectiveness
◆ Cost to develop and maintain should not exceed
profit
CSCE 1001 – Fundamentals of
21
Computing I
Software Engineering Goals cont.
◼ Adaptability
◆ SW system that is adaptive is easier to alter and
expand
◼ Reusability
◆ Improves reliability and maintainability, and
reduces development costs
CSCE 1001 – Fundamentals of
22
Computing I
