UNIT – II

INTRODUCTION TO PROBLEM
SOLVING

FYBTEC
H Subject : Programming and Problem Solving
 Unit II Contents
2

◻ Introduction to Problem Solving: Problem solving process/framework,

Programming Paradigms: Imperative, Object Oriented, Functional and Logic
programming. Characteristics of Programming Languages, Role of programming
languages, need of studying programming languages.
◻ Programming Design Tools: Algorithms, Pseudo-code and Flowchart, Case studies
for Algorithm, Flowchart and Pseudocode. Top-Down and Bottom-Up design
approach. Software Development Life Cycle.
 Introduction to Problem Solving
3

◻ Introduction to Problem Solving: Problem solving process/framework,

Programming Paradigms: Imperative, Object Oriented, Functional and Logic
programming. Characteristics of Programming Languages, Role of programming
languages, need of studying programming languages.
 Computer Programming– Three Stages
4

◻ Computer programming can be divided into three distinct areas

of activity:
1. Problem definition and problem solving
2. Creating a structured solution (or algorithm)
3. Coding (e.g. C, Java, C++)
◻ Consider an example as case of customer while marketing
• Specify the problem
• Solve the problem
• Specify solution in structured format
 Problem Solving, Algorithm Development
and Coding
5

◻ In problem solving, algorithm development and coding we tend to

view problems at different levels of abstraction.

🞑 Problem solving is done at a high level of abstraction. Much of

the detail is omitted at this stage in order that the problem can
be more easily specified and solved.

🞑 Algorithm development works at a lower level of abstraction

than problem solving. It contains much of the detail that will
eventually become the program. However, it still omits the finer
detail required in the final compute program

🞑 Coding works at a very low level of abstraction. Programming

code must be written with every single detail a computer needs
to carry out a task included.
 Contd…
6

◻ Problem solving, algorithm development and coding

are also different in terms of the language that is used
to complete the activity:
🞑Problem solving is generally done using use
natural, everyday language
🞑Algorithm development is done using a specialist,
semi-structured language (pseudo code)
🞑Coding is done using a highly-structured
(programming) language that is readable by
machines
 What is a Problem?
7

◻ There are many different kinds of problems:

🞑How do I get to Oxford from London?
🞑Why is it wrong to lie?
◻ For a problem to be solvable through the use of a
computer, it must generally:
🞑Be technical in nature with objective answers that can
be arrived at using rational methods
🞑Be well-structured
🞑Contain sufficient information for a solution to be
found
🞑Contain little, if any, ambiguity.
 When Can You Use a Problem Definition?
8

◻ Starting Point

◻ Expected Outcome

◻ Possible Procedure
 How do We Solve Problems?
9

◻ We need to THINK!
◻ We need to engage in one or more of the following
types of thinking:
🞑 Logical reasoning
🞑 Mathematical reasoning
🞑 Lateral thinking
◻ Problem solving is easier if we employ a problem
solving framework and an appropriate problem
solving strategy to aid us.
 A Problem Solving Framework
10

◻ An outline framework for problem solving:

1. Understand the problem
2. Devise a plan to solve the problem
3. Carry out the plan
4. Assess the result
5. Describe what has been learned from the process
6. Document the solution.

◻ In Vickers, this framework is called the How to Think Like a

Programmer (HTTLAP) approach to problem solving.
 Understanding the Problem
11

◻ To understand a problem
🞑We need to read and reread it till we understand every
detail
🞑We need to dissect the problem into its component
parts (e.g. problems and sub-problems)
🞑We need to remove any ambiguity
🞑We need to remove any information that is extraneous
to the problem
🞑We need to determine our knowns and our unknowns
🞑We need to be aware of any assumptions we are
making.
 Devise a plan to the solve the problem
12

◻ If a problem contains a set of sub-problems, in what

order are you going to solve them?
◻ How are you going to represent the problem:
🞑 Numerically?
🞑 Graphically?
🞑 Tabular data?
🞑 Natural language?
◻ Does the problem lend itself to a particular problem
solving strategy or strategies:
🞑 Working backwards?
🞑 Logical reasoning?
🞑 Finding a pattern?
🞑 Accounting for all possibilities?
 Carry Out the Plan
13

◻ Consider the following problem:

In a room with ten people, everyone shakes hands with
everyone else exactly once. In total, how many handshakes
are there?
◻ How would you represent and solve the problem?
◻ Different strategies to be used
 Assessing the Results
14

◻ It is very unusual when solving complex problems to achieve

