1. Fundamentals of algorithms

Question 1

Define algorithm (important)

Answer 1

An algorithm is a sequence of steps that can be followed to complete a task

Question 2

An algorithm that can be translated into any programming language is …

Answer 2

Language independent

Question 3

What is the focus on in an algorithm, and what is it not on?

Answer 3

Whether algorithms are designed with pseudo-code or flowcharts, the focus is on the logic of the steps instead of the programming language because programmers should be able to translate an algorithm into any programming language, for example, from Python to C++.

Question 4

What is processing ?

Answer 4

Processing refers to any operation the computer system is performing on data, for example doing a calculation or searching for something.

Question 5

Flow chart symbol:

Represents the flow from one component to the next

Answer 5

Arrow(/line)

Question 6

Flow chart symbol:

Process - an action

Answer 6

Square box

Question 7

Flow chart symbol:

Subroutine

Answer 7

Rectangle with a vertical line on each side

Question 8

Flow chart symbol:

Input/output

Answer 8

Parallelogram

Question 9

Flow chart symbol:

Decision (yes/no/true/false decision)

Answer 9

Diamond

Question 10

Flow chart symbol:

Start/Stop (terminator)

Answer 10

Oval

Question 11

Decomposition definition

Answer 11

Decomposition means breaking a problem into a number of sub-problems, so that each sub- problem accomplishes an identifiable task, which might itself be further subdivided.

Question 12

Decomposition definition (Important)

Answer 12

Decomposition means breaking a problem into a number of sub-problems, so that each sub- problem accomplishes an identifiable task, which might itself be further subdivided.

Question 13

Abstraction definition (important)

Answer 13

Abstraction is the process of removing unnecessary detail from a problem

(so that the important details can be focused on. This can make solving the problem easier.)

Question 14

Real life example of abstraction

Answer 14

An example of abstraction is the London Underground map. It details tube lines, services that run on them and the stations. This is all that is required for a passenger to be able to plan a journey from one station to another. Other details, such as real geographical location, distance between stations, depth underground and number of platforms are not included as they are irrelevant to journey planning on the Underground.

Question 15

What is ‘dry running’ an algorithm (definition not important)

Answer 15

Dry running an algorithm means to assign the values to variables of an algorithm and to do any processing that takes place without translating it into code.

Question 16

2 ways to determine the purpose of an algorithm

Answer 16

Trace tables, visual inspection

Question 17

When are trace tables used?

Answer 17

Used when testing a program to record changes in variable values as code executes.

Question 18

Contract a trace table.
Input is 5.

num ← USERINPUT
FOR number ← 1 TO 10
OUTPUT number * num
ENDFOR

Answer 18

Num Number Output
1 5 5
2 10
3 15
4 20
5 25
6 30
7 35
8 40
9 45
10 50

Question 19

When to use visual inspection?

Answer 19

Some algorithms follow a pattern that can be recognised. Many of these are referred to as standard algorithms and often follow a set pattern for searching for or sorting data. Sometimes it is clear what this is just by looking at the pseudo-code.

Question 20

When to use visual inspection? (Don’t need to remember:
‘Students should be able to use trace tables and visual inspection to determine how simple algorithms work and what their purpose is.’)

Answer 20

Some algorithms follow a pattern that can be recognised. Many of these are referred to as standard algorithms and often follow a set pattern for searching for or sorting data. Sometimes it is clear what this is just by looking at the pseudo-code.

Question 21

Pseudo-code algorithm to search through a word and match a letter (hangman)

Answer 21

guess ← USERINPUT
FOR i ← 0 TO LEN(word)
IF word[i] = guess THEN
OUTPUT “found”
ENDIF
ENDFOR

Question 22

What does efficiency look at? (2)

Answer 22

Efficiency looks at how much time it takes to run a particular algorithm and how much space is needed.

Question 23

What does efficiency look at? (2)

Answer 23

Efficiency looks at how much time it takes to run a particular algorithm and how much space is needed.

(But “Exam questions in this area will only refer to time efficiency”)

Question 24

Function of search algorithms

Answer 24

Search algorithms allow data sets to be examined and for specific items to be found

Question 25

Function of sort algorithms

Answer 25

Sort algorithms allow data sets to be put into order

Question 26

2 methods of searching

Answer 26

linear search
binary search

Question 27

2 methods of sorting

Answer 27

bubble sort
merge sort

Question 28

Linear search steps

Answer 28

This is a simple algorithm used to find a value in a list of data. The algorithm runs as follows:

