Patterns of algorithms:
sequence -> single value (reduction)
Counting
Used to count a number of elements in a collection, or to count the number of times a certain condition is satisfied.
Input
Postcondition
Implementation
int cnt = 0;
for (int i = 0; i < X.Length; i++){
// simple conditional expression can be used
// instead of a function call F(X[i])
if (F(X[i])){
cnt++;
}
}Maximum selection
Used to find the maximum element (value or index or both) in a collection.
Input
Postcondition
Short notation:
Implementation
int maxInd = 0;
int maxVal = X[0];
// iterate over the collection
// start from 1, because we already have the first element
for (int i = 1; i < X.Length; i++){
// if the current element is greater than the current maximum
if (X[i] > maxVal){
maxInd = i;
maxVal = X[i];
}
}Maximum selection can be used on a collection of complex elements, where the maximum is determined by a certain attribute of the element. E.g. find the employee with the highest salary.
int maxInd = 0;
int maxVal = X[0].salary;
for (int i = 1; i < X.Length; i++){
// logical expression can be substituted with a function call
// if more complicated logic is needed
if (X[i].salary > maxVal){
maxInd = i;
maxVal = X[i].salary;
}
}Note
Minimum selection is similar to maximum selection, but the condition is reversed.
Selection
Used to select an element that has a certain attribute from a collection. It is assumed that the element is present in the collection.
Input
Postcondition
Short notation:
Implementation
int ind = 0;
int val = 0;
int i = 0;
while (i < X.Length){
// simple conditional expression can be used
// instead of a function call F(X[i])
if (F(X[i])){
ind = i;
val = X[i];
}
i++;
}Decision
Used to determine if a collection has an item/element with certain attribute.
Input
Postcondition
Implementation
bool exists = false;
int i = 0;
while (!exists && i < X.Length){
// simple conditional expression can be used
// instead of a function call F(X[i])
if (F(X[i])){
exists = true;
}
i++;
}A variation of Decision PoA is Decision(All), which is used to determine if all elements in a collection have a certain attribute.
Postcondition
Implementation
bool all = true;
int i = 0;
while (all && i < X.Length){
// simple conditional expression can be used
// instead of a function call F(X[i])
if (!F(X[i])){
all = false;
}
i++;
}Search
Used to find an element with a given attribute (value or index or both) in a collection, element may not exist in that collection.
Search combines the functionality of Decision and Selection PoAs.
Input
Postcondition
Short notation:
Implementation
bool exists = false;
int ind = 0;
int val = 0;
int i = 0;
while (!exists && i < X.Length){
// simple conditional expression can be used
// instead of a function call F(X[i])
if (F(X[i])){
exists = true;
ind = i;
val = X[i];
}
i++;
}There are many variations of implementation, e.g. if element exists can be determined by checking if the original value if ind has changed or not.
int ind = -1;
int val = 0;
int i = 0;
while (ind < 0 && i < X.Length){
if (F(X[i])){
// if index is changed, then element exists
ind = i;
val = X[i];
}
i++;
}In case of using a variation of search - postcondition has to reflect that.
Sequence calculation
Used to calculate a single value from a collection of values using a transformation function.
Examples: sum, product, concatenation of all the elements of a collection.
Input
Postcondition
Specific example: Summation
Postcondition
Implementation
int sc = 0;
for (int i = 0; i < X.Length; i++){
sc += X[i];
}Specific example: Product
Postcondition
Implementation
int sc = 1;
for (int i = 0; i < X.Length; i++){
sc *= X[i];
}Specific example: Concatenation
Postcondition
Implementation
string sc = "";
for (int i = 0; i < X.Length; i++){
sc += X[i];
}