Overview of Problems and Problem solving Concepts

Lecture Note (Week 1)

The CSC121 Team

Learning Objectives

Understand what a problem is in computing terms

Describe the difference between heuristic and algorithmic solutions to problems

List and describe the six problem-solving steps to solve a problem that has an algorithmic solution.

Use the six problem-solving steps to solve any problem

Lecture Outline

What is a Problem?

Types of Problems

What is Problem Solving?

Solution Techniques

Problem Solving using Computers

Process Of Problem Solving (6 steps)

What is a Problem?

Problems exist in every area of our daily lives

List Specific Examples of Problems

Problems are obstacles to overcome.

E.g. Solve a Maths equation, Make a decision, accomplish a task etc.

A Problem can be defined as an unpleasant situation or condition which a better or perfect state is desired.

The situation is referred to as the present state, and the desired state is known as the goal state.

Reaching the goal state is achieved by following

a sequence of steps which can be either simple or complex.

Inputs made to the present state is what determines if the desired goal stage will be reached.

Therefore a problem is defined by its input and the property of its desired goal state.

Types of Problems

Routine Problems

A problem with a simple, and predictable solution.

Solve a math problem, spell a word etc.

Non-routine Problems

A problem with subjective, abstract and complex solutions.

More difficult to solve

Arrange 10 popular languages from best to least

Problem Solving

Problem solving�is the application of ideas, skills, or factual information as inputs in specific sequence of steps to attain to the solution to a problem or to reach a desired goal state.�

Problem Solving

The sequence of steps is called the Solution to the problem.

The solution of a problem will take defined inputs and produce the desired output.

Problem Solving

However,

One problem can have multiple solutions,

But the aim of computer programmers is to find the best solution to the given problem.

Not all Problems have straight-forward solutions,

Some require a series of trial and error before a solution can be reached

In-class Interaction [5Mins]

List some problems that have more than one solution

Identify the best solution?

List some problems with solutions that would involve trial and error?

Types of Solution Approaches

In computer programming, there are two classifications of solutions to problems

Algorithmic Solutions

Heuristic Solutions

Algorithmic Solution

These are solutions to problems in which the desired state is achieved by a defined and finite sequence of steps

E.g. to make pizza, to get the CST building from the Hostel, to determine the number of rooms in Senate Building etc.

The sequence of steps it takes to arrive at the goal/desired state is called Algorithm.

Heuristic Solutions

These are solutions to problems in which the goal state is reached by series of steps which emerge

From Knowledge and Experience

From various Trials and Error

Therefore, solutions that cannot be reached by direct steps are called Heuristics Solutions.

For Example

Making a speech at an event, playing and winning a soccer game, find the right marriage partner.

Focus of this Course

This course is mainly concerned with Algorithmic solution to problems,

Which can be solved by the computers.

Heuristics solutions are achieved

Using artificial intelligence techniques.

E.g. Artificial Neural Network, Fuzzy Logic, Constraint Optimization etc.

Some Solution Techniques (1 of 5)

Abstraction

Solving the problem in a model of the system before applying it to the real system

Analogy

Using a solution that solved an analogous problem

Brainstorming

Suggesting a large number of solutions or ideas and combining and developing them until an optimum is found(especially among groups of people)

Some Solution Techniques (2 of 5)

Trial-and-Error

Testing possible solutions until the right one is found

Hypothesis testing

Assuming a possible explanation to the problem and trying to prove (or, in some contexts, disprove) the assumption

Reduction

Transforming the problem into another problem for which solutions exist

Some Solution Techniques (3 of 5)

Lateral thinking

Approaching solutions indirectly and creatively

Means-ends analysis

Choosing an action at each step to move closer to the goal (e.g. sorting numbers)

Method of focal objects

Synthesizing seemingly non-matching characteristics of different objects into something new

Morphological analysis

Assessing the output and interactions of an entire system

Some Solution Techniques (4 of 5)

Research

Employing existing ideas or adapting existing solutions to similar problems

Root cause Analysis

