Home Topic 4 Last Next


Discuss an algorithm to solve a specific problem.


Teaching Note:

Students should be expected to discuss the differences between algorithms, including both standard and novel algorithms. For example, discussing the advantages and disadvantages of using a binary search as opposed to a sequential search.


Sample Question - FORMER CURRICULUM:

The account names and telephone numbers of individuals are stored in a sequential file.
It is important the data can be displayed alphabetically according to account name.

((a) Define the term sequential file organization. [2 marks])

(b) Suggest a suitable sequential file organization for this set of data. [2 marks]

(c) Outline how a telephone number can be retrieved from the file if the account
name is known (assume non-repeated account names). [2 marks]

A new telephone number and account name are to be added to the middle of the file.

(d) Given the organization you suggested in part (b), explain the steps that would
need to be undertaken to enable this new data to be added to the file. [3 marks]
Over time, the file becomes very large and there are a lot of additions and deletions
as new telephone numbers and account names are added to the file, and old ones
are deleted.

(e) Outline why sequential organization would not be an appropriate file organization
method in this case. [3 marks]

JSR Notes:

Even before getting to the Teaching Note examples, here's a great example, of a fairy sophisticated algorithm, but, still, one which can be understood. It's the classic "8 Queens on a Chessboard" problem. This can be used throughout these "algorithm" assessment statements.


So, first of all, dealing with the Teaching Note standard example:

Binary search:

Advantage: faster, particularly with large sets of data. The efficiency increases exponentially with the size of the set of data in fact, since with each step, half of the remaining elements are eliminated from the possible location of the search key.

Disadvantage: the data set (i.e. array) has to be sorted, and sorting takes a lot of processing. So this is a particular penalty to pay if the data set will continually change and so continually need to be sorted.

Sequential Search:

Advantage: The data set (i.e. array) does not have to be sorted, so this saves, potentially, a lot of processing.

Disadvantage: It can be slow, particularly for large data sets. The best case scenario is that the key is found with the first step, but the worst case is that it takes the same number of steps as the number of elements in the array to find the (last) element. This makes the average number of search steps to be n/2, with n the size of the array.


Other potential algorithms to discuss:

The bubble-sort vs. the selection sort.

The various "smart", and "smarter" bubble-sorts and selection-sorts.

(Later, iterative vs. recursive algorithms, like with the binary search.)

Other common algorithms, like finding the average in an array of elements, or the smallest/largest of them.

Looping through a 2D array.