Lecture notes
Complete Computer Science Theory Notes for AS/A Level
- Module
- Institution
- Book
Complete computer science notes. Achieved an A grade by using these notes.
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
More summaries for
-
Information Representation
-
Topical Lecture A level notes , Cambridge International AS and A Level Computer Science (9806)
-
CIE AS Computer Science Paper 1 notes
Seller
Follow
martamelero
Content preview
Computer Science Theory NotesDATA REPRESENTATION
User defined data types are necessary because whenever a program gets reasonably large,
their use makes the program more understandable and less error prone.
● *Note* While a simple built-in/non-composite data type may be the same for any
program, there can not be a “record” type due to the fact that for every problem there will
be a different set of values.
Non-composite user defined data types: Does not involve reference to another type.
● Enumerated- Defines a list of ordered values/items in a collection.
TYPE
Days = (Monday, Tuesday, Wednesday, Thursday, Friday, Saturday,
Sunday)
ENDTYPE
Variables can then be declared and assigned using this data type. They can also be
processed, as each variable defined within the data type is ordinal, IF statements are
possible.
DECLARE DayOfTheWeek : Days DECLARE DayOfTheWeek : Days
DECLARE Weekend : Boolean IF DayOfTheWeek = Saturday OR
IF DayOfTheWeek > Friday DayOfTheWeek = Sunday
Weekend = TRUE THEN
ENDIF OUTPUT “Weekend”
ELSE
OUTPUT “Weekday”
ENDIF
When assigning variables certain values defined within the data type, in pseudocode it
would be as always (FirstDayOfWeek ← Monday) but in programming language, it would
be FirstDayOfWeek = Days.Monday.
● *Note* the user defined data type is mentioned when assigning the variable.
● Pointer- Used to reference a memory location.
It is useful because it saves space, since reserving storage as you would do with an
array can be potentially wasteful. An array declaration statement will reserve memory for
the storage of data, for example 100 storage spaces. These 100 storage spaces each
reserve memory spaces for whichever amount of data items to be used. These 100
spaces could be either not enough or too many, therefore wasting storage space. With
the use of a pointer data type, main memory will be allocated as and when required at
1
, run-time instead of in advance, allowing dynamic memory allocation. A pointer stores the
memory location of of a certain variable.
TYPE
MyPointer = ^Variable
^Variable provides a value which points to data Variable stored in memory.
DECLARE Pointer : MyPointer ”^” is not required
DataPointedTo ← Pointer^ Data is being deferenced. The data held
within the memory location pointed to by
Pointer is assigned to DataPointedTo.
Composite user defined data types: Reference to at least one or more other types.
● Set- Allows program to create sets and apply mathematical operations defined in set
theory which include:
○ Union
○ Difference
○ Intersection
○ Include/exclude element to/from set
○ Check whether element is in set
It’s useful because it condenses pseudocode statements and lets you apply
mathematical operations.
Consider a menu driven program with options 1-7 which redirect you to different places.
Method 1: Alternative method using sets:
DECLARE Choice : Integer TYPE
IF Choice = 1 OR Choice = 2 OR … OR ValidChoice = SET OF (1,2,3,4,5,6,7)
Choice = 7 ENDTYPE
THEN
… DECLARE Choice : Integer
● *Note* Long winded IF statement. IF Choice IN ValidChoice
THEN
…
● *Note* Condensed
● Record- Allows to collect together a fixed number of components of different data types
to form a coherent whole.
2
, It is one of the most useful types therefore one of the most used. Often, applications
need more than one data value of different types, hence why this data type is so useful.
TYPE
EmployeeRecord
DECLARE EmployeeFirstName : STRING
DECLARE DateEmployed : DATE
DECLARE Salary : CURRENCY
ENDTYPE
When accessing an individual data item, dot notation can be used. For example, to
access the first name of an employee, assuming that it is stored in an array in array
location 1 you would use Employee(1).EmployeeFirstName ← “Mike”.
● Class and object- In object oriented programming, a program defines the classes to be
used which are all user-defined data types. (Look at practical notes).
File organization and access:
● Serial file organization- Contains records without a defined order other than
chronological. The records can only be red from the file in order.
○ Useful to record bank transactions, as every time the user interacts with the
account, it would be recorded. The records would enter in chronological order, no
other type of organization is necessary.
They can only be accessed sequentially, meaning that in the case you have, for
example, 13 records, in order to read the 12th you would have to read the previous 11
first.
● Sequential file organization- Contains records with a defined order. It is the type of file
suited for long term storage of data, as it is considered the alternative to a database. For
this matter, a sequential file can be used as a master file to a serial file. In order to allow
a certain order there has to be a key field for which the value is unique and sequential
but not necessarily consecutive. (Different to primary key in a database as this doesn’t
need to be sequential.) A particular record is found by sequentially reading the value of
the key field until the required value is found.
○ For its use as a master file in the baking scenario, it could manage an individual
customer account. Periodically, the transaction file would be red and all the
affected customer account master files would be updated.
Can be accessed both sequentially or directly.
○ Sequentially: Acts in the same way as when accessing a serial file sequentially.
○ Directly: the sequential file needs to have been created with fixed length records
and in conjunction with an index file. This index file is stored in memory to allow
the fast access to the values and the index position in the fixed length sequential
3
, file. The software will then set up a file pointer by multiplying its index position by
the number of bytes saved for each record and therefore retrieve the value to be
found.
● Random file organization/Direct file organization- Random referring to the fact that that
the access is not defined by a sequential reading of the file. Data can be both written
and read in the same session. Suitable for large files because of the access time
compared to other file organization methods. Each record is given an address in the
form of a record key which can be allocated as an integer, or it can be hashed in some
way. Data cannot be located immediately using an identifiable record, instead, direct
access to a nearby record, followed by a limited serial search may be required.
○ Hashing algorithm- Position is calculated by taking as an input the value for the
key field, altering it in some way and outputting a value for the position of the
record relative to the start of the file. The algorithm must take into account the
maximum length of the file. The reason why a limited serial search may be
necessary is because if the calculation applied to the key field outputs a number
that already exists, then the record will be stored in the next position.
Can be accessed directly using either its known record key or a hashing algorithm.
Binary floating point representation: A representation of real numbers (containing a decimal
part) that stores a value for the mantissa and a number for the exponent.
● When more bits are allocated to the MANTISSA = greater accuracy.
● When more bits are allocated to the EXPONENT = greater range of numbers can be
represented.
○ The alternative to this would be using fixed point representation, which isn’t as
effective as a smaller range of numbers is able to be represented. This uses a
number of bits for the whole number part and a number of bits for the fractional
part.
It is important to keep in mind that the binary representation of a number may be only an
approximation, resulting in loss of accuracy and possibly a rounding error.
Floating point representation example- 11.5
1. Convert 11.5 into binary using fixed point representation
2. How many places do you need to move the decimal point in order for it to be
normalized (most significant bit=0)? Answer = EXPONENT
● *Note* Take into account the number of bits provided for the mantissa and the
exponent. For the mantissa, put 0s to the right until it is the number of bits
required. For the exponent, put 0s on the left.
1 0 1 1 (.) 1
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller martamelero. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £5.29. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
50064 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now