the correct result first time round.
◻ To verify our solutions are correct, we need to take a few
steps backwards:
🞑 Was our understanding of the problem correct?
🞑 Did we overlook anything?
🞑 Did we choose the correct strategy?
🞑 Did we employ that strategy correctly?
🞑 Have we made any incorrect or unwitting assumptions?
◻ However, it is often very difficult to spot our own mistakes. It
is often better, therefore, to have somebody else verify our
solutions for us.
 Contd…
15

◻ Sometimes solutions appear correct, but are in fact

wrong, due to an initial misunderstanding of a
problem (What Vickers calls, errors of the third
kind).
◻ If you have misunderstood a problem, it does not
matter how good a coder you are, your program
will not work as it is supposed to.
◻ Therefore getting the problem-solving part of
programming right is absolutely essential if we are
to build programs that work as they are supposed to
work.
 Describing What you have Learned
16

◻ You can only become a good problem solver by

reflecting on your experiences of problem solving.
◻ Keeping a record of problems you have attempted,
your success, failures, the approaches you have
used, etc. will:
🞑Broaden your problem solving repertoire
🞑Help you to recognize similarities/patterns in problems
🞑Help you identify and fix logical or implementation
errors
🞑Help you to solve problems faster and more effectively
 Documenting the Solution
17

◻ Documenting a solution will help you to generalize your

approach to other similar problems.
◻ Do you recognize the following type of problem? How
would you solve it?

Carlos and his friends have a fantasy football league in which each team will play
each other three times. The teams are Medellin, Cali, Antigua, Leon, Juarez,
Quito and Lima. How many games will be played in all?

◻ It will also prevent you forgetting how you arrived at your

solutions.
◻ In the long run, it will make you a better problem solver
and eventually a better programmer.
 Computer Problem-Solving
18
 The Interactions Between Problem-Solving
Phases
19
 Conveying solution in a formal language
20

Purpose of program planning

◻ To write a correct program, programmer must write
each and every instruction in the correct sequence.
◻ Logic (instruction sequence)of the program can be
very complex.
◻ Hence program must be planned before they are
written to ensure program instructions are:
◻ Appropriate for the problem
◻ In the correct sequence
 Programming Paradigms
21

A programming paradigm is a pattern of problem-

solving thought that underlies a particular genre of
programs and languages.
There are four main programming paradigms:
🞑Imperative
🞑Object-oriented
🞑Functional
🞑Logic (declarative)
 Imperative Paradigm
22

Follows the classic von Neumann-Eckert model:

🞑Program and data are indistinguishable in memory
🞑Program = a sequence of commands
🞑State = values of all variables when program runs
🞑Large programs use procedural abstraction

Example imperative languages:

🞑Cobol, Fortran, C, Ada, Perl, …
 The von Neumann-Eckert Model
23
 Object-Oriented (OO) Paradigm
24

An OO Program is a collection of objects that interact

by passing messages that transform the state.
When studying OO, we learn about:
🞑 Sending Messages
🞑 Inheritance
🞑 Polymorphism
Example OO languages:
Smalltalk, Java, C++, C#, and Python
 Contd…
25
 Functional Paradigm
26

Functional programming models a computation as a

collection of mathematical functions.
🞑Input = domain
🞑Output = range
Functional languages are characterized by:
🞑Functional composition
🞑Recursion
Example functional languages:
🞑Lisp, Scheme, ML, Haskell, …
 Functional vs Imperative
27

◻ Compute Factorial Function

🞑In Imperative Programming Languages:
fact(int n) {
if (n <= 1) return 1;
else
return n * fact(n-1);
}
❑ In Functional Programming Languages: Scheme
(define (fact n)
(if (< n 1) 1 (* n (fact (- n
1)))
))
 Logic Paradigm
28

Logic programming declares what outcome the

program should accomplish, rather than how it
should be accomplished.
When studying logic programming we see:
🞑 Programs as sets of constraints on a problem
🞑 Programs are expressed as rules in formal language
🞑 Programs that achieve all possible solutions
🞑 Programs that are nondeterministic
Example logic programming languages:
🞑 Prolog
Summary: Programming Paradigm

⮚ Imperative Programming
⮚ Follows the classic von Neumann-Eckert model
⮚ Variables, assignment statements, and iteration
⮚ e.g. C, Fortran ,Pascal

⮚ Object Oriented Programming

⮚ Class and Object based.
⮚ e.g. C++,JAVA ,Python
Summary: Programming Paradigm

