Aims

Markscheme

This is an introduction to Programming projects and sorting algorithms.

The aims for this unit are outlined in the course specification from page 11

Candidates should be able to:

Algorithms

(a) understand algorithms (written in pseudocode or flow diagram), explain what they do, and correct or complete them

(b) produce algorithms in pseudocode or flow diagrams to solve problems.

Programming languages

(c) explain the difference between high level code and machine code

(d) explain the need for translators to convert high level code to machine code

(e) describe the characteristics of an assembler, a compiler and an interpreter

(f) describe common tools and facilities available in an integrated development environment (IDE): editors, error diagnostics, run-time environment, translators, auto-documentation.

Control flow in imperative languages

(g) understand and use sequence in an algorithm

(h) understand and use selection in an algorithm (IF and CASE statements)

(i) understand and use iteration in an algorithm (FOR, WHILE and REPEAT loops).

Handling data in algorithms

(j) define the terms variable and constant as used in an imperative language

(k) use variables and constants

(l) describe the data types integer, real, Boolean, character and string

(m) select and justify appropriate data types for a given program

(n) perform common operations on numeric and Boolean data

(o) use one-dimensional arrays.

Testing

(p) describe syntax errors and logic errors which may occur while developing a program

(q) understand and identify syntax and logic errors

(r) select and justify test data for a program, stating the expected outcome of each test.

Activity 1

Starter Exercise. - work in pairs on this, but everybody needs to have every part of your paired code.

Learning aims:

See aims a,b,g,o,p,q,r

Tasks

Two variables a and b can be swapped by using a temporary variable to store an intermediate, This can be achieved by storing the contents of a in the temporary variable, storing the contents of b in a, and then storing the contents of the temporary variable back into b.

1. Rewrite the algorithm described as a flow chart
2. Rewrite the algorithm described in pseudo code
3. Create a test for your swap function. Remember that you will need to choose suitable input values for your test, and work out what the outcomes should be.
4. Write the function, and show that your test passes

What to hand in

To show completion of this task you should submit a word document with the following:

• Your flow chart
• Your pseudo code
• Your test function (could be a screen shot of your code)
• Your function (again could be a screen shot)
• A screenshot showing successful running of your test.

Note if you don't get it right first time - show the errors you made in your word document, and show the corrected version.

Activity 2

Bubble sort

Work in pairs - But not the same pairs as for activity 1

Learning aims:

To be able to implement a bubble sort. Also see aims a,b,g,h,i,o,p,q,r

Tasks

A bubble sort works by iterating accross a list, and swaping two elements if they are in the wrong order

1. Rewrite the algorithm described as a flow chart
2. Rewrite the algorithm described in pseudo code
3. Create a test for your swap function. Remember that you will need to choose suitable input values for your test, and work out what the outcomes should be.
4. Write the function, and show that your test passes

What to hand in

To show completion of this task you should submit a word document with the following:

• Your flow chart
• Your pseudo code
• Your test function (could be a screen shot of your code)
• Your function (again could be a screen shot)
• A screenshot showing successful running of your test.

Note if you don't get it right first time - show the errors you made in your word document, and show the corrected version.

Activity 3

Selection sort

Work in pairs - But not the same pairs as for activity 1 or 2.

Learning aims:

To be able to implement a selection sort. Also see aims a,b,g,h,i,o,p,q,r

A selection sort works by traversing a list, removing the smallest item, in the first list, and placing it in a new list, then outputting the newly created list at the end.

What to hand in

To show completion of this task you should submit a word document with the following:

• Your pseudo code
• Your test function (could be a screen shot of your code)
• Your function (again could be a screen shot)
• A screenshot showing successful running of your test.

Note if you don't get it right first time - show the errors you made in your word document, and show the corrected version.

Activity 4

Merge Sort

Work in pairs - But not the same pairs as for activity 1, 2, or 3.

Learning aims:

To be able to implement a merge sort. Also see aims a,b,g,h,i,o,p,q,r

A merge sort involves two stages. firstly a list is recursively broken down into its component parts. Then it is build up again, each merge creating a larger sorted list.

This may take more than one function to acomplish.

What to hand in

To show completion of this task you should submit a word document with the following:

• Your pseudo code
• Your test function (could be a screen shot of your code)
• Your function (again could be a screen shot)
• A screenshot showing successful running of your test.

Note if you don't get it right first time - show the errors you made in your word document, and show the corrected version.

Activity 5

Comparing sorting algorithms

Work in pairs - But not the same pairs as for activity 1, 2, 3 or 4.

Learning aims:

To be able to compare merge, selection and bubble sorts. Also see aims a,b,g,h,i,o,p,q,r

Your task here is to compare your three sorting algorithms. The key question here is what makes a 'good' algorithm, and how can you measure the 'goodness' of the algorithm.

Activity 6

Evaluation

Learning aims:

To be able to compare merge, selection and bubble sorts. Also see aims a,b,g,h,i,o,p,q,r

Task

You are to write an evaluation of the project you have completed.

Key questions

1. What did you set out to achieve?
2. Did you achieve the aim?
3. What data types did you use, why did you use them?
4. Could you improve on the algorithms used?

In the second section of your evaluation please complete a self review - (WWW, EBI, LA)