1 of 11

PROBLEM SOLVING TECHNIQUES

By

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 11

  • Problem
  • Given a set of n students’ examination marks (in the range 0 to 100) make a count of the number of students that obtained each possible mark.
  • Algorithm development
  • Here, we are required to do the distribution of a set of marks.
  • This problem is an example of frequency counting problem.
  • First Approach (Inefficient)
  • Take 101 variables C0, C1, C2, ….., C100 each corresponding to a particular mark.

Dept of CSE

2025-26

Array Counting or Histogramming

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 11

while less than n marks have been examined do

​

​

​

​

​

  • The difficulty with this approach is that we need to make 101 tests (only one of which is successful) just to update the count for one particular mark.
  • Furthermore our program is very long.

Dept of CSE, PVPSIT

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 11

  • To begin the search for a better solution let us solve the problem without computer.
  • An approach we could take is illustrated by the following diagram:

​

​

​

​

  • Take a piece of graph paper or divide plain paper up into slots each of which can be identified with a particular mark value.
  • The next step is to examine each mark, and, depending on its value, we place a star in the corresponding mark’s slot.

​

Dept of CSE, PVPSIT

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 11

  • One-step Approach/indexing by value (Efficient)
  • We need to recognize that the array is more useful in the solution to our problem.
  • Set up an array with 101 locations, each location corresponding to a particular mark value.
  • For example,

Dept of CSE, PVPSIT

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 11

  • If 15 students obtained the mark 57, then we will have the number 15 in location 57when all marks have been examined.
  • When mark 57 is read add one to the previous count in the location 57 and initially location 57 must be set up with zero.

​

  • For the mark 57

​

  • For the mark m

​

  • Prior to beginning the counting process the array must have all its elements set to zero.

​

​

Dept of CSE, PVPSIT

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 11

  • Pseudo-code:
  • a: array[0..100] set zero in all the 101 locations
  • n: number of students’ marks
  • begin

for i:= 1 to n do

begin

read m

a[m] := a[m]+1

end

for i:= 0 to 100 do

begin

write a[i]

end

    • end

​

Dept of CSE, PVPSIT

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 11

  1. Prompt and read in n the number of marks to be processed.
  2. Initialize all locations of the counting array a[0..100] to zero.
  3. While there are still marks to be processed, repeatedly do

(a) read next mark m.

(b) add one to the count in location m in the counting array.

4. Write out the marks frequency count distribution.

Dept of CSE, PVPSIT

2025 - 26

Algorithm description

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 11

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

Dept of CSE, PVPSIT

2025 - 26

Algorithm:

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 11

  1. Essentially n steps are required to generate the frequency histogram for a set of n marks.
  2. After i marks are examined the jth element in the a array will contain an integer representing the number of times j encountered n the first i marks.
  3. The idea of indexing by value is important in many algorithms because of its efficiency.
  4. Applications
  5. Statistical analysis

Dept of CSE, PVPSIT

2025 - 26

Notes on design

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 11

4.2.1 modify the algorithm above so that a histogram is obtained only for each ten percentile range (e.g. 0->10%, 11->20%, …) rather than for each individual mark.

Dept of CSE, PVPSIT

2025 - 26

Supplementary problems

PVPSIT (Autonomous)

Problem Solving Techniques