⮚ Functional Programming
⮚ Computing by applying functions to given parameters
⮚ e.g. LISP, Scheme, ML,Haskell

⮚ Logic Programming
⮚ Rule-based (rules are specified in no particular order)
⮚ e.g. Prolog
 What is Programming Language
31

◻ A programming language is a notational system for

describing computation in machine-readable and
human-readable form.
◻ A programming language is a tool for developing
executable models for a class of problem domains.
 What is Programming Language
32

◻ English is a natural language. It has words, symbols

and grammatical rules.
◻ A programming language also has words, symbols
and rules of grammar.
◻ The grammatical rules are called syntax.
◻ Each programming language has a different set of
syntax rules.
 Characteristics of Programming Languages
33

◻ The language must allow the programmer to write simple, clear and
concise programs.
◻ It must be simple to use so that a programmer can learn it without
any explicit training.
◻ It must be platform independent. That is, the program developed
using the programming language can run on any computer system.
◻ The Graphical User Interface (GUI) of the language must be
attractive, user-friendly, and self-explanatory.
◻ The function library used in the language should be well
documented so that the necessary information about a function can
be obtained while developing application.
 Characteristics of Programming Languages
(Cont…)
34

◻ Several programming constructs supported by the language

must match well with the application area it is being used for.
◻ The programs developed in the language must make efficient
use of memory as well as other computer resources.
◻ The language must provide necessary tools for development,
testing, debugging, and maintenance of a program. All these
tools must be incorporated into a single environment known
as Integrated Development Environment (IDE), which enables
the programmer to use them easily.
◻ The language must be consistent in terms of both syntax and
semantics.
 Role of Programming Languages
35

◻ A programming language is formal language that specifies a

set of instructions that can be used to produce various kinds of
output .
◻ Programming languages generally consist of instructions for a
computer .
◻ Programming languages can be used to create programs that
implement specific algorithms.
 Cont’d…
36

Steps in learning English Language-

Alphabets Words Sentences Paragraph

Steps in learning C-Language-

Alphabets/
Constants/
Digits/ Program
Variables/ Instructions
Special
Keywords
Symbols
 Need to Study Programming Language
37

◻ To improve your ability to develop effective algorithms.

◻ To improve your use of existing programming languages.
◻ To increase your vocabulary of useful programming
constructs.
◻ To allow a better choice of programming language.
◻ To make it easier to learn a new language.
◻ To make it easier to design a new language.
 Unit-II Contents
38

◻ Programming Design Tools: Algorithms, Pseudo-code and Flowchart, Case

studies for Algorithm, Flowchart and Pseudocode. Top-Down and Bottom-Up
design approach. Software Development Life Cycle.
 Algorithm, Flowchart and Pseudo
Code
39

◻ A typical programming task can be divided into two phases:

1. Problem solving phase

🞑 produce an ordered sequence of steps that describe solution of
problem
🞑 this sequence of steps is called an algorithm
2. Implementation phase
🞑 implement the program in some programming language
 Algorithm, Flowchart and Pseudo
Code
40

◻ Algorithms, Flowcharts and Pseudo Codes are different

tools used for creating new programs, especially in
computer programming
◻ Algorithm
🞑 Set of step-by-step instructions that perform a specific task or operation
🞑 It is a Natural language and NOT programming language
◻ Flowchart
🞑 Visual program design tool
🞑 Semantic symbols describe operations to be performed
◻ Pseudo code
🞑 Set of instructions that mimic programming language instructions
 What is an Algorithm?
41

◻ Step-by-step description of how to achieve a solution

for a given problem
◻ refers to the logic of the program or sequence of
instructions
◻ It is defined as a sequence of instructions that when
executed in the specified sequence, the desired results
are obtained.
 Algorithm
42

◻ Algorithm is a representation of a solution to a problem

◻ It is commonly used for data processing, calculation and other

related computer and mathematical operations

◻ To be an algorithm, a set of rules must be unambiguous and

have a clear stopping point
 Characteristics of an Algorithm
43

❑Should be precise and unambiguous

❑Should be executed in a finite time
❑Should not be repeated infinitely. algorithm will
ultimately terminate.
❑Desired results are obtained
❑ Must have start and stop steps
 Example
44

◻ Algorithm to add two given numbers:

Step 1: START
Step 2: Read two numbers A and B
Step 3: Add numbers A and B and store result in C
Step 4: Display C
Step 5: STOP
 Example
45

