Best refernece to algorithms is the "Method Of Algorithm Description" Second Edition
http://www.boredofstudies.org/other/1995_SDD_N_Methods_of_Algorithm_Description_BOS.pdf
Its got all the goods u need to know.
Know ur Basic structures ==> sequence, selection, repetition.
Jus made a couple of notes & summaries on these structures hope they help.
Sequence
Sequence
process 1
Process n
Eg1:
BEGIN
add coffee
add sugar
add hot water(H20)
add milk
stir well
END
Binary Selection(2 possible paths/process)
Here there is only 1 process (add milk), the other possible path/process is do nothing(not add milk) which is quiet obvious so it is lefted out). NOTE that it does not use "ELSE".
IF condition
THEN
do process
ENDIF
Eg1:
IF you want milk
THEN
add milk
ENDIF
Here there are 2 process. Process 1 "add milk", the other possible path/process is "add cream".
The use of "ELSE" allows 1 of the 2 accepable paths/process to be done.
IF condition
THEN
do process 1
ELSE
do process 2
ENDIF
Eg2:
IF you want milk
THEN
add milk
ELSE
add cream
ENDELSEIF
Combining both Sequence & Selection
Eg3:
BEGIN
add coffee
add sugar
add hot water(H20)
IF you want milk
THEN
add milk
ELSE
add cream
ENDELSEIF
END
Multi-way Selection(Casewhere)
Multi-way slection allows for any number of possible choices & processes.
The process taken is determined by the selection of the choice.
CASEWHERE expression
Choice 1: process 1
Choice 2: process 2
Choice n: process n
OTHERWISE: default process
ENDCASE
Eg1:
CASEWHERE temperature
<16 : run two heating units
Between 16 to 20: run one heating units
Between 21 to 28: run one cooling units
OTHERWISE: run two cooling units
ENDCASEWHERE
Repetition(Loops)
Repetition allows a portion of an algorithm to be done any number of times
depending on the condition being met. In order to stop a loop, a termination
condition is used. This termination condition can be at the beginning or the
end of the loop(pre-test or post-test).
Pre-Test(Guarded Loop)
The word "Pre" implies b4. Think in terms of the condition. The condition is b4
the process(es).The body of the loop is executed repeatedly after, WHILE the temination condition holds true(Guarded Loop).
Here the condition has to be met b4 it gets into the loop.
Pre-Test repetitions uses WHILE and ENDWHILE.
WHILE condition is true
do process(es)
ENDWHILE
Eg1:
WHILE there are no barriers in the way //Condition
proceed to next room //Process
ENDWHILE
Post-Test(Unguarded Loop)
The word "Post" implies after. Think in terms of the condition. The condition is after
the process(es).The body of the loop is executed repeatedly b4 the temination condition,
UNTIL the temination condition holds true(Unguarded Loop). Here the process(es) are done b4
the condition is met. Post-Test repetitions uses REPEAT and UNTIL.
REPEAT do process
UNTIL condition is true
Eg2:
REPEAT kill all monsters //Process
UNTIL there are no monster remaining //Condition
Subprograms
Complete part programs that are used from within the main program section. Subprograms are
indentified and indicated with an
Underline.
BEGIN MAINPROGRAM
process 1
process 2
process 3
process n
END MAINPROGRAM
BEGIN SUBPROGRAM process 3
do this
do that
END SUBPROGRAM process 3
Not a very good example. Only used to illustrate Subprograms.
Eg1:
BEGIN MAINPROGRAM
Get NumOfPlayers
Stop=False
PNum=1
FOR Index=1 To NumOfPlayers
PTotal(Index)=5
ENDFOR
Index=1
WHILE Stop=False
IF Index=11
THEN
Index=1
ENDIF
ENDWHILE
Spin=RND(6) {RND(6) returns a number 1-6}
CASEWHERE Spin
1:
WinOne(Index,PTotal)
2:
LoseOne(Index,PTotal)
3:
WinFive(Index,PTotal)
4:
LoseFive(Index,PTotal)
5:
AllWin(Index,PTotal,NumOfPlayers)
6:
AllLose(Index,PTotal,NumOfPlayers)
ENDCASEWHERE
FOR Count=1 To NumOfPlayers
IF Ptotal(Count)>=50
THEN
Stop=True
ENDIF
ENDFOR
Index=Index+1
Print "The Winner is player number"
Findwinner
END MAINPROGRAM
BEGIN SUBPROGRAM LoseOne(Pos,PArray)
Parray(Pos)=PArray(Pos)-1
Return PArray
END SUBPROGRAM LoseOne
Arrays
An array is a structured data type that lets the programmer store multiple values(common data
type) in such a way that processing & storing data is greatly simplified.
Consider this array called Array_Num containing 6 elements(Index):
[7][4][2][8][5][9]
Finding Max_Val
BEGIN
Index=2
LastIndex=6
Max_Val=Array_Num[1] // Assuming the first element is the highest
WHILE Index<=LastIndex
IF Array_Num[Index]>Max_Val
THEN
Max_Val=Array_Num[Index]
ENDIF
Index=Index+1
ENDWHILE
Print "The highest number is" Max_Val
END
Ur Output should be 9
Finding Min_Val
BEGIN
Index=2
LastIndex=6
Min_Val=Array_Num[1] // Assuming the first element is the smallest
WHILE Index<=Lastindex
IF Array_Num[Index] < Min_Val
THEN
Min_Val=Array_Num[Index]
ENDIF
Index=Index+1
ENDWHILE
Print "The smallest number is" Min_Val
END
Ur Output should be 2
Linear Search
Used for unsorted arrays
BEGIN
Index=1
LastIndex=6
Found=False (Not found)
Get Target
WHILE Index<=LastIndex
AND Found=False
IF Array_Num[Index]=Target
THEN
Found=True
FoundPosition=Index
ENDIF
Index=Index+1
ENDWHILE
IF Found=True
THEN
Print "Target found at" FoundPosition
ELSE
Print "Target not found"
ENDELSEIF
END
Binary Search
Consider this array called Array_Item containing 6 elements(Index):
[Mouse][Keyboard][Printer][Scanner][Speaker][Monitor]
Which search technique would u use, Linear 0r Binary search? In this case a Binary search would be much more efficient. Used efficiently for ordered arrays.
BEGIN
Lower=1
Upper=6
Found=False (Not found)
Get Target
REPEAT Middle=Int(Lower+Upper)/2
IF Array_Item[Middle]=Target
THEN
Found=True
FoundPosition=Middle
ELSE
IF Target < Array_Item[Middle]
THEN
Upper=Middle-1
ELSE
Lower=Middle+1
ENDELSEIF
ENDELSEIF
UNTIL Found=True
OR Lower=Upper
IF Found=True
THEN
PRINT "Target found at" FoundPosition
ELSE
PRINT "Target not found"
ENDELSEIF
END
Records Of Arrays
Records are a metod of combining 2 or more simple data types that are related.
If we need to store many different items of different data types which is related,
we can use an array of records.
Consider:-
Student Record=Record
Firstname: String
Surname: String
Gender: String
ID: Integer
END Student Record
Student array(1...1000) of student record
This algorithm finds a particular student and obtains all details of that student.
//Finds student ID from Student file (Array, Records) respectively
Function Findstudent(Student ID, Student file)
Index=1
Found=False(Not Found)
WHILE Index<=1000
AND Found=False
IF Student ID=Studentfile(Index).ID
THEN
Found=True
RETURN Studentfile(Index).ID,Studentfile(Index).Firstname,Studentfile(Index).Surname,
Studentfile(Index).Gender
ELSE
Index=Index+1
ENDELSEIF
ENDWHILE
END Findstudent
Swap Algorithm
BEGIN
Get Number 1
Get Number 2
Num(1)=Number 1
Num(2)=Number 2
Temp=Num(1)
Num(1)=Num(2)
Num(2)=Temp
END
Feel free to correct any errors ^_^