Identifying the cause of the problem

Proof

Try to prove that the problem cannot be solved. The point where the proof fails will be the starting point for solving it

Some Solution Techniques (5 of 5)

Divide and Conquer (D&C)

Breaking down a large, complex problem into smaller, solvable problems

Solving Problems with Computers

Computers are built to deal with algorithmic solutions,

Often difficult or very time consuming for humans.

Solving a complex mathematical equation or arranging 3000 names in alphabetical order is an easy task for the computer.

Problem Solving: Humans & Computers

Human beings can arrive at heuristic solutions better than computers.

For humans, these problem are not difficult

Identify a human s voice, play free kicks or how to speak Spanish

For computers, the difficulty is in programming the machine to solve the problem:

How can computers be programmed (in a set of steps) to play free kick, or speak Spanish?

However&

The field of Computer Science that deals with heuristic types of problems is called Artificial Intelligence (AI).

AI enables a computer to do things like build its own knowledge-bank and speak in a human language.

In AI, computers and computer�software�are capable of intelligent behavior and the goals of AI includes:

Reasoning, knowledge, planning, learning, natural language processing (communication), perception and the ability to move and manipulate objects etc.

6 Steps of Solving any Problem

Identify the Problem

Understand the Problem

Identify alternative solutions to problem

Create a list of possible solutions

Select the best way to solve the problem from the list

List out the instructions that are involved in the selected solution to the problem

Evaluate the solution

Identify the Problem

The first step of solving any problem is to

Identify the problem

You must ask, what is the problem?

A set of problems may be given to you by the instructors, or you may have to identify a problem on your own.

A problem not known cannot be solved.

Understand the Problem

Understanding the problem entails, having a good knowledge base of the problem.

For Example Solving

Computer hardware problem, requires knowledge about computer parts.

Calculus problems requires knowledge of calculus

In providing solution, one must communicate with the client and understand what is involved in solving the problem.

Identify alternative Solutions to Problem

A problem might have more than one solution.

List as many alternate solutions as much as possible.

Interacting with others in a brainstorming session, could provide insights to alternative ways of solving the problem.

Create a list of all the possible ways to solving the problem

Select the best Solution

Evaluate the Pros and Cons of each of the possible solutions

The evaluation would determine the best solution to select

List Instructions Involved in the Solution

The instructions are the step-by-step procedures that will be followed to arrive at the desired goal state.

Instructions are useless except understood by the individual or machine.

Instructions must be in:

Human or Computer-readable forms

These Steps are called ALGORITHMS

Evaluate Solution

In evaluating the solution, the result of the solution is checked to ensure correctness.

Also the solution must meet/satisfy the need of the person, or the situation requesting the solution.

If the result is unsatisfactory or incorrect,

The list of instructions must be reviewed or

The other 5 Steps must be repeated.

6-Steps in Action

Lets Explore the 6 Steps in Action

Identify the Problem

How does Someone get to CST Building from Daniel Hall in 10 Mins?

Understand the Problem

The knowledge base of the individual and the layout of the campus must be considered.

Also the various constraint of the campus should be known,

e.g. one would not include using a private-jet or helicopter as solutions.

Identify Alternatives Solutions

Use a Cab

Use a bicycle

Drive a personal car

Use Shuttle Bus

Walk through the Female Halls area

Jogging

Walk through the main road

Ask for a Lift from vehicles passing by

Select the best Alternative

To select the best, weed out alternatives that are not acceptable,

e.g. those that would require much money, energy or time.

Specify the pros and cons,

Make a final decision.

List the instructions

Prepare a list of instructions (Steps) that will be taken, in the minutest detail that will result in getting to CST Building in 10 minutes

Evaluate the Solution

See if the result matches the expectation of the problem.

If not, the instructions (Steps) should be reviewed or the overall process should be repeated.

Assignment

Write Short Notes on 5 Solution Techniques highlighted in this lecture note.

Maximum of 3 Pages

Submission via Moodle

Lifeline:

Blank

Blank