HackMDArrays in IB PSEUDOCODE
tags: Computer Science IB
Arrays
For this section I'm relying heavily in this sources:
https://www.programiz.com/cpp-programming/arrays
https://www.w3schools.com/cpp/cpp_arrays.asp
Arrays are a particular type of collection. The idea is that we are going to store in one variable more than one value. One way to do it is using an array.
This is the declaration of an array of integers (int) with 5 numbers:
int numbers[5] = {1, 10, 20, 30, 50};
The length (or size) of a specific array is how many elements can contain.
Arrays in most programming languages are very efficient (specially regarding memory usage) but they have some inconvenients. The main one is that once we have declared the size of an array it cannot be changed during the execution.
Array index and values
The first problem that we need to address is that we want to access a particular element (also called member) of the array. To do that we need to use the concept of index. The index is the address inside of the array. To access one of the elements we need to write the name of the array and, in brackets write the number of the index.
Indexes in computer science start with zero, so the first element is the [0] element, the second is the [1] element and the last is [n-1] being n the length of the array.
Let's supose the example of the web in programiz. In C++ we can initialize the array like this:
// declare and initialize and array
int x[6] = {19, 10, 8, 17, 9, 15};
Here is the visualization of the elements
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
source
So if we write this code we can use those members to asign other values or we can use it in if statements as we please.
For example
int x[6] = {19, 10, 8, 17, 9, 15};
int y = x[2]; //8
int z = 0;
if (x[4] < x[1]) //this happens because 9 is lesser than 10
{
z = x[3] + x[0]; //17+19 =36
}
else { //this doesn't happen
z = z + x[5];
}
Array definition and array access
You may see that sometimes we are using MyArray[100] and other times is MyArray[0]. Why is that? Is not the size of the array constant?
When we define the array in many programming languages we can define the array size in the same line. For example:
int x[6] = {19, 10, 8, 17, 9, 15};
Exercise 15
Write the output of this code that it's going to happen through serial.
This and the next is a typical exam exercise to see if you get the concept of index of arrays
Serial.begin(9600);
int x[7] = {19, 10, 8, 17, 9, 15, -10};
int y = x[3];
Serial.println(y);
int z = 0;
if (x[6] < x[1])
{
z = x[4] + x[0];
Serial.println("Dinosaur");
}
else {
z = z + x[2] +10;
Serial.println("Shark");
}
Serial.println(z);
The solution with the explanation in the comments is in the spoiler section
Solution:
17
Dinosaur
28
The answer in this case are separated through lines since we're using Serial.println but in an exam I will accept them separated in other ways as long as they are in the correct order.
Serial.begin(9600);
int x[7] = {19, 10, 8, 17, 9, 15, -10};
int y = x[3]; //forth element
Serial.println(y);
int z = 0;
if (x[6] < x[1]) //this happens
{
z = x[4] + x[0]; // 9 +19
Serial.println("Dinosaur");
}
else { //this doesn't happen
z = z + x[2] +10;
Serial.println("Shark");
}
Serial.println(z);
Exercise 16
Write the output of this code that it's going to happen through serial.
In this case we are going to use also values as indexes. Beware!
Serial.begin(9600);
int numbers[8] = {3, 1, 5, 8, 1, 2, 1, 3};
int x = numbers[1];
int y = numbers[x+1];
int z = numbers[numbers[2]];
Serial.println(x);
Serial.println(y);
Serial.println(z);
The solution with the explanation in the comments is in the spoiler section
Solution:
1
5
2
The answer in this case are separated through lines since we're using Serial.println but in an exam I will accept them separated in other ways as long as they are in the correct order.
Serial.begin(9600);
int numbers[8] = {3, 1, 5, 8, 1, 2, 1, 3};
int x = numbers[1]; // Second element
int y = numbers[x+1]; // x is 1, so the third element. 5
int z = numbers[numbers[2]]; //the third element is 5, so the sixth element is 2
Serial.println(x);
Serial.println(y);
Serial.println(z);
The length problem
As a teacher I observed that the concept of length of an array sometimes is not clear and is key for understanding the loops through arrays.
The length of the array will be usually given in a variable or as part of the problem "we have a hotel with 100 rooms, and each number of the room is stored in an array" means that we have an array of length 100.
In C++ we cannot use length of an array as propiety so it's common to have something like this
int MyArrayLength = sizeof(MyArray) / sizeof(MyArray[0]);
This calculates the size in memory of the whole array and divides it by the size of the first element. This gives the numbers of elements.
Sometimes we have a more complex version of this. In the code that we used in the melody player we found this code in the line 172
int notes = sizeof(melody) / sizeof(melody[0]) / 2;
This was because in this code the melody array has 2 elements for each note (frequency and the divider of the duration).
More info here
In other programming languages (such as java) we usually can access the length of an array using a length propiety.
//BEWARE JAVA CODE
int[] exampleArray = {1,2,3,4,5};
int exampleArraySize = exampleArray.length;
System.out.print("This Java array size is: " + exampleArraySize );
//The Java array length example prints out the number 5
Loops with arrays
In class we have discussed the implementation of simple algorithms such as min, max and average. For doing that we need to use loops (for loops or while loops).
This types of algorithms are called iterate through an array.
Usually we can see 2 types of iteration algorithms (but there are more!).
- Extensive loops. This kind needs to go through each element to do something with that element (add to a sum when we find the average for example).
- Selective loops. that only want to do something to part of the elements or even just one (like when we do the min) but we need to check a condition to do that (With an if clause)
In the for loop usually will be something like this:
for (int i = 0; i < [ARRAY_LENGTH]; i ++) {
//code to execute
}
//PSEUDOCODE
loop I from 0 to [ARRAY_LENGTH]-1
//things to do
//the element will be accessed with ARRAY[I]
end loop
Is common to use i of index, but this is usually up to the programmer and I will consider correct any name for the variable.
The ARRAY_LENGTH is the array length given by the context. Consult the length problem to revise if you need.
In the code usually we want to do something with the element of the array. If the array is called "myArray" this would be "myArray[i]".
A selective loop would look like this
for (int i = 0; i < [ARRAY_LENGTH]; i ++) {
if (condition)
{
//code to execute
}
}
//PSEUDOCODE
loop I from 0 to [ARRAY_LENGTH]-1
if (condition) then
//things to do
//the element will be accessed with ARRAY[I]
end if
end loop
The condition usually will look for a condition of the specific element so we can expect to see in the condition "myArray[i]".
We can use for loops, while loops and for each loops. I haven't covered for each loops but I will mark it as correct (if they are correctly written). You can find more info about for each loops in this LINK
Now that we have discussed the abstraction we can see the basic algorithms.
Exercise 17
Now we're running a foodtruck about selling corn.
We have an array with all the prices of our products (23 different ways of having a cup of corn with stuff on it) with a range that goes from 2 euros to 10 euros.
Output the minimum, the maximum and the average of the prices that are available.
The solutions with the explanation in the comments is in the spoiler section
This exercise is not an exam like question but the student should know how these works in order to create more complex algorithms
Maximum
PSEUDOCODE
I = 0
MAX = prices [0]
loop while I < 23
if MAX < prices[I] then
MAX = prices[I]
end if
I = I +1
end loop
output MAX
double max = prices[0]; //we initialize the maximum with the first value. It's a double because we're comparing doubles.
for(int i = 0; i < 23; i++) //the number is the name of different products that we can find
{
if (max < prices[i]) { //if the element that we are inspectinc has a bigger value that our max, we update the max
max = prices[i];
}
}
Serial.println(max);
Minimum
double min = prices[0]; //we initialize the maximum with the first value. It's a double because we're comparing doubles.
for(int i = 0; i < 23; i++) //the number is the name of different products that we can find
{
if (min > prices[i]) {//if the element that we are inspectinc has a smaller value that our min, we update the min
min = prices[i];
}
}
Serial.println(min);
Average
SUM = 0
loop for X from 0 to 22
SUM = SUM + prices[X]
end loop
average = sum div 23
output average
double sum = 0; // we're adding all the values on the array so we start with 0
for(int i = 0; i < 23; i++) //the number is the name of different products that we can find
{
sum = sum + prices[i]; //also
}
double average = sum / 23;
Serial.println(min);
Exercise 18
We have an array of 50 different grades from students that go from 0.0 to 10.
We want to know the index of the highest array and the number of passes (they pass with a 5.0 or higher grade).
Construct a code that outputs this information. The name of the array is grades.
The solutions with the explanation in the comments is in the spoiler section.
This exercise is an exam like question.
We can do it in just one loop or two different loops. Both options are fine for this purpose.
Finding the maximum index with pseudocode
PSEUDOCODE
MAX = grades[0]
MAX_I = 0 //maximum index. Temporary for now
loop A from 0 to 49
if MAX < grades[A]
MAX = grades[A]
MAX_I = A
end if
end loop
output MAX_I
Output the number of passes
PSEUDOCODE
COUNT= 0
I = 0
loop while I<=49
if grades[I] >= 5 then
COUNT = COUNT + 1
end if
I = I + 1
end loop
output COUNT
int bestGradeIndex = 0; //we can initialize this as 0 or -1. It's an int because the
double bestGrade = grades[0]; //the same idea when we had the max. We need to use it because we still need to know the max.
for(int i = 0; i < 50; i++) //the number is the number of grades
{
if (bestGrade < grades[i]) { //if the element that we are inspectinc has a bigger value that our max, we update the max
bestGrade = grades[i];
bestGradeIndex = i; //We need to update the index that is the one that we're going to output
}
}
Serial.println(bestGradeIndex); //output the first task.
int passed = 0; //initialized counter of people that have passed.
for(int i = 0; i < 50; i++) //the number is the number of grades
{
if (grades[i] >= 5) { //if the element that we are inspectinc has a bigger value that our max, we update the max
passed ++;
}
}
Serial.println(passed);//output the second task.
Solution with only one loop (a bit more confusing but legal for the exam)
int bestGradeIndex = 0;
double bestGrade = grades[0];¡
for(int i = 0; i < 50; i++)¡
{
if (bestGrade < grades[i]) { ¡
bestGrade = grades[i];
bestGradeIndex = i; ¡
}
if (grades[i] >= 5) {
passed ++;
}
}
Serial.println(bestGradeIndex); //output the first task.
Serial.println(passed);//output the second task.
Exercise 19
This exercise is the same as 18 but is asking about construting functions. Take notice of the differences in the statement
We have an array of 50 different grades from students that go from 0.0 to 10.
We want to know the index of the highest array and the number of passes (they pass with a 5.0 or higher grade).
We're going to implement a couple of functions that return this information. The first one is "highestGradeIndex" and the second is "passes". The name of the array is grades and is a double type and is a global variable.
Remember that global variables are variables that we can access in any part of the code.
We can consider that the instruction Serial.begin(9600); has been already called.
The solutions with the explanation in the comments is in the spoiler section.
We need to split this into two different functions, we cannot do them in just one algorithm.
The highestGradeIndex function:
highestGradeIndex ()
BEST_GRADE = grades[0]
BEST_GRADE_INDEX = 0
loop for I from 1 to 49
if BEST_GRADE < grades[I] then
BEST_GRADE_INDEX = I
BEST_GRADE = grades[I]
end if
end loop
return BEST_GRADE_INDEX
end method
passes ()
PASSED = 0
loop for I from 0 to 49
if (grades[I]) >= 5) then
PASSED = PASSED +1
end if
end loop
return passed
end method
Strings: arrays of characters
Here you have more activities to do to practice (with pseudocode and C++)
Strings are arrays of characters. We have access to several functions that are going to do something
Parallel arrays
When we have 2 or more arrays which elements of the same index refer to the same entity (a student, a car, an employee, a flight) we call them Parallel arrays.
We usually have to collect information from one of the arrays and output the other one.
Classic example is to store in one array the grades of the students and in other the names of the students. So, if you want to output who got the best (or worst) grade you will check the array of the grades but you will use the same index to output the name of the student using the array which has the names of the students
Exercise 20
Number of followers of EXO.
We're the managers of EXO and we want to check the performance of these members in social media.
We have 2 arrays. One array is EXObandMember with the names of the band members ( Baekhyun, Chen, Lay, Sehun, Chanyeol, D.O., Kai, Suho, Xiumin) and the other is a parallel array called followersInstagram
Create in pseudocode an algorithm that outputs who has the most number of followers in instagram and the number of follows that they have.
The solutions with the explanation in the comments is in the spoiler section.
Result only:
PSEUDOCODE
EXObandMember[9]
followersInstagram[9]
MAX = followersInstagram[0]
MAX_INDEX = 0
loop for N from 1 to 8 // we start at 1 because we're already have the first one and we end in LENGTH -1
if followersInstagram[N] > MAX then
MAX = followersInstagram[N]
MAX_INDEX = N
end if
end loop
output EXObandMember[MAX_INDEX]
output MAX
Process
//EXObandMember[9]
// finding only the maximum value of followersInstagram
MAX = followersInstagram[0]
loop for I from 0 to 8 //The array has 9 elements
if MAX < followersInstagram[I] then
MAX = followersInstagram[I]
end if
end loop
// finding also the index of followersInstagram that has the maximum value
MAX = followersInstagram[0]
MAX_INDEX = 0
loop for I from 0 to 8 //The array has 9 elements
if MAX < followersInstagram[I] then
MAX = followersInstagram[I]
MAX_INDEX = I
end if
end loop
// using that index to output the name of the person
//followersInstagram []
//EXObandMember []
MAX = followersInstagram[0]
MAX_INDEX = 0
loop for I from 0 to 8 //The array has 9 elements
if MAX < followersInstagram[I] then
MAX = followersInstagram[I]
MAX_INDEX = I
end if
end loop
Output EXObandMember[MAX_INDEX] //band member with most followers on instagram
Output MAX //most followers on instagram
//Output EXObandMember[MAX] Error because EXObandMember[ 3 million something]doesn't exist since there are only 9 members
Output followersInstagram[MAX_INDEX] //Same as output Max
Exercise 21
In the same context of the last exercise we need to know the member that is nearest the average amount of followers in instagram.
For this we need 2 loops. First to find the average. Second to decide which band member has a lower difference with the average.
The solutions with the explanation in the comments is in the spoiler section.
PSEUDOCODE
EXObandMember[9]
followersInstagram[9]
//First find the average
SUM = 0
loop for N from 0 to 8
SUM = SUM + followersInstagram[N]
end loop
AVG = SUM div 9 //remember to use div in these contexts
// Once we know the average we need to know the difference between each member audience and that average. And which difference has a lower absolute value.
//We find the difference between the average and the first group member. (later we're going to compare it with the rest of the differences)
DIFFERENCE = AVG - followersInstagram[0]
//In this part we asign to LOWEST_DIFFERENCE the absolute value
if (DIFFERENCE < 0) then
LOWEST_DIFFERENCE = - DIFFERENCE
else
LOWEST_DIFFERENCE = DIFFERENCE
end if
// if we had access to something like abs(x) that returns the absolute value of a given number we can write this other one liner
// LOWEST_DIFFERENCE = ABS(AVG - followersInstagram[0])
LOWEST_DIFFERENCE_INDEX = 0 //We have the index value because we want the name so we have to save it somewhere.
loop for I from 1 to 8 // FROM 1 because we're comparing the first one with the rest, so we can start with the second one
DIFFERENCE = AVG - followersInstagram[I] //calculate difference
if (DIFFERENCE < 0)
DIFFERENCE = - DIFFERENCE // Finding the absolute value of the difference
end if
if (DIFFERENCE < LOWEST_DIFFERENCE) //Minimum absolute value finding
LOWEST_DIFFERENCE = DIFFERENCE
LOWEST_DIFFERENCE_INDEX = I
end if
end loop
output EXObandMember[LOWEST_DIFFERENCE_INDEX]
Exercise 22
Using the same context of EXO members, output the name of all the members that are over 10 000 000 followers in instagram.
(solution by Y.C)
Flag variables while looking into arrays
Flag variables are boolean variables that we use to store information.
Exercise 23
Flights destinations.
We have in an array called flightDestinations[4500] the destination code for all the flights that had happen in one month in Barcelona's Airport. This destination codes are 3 letters that are unique for each airport ("IBZ" for Ibiza, "SCL" Santiago de Chile, "EZE" for Buenos Aires, "MAD" for Madrid and so on). These flights can have the same destination so they will be repeated. For example we can expect that IBZ could be even repeated 100 times in a month.
1st part. Output how many times there is a flight to ICN (Seoul)
PSEUDOCODE
COUNT = 0
loop for N from 0 to 4499
if flightDestinations[N] = "ICN" then //remember to put the quotes in strings!
COUNT = COUNT + 1
end if
end loop
output COUNT
We have another array that is called SpanishDestinations[] with the codes of the Spanish airports. There are 48 airports in Spain.
The arrays SpanishDestinations and flightDestinations are not parallel (they don't refer to the same flight)
First we're going to check if the first flight is a National flight or an international flight. To do that we need to check if the String is inside Spanish Destinations.
So let's start simple and let's see if the 3rd flight of the month(index number 2, remember) is a National or international flight. Output "national" if it is, "international" otherwise
PSEUDOCODE
flightDestinations[4500] // the array with all the flights even if we're using here just one to start easy
SpanishDestinations[48] // the size is the number of airports
NATIONAL_DESTINATION = false // we set a boolean flag. The name of the variable, as always is depending on the student. I wrote here a long one but you can write FLAG or NATIONAL or even F
loop for N from 0 to 47 // Length of Spanish Destinations - 1
if (flightDestination[2] = SpanishDestinations[N]) then
//here we are checking if the 3rd flight on flightDestinations is equal to each of the elements of the array of 48 airports in Spain
NATIONAL_DESTINATION = true
// if it is, we need to change the flag variable to true, because we have found that this destination is national
break
//here we break the loop so we don't keep looking if we have found what we're looking for.
end if
end loop
if NATIONAL_DESTINATION then //writing NATIONAL_DESTINATION is the same as NATIONAL_DESTINATION = true
output National
else
output international
end if
Now let's output how many national flights have we had in Barcelona last month.
In this case we are going to need that flag variable and we're not looking for only one of the flights in flightDestinations but all of them. So we need to loop through all of them. We're going to need a nested loop (a loop inside a loop)
PSEUDOCODE
flightDestinations[4500] // the array with all the flights even if we're using here just one to start easy
SpanishDestinations[48] // the size is the number of airports
COUNT = 0
loop for X from 0 to 4499 //total number of flights last month
NATIONAL_DESTINATION = false
loop for N from 0 to 47
if (flightDestination[X] = SpanishDestinations[N]) then
NATIONAL_DESTINATION = true
break
end if
end loop
if NATIONAL_DESTINATION then //writing NATIONAL_DESTINATION is the same as NATIONAL_DESTINATION = true
COUNT = COUNT +1 //instead of outputing "national" we update the counter
end if
end loop
output COUNT
Execrise 23 B
Change the previous code so it displays the international destinations instead of the national ones.
Solution in the spoilers:
Three posible solutions
flightDestinations[4500] // the array with all the flights even if we're using here just one to start easy
SpanishDestinations[48] // the size is the number of airports
COUNT = 0
loop for X from 0 to 4499 //total number of flights last month
NATIONAL_DESTINATION = false
loop for N from 0 to 47
if (flightDestination[X] = SpanishDestinations[N]) then
NATIONAL_DESTINATION = true
break
end if
end loop
if NATIONAL_DESTINATION then //writing NATIONAL_DESTINATION is the same as NATIONAL_DESTINATION = true
COUNT = COUNT +1 //instead of outputing "national" we update the counter
end if
end loop
output 4500 - COUNT
flightDestinations[4500] // the array with all the flights even if we're using here just one to start easy
SpanishDestinations[48] // the size is the number of airports
COUNT = 0
loop for X from 0 to 4499 //total number of flights last month
NATIONAL_DESTINATION = false
loop for N from 0 to 47
if (flightDestination[X] = SpanishDestinations[N]) then
NATIONAL_DESTINATION = true
break
end if
end loop
if NOT_NATIONAL_DESTINATION then //writing NATIONAL_DESTINATION is the same as NATIONAL_DESTINATION = true
COUNT = COUNT +1 //instead of outputing "national" we update the counter
end if
end loop
output COUNT
flightDestinations[4500]
SpanishDestinations[48]
COUNT = 0
loop for X from 0 to 4499
INTERNATIONAL_DESTINATION = True
loop for N from 0 to 47
if (flightDestination[X] = SpanishDestinations[N]) then
INTERNATIONAL_DESTINATION = False
break
end if
end loop
if INTERNATIONAL_DESTINATION then
COUNT = COUNT +1
end if
end loop
output COUNT
This solution is not correct because it doesn't evaluate properly
flightDestinations[4500] // the array with all the flights even if we're using here just one to start easy
SpanishDestinations[48] // the size is the number of airports
COUNT = 0
loop for X from 0 to 4499 //total number of flights last month
INTERNATIONAL_DESTINATION = FALSE
loop for N from 0 to 47
if (flightDestination[X] =/ SpanishDestinations[N]) then
INTERNATIONAL_DESTINATION = TRUE
break
end if
end loop
if INTERNATIONAL_DESTINATION then
COUNT = COUNT +1
end if
end loop
output COUNT
Exercise 24
Output the percentage of flights that were international last month. (Small variation from the last exercise)
Solution:
PSEUDOCODE
flightDestinations[4500] // the array with all the flights even if we're using here just one to start easy
SpanishDestinations[48] // the size is the number of airports
COUNT = 0
loop for X from 0 to 4499 //total number of flights last month
NATIONAL_DESTINATION = false
loop for N from 0 to 47
if (flightDestination[X] = SpanishDestinations[N]) then
NATIONAL_DESTINATION = true
break
end if
end loop
if NOT NATIONAL_DESTINATION then //writing NATIONAL_DESTINATION is the same as NATIONAL_DESTINATION = true
COUNT = COUNT +1 //instead of outputing "national" we update the counter
end if
end loop
PERCENTAGE = (COUNT / 4500) * 100
output PERCENTAGE
credits to S.A.
Output how many different locations are there in the array flightDestinations.
PSEUDOCODE
flightDestinations[4500] //given array
differentLocations[4500] //empty array of strings with the Maximum possible different number of destinations (the number of actual flights)
COUNT = 1 // there is at least 1 posible location
differentLocations[0] = flightDestinations[0] //We set the first possible flight destination
loop for N from 1 to 4499 //look for every flight that is not the first one
newDestination = true // this is a boolean flag. It's true if it's a new destination but it will be false if we prove otherwise.
loop for X from 0 to COUNT -1 //we do a loop looking to the filled elements of the array differentLocations
if flightDestinations[N] = differentLocations[X]
newDestination = false
break // this is optional. This will break the inner loop (the X one)
end if
end loop
if (newDestination) then //if there is no match in the differentLocations array it means that we have to add it
differentLocations[COUNT] = flightDestinations[N]
COUNT = COUNT + 1
end
end loop
output COUNT
Let's trace this table for this 6 values of flightDestinations
{MAD, IBZ, MAD, SCL, EZE, IBZ}
For being more understandable we are going to write the line of the code that we are. In an exam you are not going to be asked to do that.
| line | COUNT | N | flightDestinations[N] | X | differentLocations [X] | newDestination |
|---|---|---|---|---|---|---|
| 5 | 1 | |||||
| 7 | 1 | 1 | IBZ | |||
| 8 | 1 | 1 | IBZ | true | ||
| 8 | 1 | 1 | IBZ | 0 | MAD | true |
| 10 | 1 | 1 | IBZ | 0 | MAD | true |
| 15 | 1 | 1 | IBZ | / | / | true |
| 16 | 1 | 1 | IBZ | / | / | true |
| 8 | 2 | 2 | MAD | / | / | true |
| 9 | 2 | 2 | MAD | 0 | MAD | true |
| 10 | 2 | 2 | MAD | 0 | MAD | true |
Do a trace table with this data in Flight Destinations
{MAD, CDG, MAD, SCL, CDG, IBZ}
| COUNT | N | flightDestinations[N] | X | differentLocations [X] | newDestination |
|---|---|---|---|---|---|
| - - | –––– | –––– | –––– | –––– |
Counting with another array
Output which Spanish airport has had the most number of flights from Barcelona last month.
In this case we have these arrays
flightDestinations[4500]
SpanishDestinations[48]
So for doing that we are going to need another array (SpanishCounters) to store the counts of each of the 48 Spanish airports. After that we just have to find the maximum and output the name using the code stored in SpanishDestinations
PSEUDOCODE
flightDestinations[4500] // the array with all the flights even if we're using here just one to start easy
SpanishDestinations[48] // the size is the number of airports
SpanishCounters[48] //we define this array
loop for X from 0 to 4499 //total number of flights last month
//no need for flag variable
loop for N from 0 to 47
if (flightDestination[X] = SpanishDestinations[N]) then
SpanishCounters[N]= SpanishCounters[N] + 1
break
end if
end loop
end loop
output
MAX = SpanishCounters[0]
MAX_INDEX
loop C from 0 to 47
if MAX < SpanishCounters[C] then
MAX = SpanishCounters[C]
MAX_INDEX = C
end if
end loop
output SpanishDestinations[MAX_INDEX]
EVEN MORE COMPLEX Exercise 25
Tell (output) which destination is the most popular in the last month
For doing that we need the array with diffent possible destinations. If it's not given, we can do it with the previous code.
After this, then we need to populate an array.
PSEUDOCODE
flightDestinations[4500]
differentLocations[4500]
COUNT = 1
differentLocations[0] = flightDestinations[0]
loop for N from 1 to 4499
newDestination = true
loop for X from 0 to COUNT -1
if flightDestinations[N] = differentLocations[X]
newDestination = false
break
end if
end loop
if (newDestination) then
differentLocations[COUNT] = flightDestinations[N]
COUNT = COUNT + 1
end
end loop
//define a new array with the population of the destinations (numbers that are repeated)
counterLocations[COUNT] //started with 0 all the elements
loop for D from 0 to 4499 // loop through flightDestinations
loop for I from 0 to COUNT - 1 // loop through differentLocations
if differentLocations[I] = flightDestinations[D] then
counterLocations[I] = counterLocations[I] +1
end if
end loop
end loop
//
MAX = counterLocations[0]
MAX_INDEX = 0
loop T from 0 to COUNT - 1
if MAX < counterLocations[T] then
MAX = counterLocations[T]
MAX_INDEX = T
end if
end loop
output differentLocations[MAX_INDEX]
flightDestinations[4500]
differentLocations[4500]
counterLocations[4500]
COUNT = 1
differentLocations[0] = flightDestinations[0]
counterLocations[0] = 1
loop for N from 1 to 4499
newDestination = true
loop for X from 0 to COUNT -1
if flightDestinations[N] = differentLocations[X]
newDestination = false
counterLocations[X] = counterLocations[X] +1
break
end if
end loop
if (newDestination) then
differentLocations[COUNT] = flightDestinations[N]
counterLocations[COUNT] = 1
COUNT = COUNT + 1
end
end loop
//
MAX = counterLocations[0]
MAX_INDEX = 0
loop T from 0 to COUNT - 1
if MAX < counterLocations[T] then
MAX = counterLocations[T]
MAX_INDEX = T
end if
end loop
output differentLocations[MAX_INDEX]
Exercise 26 from a class exam
We selling lemonade and other juices for having some extra fundings. To analyze the different sales we have filled an array with all the names of the different products PRODUCTS with these values [“Lemonade”, “Orange juice”, “Orange banana”, “Orange carrot”, “Tropical smash”] and we have another parallel array with their corresponding prices called PRICES with values that go from 500 to 3000 Chilean Pesos.
A.1) State the size of the array PRICES [1 mark]
5
Last weekend we have been taking notes of the sales and we have an array called SALES with the 80 sales with the name of the different products we have sold. Here you can see the first values of the array SALES:
{“Orange juice”, “Orange juice”, “Lemonade”, “Orange carrot”, “Lemonade”, “Orange juice”, …}
All the possible values of SALES are inside PRODUCTS.
A.2) Construct a code that outputs the number of times that we have sold lemonade last weekend. [4 marks]
COUNT = 0
loop for X from 0 to 79
if SALES[X] = "Lemonade" then
COUNT = COUNT +1
end if
end loop
output COUNT
Marking: 1 for correct loop, 1 for output, 1 for updating the variable, 1 for correct if
A.3) Construct a code that outputs the total amount of income in chilean pesos this weekend. Use the parallel array PRICES. [6 marks]
The solution is at the end of the explanation.
For doing this we need to understand that each sale has associated with one name (in products) and each product has a price.
To find the total amount of income we need to add the prices of all the elements that we have sold.
So first we need a loop through the array of SALES (that one has a length of 80).
For each element we need to loop through the array of PRODUCTS (that one has a length of 5) to find which index is it.
Once we know the index of the PRODUCT then we can add to SUM the price of the product since PRICES is a parallel array of PRODUCTS.
SUM = 0
loop for X from 0 to 79
loop for J from 0 to 4
if SALES[X] = PRODUCTS[J] then
SUM = SUM +000 PRICES[J]
break //optional
end if
end loop
end loop
output SUM
Marking: 1 for correct each loop, 1 for output, 1 for updating the variable, 1 for correct if, 1 for using the parallel array
Exercise 27 trace table of simple array
(inspired by Nov 22 exercise)
Consider this one-dimensional array COUNTRIES
| [0] | China |
| [1] | Tailand |
| [2] | Australia |
| [3] | Egypt |
| [4] | Denmark |
Construct a trace table for the following algorithm
T = 4
loop while T > = 0
B = T mod 4
output COUNTRIES[B]
T = T -1
end while
Solution:
| T | T > = 0 | B | Output |
|---|---|---|---|
| 4 | true | 0 | China |
| 3 | true | 3 | Egypt |
| 2 | true | 2 | Australia |
| 1 | true | 1 | Tailand |
| 0 | true | 0 | China |
| -1 | false | 0 | - |
Exercise 27 variation 1
(I changed the algorithm)
Consider this one-dimensional array COUNTRIES
| [0] | China |
| [1] | Tailand |
| [2] | Australia |
| [3] | Egypt |
| [4] | Denmark |
Construct a trace table for the following algorithm
T = 6
loop while T > = 0
B = T mod 4
output COUNTRIES[B]
if T mod 2 = 0 then
T = T - 3
else
T = T + 1
end while
Solution
credit to Y.C.
Exercise 27 variation 2
(I changed the algorithm)
Consider this one-dimensional array COUNTRIES
| [0] | China |
| [1] | Tailand |
| [2] | Australia |
| [3] | Egypt |
| [4] | Denmark |
Construct a trace table for the following algorithm
T = 0
loop while T < 7
B = T mod 4
output COUNTRIES[B]
T = T + 1 + B
end while
Exercise with parallel arrays and use of functions.
(credit: R.G. with modifications)
There is a calculation that you can use to find the Goal Assist that is a ratio that ponders a little bit more the Goal than the assist (we don't need to know the details). To find out you need to use the function calcGA(Goals, Assist) that if you send the number of goals and the number of assist it will send you back the info that ratio.
We have 3 parallel arrays that refer to 30 players, with NAMES, GOALS and ASSIST that they have done over a season.
Construct an algorithm which will output the names of all the football players whose GA (Goal/assist)is greater than this group's average GA.
Be aware that you should use "calcGA()" in your answer
Solution in the spoiler
sum = 0
loop for K from 0 to 29
sum = sum + calcGA(GOALS[K], ASSIST[K])
end loop
average = sum/30
loop for K from 0 to 29
if calcGA (GOALS[K], ASSISTS[K]) > average then
output NAME[K]
end if
end loop
In the first part of this code (1-5 line) we are counting group's average GA, using "for" and then dividing sum to 30 (30 people).
In the second part we are already writing the code itself, wich calculates how many people have GA greater than the group's average
Standard algorithms on linear arrays (4.2.1)
Search algorithms
Sequential search ("linear to find")
Starts with the first element and compares each elemen to the one we're looking for until it is found.
MY_ARRAY [25] //array that we need to find something
SEARCHED_VALUE //Value that we're looking for
loop for I from 0 to 24
if MY_ARRAY[I] == SEARCHED_VALUE then
// do something
// usually we add here break
end if
end loop
Works on every type of array, no matter if it's sorted and it has a O(n) complexity.
With collections work this way:
MY_COLLECTION
SEARCHED_VALUE //Value that we're looking for
loop while MY_COLLECTION.hasNext()
CURRENT_VALUE = MY_COLLECTION.getNext()
if CURRENT_VALUE == SEARCHED_VALUE then
// do something
// usually we add here break
end if
end loop
Example 1:
We have a couple of parallel arrays with a size 20. One that is called NAMES and the other is called TIMES_THAT_HAVE_GONE_TO_SKI
If we want to know if somebody has gone to ski exactly 3 times we can use a linear search.
Construct the pseudocode to output the name of somebody who has been skiing exactly 3 times
loop I from 0 to 19
if (TIMES_THAT_HAVE_GONE_TO_SKI[I] == 3) then
output NAMES[I]
break //if we want to output only one
end if
end loop
Binary search (aka sorted and split)
Also known as "half-interval search". This is a good algorithm (O(log (n)) of complexity) but requires that the array has to be sorted before executing it.
So the steps are
Compare the search value with the element of the middle of the array. The posibilities are 3.
- We found it!
- The value in the middle of the array is less than the searched value. Then we have to look in the top part of the array.
- The value in the middle of the array is more than the searched value. Then we have to look in the bottom part of the array.
Here you have an image of how it works
source geeksforgeeks
Beware: this array doesn't work! find out why using a trace table!
MY_ARRAY [25] //SORTED array that we need to find something
SEARCHED_VALUE //Value that we're looking for
I = 25 div 2 +1
HALF = 25 div 2
RANGE = HALF
FOUND = FALSE
EXIT = FALSE
loop while NOT FOUND AND RANGE > 0
RANGE = HALF
if SEARCHED_VALUE = MY_ARRAY[I] then
FOUND = TRUE
else if SEARCHED_VALUE < MY_ARRAY[I] then
HALF = HALF div 2
I = I - HALF
else then
HALF = HALF div 2
I = I + HALF
end if
end loop
if FOUND then
//do something
else then
// do something else
end if
Implementation transalated from here:
https://www.geeksforgeeks.org/binary-search/
MY_ARRAY [25] //SORTED array that we need to find something
SEARCHED_VALUE //Value that we're looking for
FOUND = FALSE
LOW = 0
TOP = 25-1 //MY_ARRAY length - 1
loop while LOW <= TOP and NOT FOUND
MID = LOW + ((TOP - LOW) div 2);
if MY_ARRAY[MID] = SEARCHED_VALUE then
FOUND = TRUE
else if MY_ARRAY[MID] < SEARCHED_VALUE then
LOW = MID + 1
else
TOP = MID - 1
end if
end loop
if FOUND then
//do something
else then
// do something else
end if
Remember that LOW, MID and TOP are refering to indexes and not about values.
The index of the Searched value will be stored in the MID variable in this implementation.
Example:
We have a dictionary of slang words used in the 70s in London in a corpus that has 1000 words. All those words are sorted alphabetically. The name of the array is WORDS_CORPUS
Corpus linguistics is the study of a language as that language is expressed in its text corpus (plural corpora), its body of "real world" text. More info here
Construct a pseudocode algorithm using binary search to try to find if "punk" is in that dictionary. It will output if it's or not.
In most programming languages you can compare words in English with usual comparators and it will work fine. For not English languages things are usually tricker.
In this way 'A' is "smaller" than 'B' and 'D' is "bigger" than 'C'
Also "Aaron" will be evaluated as smaller if you compare it with "Berthe" and "Sofya" will be bigger than "Chenxi"
Solution in the spoiler section.
WORDS_CORPUS [1000] //we write the array so we have clear what are we working with
SEARCHED_WORD = "punk"
FOUND = false
LOW = 0
TOP = 1000 -1
loop while LOW <= TOP and FOUND == false
MID = LOW + ((TOP-LOW) div 2)
if WORDS_CORPUS [MID] == SEARCHED_WORD then
FOUND = true
else if WORDS_CORPUS [MID] < SEARCHED_WORD then
LOW = MID +1
else //this is n case WORDS_CORPUS is bigger than searched word
TOP = MID -1
end if
end loop
if FOUND then
output "the word "+ SEARCHED_WORD + " is in the corpus"
else
output "the word "+ SEARCHED_WORD + " is not in the corpus"
end if
Exercise of tracing a binary search
We have the following array:
TIMESTAMPS = {1002, 1003, 1023, 1240, 1560, 1850, 1950}
Write a tracetable using a binary search algorithm. One of the colums should be output. The searched value is 1560
TIMESTAMPS = {1002, 1003, 1023, 1240, 1560, 1850, 1950}
SEARCHED_VALUE = 1560
FOUND = FALSE
LOW = 0
TOP = 7-1 //TIMESTAMPS length - 1
loop while LOW <= TOP and NOT FOUND
MID = LOW + ((TOP - LOW) div 2);
if TIMESTAMPS[MID] = SEARCHED_VALUE then
FOUND = TRUE
else if TIMESTAMPS[MID] < SEARCHED_VALUE then
output "we need to look in the upper values"
LOW = MID + 1
else
output "we need to look in the lower values"
TOP = MID - 1
end if
end loop
if FOUND then
output "value found!"
else then
output "value NOT found! = ("
end if
Possible solution
credit to Y.C.
Do the same with the searched values of 900, 1003 and 1951
Sorting arrays
Why sorting
Because if we have the elements sorted, we can use binary search, so everything is way more easy to find.
(source)
Imagine that we have a dictionary without sorting, it would be very complicated to use!
Remember how to swap ellements
For sorting we need to one way or another swap elements between them. For doing that the main way is with this template.
//we want to interchange MY_ARRAY[N] with MY_ARRAY[M]
TEMP = MY_ARRAY[N]
MY_ARRAY[N] = MY_ARRAY[M]
MY_ARRAY[M] = TEMP
Remember that MY_ARRAY depends on context and it's the name of an array, and N and M are variables that can vary on context or be dependent one to the other.
In python
myArray[N], myArray[M] = myArray[M], myArray[N]
There are more sorting methods but IB wants you to know these:
Bubble sort
Bubble sort works by comparing pairs of elements, if they match they swap, if not, we continue looking.
More info on that here:
https://www.geeksforgeeks.org/bubble-sort/
Citing them:
In Bubble Sort algorithm,
traverse from left and compare adjacent elements and the higher one is placed at right side.
In this way, the largest element is moved to the rightmost end at first.
This process is then continued to find the second largest and place it and so on until the data is sorted.
The complexity is
Generic implementation in IB pseudocode
MY_ARRAY [X] //array of x elements
loop I from 0 to X-2
loop J from 0 to (X-2)- I
if MY_ARRAY[J] > MY_ARRAY[J+1] then
TEMP = MY_ARRAY[J]
MY_ARRAY[J]=MY_ARRAY[J+1]
MY_ARRAY[J+1] = TEMP
end if
end loop
end loop
WHY -2 ?? ? QUESTION MARK ?
Remember that we are looking into pairs of elements. So, if we're looking to the element J and the next, J+1, the last element index is J+1. The last index is X-1 so the maximum value of J is X -2
Using math:
Selection sort
More info here:
https://www.geeksforgeeks.org/selection-sort/
Selection sort is a simple and efficient sorting algorithm that works by repeatedly selecting the smallest (or largest) element from the unsorted portion of the list and moving it to the sorted portion of the list.
Sort of sorting exercise
(similar to Nov 2018)
We have 2 parallel arrays: FIRSTNAMES [6000] and LASTNAMES [6000]. They hold the information of the last 6000 people that want a ticket to go to a concert of Coldplay. Since we want to use binary search to get the information of these people, we need to sort these arrays.
(source I think that 6000 is maybe too few)
Construct in pseudocode an algorithm that sort these arrays by last name using bubble sort (A not very good idea but you have to follow orders). Take into account that you will also need to change the first names so the arrays keep being parallel.
Credit Y.C.
loop I from 0 to 6000 -2
UNSORTED = false
loop J from 0 to 6000 -2 - I
if LASTNAMES[J] > LASTNAMES[J+1] then
TEMP1 = LASTNAMES[J+1]
TEMP2 = FIRSTNAMES[J+1]
LASTNAMES[J+1] = LASTNAMES[J]
FIRSTNAMES[J+1] = FIRSTNAMES[J]
LASTNAMES[J] =TEMP1
FIRSTNAMES[J] = TEMP2
UNSORTED = TRUE
end if
end loop
if NOT UNSORTED then
break
end if
end loop
Credit L.C. (with edit)
Construct in pseudocode an algorithm that sort these arrays by last name using selection sort (A not very good idea but you have to follow orders). Take into account that you will also need to change the first names so the arrays keep being parallel.
FIRSTNAMES[6000]
LASTNAMES[6000]
LOOP MIN FROM 0 TO 5998
I = MIN
LOOP CURRENT FROM MIN+1 TO 5998
if LASTNAMES[CURRENT]< LASTNAMES[I] then
I = CURRENT
end if
end loop
if I != MIN then
TEMP = LASTNAMES[I]
LASTNAMES[I]= LASTNAMES[MIN]
LASTNAMES[MIN] = TEMP
TEMP = FIRSTNAMES[I]
FIRSTNAMES[I] = FIRSTNAMES[MIN]
FIRSTNAMES[MIN] = TEMP
end if
end loop
Credit A.P. (with edit)
Sorting exercise 2
We have an array of the grades of students. There are 2 parallel arrays, one is NAMES and the othere is GRADES (50 students). The grades are integers that go from 1 to 7 (IB style)
First we want to order the Students so the students with the best grades are in the first part of the array and the last are the ones with lower grades.
Construct an algorithm that using selection sort sort both arrays.
Construct an algorithm that using bubble sort sort both arrays.
DOUBLE UP
This is just for practice. I don't recall any problem with 2 levels of order in an IB exam.
In the same context (NAMES, GRADES, 50 elements)
Now we want to order not only by grades (that we have from 1 to 7 but we want also a sub-order that is going to be by name) so if there are 2 students with the same grade, the first in the alphabetical order will be displayed first.
For this one we are going to order it by parts. We need to detect if they are the same and them use a function to sort the sub-arrays.
loop I from 0 to 48
UNSORTED = false
loop J from 0 to 48 - I
// remember that this is lesser than!
if GRADES[J] < GRADES[J+1] then
//SWAPPING
TEMP1 = GRADES[J+1]
TEMP2 = NAMES[J+1]
GRADES[J+1] = GRADES[J]
NAMES[J+1] = NAMES[J]
GRADES[J] =TEMP1
NAMES[J] = TEMP2
UNSORTED = TRUE
end if
end loop
if NOT UNSORTED then
break
end if
end loop
//Now Grades is sorted and names is mostly sorted
CURRENT_INDEX = 0
loop I from 1 to 48
if GRADE[CURRENT_INDEX] != GRADE[I]
loop J from CURRENT_INDEX to I -1
loop K from CURRENT_INDEX to I -1 -J
// we're looking for alphabetical order
// so we swap in the other case
if NAMES[K] > NAMES[K+1] then
TEMP = NAMES[K]
NAMES[K] = NAMES [K+1]
NAMES[K+1] = TEMP
//we don't need to update grades because they yave the same value!
end if
end loop
end loop
CURRENT_INDEX = I
end if
end loop
