1 of 11

PROBLEM SOLVING TECHNIQUES

By

​

B. Vinay Kumar

Assistant Professor

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 11

  • Problem
  • Find the maximum number in a set of n numbers.
  • Algorithm development
  • Maximum Number: The maximum is that number which is greater than or equal to all other numbers in the set.
  • The maximum may not be unique.
  • The maximum is only defined for set of one or more elements.
  • For example:

B. Vinay Kumar

Thursday, April 3, 2025

FINDING THE MAXIMUM NUMBER IN A SET

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 11

  • After studying the above example, all numbers need to be examined to establish the maximum.
  • A second conclusion is that comparison of the relative magnitude of numbers must be made.
  • A Basic Approach (In the Absence of a Computer)
  • When we are given a short list of numbers and asked to find the maximum we simply scan the list and supply the answer.
  • For the above example quickly be able to respond that 21 is the maximum.
  • The mechanism we “seem” to apply is to scan the numbers and select one which we “feel” is bigger than the rest.
  • We then rescan the numbers to check the validity of our assumption.

B. Vinay Kumar

Thursday, April 3, 2025

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 11

  • If we encounter a large number we rescan the set comparing the numbers with our new candidate.
  • The process is repeated until we are satisfied with our choice.
  • For the short lists this whole process is so fast.
  • For longer lists (thousand or more numbers) it is not nearly so easy to apply this strategy.
  • So we need to systematize our approach.
  • (Systematic Approach)
  • The simplest and most systematic way to examine every item in a list is to start at the beginning of the list and work through, number by number, until the end of the list is reached.
  • At each step a comparison is needed.

B. Vinay Kumar

Thursday, April 3, 2025

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 11

  • Imagine for a moment that we are given the task of finding the maximum among one thousand numbers by having them flashed up on a screen one at a time.
  • When the first number appears on the screen we have no way of knowing whether or not it is the maximum.
  • Better we can write it down as our temporary candidate for the maximum.
  • When the second number appears on the screen we must have an idea what to do?
  • Three situations are possible:
  • The second number can be less than our temporary candidate for the maximum;
  • The second number can be equal to our temporary candidate for the maximum;
  • The second number can be greater than our temporary candidate for the maximum;

B. Vinay Kumar

Thursday, April 3, 2025

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 11

  • If situation (1) or (2) apply our temporary candidate for the maximum is still valid and so there is no need to change it.
  • Then move on and compare the third number with the new temporary maximum and so on
  • However, if the second number is greater than our temporary maximum, we must cross out our original temporary maximum and write down the second number as the new temporary maximum.
  • And we then move on and compare the third number with the new temporary maximum and so on.
  • This strategy can form the basis of our computer algorithm.

1. while all array elements not examined do

(a) if the current array element > temporary maximum then update the temporary maximum.

B. Vinay Kumar

Thursday, April 3, 2025

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 11

  • When we start solving the problem, there is no temporary maximum at the time when the first element is considered.
  • So, when the first number appeared we immediately, without comparison, consider it as the temporary maximum.
  • max := a[1]
  • Pseudo-code:
  • a: Initialize array a[1..n]
  • begin

i:=1

max:= a[i]

for i := 2 to n do

if a[i] > max then max := a[i]

amax := max

    • end

B. Vinay Kumar

Thursday, April 3, 2025

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 11

  1. Establish an array a[1..n] of n elements n>=1.
  2. Set temporary maximum max to first array element.
  3. While less than n array elements have been considered do

(a) if next element greater than current max then assign it to max.

4. Return maximum max for the array on n elements.

B. Vinay Kumar

Thursday, April 3, 2025

Algorithm description

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 11

  • Step 0: Start
  • Step 1: Read N
  • Step 2: I = 1
  • Step 3: Repeat Step 4, 5 and 6 till I<=N
  • Step 4: Read m
  • Step 5: A[I] := m
  • Step 6: I:= I+1
  • Step 7: Reset I (I := 2)
  • Step 8: max := A[1]
  • Step 9: Repeat Step 10 and 11 till I<=N

B. Vinay Kumar

Thursday, April 3, 2025

Algorithm:

  • Step 10: If A[I] > max then max:=A[I]
  • Step 11: I:= I+1
  • Step 12: Display max as result
  • Step 13: Stop

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 11

  • Notes on design
  • The number of comparisons needed to find the maximum in an array of n elements is n-1.
  • Sometimes algorithms to find maximum are initialized by setting max=0.
  • Applications
  • Plotting, scaling, sorting.

B. Vinay Kumar

Thursday, April 3, 2025

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 11

  • 4.3.1 design an algorithm to find the minimum in an array.

B. Vinay Kumar

Thursday, April 3, 2025

Supplementary problems (4.3.1)

PVPSIT (Autonomous)

Problem Solving Techniques