1. Identify a search term.
2. Look at the first item in the list.
3. Compare the item with the search term.
4. Is the current item the same as the search term? If so, the item has been found. If not, move to the next item.
5. Repeat from step two until the last item in the list has been reached.
6. If the end of the list has been reached and the search term has not been found, then the search term is not in the list and the algorithm can stop.

Question 29

Linear search algorithm to search the following list for the number 1:

3, 2, 4, 1, 5

Answer 29

The algorithm would produce:

3, 2, 4, 1, 5 (1 compared to 3 - not found)

3, 2, 4, 1, 5 (1 compared to 2 - not found)

3, 2, 4, 1, 5 (1 compared to 4 - not found)

3, 2, 4, 1, 5 (1 compared to 1- found)

Question 30

Must linear search be ordered? And a problem with this?

Answer 30

Because the linear search algorithm simply moves up the list and checks each item, the data in the list does not need to be in order. However, as the list gets longer the algorithm takes longer to run, making it inefficient for large lists.

Question 31

Linear search pseudo-code (dont need to know, but may be helpful)

Answer 31

find
Not saving for some reason

https://www.bbc.co.uk/bitesize/guides/zm77xfr/revision/2

Question 32

Binary search, must be _?

Answer 32

Ordered.

Binary search is a more complex algorithm than linear search and requires all items to be in order.

With each loop that is run, half of the data is removed from the search. To do this, the algorithm uses the index of items in the list - an index is the number given to the position of an item in a list.

To determine the next item to be checked in a list, the midpoint has to be identified. This is found by adding the lowest index to the highest index and dividing by two, then rounding either up or down to the nearest integer if needed. Whether we round up or down does not matter, as long as within a particular search the same method is applied. For example, if the highest index in a list is 8 and the lowest is 0, the midpoint can be found using the following sum:

Highest index (8) + lowest index (0) = 8

8/2 = 4

Question 33

Binary search steps

Answer 33

The algorithm runs as follows:

1. Start by setting the counter to the middle position in the list.
2. If the value held there is a match, the search ends.
3. If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list.
4. Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
5. The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.

Question 34

Binary search algorithm to search the following list for the number 7:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Trace table.

Answer 34

In a trace table, this would look like:

