Algorithms

Designing an Algorithm:

-specify what you must accomplish
-Design the algorithm
-Check the correctness(dry run / trace table)
-Analysis of the algorithm
-implement the algorithm
-Test the resulting program

All possible inputs of an algorithm are known as the domain
All possible outcomes of an algorithm are known as the codomain

A Basic Algorithm:
Input x --> algorithm f --> output y

recursion

• recursion is a method or function that calls itself .
• it is a type of iteration
• it must have a stopping condition to prevent endless loops
• there are two types
• tail when the last thing that happens Is the recursive call
• head , when it happens first

Post Mock revision comp 1

• scheduling
• types of scheduling
• purpose of an OS

Post Mock revision comp 2

• algorithm
• select case statements

Software cycles

Software cycles
waterfall model

feasibility study
Technical - does technology exist to solve the problem ?
Economic - Is it within the budget of the firm?
Legal - needs to comply with laws
Operational - can the system be run?
Time frame schedule - can it be done on time? (within time frame)

Analysis
The results of fact finding ,
a requirement specification or a user requirement document

Design

Implementation
a solution is created

Testing
an outline of the test strategy
results of all testing that has been carried out
an actions required after testing

Installation
This involves installing the new system or instructions how to do it

Evaluation
A time to reflect on the project

Maintenance
Could include releasing updates or fixing broken hardware
can continue for years
could be the most expensive phase of a project.
 

 

Advantages of the waterfall model

• This model is used only when the requirements are very well known, clear and fixed.
• Product definition is stable.
• Technology is understood.
• There are no ambiguous requirements
• Ample resources with required expertise are available freely
• The project is short.

Drawbacks of the waterfall model

• in the testing stage, it is very difficult to go back and change something that was not well-thought out in the concept stage.
• No working software is produced until late during the life cycle.
• High amounts of risk and uncertainty.
• Not a good model for complex and object-oriented projects.
• Poor model for long and ongoing projects.
• Not suitable for the projects where requirements are at a moderate to high risk of changing.
• you can only do one section at once for example you have to build the whole program before you can test(cant test little parts)

 the waterfall models are likely to be used in defence projects for example air craft carries use them because

 

Spiral model

 

Is a model where each phase is done more than once.it spirals round repeats, there is feedback between each stage - a good example of where the spiral model can be used is when there are many customizations that are needed and will need to be altered many times before commercial release.





Rapid application development (RAD)

They use Prototypes in order to test it to make sure it is feasible in realistic circumstances and see how it is accepted with the clients , it also enables feedback and improvements as they can keep making new small prototypes until the finals product is created.
Clients get to see something very quickly instead of waiting  5 years to find out its not how they wanted it



Extreme programing (XP)

Pair programming is when people work in a team of two and question each other and test each other in order to improve the productivity and output
Test driven development - tests that are made before the development thinking about tests before starting coding and planning ahead
continuous





Agile methodologies
A sprint is a task that takes no more than two weeks and is broken down into smaller tasks
Scrum is a small team of no more than seven people each people has a different task. At the start of the day they have a meeting of what they are planning
this means problems issues and risks are solved each day being in a constant  cycle of building and testing so if the environment changes its fine because they can adapt

binary subtraction

Sign and Magnitude

The most significant bi(MSB) is simply to represent the sign : 1 means the number is negative 0 means its positive

-4 as binary is exactly the same as denary to binary but we change the last number
10000100 = -4
00000100 = 4
replace last number with 1 or 0 but it then means you can only represent with 7 bits
can only represent -127 to 127 as the 8 bit is wasted changing the negativity
or -255 to 255


Twos complement - if it is in twos complement then it will change the whole binary number
more efficient as you use the whole number range.
e.g to work out 90
you first work it out in binary 01010110
you then have to make - 90
you leave all numbers until first 1 and leave it (then invert all of them)
01010110
10101010

most significant part is negative for example
-128 64 32 16 8 4 2 1
 1      0    1   0  1 0 1 0


floating point numbers in binary

Floating point binary is used to hold really big, really small or really accurate
numbers using just 8 bits.

Using the example 0.92 × 10 squared , 0.92 is the mantissa, 10 is the base and 2 is
the exponent.

The mantissa is the part of the floating point number that represents the
significant digits of that number.

The exponent is the power to which the number in the mantissa is to be
raised.



The larger number of bits used in the mantissa will allow a number to be represented
with greater accuracy, however this will reduce the number of bits in the exponent and
consequently the range of values which can be represented.

maintissa = accuracy
exponent = range

Data structures

Data structure

Simple way of representing the data held in a computers memory .There are hundreds of different data structures available to program

 

• One dimensional arrays

• Two dimensional
•  Three dimensional arrays
• Records
•   Tuples
•  Lists
•   Stacks
•  queues

Two types of data structures are static or dynamic

Static - size of the disk doesn’t change, they are easy to program and you always know how much space they will take up

Memory is allocated at compile time and is fixed size

- Memory allocation is fixed so there will be no problem adding or removing data items

- Can be very inefficient as the memory for the data structure has been set regardless of whether it is needed or not when the program is executing

- Easier to program as there is no need to check on data structure size at any point

