A-level Computing/WJEC (Eduqas)/Component 1/Algorithms and programs

From Wikibooks, open books for an open world
< A-level Computing‎ | WJEC (Eduqas)
Jump to navigation Jump to search

Algorithms:

An algorithm is a finite set of instructions to solve a specific problem. There are two main methods to represent an algorithm, which are Pseudocode and flowcharts.

Representation[edit]

Pseudocode[edit]

Pseudocodes are algorithms written in a 'generic' language. They are written with no one programming language in mind, but rather with the aim of being in a form closer to plain English. This allows the programmer to understand the logical and algorithmic side of a solution without having to worry about the nuances of a coding language. There is no one standard way to write psudeocode. Instead, it borrows ideas, basic functions and crude semantics from a wider range of languages. Providing pseudocode is unambiguous, and the basic rules of any programming language are adhered to (such as variable declaration and statement completion) and is accepted as a standard.

Flowcharts[edit]

Flowcharts are a method of visually representing an algorithm. This is done by use of a diagram, beginning at a start label and following lines between various statements and questions that are enacted and adhered to until an endpoint is reached.

Each different instruction type is represented with a different shape: the start and end points are usually represented with an oval or a rounded rectangle, a process (such as a calculation) takes place within a rectangle, input is taken in by a trapezium, a parallelogram represents output, and a diamond (rhombus) is used to represent a decision. A decision-diamond will be where the path through a flowchart forks, with two lines coming out from it, which are usually labelled YES or NO. When following a flowchart, the correct line is selected based on the answer to the question written on the decision-diamond itself.

As you can probably tell, a flowchart quickly becomes complex for larger programs, can take a while to create with sufficient complexity, and is often laborious to follow. As a result, flowcharts are generally only used for smaller, less complex problems.

Contents[edit]

Parts of an algorithm[edit]

Any part in an algorithm can be belonging to one of three defined types. The first of these is the sequence, which is any set of instructions that must be followed in order, such as calculations. It is vital to understand the possible calculations used in a program, and so they are listed here.

Operator Symbol Description Example
Addition + Adds two values 3+4=7
Subtraction - Takes one value away from the other 7-4=3
Multiplication * Multiply one value by the other 3*4=12
Division / Divides one value by the other 12/4=3
Integer Division DIV or \ Divides one value by the other, returning only the whole number 10DIV3 = 3
Modulo MOD Divides one value by the other, returning only the remainder 10MOD3 = 1
Negation - Flips the sign on the number -(3) = -3
Exponential ^ Raise the first number to the power of the second 7^2 = 49

The second type is selection. These are statements that determine the output (or what code to be run) based on the given inputs and the logical rules set by the programmer. This is the basic IF statement - IF this is true, then do this ELSE do that. The final part of an algorithm is iteration - where code is intended to be run multiple times, until a terminating condition is met. Examples include the FOR loop, which will repeat for a set number of time, and the WHILE loop, which repeats while a certain condition is true.

Each part of any algorithm depends on variables for data storage. A variable is a named location in a computer's memory that can be used to store data while a program is running, which can then be called upon later. This is stored with a computer's RAM, which is labelled with memory addresses starting from 0. Variables are usually assigned names within a program, with specific details of storage location being left to the translator. Along with the information it stores, a variable has two main qualities - its scope and its lifetime. Simply put, a variable's scope is where in the program it is accessible from, whilst a variable's lifetime is the length of time a variable is accessible for. A local variable has a small scope and a limited lifetime, as it is only accessible within the subroutine that defines it, whilst a global variable, which exists for the entire length of the program, will have a large scope and a long lifetime.

Similar to variables, constants also play a role. These hold a fixed value within a program, unlike a variable, which can be changed at any time. A constant is instead defined at the very start of a program, and will hold the same value throughout, going as far as throwing an error if any part of the program tries to change it. This prevents accidental changes to a constant, but by defining it in this way, if it ever needs changing, it can be reassigned by the programmer simply by changing the line in which it is defined. Important constants include PI, VAT rate and HTTP error codes, some of which are shown below.

