Problem Solving and Algorithms Development
Dr. Odelu Vanga
Department of Computer Science and Information Systems
Birla Institute of Technology and Science Pilani
Hyderabad Campus
[email protected] January 22, 2019
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 1 / 41
Today’s Objectives
Understand the concept of an algorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 2 / 41
Today’s Objectives
Understand the concept of an algorithm
Three constructs for developing algorithms:
(1). sequence, (2). decision, and (3). repetition
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 2 / 41
Today’s Objectives
Understand the concept of an algorithm
Three constructs for developing algorithms:
(1). sequence, (2). decision, and (3). repetition
Understand the concept of
modularity and subalgorithms
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 2 / 41
Problem Solving
Can you think of a day in your life which goes without problem solving?
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 3 / 41
Problem Solving
Can you think of a day in your life which goes without problem solving?
If someone asks you, what is time now?
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 3 / 41
Problem Solving
Can you think of a day in your life which goes without problem solving?
If someone asks you, what is time now?
seeing time in your watch and telling him
a kind of problem solving
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 3 / 41
Problem Solving
Can you think of a day in your life which goes without problem solving?
If someone asks you, what is time now?
seeing time in your watch and telling him
a kind of problem solving
A typical programming task can be divided into two phases
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 3 / 41
Problem Solving
Can you think of a day in your life which goes without problem solving?
If someone asks you, what is time now?
seeing time in your watch and telling him
a kind of problem solving
A typical programming task can be divided into two phases
1 Problem solving phase: The sequence of statements which will
produce the desired output for the given input.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 3 / 41
Problem Solving
Can you think of a day in your life which goes without problem solving?
If someone asks you, what is time now?
seeing time in your watch and telling him
a kind of problem solving
A typical programming task can be divided into two phases
1 Problem solving phase: The sequence of statements which will
produce the desired output for the given input.
2 Implementation phase: Implement the program in some
programming language.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 3 / 41
Algorithm Development
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 4 / 41
Properties of Algorithm
1) Finiteness: An algorithm must always terminate after a
finite number of steps.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 5 / 41
Properties of Algorithm
1) Finiteness: An algorithm must always terminate after a
finite number of steps.
2) Definiteness: Each step of an algorithm must be precisely
defined.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 5 / 41
Properties of Algorithm
1) Finiteness: An algorithm must always terminate after a
finite number of steps.
2) Definiteness: Each step of an algorithm must be precisely
defined.
3) Input: The input is the data to be transformed during the
computation to produce the output.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 5 / 41
Properties of Algorithm
1) Finiteness: An algorithm must always terminate after a
finite number of steps.
2) Definiteness: Each step of an algorithm must be precisely
defined.
3) Input: The input is the data to be transformed during the
computation to produce the output.
4) Output: Always expects result in terms of output from an
algorithm.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 5 / 41
Properties of Algorithm
1) Finiteness: An algorithm must always terminate after a
finite number of steps.
2) Definiteness: Each step of an algorithm must be precisely
defined.
3) Input: The input is the data to be transformed during the
computation to produce the output.
4) Output: Always expects result in terms of output from an
algorithm.
5) Effectiveness: Algorithms to be developed/written using
basic operations.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 5 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Expected output: Positive number.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Expected output: Positive number.
Algorithm:
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Expected output: Positive number.
Algorithm:
1: Start
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Expected output: Positive number.
Algorithm:
1: Start
2: Read n1
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Expected output: Positive number.
Algorithm:
1: Start
2: Read n1
3: Read n2
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Expected output: Positive number.
Algorithm:
1: Start
2: Read n1
3: Read n2
4: Sum ← n1 + n2
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Expected output: Positive number.
Algorithm:
1: Start
2: Read n1
3: Read n2
4: Sum ← n1 + n2
5: Print Sum
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Algorithm Development
1. Define the essential input to the algorithm.
2. Specify desired output after algorithm is executed.
3. Statements in the algorithm should define clearly.
Problem: Write an algorithm to find sum of two positive numbers
Inputs to the algorithm: two positive numbers.
Expected output: Positive number.
Algorithm:
1: Start
2: Read n1
3: Read n2
4: Sum ← n1 + n2
5: Print Sum
6: Stop
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 6 / 41
Finding the largest integer among five integers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 7 / 41
Finding the largest integer among five integers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 7 / 41
Finding the largest integer among five integers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 8 / 41
Finding the largest integer among five integers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 9 / 41
Finding the largest integer among five integers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 10 / 41
Finding the largest integer among five integers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 11 / 41
Finding the largest integer among five integers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 12 / 41
Defining actions in FindLargest algorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 13 / 41
Defining actions in FindLargest algorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 14 / 41
Defining actions in FindLargest algorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 15 / 41
Defining actions in FindLargest algorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 16 / 41
Defining actions in FindLargest algorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 17 / 41
Defining actions in FindLargest algorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 18 / 41
FindLargest refined
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 19 / 41
Generalization of FindLargest
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 20 / 41
Three Constructs
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 21 / 41
Three Constructs
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 22 / 41
Three Constructs
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 23 / 41
Algorithm FindLargest of N numbers
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
2: Set Counter to 0
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
2: Set Counter to 0
3: while (Counter less than N)
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
2: Set Counter to 0
3: while (Counter less than N)
3.1: if (the integer is greater than Largest)
then
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
2: Set Counter to 0
3: while (Counter less than N)
3.1: if (the integer is greater than Largest)
then
3.1.1: Set Largest to the value of the integer
End if
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
2: Set Counter to 0
3: while (Counter less than N)
3.1: if (the integer is greater than Largest)
then
3.1.1: Set Largest to the value of the integer
End if
3.2: Increment Counter
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
2: Set Counter to 0
3: while (Counter less than N)
3.1: if (the integer is greater than Largest)
then
3.1.1: Set Largest to the value of the integer
End if
3.2: Increment Counter
End while
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
2: Set Counter to 0
3: while (Counter less than N)
3.1: if (the integer is greater than Largest)
then
3.1.1: Set Largest to the value of the integer
End if
3.2: Increment Counter
End while
4: Return Largest
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Algorithm FindLargest of N numbers
Input: N positive integers
Output: Largest number
Start
1: Set Largest to 0
2: Set Counter to 0
3: while (Counter less than N)
3.1: if (the integer is greater than Largest)
then
3.1.1: Set Largest to the value of the integer
End if
3.2: Increment Counter
End while
4: Return Largest
End
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 24 / 41
Concept of Subalgorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 25 / 41
Concept of Subalgorithm
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 26 / 41
Concept of Subalgorithm
Algorithm: FindLargest
Input: A list of positive integers
Start
1: Set Largest to 0
2: while (more integers)
2.1: FindLarger
End while
3: Return Largest
End
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 27 / 41
Concept of Subalgorithm
Subalgorithm: FindLarger
Algorithm: FindLargest Input: Largest and current
Input: A list of positive integers integer
Start Start
1: Set Largest to 0 1: if (the integer is greater than
2: while (more integers) Largest)
2.1: FindLarger then
End while 1.1: Set Largest to the value of
the integer
3: Return Largest
End if
End
End
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 27 / 41
Recursion
Iterative definition of factorial
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 28 / 41
Iterative factorial
Factorial
Input: A positive integer num
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 29 / 41
Iterative factorial
Factorial
Input: A positive integer num
Start
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 29 / 41
Iterative factorial
Factorial
Input: A positive integer num
Start
1: Set FactN to 1
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 29 / 41
Iterative factorial
Factorial
Input: A positive integer num
Start
1: Set FactN to 1
2: Set i to 1
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 29 / 41
Iterative factorial
Factorial
Input: A positive integer num
Start
1: Set FactN to 1
2: Set i to 1
3: while (i is less than or equal to num)
3.1: Set FactN to FactN × i
3.2: Increment i
End while
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 29 / 41
Iterative factorial
Factorial
Input: A positive integer num
Start
1: Set FactN to 1
2: Set i to 1
3: while (i is less than or equal to num)
3.1: Set FactN to FactN × i
3.2: Increment i
End while
4: Return FactN
End
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 29 / 41
Recursion
Iterative definition of factorial
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 30 / 41
Recursion
Iterative definition of factorial
Recursive definition of factorial
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 30 / 41
Recursive factorial
Factorial
Input: A positive integer num
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 31 / 41
Recursive factorial
Factorial
Input: A positive integer num
Start
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 31 / 41
Recursive factorial
Factorial
Input: A positive integer num
Start
1: if (num is equal to 0)
then
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 31 / 41
Recursive factorial
Factorial
Input: A positive integer num
Start
1: if (num is equal to 0)
then
1.1: return 1
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 31 / 41
Recursive factorial
Factorial
Input: A positive integer num
Start
1: if (num is equal to 0)
then
1.1: return 1
else
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 31 / 41
Recursive factorial
Factorial
Input: A positive integer num
Start
1: if (num is equal to 0)
then
1.1: return 1
else
1.2: return num × Factorial(num − 1)
End if
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 31 / 41
Recursive factorial
Factorial
Input: A positive integer num
Start
1: if (num is equal to 0)
then
1.1: return 1
else
1.2: return num × Factorial(num − 1)
End if
End
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 31 / 41
Recursion
Tracing recursive solution to factorial problem
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 32 / 41
Recursion
Tracing recursive solution to factorial problem
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 33 / 41
Recursion
Tracing recursive solution to factorial problem
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 34 / 41
Recursion
Tracing recursive solution to factorial problem
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 35 / 41
Recursion
Tracing recursive solution to factorial problem
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 36 / 41
Recursion
Tracing recursive solution to factorial problem
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 37 / 41
Recursion
Tracing recursive solution to factorial problem
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 38 / 41
Recursion
Tracing recursive solution to factorial problem
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 39 / 41
Prime Number Testing
Problem: Write an algorithm which will test whether a given integer
value is prime or not.
Could you write this ?
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 40 / 41
Prime Number Testing
Problem: Write an algorithm which will test whether a given integer
value is prime or not.
Could you write this ?
Start
1: M ← 2
2: input N
3: MAX ← SQRT (N)
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 40 / 41
Prime Number Testing
Problem: Write an algorithm which will test whether a given integer
value is prime or not.
Could you write this ?
Start
1: M←2
2: input N
3: MAX ← SQRT (N)
4: while M ≤ MAX do
4.1: If (M × (N/M) = N then
4.1.1: Return “number is not a prime”
4.2: M ← M + 1
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 40 / 41
Prime Number Testing
Problem: Write an algorithm which will test whether a given integer
value is prime or not.
Could you write this ?
Start
1: M←2
2: input N
3: MAX ← SQRT (N)
4: while M ≤ MAX do
4.1: If (M × (N/M) = N then
4.1.1: Return “number is not a prime”
4.2: M ← M + 1
5: Return “number is prime”
Stop.
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 40 / 41
Prime Number Testing
Problem: Write an algorithm which will test whether a given integer
value is prime or not.
Could you write this ?
Start
1: M←2
2: input N
3: MAX ← SQRT (N)
4: while M ≤ MAX do
4.1: If (M × (N/M) = N then
4.1.1: Return “number is not a prime”
4.2: M ← M + 1
5: Return “number is prime”
Stop.
Could you develop recursive function ?
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 40 / 41
.
Thank You
Dr. Odelu Vanga (BITS-Pilani Hyderabad) CS F111 January 22, 2019 41 / 41