Dynamic – on the other hand do not have a limited size and can expand or shrink as needed, they tend to be more complex to implement

- Memory is allocated to the data structure as the program executes
- The structure can overflow and exceed its allowed limit or underflow should it become empty.
- Makes the most efficient use of memory as it only uses what it needs
- Harder to program as the software needs to keep track of size and data items at all time

 

Big O notation is how efficiency is measured of data structures

http://www.bigocheatsheet.com

1D – a row of data (e.g. list of names)

2D – 2 rows of data (x and y) e.g. 3x4 grid

3D- cube of data e.g. 3x3x3 grid

 

All have a unique identifier e.g. Names
- All of the same data type
- All elements of the array have an index number starting at position 0.
- To access or change data you simply call the index number of the data you want
- Arrays are static data structures so their size cannot be changed after they are compiled
- To refer to 2D arrays you must use 2 index numbers which correspond to the x and y coordinates of the table
- For 3D again 3 index numbers of the x, y, z coordinates in the table
- Array values are stored in a contiguous way (one after the other) and 2D arrays are allocated in row  order (first row then second etc)
- They can be global or local variables
- It is impossible to remove all elements from an array once it has been created however you can set the elements to NULL (None in Python) instead


Searching for arrays
array values are stored in contiguous memory locations and 2D arrays are allocated in row-major order .


for loop knows how many times it needs to loop
while loop doesn't know how many times to loop

in python none = blank space

Records
a record is used to organise date by an attribute for example to store data for an address book the attributes could be the first_name_second_name
The data in this record is accessed through its name for example
first name.
The data in a record is unordered data structure but indices may be programmed to provide that data ordered on a particular field

Lists and tuples
lists and tuples are pythons versions of arrays and share may similarities but have minor differences

Tuples:
- Similar to records used to group together related values
- Similar to a 1D array
- Tuples cannot be edited once they have been assigned (immutable)
- Commonly used where it is important that data can be accessed and not changed
- Can contain values of different data types
- Items are retrieved again using an index, the same as an array
- Trying to assign a new value to the tuple will produce an error message
student = ('James', 'Smith', '30/01/2000', 'Computer Science') - TUPLE USES ()


 Lists:
- Can contain values of different data types
- Can be edited after they been assigned (mutable)
- Uses an index number to retrieve data - harder to use than attributes in records and less user friendly

A list is a simple structure of data that is cross between tuples and arrays . like tuples , lists can hold a range of data types but like arrays their elements can be edited (mutable)once they have been initiated . in principle a list is an ordered set of data organised by an index , so accessing the data is through an index value for that data.
 [list use square brackets]

when comparing lists and records the ability that records face to identify data by attributes rather than index does make the record structure more user friendly in use while being more complex to initialise.

CRAIGNDAVE FAM



STACKS
Stacks:
- Good for linear data
- LIFO data structure (last in, first out) -  add from the top and remove from the top (pile of pancakes)
- Adding data to a stack is called pushing
- Removing data is called popping
- Stacks are implemented into programs using a variable that points to the top of an array each time data is added or pointers within a computers memory.
- A pointer is used to locate the top of the stack starting at 0 and keep track of the top of the stack
- A stack overflow could happen if you are trying to push data into a full stack or if you try to pop data into an empty stack then an error will occur






IF stack pointer = maximum
         THEN report stack full
ELSE
         Increase stack pointer by +1
         set stack (stack pointer to data)
END IF


IF stack pointer = minimum
         THEN report stack empty
ELSE
        set data too stack (stack pointer)
        decrease stack pointer by -1
END IF



Queues:

 - FIFO (first in, first out) - most recent piece of data is therefore the last to be taken out
- The data within a queue does not physically move forward in the queue, instead two pointers are used to denote the front (data removed) and back (data added) of the queue.
 -the pointers move in memory location not the data
-queues unlike stacks are a circular data structure







- data can be pushed and popped like stacks , (the start and end pointer moves)
- the structure will allow the pointers to loop round as its circular meaning the end point can look like its before the start
-
 Q2 A stack contains the values 3, 4, 5, with 3 being the first value stored and 5 the last. Show how the stack changes after the following commands: POP, PUSH 7, POP, PUSH 8, PUSH 9.

start	pop	push 7	pop	push 8	push(9) 9
5		7		8	8
4	4	4	4	4	4
3	3	3	3	3	3

 
A -----------------------------------------


Q3  A queue contains the values 3, 4, 5, with 3 being 3 being the first value stored and 5 the last, Show how the queue changes after the following commands: POP, PUSH 7, POP, PUSH 8, PUSH 9.

A

--

3	4	5			start
	4	5			pop
	4	5	7		push 7
		5	7		pop
		5	7	8	push 8
		5	7	8	9 (push 9)

SCOPE of prgramming

Scope variables ( in mock)

A variable is a storage of data that can be altered and changed at any time
constant is similar however the value cant be changed once it has been entered.
A global variable is accessible form all parts of a program
A local variable is only accessible within a function / procedure.

GOOD Programming
- Using meaningful identifiers for variable names
- Use commenting to aid understanding:
- Avoid use of global variables in favour of local variables.

local variables use less memory as the variable sis gone once the function is
global variables can become confusing as by using the same variable names data would be overwritten