- Program preparation is stretched to a number of levels
- In place of writing long list of statements, the statements are separated into different modules at various levels.
- The stretching is most general to most specific.
- Program is structured as hierarchy of various tasks.
- As the techniques moves from top to bottom, it is a type of specialization.
- Main module can be designed well before without requiring details of complete design.
- Testing can be done after inserting down level modules one-by-one.
- Parallel development is possible because of top and down level modules design.
Saturday, November 8, 2014
Rules for making Flowchart
"What are the rules for making the flowchart?"
Rule 1: The flowchart should contain one start and one stop box (terminator).
Rule 2: The symbols of the flowchart are always labeled with simple codes.
Rule 3: The codes used in the flowchart should not give more than one meaning.
Rule 4: The control flows are always represented by directed arrows.
Rule 5: The control flow lines touch the boundary of any box either while leaving from or while entering into the box.
Rule 6: The control flow lines should not cross each other.
Rule 7: The flow line moves in vertical direction either from top to bottom or from bottom to top.
Rule 8: The flow line moves in horizontal direction either from left to right or from right to left.
Rule 9: Only one flow line comes out from all the boxes or symbols excepts decision box.
Rule 10: Two lines can flow from the decision box if single condition is checked. It means a single condition results in one of the two values TRUE or FALSE
Rule 1: The flowchart should contain one start and one stop box (terminator).
Rule 2: The symbols of the flowchart are always labeled with simple codes.
Rule 3: The codes used in the flowchart should not give more than one meaning.
Rule 4: The control flows are always represented by directed arrows.
Rule 5: The control flow lines touch the boundary of any box either while leaving from or while entering into the box.
Rule 6: The control flow lines should not cross each other.
Rule 7: The flow line moves in vertical direction either from top to bottom or from bottom to top.
Rule 8: The flow line moves in horizontal direction either from left to right or from right to left.
Rule 9: Only one flow line comes out from all the boxes or symbols excepts decision box.
Rule 10: Two lines can flow from the decision box if single condition is checked. It means a single condition results in one of the two values TRUE or FALSE
Design an algorithm to search a number using binary search technique
Binary Search algorithm is applied where we want to search number in sorted numbers. In this algorithm, first to find mid position of the list and divide the list into two parts. If number is equal to mid then position find easily , this is the best case of binary search.
Problem: Design an algorithm to search a number using binary search technique.
Input : A list (array) of numbers in ascending order, number of elements in the list and key to search.
Output: Returns 1 if the key is found otherwise returns 0
BIN_SEARCH(LIST, N, KEY)
[LIST is an array of numbers in ascending order]
[N is the size of the array and KEY is the number to search]
L <-- 0; H<-- N-1; [Assuming that array index start from 0]
M <-- INT ( (L+H) /2 ) [Get the quotient or integer part after division]
Repeat While (L <= H)
If(Key == LIST[M]) then:
Return 1 [Key found]
Else:
If(Key < LIST[M] ) then:
H <-- M-1 [Move to the left half of the list]
Else:
H <-- M+1 [Move to the right half of the list]
[End of If]
[End of If]
[End of While]
Return 0 [Key not found]
Exit.
Problem: Design an algorithm to search a number using binary search technique.
Input : A list (array) of numbers in ascending order, number of elements in the list and key to search.
Output: Returns 1 if the key is found otherwise returns 0
BIN_SEARCH(LIST, N, KEY)
[LIST is an array of numbers in ascending order]
[N is the size of the array and KEY is the number to search]
L <-- 0; H<-- N-1; [Assuming that array index start from 0]
M <-- INT ( (L+H) /2 ) [Get the quotient or integer part after division]
Repeat While (L <= H)
If(Key == LIST[M]) then:
Return 1 [Key found]
Else:
If(Key < LIST[M] ) then:
H <-- M-1 [Move to the left half of the list]
Else:
H <-- M+1 [Move to the right half of the list]
[End of If]
[End of If]
[End of While]
Return 0 [Key not found]
Exit.
Friday, November 7, 2014
Design an algorithm to search a number using linear search technique
Problem: Design an algorithm to search a number using linear search technique.
Input : A list (array) of numbers, number of elements in the list and key to search.
Output : Returns 1 if the key is found otherwise returns 0.
LSEARCH(LIST, N, KEY)
[LIST is an array of numbers, N is the size of the array and key is the number to search]
Repeat For I=0, 1, 2, 3......N-1 [Assuming that array index starts from 0]
If(Key == LIST[I]) then:
Returns 1
[End of If]
Returns 0
Exit.
Input : A list (array) of numbers, number of elements in the list and key to search.
Output : Returns 1 if the key is found otherwise returns 0.
LSEARCH(LIST, N, KEY)
[LIST is an array of numbers, N is the size of the array and key is the number to search]
Repeat For I=0, 1, 2, 3......N-1 [Assuming that array index starts from 0]
If(Key == LIST[I]) then:
Returns 1
[End of If]
Returns 0
Exit.
Design an algorithm to find sum of 'N' natural numbers
Problem: Design an algorithm to find sum of 'N' natural numbers between N1 and N2.
Input : Two numbers N1 and N2.
Output: Sum of N natural numbers.
SUM(N1, N2)
[N1 and N2 are two different natural numbers]
If N1> N2 then:
MAX <-- N1
MIN <-- N2
ELSE:
MAX<-- N2
MIN <-- N1
[End of If]
MIN <-- MIN-1 [ to include MIN in sum]
SUM 1 <-- (MIN * (MIN+1))/2
SUM 2 <-- (MAX * (MAX+1))/2
Return SUM2- SUM1
Exit.
In the above algorithm to find the sum of N natural numbers, the formula N(N+1)/2 is used. Instead of a formula, repetitive statements can also be used that run from MIN to MAX with step 1. The algorithm can be re-written as:
Input : Two numbers N1 and N2.
Output: Sum of N natural numbers.
SUM(N1, N2)
[N1 and N2 are two different natural numbers]
If N1> N2 then:
MAX <-- N1
MIN <-- N2
ELSE:
MAX<-- N2
MIN <-- N1
[End of If]
SUM <-- 0
Repeat For I= MIN, MIN+1, MIN+2..........MAX
SUM <-- SUM+1
[End of For]
Return SUM
Exit.
Tracing:
Suppose that the above algorithm SUM1 is called with two numbers 23 and 11.
In the If statements 23>11 condition is TRUE, therefore MAX becomes 23 and MIN becomes 11.
Now the loop repeats for 11, 12, 13, 14 up to 23
(I values).
Every time when the loop is repeated I is added to SUM.
So, finally the value of SUM is returned from the algorithm.
Input : Two numbers N1 and N2.
Output: Sum of N natural numbers.
SUM(N1, N2)
[N1 and N2 are two different natural numbers]
If N1> N2 then:
MAX <-- N1
MIN <-- N2
ELSE:
MAX<-- N2
MIN <-- N1
[End of If]
MIN <-- MIN-1 [ to include MIN in sum]
SUM 1 <-- (MIN * (MIN+1))/2
SUM 2 <-- (MAX * (MAX+1))/2
Return SUM2- SUM1
Exit.
In the above algorithm to find the sum of N natural numbers, the formula N(N+1)/2 is used. Instead of a formula, repetitive statements can also be used that run from MIN to MAX with step 1. The algorithm can be re-written as:
II algorithm
Problem: Design an algorithm to find sum of 'N' natural numbers between N1 and N2.Input : Two numbers N1 and N2.
Output: Sum of N natural numbers.
SUM(N1, N2)
[N1 and N2 are two different natural numbers]
If N1> N2 then:
MAX <-- N1
MIN <-- N2
ELSE:
MAX<-- N2
MIN <-- N1
[End of If]
SUM <-- 0
Repeat For I= MIN, MIN+1, MIN+2..........MAX
SUM <-- SUM+1
[End of For]
Return SUM
Exit.
Tracing:
Suppose that the above algorithm SUM1 is called with two numbers 23 and 11.
In the If statements 23>11 condition is TRUE, therefore MAX becomes 23 and MIN becomes 11.
Now the loop repeats for 11, 12, 13, 14 up to 23
(I values).
Every time when the loop is repeated I is added to SUM.
So, finally the value of SUM is returned from the algorithm.
Design an algorithm to find the GCD and LCM of two positive numbers
Problem : Design an algorithm to find the GCD (Greatest Common Divisor) of two positive numbers and use the same to find LCM of two positive numbers.
Input: Two Numbers
Output : Least Common Multiple of two numbers.
GCD(NUM1, NUM2)
Rem <-- NUM1 % NUM2 [% Modulus Operator]
Repeat While Rem <> 0
NUM1 <-- NUM2
NUM2 <-- Rem
Rem <-- NUM1 % NUM2
[End of While]
Return NUM2
Exit.
LCM(NUM1, NUM2)
Return (NUM1 * NUM2) / GCD( NUM1, NUM2)
Exit.
NOTE : Here in this example algorithm, finding LCM in the main problem that can be divided into sub-problem like finding the GCD first and using the same to solve the main problem. So, GCD algorithm is written first and than the other algorithm that can be divided into small problems and algorithm can be written to solve such small problems.
Rem <-- 12 % 16 i.e. Rem= 12
Rem is not equal to zero. So, NUM1=16 and NUM2 =12
Rem<-- 16%12 i.e. Rem=4
Rem is not equal to Zero. So, NUM1 =12 and NUM2 =4
Rem <-- 12 % 4 i.e. Rem=0
Rem is equal to Zero.
So, GCD algorithm returns NUM2 that is 4.
When the algorithm LCM gets the result from GCD algorithm its find the expression value
(NUM1 * NUM2) / GCD (NUM1, NUM2). i.e. (12 * 16)/4
It is equal to 48. 48 is the LCM of 12 and 16
Input: Two Numbers
Output : Least Common Multiple of two numbers.
GCD(NUM1, NUM2)
Rem <-- NUM1 % NUM2 [% Modulus Operator]
Repeat While Rem <> 0
NUM1 <-- NUM2
NUM2 <-- Rem
Rem <-- NUM1 % NUM2
[End of While]
Return NUM2
Exit.
LCM(NUM1, NUM2)
Return (NUM1 * NUM2) / GCD( NUM1, NUM2)
Exit.
NOTE : Here in this example algorithm, finding LCM in the main problem that can be divided into sub-problem like finding the GCD first and using the same to solve the main problem. So, GCD algorithm is written first and than the other algorithm that can be divided into small problems and algorithm can be written to solve such small problems.
Tracing
Suppose that the LCM algorithm is called using 12 and 16. The algorithm calls GCD with 12 and 16.Rem <-- 12 % 16 i.e. Rem= 12
Rem is not equal to zero. So, NUM1=16 and NUM2 =12
Rem<-- 16%12 i.e. Rem=4
Rem is not equal to Zero. So, NUM1 =12 and NUM2 =4
Rem <-- 12 % 4 i.e. Rem=0
Rem is equal to Zero.
So, GCD algorithm returns NUM2 that is 4.
When the algorithm LCM gets the result from GCD algorithm its find the expression value
(NUM1 * NUM2) / GCD (NUM1, NUM2). i.e. (12 * 16)/4
It is equal to 48. 48 is the LCM of 12 and 16
Design an algorithm to find minimum of two distinct numbers
Problem: Design an algorithm to find minimum of two distinct numbers and using the same, find minimum of three distinct numbers.
Input : For sub-algorithm 2 numbers and for main algorithm 3 numbers.
Output: Minimum number
MIN_OF_2(NUM1, NUM2) [Sub-Algorithm]
[NUM1 and NUM2 are two numbers]
If NUM1<NUM2 Then:
Return NUM1
Else:
Return NUM2
[End of If]
Exit
MIN_OF_3(NUM1,NUM2,NUM3) [Main Algorithm]
[NUM1, NUM2, and NUM3 are distinct numbers]
Returns MIN_OF_2(MIN_OF_2(NUM1, NUM2), NUM3)
Exit
Input : For sub-algorithm 2 numbers and for main algorithm 3 numbers.
Output: Minimum number
MIN_OF_2(NUM1, NUM2) [Sub-Algorithm]
[NUM1 and NUM2 are two numbers]
If NUM1<NUM2 Then:
Return NUM1
Else:
Return NUM2
[End of If]
Exit
MIN_OF_3(NUM1,NUM2,NUM3) [Main Algorithm]
[NUM1, NUM2, and NUM3 are distinct numbers]
Returns MIN_OF_2(MIN_OF_2(NUM1, NUM2), NUM3)
Exit