Code Meaing
400 Bad Request
401 Unauthorised
402 Payment Required
403 Forbidden
404 Page not found

Subroutines[edit]

Large programs can also be broken into named blocks of code that carry out specific tasks. These are subroutines, and are important as, once defined, a subroutine can be called upon to perform its task at any point within a program. This makes them ideal for solving problems where the same sequence of instructions will need to be repeated throughout. Most languages use two types of subroutine - functions and procedures. Both act very much in the same way, except for the crucial detail that a function must return a single value to the main body of the program, while a procedure doesn't. This distinction is normally made clear in the way functions and procedures are defined.

Both types of subroutine rely on parameters to pass values into (and out of) themselves. These can either be passed by value, where the subroutine is told the value of the parameter, but isn't told the location (in effect, only passing a copy), or through a pass by reference, where the subroutine is told the memory address of the variable it wants to use. The key difference is that any changes made to a pass by reference parameter are kept once the subroutine has ended, whilst the changed made to a pass by value parameter are not permanent, they're only accessible during that pass of the routine.

A key advantage of subroutines is the ability to harness the power of recursion. This is where, during the course of its commands, a subroutine calls itself. This has the effect of opening a new copy of the subroutine, putting the current one on the top of a stack, to be returned to later. This will repeat until a base case it met, at which point the current recursion of the subroutine carries out the rest of its statements and then ends, allowing the previous recursion to finish its commands, and so on, until all the subroutines have been taken off the stack. Recursive subroutines provide an efficient way to carry out an operation multiple times in sequence, and can be cleverly implemented to quickly solve more complex problems (see Tower of Hanoi, which can be solved by recursively solving for one disk less each time, until the problem is reduced to moving a single piece).

Comments[edit]

Comments, sometimes called annotations, are pieces of English that are inserted into code. They describe how the code works to other developers, but are not needed in any way for the program to run. When the program is being compiled, the comments and any whitespace within them is discarded.

/* This sets the background colour of the page to be orange. Might be a bit garish, but still. */
body {background-color: orange;}

Self-Documenting Identifiers[edit]

To avoid having to describe what code does to the unseasoned reader, developers use self-documenting identifiers. These document what they do in the name, hence the way we describe them. For an example of a self-documenting identifier, see the previous comment example. The 'background-color' CSS property defines exactly what it is changing, so it is not usually commented upon. If developers commented every color, the comments wouldn't be of much help - be sparing, but include comments when absolutely necessary to document your code.

Program Layout[edit]

Some languages explicitly require you to lay your code out in a certain way in order for it to work. However, others are rather lax in their approach. Good program layout requires you to indent your code and conform to certain standards such as putting spaces between operators. Some companies prefer writing in camelCase and others in Snake_Case, but whichever you use, you should stick to it throughout your entire coding project. See below for a idea of what is meant by program layout.

if CodeLayoutCheckPassed = 1 then
       codeIndented = 1
       selfDocumentingIdentifiersUtilised = 1
else
       codeIndented = 0
       selfDocumentingIdentifiersUtilised = 0
end if

This would be less preferable, as you can't see the different paths the program could take:

if CodeLayoutCheckPassed=1 then
code_Indented=1
self_Documenting_IdentifiersUtilised=1
else
code_Indented=0
self_DocumentingIdentifiersUtilised=0
end if

User Input[edit]

Validation[edit]