Write an algorithm to find the largest among three

different numbers entered by user.
Step 1:START
Step 2:Declare variables a,b and c.
Step 3:Read variables a,b and c.
Step 4:If a>b
If a>c
Display a is the largest number.
Else
Display c is the largest number.
 Contd…
46

Else
If b>c
Display b is the largest number.
Else
Display c is the largest number.
Step 5:STOP
 Generalized Algorithm
47

◻ Logic written in universal or general terms

◻ Algorithms are written in general languages which
can be used by any one
◻ Knowledge of programming language is not
required
◻ Only solution of problem is given, implementation
details are not required
◻ Becomes easy to find solution
◻ Anyone can refer this algorithms
 How to Make Algorithms Generalized
48

◻ Solve problem by person who will not be

expert in implementation
◻ Use generalized logic to solve problem
 Infinite Loop
49

◻ Loop mean repeat set of instruction till specific

condition is true
◻ Infinite loop is endless loop, i.e. it never ends
◻ Infinite loop occurs when condition remains always
true or no termination condition exists
◻ Due to infinite loop, program never ends
 Avoiding Infinite Loops
50

Avoided by limiting the number of repetitions of

loop
Two ways:
❑ By counting fixed count is used for repeating
loop
❑ By using sentinel value It is special value
whose presence guarantees termination of
loop
 Different Ways to Represent an Algorithm

51

❑ As a flowchart
❑ As a pseudocode
❑ As a program
 Program Planning Tools
52

❑Flowchart
❑ Structure charts
❑ Pseudo codes
 Flowchart
53

◻ Flowchart is a tool developed in the computer industry, for

showing the steps involved in a process

◻ A flowchart is a diagram made up of boxes, diamonds and

other shapes, connected by arrows - each shape represents a
step in the process, and the arrows show the order in which they
occur

◻ Flowcharting Symbols:
■ There are 6 basic symbols commonly used in flowcharting of assembly
language programs: Terminal, Process, input/output, Decision, Connector
and Predefined Process
54
Flowchart
◻ Pictorial representation of an algorithm
◻ Steps of an algorithm are shown in different
shapes and logical flow is indicated by
arrows
◻ Boxes represent different operations
◻ Arrows shows sequence of operations
◻ Helps to understand logic of program
 Flowchart Symbols
55
 Flowchart Examples
56

Add two numbers and display result

START

Read A and B

C=A+B

Display C

STOP
 Flowchart Examples
57

Find the largest of given two numbers

START

Read A and B

NO
Is
A>B

YES

Display A Display B

STOP
 Draw flowchart to find the largest among three different
numbers entered by user.
58
 Advantages and Limitations
◻ Advantages:
59

🞑 Better Communication
🞑 Proper Program Documentation
🞑 Effective Coding
🞑 Systematic Debugging
🞑 Systematic Testing
◻ Limitations:
🞑 Time consuming
🞑 Difficult to modify
🞑 No update
🞑 No standards
 Pseudocodes
60

◻ “Pseudo” – imitation or false

◻ “Code” – instructions written in a programming
language
◻ Combination of English and Programming Language
◻ Focuses on developing the logic of the program
without worrying about the syntax
 Pseudo Code
61

◻ Pseudo code is one of the tools that can be used to write a preliminary
plan that can be developed into a computer program

◻ Pseudo code is a generic way of describing an algorithm without use of

any specific programming language syntax

◻ It is, as the name suggests, pseudo code i.e. it cannot be executed on a

real computer, but it models and resembles real programming code, and is
written at roughly the same level of detail

◻ Computer science textbooks often use pseudo code in their examples so

that all programmers can understand them, even if they do not all know
the same programming languages
 Example
62

Accept two numbers :-

if first number > second number

display “First number is greater”
else
display “ second number is greater”
 Advantages and Limitations
63

◻ Advantages
🞑 Focuses on logic of program without worrying about syntax
🞑 Language independent; can be translated to any computer
language code
🞑 Easier to develop program from pseudocode than flowchart
🞑 More concise, readable, and easier to modify
◻ Limitations
🞑 No visual representation of program logic
🞑 No standards
🞑 Cannot be compiled and executed hence correctness cannot
be verified
Example:
Algorithm, Flowchart and Pseudo Code
64

◻ Determine a student’s final grade indicating whether he/she is passing

or failing. The final grade is calculated as the average of four marks.
Algorithm:
Step 1: Start
Step 2: Input a set of four marks
Step 3: Calculate the grade by adding and dividing by 4
Step 4: if grade is below 50
Print “FAIL”
else
Print “PASS”
Step 5: Stop

