Basic Problems (Level 2)

[ Home Page ]  [ Back ]  [ Content of Contributions ]  [ Movement: Green Leaf World ]

---------------------------------------------------------------------

Objective:

In this article, the objective is to realize the following points with the help of very simple problems

1. Requirement of proper assumption,
2. Iterative Algorithms (Loop Structure) 
3. Observation of the behavior of the problem (Analysis) & selection of way of attacking to the problem.

Problem 03

Problem Statement: Find the a given number is even or odd.
Problem Analysis & Specifications:

1. The number must be integer, let, iNum as input.
2. The result may be assume to be
1. 1, when iNum is Even and
2. 0, when iNum is Odd
3. So, the result is also integer, Let, iIsEven is the output.

Algorithm_03.01: Check_Even_Odd(iNum, iIsEven)
Steps:
1. iIsEven:= 1
2. IF ( (iNum%2) = 1 ) Then,
     iIsEven:= 0
   End of IF
3. Return

Now, make a small change in the specification 2, as,
The result may be assume to be
  0, when iNum is Even and
  1, when iNum is Odd.

Observe the following algorithm

Algorithm_03.02: Check_Even_Odd(iNum, iIsEven)
Steps:
1. iIsEven:= ( iNum % 2 )

2. Return

Now tell me,

Q1) Which algorithm is more efficient and why?

Q2) Do you think that, the change in the algorithm_03.02 is really effective or worthless?

Q3) Do you think, assumption matters in the way of writing a good algorithm?

So, try to remember,a

very small change in an assumption,

can solve a very big problem....

a very small change in an assumption,

can create a very big problem....

Now, we are going to observe such problem domain, where number of computations is not constant. Number of computations required will depend on the input value given.

 

Problem 04

Problem Statement: Find the highest digit in a given number.

Problem Analysis & Specifications:

1. Number of comparisons required by this problem is defined by how much digits present in the number. So, multiple time computation of same code is required here. When this situation comes in the seen, we have two models to handle this kind of problems, 
1. Iterative method or 
2. Recursive method (will be discussed later) 
2. The given number must be integer, let, iNum as input. 
3. Lowest digit is 0 and highest digit is 9. So, this is the limited boundary of the result, which is an integer. Let, iMaxDigit is the output.

Algorithm_04.01: Check_Max_Digit(iNum, iMaxDigit)

Steps:

1. iMaxDigit:= 0 [ Initialization ]

2. Repeat the following sub operations while iNum > 0,

   2.1 New_Digit:= (iNum%10) [ Extracting one digit]

   2.2 IF ( New_Digit > iMaxDigit ) Then [ Is it greater ]

       2.2.1 iMaxDigit:= New_Digit [ Update ]

       End of IF

   2.3 iNum:= (iNum/10) [ Update ]

   End of the Step 2 Loop

3. Return

Now, the same algorithm, writing again, without any changes in the steps. Only, notation has been changed a little.

Algorithm_04.02: Check_Max_Digit(iNum, iMaxDigit)

Steps:

1. iMaxDigit:= 0                         [ Initialization ]

2. WHILE ( iNum > 0 )

     New_Digit:= (iNum%10)               [ Extracting one digit]

     IF ( New_Digit > iMaxDigit ) Then   [ Is it greater ]

       iMaxDigit:= New_Digit             [ Update ]

     End of IF

     iNum:= (iNum/10)                    [ Update ]

   End of WHILE

3. Return

Now, tell me

Q4) Among Algorithm_04.01 & Algorithm_04.02, which structure you would like to see in the future articles? Also state why you like this structure?

Ok, now consider iNum= 12345697. So, how the digits will be extracted from iNum? 7, 9, 6, 5, 4, 3, 2, 1. So, the changes in the iMaxDigit will be 0, 7, 9, the value 9 will remain unchanged after second iteration. So, what is the requirement of further iterations when solution is achieved? Remember, if solution found at any time, no need to perform further operations, it is non-sense to operate without requirement. So, the third version of the simple algorithm is given below:

Algorithm_04.03: Check_Max_Digit(iNum, iMaxDigit)

Steps:

1. iMaxDigit:= 0                              [ Initialization ]

2. WHILE ( iNum > 0 )

     New_Digit:= (iNum%10)               [ Extracting one digit]

     IF ( New_Digit = 9 ) Then                     [ Is Result ]

       iMaxDigit:= New_Digit                          [ Update ]

       Return
     ELSE IF ( New_Digit > iMaxDigit ) Then   

       iMaxDigit:= New_Digit                   [ Is it greater ]

     End of IF

     iNum:= (iNum/10)                                 [ Update ]

   End of WHILE

3. Return

Now, tell me
Q5) Which algorithm you will prefer to write your program?

Next, we will observe behavior of two very similar problems to select proper of way to attack the problem.

1. Finding all factors of a number and
2. Finding a number is Prime or not

Both, are based on the factors. 

Factor: A factor can simply defined as, an integer k is said to be a factor of N, if and only if (N/K) is an integer.

Prime: An integer N is said to be a prime number if and only if there are only factors {1, N}.

Observe:

Factors(100) = {1, 2, 4, 5, 10, 20, 25, 50, 100}

             = {1, 2, 4, 5, 10} U {10, 20, 25, 50, 100}

See both the set having same number of elements ! Is is surprising? No, it is the fact, factors always comes in pair. unable to understand why this two set. Ok, change the representation a little bit.

Factors(100) = {1, 2, 4, 5, 10} U {100, 50, 25, 20, 10}
                    Set A                Set B

Still not getting any idea, Ok, look another representation

A      B      N
1  X  100  = 100

2  X  50   = 100

4  X  25   = 100

5  X  20   = 100

10 X  10   = 100

Now, think what can be the upper limit required to perform,

1. Find all Factors on N, for any N>=2.
2. Check a given number N is prime or not, for any N>=2.

No, this is not a question to be answered now. Think it as a puzzle. Solve it.

In, our Computer Science & Engineering, we need to study behavior of the problem, i.e. the correlation among the values as well as distribution of the values. This defines the pattern of the problem.

As in medical science, it is believed that, that main reason for any decease/ any property is based on the sequence of DNA & RNA. Similarly, in our domain, it is also believed that, the sequence, i.e, correlation & distribution, defines a particular problem. So, if you can understand the mathematical properties of a problem, it will give you the solution to that problem.

Simply we says in our daily life, that,  

"know your enemy well to defeat them"

Do you think this statement is non-sense? I don't think.

But, I have a question.
What is way to know your enemy more?
In my opinion, probably, the best way is to spend more time with your enemy.

If you are ignoring your enemy, it is the fear, that, you may loose. It means, you surrendering without fighting. It means, neither you have the attitude to fight, nor, you believe yourself.

Only way to learn any subject- spend more time with it, which you feel hard to understand. Practice that more, where you are failing often.

There are so many problems, among them, I am selecting a very few interesting problems to give idea to you. you need to do lot of algorithms, after confidence will be visible.

If you didn't started writing programs related to algorithms we are discussing, start it. After a certain time, you will not be able to understand, if some programming facts are not get clarified. Time & Space(memory) are two important issues related with algorithm.

In the next article, some more complex patterns(of problem) will be discussed.