Search term Start End Mid Found List
7 1 10 5 False [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
6 10 8 False [6, 7, 8, 9, 10]
6 7 6 False [6, 7]
7 7 7 True [7]

Question 35

Binary search algorithm pseudo-code (dont need)

Answer 35

find find then
End

Question 36

When to use linear vs binary searches?

Answer 36

Although linear and binary searching produces the same overall results, linear search is best used when the data is not in order, or for smaller lists. However, when the list is much longer and the data is in order, it is far more efficient to calculate the indexes needed to perform a binary search.

Question 37

Compare binary vs linear search to search the following list for the number 7:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Answer 37

Linear search would require eight steps to find the search term in the list.

In a trace table, this would look like:

Linear search trace table

Search term Index Data Found List
7 1 1 False [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7 2 2 False [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7 3 3 False [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7 4 4 False [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7 5 5 False [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7 6 6 False [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7 7 7 True [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
In contrast, binary search would take just four steps to find the same number.

In a trace table, this would look like:

Binary search trace table

Search term Start Index Data Found List
7 1 10 5 False [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
7 6 10 8 False [6, 7, 8, 9, 10]
7 6 7 6 False [6, 7]
7 7 7 7 True [7]

Question 38

Linear search advantages (4)

Answer 38

Performs well with small and medium-sized lists

Fairly simple to code

The data set does not need to be in any particular order (some algorithms need an ordered list)

It doesn’t break if new items are inserted into the list.

Question 39

Linear search disadvantages (2)

Answer 39

May be too slow to process large lists or data sets

If the search criteria only matches the last item in the list, the search has to go through the entire list to find it.

Question 40

Binary search advantages (2)

Answer 40

Very good performance over large ordered lists.

A binary search takes a maximum of 8 loops to find an item in a list of 1000 items, whilst a linear search worst case would have to search all 1000 items in the list.

Question 41

Binary search disadvantages (3)

Answer 41

Binary search can only work on an ordered list. If the list is random, then a linear search is the only way

It is a bit more complicated than a linear search to code and so for small lists a linear search is just as good.

If it is a constantly updated list with items added or removed, the list will need re-ordering every time which may slow down the overall performance compared to a linear search.

Question 42

What is bubble sort - just what it does.
What is each run known as?
When does the bubble sort stop?

Answer 42

An example of a sorting algorithm is bubble sort. This is a simple algorithm used for taking a list of unordered numbers and putting them into the correct order.

Each run through the list, from start to finish, is known as a pass. The bubble sort continues until a pass is made where no values have been swapped. At this point, the list is sorted.

Question 43

Bubble sort algorithm steps

Answer 43

The algorithm runs as follows:

1. Look at the first number in the list.
2. Compare the current number with the next number.
3. Is the next number smaller than the current number? If so, swap the two numbers around. If not, do not swap.
4. Move to the next number along in the list and make this the current number.
5. Repeat from step 2 until the last number in the list has been reached.
6. If any numbers were swapped, repeat again from step 1.
7. If the end of the list is reached without any swaps being made, then the list is ordered and the algorithm can stop.

Question 44

Use bubble sort to sort the following list:

27, 4, 7, 12, 9

Answer 44

27, 4, 7, 12, 9

The first loop of the algorithm would produce:

4, 27, 7, 12, 9 (4<27 so the two values are swapped)

4, 7, 27, 12, 9 (7<27 so the two values are swapped)

4, 7, 12, 27, 9 (12<27 so the two values are swapped)

4, 7, 12, 9, 27 (9<27 so the two values are swapped)

4, 7, 12, 9, 27 (first pass completed - 27 has ‘bubbled’ to the top of the list)

Values were swapped so the algorithm needs to run again. The second loop of the algorithm would start with the final list and run again as follows:

4, 7, 12, 9, 27 (4<7 so the values are not swapped)

4, 7, 12, 9, 27 (7<12 so the values are not swapped)

4, 7, 9, 12, 27 (9<12 so the values are swapped)

4, 7, 9, 12, 27 (12<27 so the values are not swapped)

4, 7, 9, 12, 27 (second pass completed)

Values were swapped so the algorithm needs to run again. This time there will be no swaps as the values are in order:

4, 7, 9, 12, 27

The algorithm has completed a pass without swapping anything and it knows that the list is now ordered and can stop.

Question 45

Once sorted, does bubble sort do another pass?

Answer 45

Yes.

Once the algorithm has completed a pass without swapping anything and it knows that the list is now ordered and can stop.

Question 46

Bubble sort pseudo-code

Answer 46

data_set ← [9,2,5,23,34,56]
last_exam_position ← data_set.length - 2
swap ← true
WHILE swap == true
swap ← false
FOR i ← 0 to last_exam_position
IF data_set[i] > data_set[i +1] THEN
temp ← data_set[i+1]
data_set[i+1] ← data_set[i]
data_set[i] ← temp
swap ← true
END IF
ENDFOR
END WHILE
OUTPUT “List is now in ascending order.”

Question 47

How to change this bubble sort to descending order?

data_set ← [9,2,5,23,34,56]
last_exam_position ← data_set.length - 2
swap ← true
WHILE swap == true
swap ← false
FOR i ← 0 to last_exam_position
IF data_set[i] > data_set[i +1] THEN
temp ← data_set[i+1]
data_set[i+1] ← data_set[i]
data_set[i] ← temp
swap ← true
END IF
ENDFOR
END WHILE
OUTPUT “List is now in ascending order.”

Answer 47

> becomes < (in IF statement)

Question 48

Merge sort overview - what is it?

Answer 48

Another example of a computer sorting algorithm is merge sort. This is a more complex algorithm than bubble sort, but can be more efficient.

The merge sort algorithm repeatedly divides a list into two until all the elements are separated individually. Pairs of elements are then compared, placed into order and combined. The process is then repeated until the list is recompiled as a whole.

Question 49

Why was merge sort developed?

Answer 49

Although bubble sorts work well on small lists of data, they are inefficient at sorting much larger lists.
The merge sort was developed to handle the sorting of large lists. It does this by breaking them down into multiple smaller lists, quickly sorting them, and then merging them back together into one larger list.

i.e. it is faster to sort these two lists then merge them back together
merge sort
than to sort the list in its entirety.

Question 50

Merge sort is an example of what algorithm ?

Answer 50

Merge sort is an example of a ‘divide-and-conquer’ algorithm because it splits down a larger problem into a number of smaller ones which are then solved. Each solution is then combined in some way to solve the larger problem.

Question 51

Merge sort:

2, 45, 6, 9, 15, 12, 7, 8

Step-by-step

Answer 51

We start off with a list of unordered numbers which we want to sort in ascending order:

[2, 45, 6, 9, 15, 12, 7, 8]

Step 1: Divide the above list into two smaller lists:

[2, 45, 6, 9] [15, 12, 7, 8]

Had there been 9 numbers then we would have a list of 4 items and a list of 5 items.

Step 2: Divide these lists into smaller, equal sized lists (dealing with an odd number if necessary):

[2, 45][6, 9] [15, 12] [7, 8]

Step 3: Continue to split each list until there is only one item per list (or zero in some cases for uneven lists):

[2] [45][6][9] [15][12] [7] [8]

Step 4: Now that the list has been split as far as possible, we can begin to merge and sort the data items:

[2, 45][6, 9] [12, 15] [7, 8]

Two adjacent lists are paired back together and they are sorted (for this example, in ascending order). The ones that changed are the 12,15 pair

Step 5: Two more adjacent lists are merged together and the items within each list are sorted, the red numbers changed position:

[2, 6, 9, 45] [7, 8, 12, 15]

Step 6: This process of merging and sorting lists continues until all of the individual lists are merged together and just one list remains. Within this list, all of the data items will be sorted into the correct order:

[2, 6, 7, 8, 9, 12, 15, 45]

Question 52

How do the comparisons work in merge sort (explanation is a bit unclear, and dont need to know)

7 11 10 5 12 4 18 15

Answer 52

7 11 10 5 12 4 18 15

The algorithm looks at the individual elements and compares them as pairs. Each pair is sorted into order:

The top row shows numbers arranged in pairs. 7 and 11, 10 and 5, 12 and 4, 18 and 15. The bottom row shows the pairs arranged with the smaller number first. So 7 and 11, 5 and 10, 4 and 12, 15 and 18
The pairs are then compared, starting with the first number in each pair. If the left hand number is smaller than the right hand number, it is placed in order. The comparison then moves up to the second number on the left hand side and the process repeats. If the right hand number is smaller, it is placed in order and the comparison moves to the next number on that side.

Here, 7 is the first left hand number and 5 is the first right hand number. 7 is bigger than 5, so 5 is placed in order:

5

The next right hand number is 10. 7 is smaller than 10, so 7 is placed in order:

5 7

The next left hand number is 11. 11 is bigger than 10, so 10 is placed in order:

5 7 10

There are no more right hand numbers to compare, so the remaining left hand numbers are placed in order:

5 7 10 11

Question 53

Bubble sort pros (3)

Answer 53

Simple to write the code for.

Simple to understand.

The data is sorted in the same memory location that it is held, so you don’t need much extra memory to run the algorithm.

Question 54

Bubble sort con (1)

Answer 54

One of the slowest ways to sort a list. For example, if the list becomes ten times larger than before, it takes almost a hundred times longer to sort. So this method of sorting is very sensitive to the length of the list.

Question 55

The ‘divide-and-conquer’ algorithm is an example of

Answer 55

Recursion

With a ‘divide-and-conquer’ algorithm, there is a lot of repeating the same steps in a similar way. In this case the algorithm says ‘Keep on dividing the list’ and ‘keep on merging and sorting’.
The statement ‘keep on …’ is a very common and powerful idea in computer programming. There is a word for it: ‘recursion’.
A recursive procedure is one that calls itself with slightly different arguments until a stop condition is met.
In order to code the merge sort algorithm efficiently, a recursive procedure is used that keeps on splitting the list and another one is used that keeps on merging and sorting the lists.

Question 56

Merge sort pseudo-code (definitely do not need)

Answer 56

procedure mergesort( var a as array )
if ( n == 1 ) return a //the list has been split so it is only one length long, so return the list

var list_1 as array = a[0] … a[n/2] // split the passed array into two lists
var list_2 as array = a[n/2+1] … a[n]

list\_1 = mergesort( list\_1 ) // split the list again by recursion
list\_2 = mergesort( list\_2 )

return merge( list\_1, list\_2 ) // use the merge procedure to re-combine and sort the list pair
end procedure

procedure merge( var a as array, var b as array ) // it accepts two incoming arrays

var c as array // use a temporary array to hold sorted items

while ( a and b have elements )
if ( a[0] > b[0] ) // begin to sort
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
end if
end while

while ( a has elements )
add a[0] to the end of c
remove a[0] from a
end while

while ( b has elements )
add b[0] to the end of c
remove b[0] from b
end while

return c // a combined sorted list is returned

end procedure

Question 57

Merge sort pros (2)

Answer 57

It is the fastest of three types of sort (bubble, insert, merge)

It is the best option to use for long lists of data (more than 1000 long)

Question 58

Merge sort cons (2)

Answer 58

More complicated to code compared to bubble and insert

It may use twice the memory size of the list - depending on the way it is coded. This becomes important if the list is millions of items long.