Pseudo code:

Read M1,M2,M3,M4
GRADE ← (M1+M2+M3+M4)/4
if (GRADE < 50) then
Print “FAIL”
else
Print “PASS”
endif
 Case Study
Algorithm and Flowchart to calculate slope of a line
65

Algorithm:

Step 1: Start

Step 2: Input x and y coordinates of line as

x1, y1, x2, y2

Step 3: if x1 and x2 are equal then

Print “Line is Vertical“
Go to Step 6
else if y1 and y2 are equal then
Print “Line is Horizontal“
Go to Step 6
else Go to Step 4

Step 4: Find Slope as y2-y1/x2-x1

Step 5: Print Slope of Line

Step 6: Stop
 Case Study
Algorithm and Flowchart to find factorial of a number
66

Algorithm:

Step 1 : Start

Step 2 : Read n

Step 3 : Initialize counter variable i to 1 and fact to 1

Step 4 : if i < n go to step 5 otherwise goto step 7

Step 5 : increment counter variable i

Step 6 : calculate fact = fact * i and goto step 4

Step 7 : Print fact

Step 8 : Stop
 Case Study
Pseudo code to find factorial of a number
67

Pseudo code:

◻ Input a number n
◻ Initialize counter variable i =1 and factorial=1
◻ while i <= n
factorial = factorial * i
i=i+1
◻ Print factorial of a number
 Case Study
Algorithm and Flowchart to find Fibonacci Series
68

Algorithm:

Step 1: Start

Step 2: Declare variables N, N1, N2, N3, i

Step 3: Initialize variables N1 = 0, N2 = 1, i = 0

Step 4: Read value of N from user

Step 5: Display N1, N2

Step 6: Repeat following statements until i < N - 2

Compute N3 = N1 + N2
N1 = N2
N2 = N3
i =i+1
Display N3

Step 7: Stop
 Case Study
Flowchart for Snake and Ladder
69
 Case Study
Flowchart for Tic-Tac-Toe
70

Start

Print Game
Over and O
Wins

Print Game
Print Game Over and X
Draw Wins

Stop
 Top down Design Approach
71

◻ Top down Design Model

◻ In top-down model, an overview of the system is
formulated, without going into detail for any part of it.
◻ Each part of the system is then refined in more details.
◻ Each new part may then be refined again, defining it in
yet more details until the entire specification is detailed
enough to validate the model.
 Top down Design
72

◻ Top down Concept in Problem Solving

◻ If we look at a problem as a whole, it may seem impossible to
solve because it is so complex. Examples:
◻ writing a University System program
◻ writing a word processor
◻ Complex problems can be solved using top-down design,
also known as stepwise refinement, where
◻ We break the problem into parts
◻ Then break the parts into parts
◻ Soon, each of the parts will be easy to do
 Top down Design
73

Main Task

Subtask
Subtask 2 Subtask 3
1
 Top down Design
74

Quadratic Solver

getEquatio getSolutio
getDelta
n n
 Advantages of Top-down Design
75

◻ Breaking the problem into parts helps us to clarify

what needs to be done.
◻ At each step of refinement, the new parts become
less complicated and, therefore, easier to figure out.
◻ Parts of the solution may turn out to be reusable.
◻ Breaking the problem into parts allows more than
one person to work on the solution.
 Bottom-up Design Approach
76

◻ In bottom-up design individual parts of the system

are specified in details.
◻ The parts are then linked together to form larger
components, which are in turn linked until a
complete system is formed.
◻ Object-oriented languages such as C++ or JAVA
use bottom-up approach where each object is
identified first.
 Bottom up Design
77

Main Task

Subtask
Subtask 2 Subtask 3
1
 Software Development Life Cycle (SDLC)
78

◻ The software development life cycle (SDLC) is a framework

defining tasks performed at each step in the software
development process
◻ SDLC is a structure followed by a development team within
the software organization
◻ It consists of a detailed plan describing how to develop,
maintain and replace specific software
◻ The life cycle defines a methodology for improving the
quality of software and the overall development process
 Software Development Life Cycle (SDLC)
79
 Text Books/Reference Books:
80

1. Pradeep Sinha, Priti Sinha, "Computer Fundamentals",

Eight edition, bpb publication.
2. Ramon Mata-Toledo, Pauline K. Cushman,
"Introduction to Computer Science", Schaum's Outline
series.