Validation occurs before any data has been committed to storage, this can be performed client-side via Javascript usually and server-side by checking it meets the criteria. Some common examples are: presence check where the input cannot be NULL (nothing), a length check to ensure input meets a character limit/requirement (enforced on password fields), format check to ensure data is entered a certain way (an email must have an @ sign) or a character check to check only the accepted characters are input (wouldn't want text in a credit card number).

Verification[edit]

Verification occurs before data is committed into the system, but is in storage. This prevents against any user mistakes, for example mis-typing a password on a registration form. There are two common ones: double entry (for passwords usually) and proof reading, for example when a page is presented with the data before ordering a pizza.

Examples[edit]

Searching Algorithms[edit]

Searching algorithms allow for the location of a certain piece of data - for example a specific user or their group permissions.

Linear[edit]

The target data is compared with each piece of data in the data structure, one by one. If a match is found, it's retrieved. If not, the item is skipped. This is repeated until the end of the data structure is reached.

Declare myArray[0 to 6]
    SearchValue is integer
    Found is Boolean
    set Found = False
    
    input SearchValue
    
    For i = 0 to 6
        if SearchValue = myArray(i)then
        set Found = True
        Output "SearchValue found at position ", i
        end if
    Next i

    if Found = False
        Output "SearchValue not found"
    end if

Binary[edit]

This method makes use of the divide and conquer method, where at every stage the dataset to be searched is halved based on the midpoint.

Declare MyArray[0 to 6]
Declare Start is integer
Declare End is integer
Declare Found is Boolean
Declare Mid is integer

set Start = 0
set End = 6
set Found = False

input SearchValue

    repeat
        set Mid = (Start + End) DIV 2
            if SearchValue = MyArray[Mid] then
                set Found = True
                Output "SearchValue found at position", Mid
            endif

        if SearchValue > MyArray[Mid] then
            set Start = Mid + 1
        endif

        if SearchValue < MyArray[Mid] then
            set End = Mid – 1
        endif

    until (Found = True) OR (End < Start)

if Found = False
    Output "SearchValue not found"
endif

Sorting Algorithms[edit]

Sorting algorithms allow an unordered set of data elements to be organised in a logical manner, for example from largest - smallest or alphabetically.

Bubble[edit]

In a bubblesort, items are moved based on whether they are higher or lower than the next item in the list. This results in the largest item repeatedly "bubbling" to the top of the list, which is where the algorithm gets its name.

Start Procedure SortMyArray
    n is integer
    temp is integer
    swapped is boolean

    set n = length(myArray) {returns the length of myArray}
    repeat
        set swapped = FALSE
            for i = 0 to (n – 1)
                if myArray[i] < myArray[i + 1] then
                temp = myArray[i + 1]
                myArray[i + 1] = myArray[i]
                myArray[i] = temp
                swapped = TRUE
                end if
            end for
   until (swapped = FALSE)

End Procedure

Insertion[edit]

Needs example/explanation.

Quick[edit]

  1. An item/pivot selected (which item is unimportant)
  2. Produce two new lists of smaller and larger numbers
  3. Repeat above points on new sublists (recursively) until sorted
Declare subprocedure QuickSort (myArray is string, indexLow is integer, indexHi is integer)

Pivot is string
tmpSwap is string
tmpLow is integer
tmpHi is integer
tmpLow = indexLow
tmpHi =indexHi
pivot = myArray (int(indexLow + indexHi)/2))

while (tmpLow <= tmpHi)
    while (myArray(tmpLow) < pivot and tmpLow < indexHi)
        tmpLow = tmpLow + 1
wend

    while (pivot < myArray(tmpHi=i) and tmpHi > indexLow)
        tmpHi = tmpHi – 1
    wend

if (tmpLow <= tmpHi) then
    tmpSwap = myArray(tmpLow)
    myArray(tmpLow) = myArray(tmpHi)
    myArray(tmpHi) = tmpSwap
    tmpLow = tmpLow + 1
    tmpHi = tmpHi -1
end if
wend

if (indexLow < tmpHi) then
    QuickSort (myArray , indexLow, tmpHi)
Elseif (tmpLow < indexHi) then
    QuickSort (my Array, tmpLow, indexHi)
end if

end sub