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