Caie A2 Level Computer Science 9618 Theory v1
Uploaded by
Kiran AliCaie A2 Level Computer Science 9618 Theory v1
Uploaded by
Kiran AliZNOTES.
ORG
UPDATED TO 2022 SYLLABUS
CAIE A2 LEVEL
COMPUTER
SCIENCE (9618)
SUMMARIZED NOTES ON THE THEORY SYLLABUS
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
requirement is for an identifier to be named with a
defined type. They have to be explicitly defined
1. Data representation before an identifier can be created-unlike built-in
data types which include string, integer, real…
==Enumerated Data type:== a list of possible
1.1. User-defined data types
data values. The values defined here have an
When object-oriented programming is not being used, a implied order of values to allow comparisons
programmer may choose not to use any user-defined to be made. Therefore value2 is greater than
data types. However, for a large program, their use will value1(they're not string values and can't be
make a program less error-prone and more quoted). This allows for comparisons to be
understandable. It also has less restriction and allows for made. It is also countable thus finite values.
inevitable user definition. The use of built in data types
TYPE
are the same for any program. However, there can't be a
<Datatype> = (<value1>,<value2>,<value
built-in record type because each different problem will
ENDTYPE
need an individual definition of a record.
1. Composite data types:
DECLARE <identifier> : <datatype>
Composite user-defined data types have a definition with
a reference to at least one other type. ==Pointer Data type:== used to reframe a
==Record Data type:== a data type that contains a memory location. it may be used to construct
fixed number of components that can be of different dynamically varying data structures. The
types. it allows the programmer to collect together pointer definition has to relate to the type of
values with different data types when these form a the variable that is being pointed to(doesn’t
coherent whole. it could be used for the hold a value but a reference/address to data).
implementation of a data structure where one or
more of the variables defined are pointer variables. TYPE
<Datatype> = ^<type name>
TYPE
ENDTYPE
<main identifier>
DECLARE <subidentifier1> : <built in data type>
DECLARE <identifier> : <datatype>
DECLARE <subidentifier2> : <built in data type>
ENDTYPE
<assignment value> ← <identifier>^
<main identifier>.<sub identifier(x)> ← <value>
Special use of a pointer variable is to access
the value stored at the address pointed to. The
==Set Data type:== allows a program to create sets pointer variable is said to be dereferenced.
and to apply the mathematical operations defined in
set theory. Operations like:
1.2. File organization and access
• Union
Contents, in a file of any type, is stored using a defined binary
• Difference
code that allows the file to be used in the way intended. But,
for storing data to be used by a computer program, there are
• Intersection
only 2 defined file types, a text file or a binary file.
A text file contains data stored according to a defined
• Include an element in the set
character code defined by ASCII or Unicode. A text file can
be created using a text editor.
• Exclude an element from the set
A binary file is a file designed for storing data to be used
by a computer program(0's and 1's). It stores data in its
• Check whether an element is in a set
internal representation(an integer value might be stored
==Objects and Classes:== in object-oriented in 2 bytes in 2's complement representation to represent
programming, a program defines the classes to be a negative number) and this file is created using a specific
used-they're all user-defined data types. Then for program. Its organization is based on records (a collection
each class, the objects must be defined. of fields containing data values). file → records → fields →
2. Non-Composite data types: values
Non-composite user-defined data types don’t
involve a reference to another type. When a Methods of file organization
programmer uses a simple built-in type the only
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
==Serial files:== contains records that have no defined different key, the next position in the file is used. this
order. A text file may be a serial file where the file has is why a search will involve direct access possibly
repeating lines which are defined by an end of line followed by a limited serial search. That's why it's
character(s). There's no end of record character. A record considered partly sequential and partly serial.
in a serial file must have a defined format to allow data to File access:
be input and output correctly. To access a specific record, The value in the key field is submitted to the hashing
it has to go through every record until found. algorithm which then provides the same value for the
File access:
Successively read record by record until the position in the file that was provided when the algorithm
data required is found thus very slow.
Uses: was used at the time of data input. It goes to that hashed
Batch processing position and through another short linear search because
Backing up data on magnetic tape of collisions in the hashed positions. Fastest access.
Banks record transactions involving customer To edit/delete data:
accounts every time there is a transaction Only create a new file if the current file is full. A deleted
==Sequential files:== has records that are ordered and is record can have a flag set so that in a subsequent reading
suited for long term storage of data and thus is process the record is skipped over. This allows it to be
considered an alternative to a database. A key field is overwritten.
required for a sequential file to be ordered for which the Uses:
values are unique and sequential. This way it can be Most suited for when a program needs a file in which
easily accessed. A sequential database file is more individual data items might be read, updated or deleted.
efficient than a text file due to data integrity, privacy and
less data redundancy. A change in one file would update Factors that determine the file
any other files affected. Primary keys from the
DBMS(database management system) need to be unique organization to use:
but not ordered unlike the key field from the sequential
files which need to be ordered and unique. A particular How often do transactions take place, how often does
record is found by sequentially reading the value of the one need to add data?
key field until the required value is found. How often does it need to be accessed, edited, or
File access: deleted?
Successively read the value In the key field until the
required key is found. 1.3. Real numbers and normalized
To edit/delete data:
Create a new version of the file. Data is copied from the
floating-point representation
old file to the new file until the record is reached which
Real number: A number that contains a fractional part.
needs editing or deleting. For deleting, reading and
Floating-point representation: The approximate
copying of the old file continue from the next record. If a
representation of
a real number using binary digits.
record has been edited, the new version is written to the
new file and the remaining records are copied to the new Format: Number = ±Mantissa × BaseExponent
file. Mantissa: The non-zero part of the number.
==Direct access/random access files:== access isn't Exponent: The power to which the base is raised to in
defined by a sequential reading of the file(random). It's order
to accurately represent the number.
well suited for larger files as it takes longer to access Base: The number of values the number systems allows a
sequentially. Data in direct access files are stored in an digit to
take. 2 in the case of floating-point
identifiable record which could be found by involving representation.
initial direct access to a nearby record followed by a
The floating point representation stores a value for the
limited serial search. The choice of the position chosen
mantissa and a value for the exponent.
must be calculated using data in the record so the same
A defined number of bits are used for what is called the
calculation can be carried out when subsequently there's
significant/mantissa, +-M. Remaining bits are for the
a search for the data. One method is the hashing
exponent, E. The radix, R is not stored in the representation
algorithm which takes the key field as an input and
as it has an implied value of 2(representing 0 and 1's).
If a
outputs a value for the position of the record relative to
real number was stored using 8 bits: four bits for the
the start of the file. To access, the key is hashed to a
mantissa and four bits for the exponent with each using two
specific location. This algorithm also takes into account
complement representation. The exponent is stored as a
the potential maximum length of the file which is the
signed integer. The mantissa has to be stored as a fixed point
number of records the file will store.
real value.
The binary point can be in the beginning after the
eg: If the key field is numeric, divide by a suitable large
first bit(immediately after the sign bit) or before the last bit.
number and use the remainder to find a position. But
The former produces smaller spacing between the values
we won't have unique positions. If a hash position is
calculated that duplicates one already calculated by a
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
that can be represented and is more preferred. It also has a Usually, the choice for the total number of bits will be
greater range than the fixed representation. provided as an option when the program is written,
however, the split between the two parts will have been
determined by the floating point processor.
If there were a choice, it's convenient to note that
increasing the number of bits for the mantissa would give
better precision but would leave fewer bits for the
exponent thus reducing the range of possible values and
vice versa.
For maximum precision, it is necessary to
normalize a floating point number.
Optimum precision will only be made once full use is
made of the bits in the mantissa therefore using the
largest possible magnitude for the value represented by
the mantissa.
Also, the two most significant bits must be different. 0 1
for positives and 10 for negatives.
-they both equal 2 but the most precise is the second one
with the, higher bits in the mantissa.
\
0.125 * 2^4 = 2 0 001 0100
0.5 * 2^2 = 2 0 100 0010
-For negatives.
0.25 * 2^4 = -4 1 110 0100
1.0 * 2^2 = -4 1 000 0010
\
When the number is represented with the highest magnitude
for the mantissa, the two most significant bits are different
Converting a denary value expressed as a real number into a
thus that a number is in a normalized representation. How a
floating point binary representation: Most fractional parts do
number could be normalized: for a positive number, the bits
not convert to a precise representation as binary fractional
in the mantissa are shifted left until the most significant bits
parts represent a half, a quarter, an eighth…(even). Other
are 0 followed by 1. For each shift left the value of the
than .5 no other values unless the ones above can be
exponent is reduced by 1. The same process of shifting is
converted accurately. So you convert by multiplying by two
used for a negative number until the most significant bits are
and recording the whole number part.
1 followed by 0. In this case, no attention is paid to the fact
For example: 8.63, 0.63 * 2 = 1.26 therefore .1 -> 0.26 * 2 =
that bits are falling off the most significant end of the
0.52 and .10 -> 0.52 * 2 = 1.04 and .101 and you keep going
mantissa. Thus normalization is shifting bits to the left until
until the required amount of bits are achieved.
the 2 most significant bits are different.
The method for converting a positive value is:
Problems with using floating point numbers:
1. Convert the whole number part
2. Add the sign bit 0 1. The conversion of real denary values to binary mostly
3. Convert the fractional part. You start by combining the two needs a degree of approximation followed by the
parts which gives the exponent value of zero. Shift the binary restriction of the number of bits used to store the
points by shifting the decimal to the beginning giving a higher mantissa. These rounding errors can become
exponent value. Depending on the number of bits, add extra significant after multiple calculations. The only way of
0's at the end of the mantissa and beginning of the exponent. preventing a serious problem is to increase the
4. Adjust the position of the binary point and change the precision by using more bits for the mantissa.
exponent accordingly to achieve a normalized form. Programming languages therefore offer options to
Therefore: 8.75 -> 1000 -> 01000 -> .11 -> 010000.11 -> work in double/quadruple precision.
0.100011(mantissa) -> 0100011000 0100(10 for M, and 4 for 2. The highest value represented is 112 thus a limited
E). range. This produces an overflow condition. If there is
a result value smaller than one that can be stored,
For negatives, use 2's complement.
there would be an underflow error condition. This
When implementing the floating point representation, a
very small number can be turned into zero but there
decision has to be made regarding the total number of
are several risks like multiplication or division of this
bits to be used and how many for the mantissa and
value.
exponent.
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
eg: One use of floating point numbers are in extended packets to hold all of the data. Each packet consists of a
mathematical procedures involving repeated calculations like header plus the user data.
TCP needs to ensure safe
weather forecasting which uses the mathematical model of delivery and that any response is directed back to the
the atmosphere. application protocol. The header has a port number
which identifies the application layer protocol at the
sending and receiving end system (however the TCP isn't
2. Communication and concerned with the receiving end system). If the packet is
one of a sequence, a sequence number is included to
Internet technologies ensure eventual correct reassembly of the user data. The
TCP is connection oriented, initially just one packet of a
2.1. Protocols sequence is sent to the network layer. Once the
connection has been established, TCP sends the other
Protocols are essential for successful transmission of data packets and receives response packets containing
over a network. Each protocol defines a set of rules that must acknowledgements. This allows missing packets to be
be agreed between sender and receiver. At the simplest identified and resent.
level, a protocol could define that a positive voltage TCP/IP Suite: A common protocol used to send data over
represents a bit with value 1. At the other extreme, a a
network.
protocol could define the format of the first 40 bytes in a Protocols are split into separate layers, which are
packet.
The complexity of networking requires a very large arranged as
a stack.
number of protocols, a protocol suite is a collection of They service each other thus maintaining the flow of
related protocols. TCP/IP is the dominant protocol suite for the data.
internet usage. Layer: A division of the TCP/IP suite.
Stack: A collection of elements/protocols/layers.
Protocol: A set of rules governing communication
between
computers.
Ensures the computers that communicate understand
each other.
MAC address: A unique number assigned to each device’s
networking hardware across the world.
IP address: A unique number assigned to each
node/networking
device in a network.
Port number: A software-generated number that specifies
an
application or a process communication endpoint
attached to an IP
address.
IP: Internet Protocol – The function of the network layer,
and the IP, is to ensure correct routing over the internet.
To do so, it takes the packet received from the transport Layer Purpose
layer and adds a further header containing the IP Application Encodes the data being sent
addresses of both the sender and receiver. To find the IP Adds IP addresses stating where the
Network/Internet
address of the receiver, the DNS system can be used to data is from and where it is going
find the address corresponding to the URL supplied in the Adds MAC address information to
user data. The IP packet(datagram) is sent to the data link specify which hardware device the
layer and therefore to a different protocol suite. The data Link message came from and which
link layer assembles datagrams into frames. Transmission hardware device the message is
now begins. Once the IP packet has been sent to the data going to
link layer, IP has no further duty. IP is a connectionless
Enables the successful transmission
service so if it receives a packet which contains an Physical
of data between devices
acknowledgement of a previously sent packet, it will
simply pass the packet on to TCP with no awareness of
When a message is sent from one host to another:
the content.
Sender side: Application Layer
TCP: Transfer Control Protocol. If an application is
Encodes the data in an appropriate format.
running on an end system where a message is to be sent
Sender side: Transport Layer
to a different end system the application will be
The data to be sent is broken down into smaller
controlled by an application layer protocol. The protocol
chunks known as
packets
will transmit the user data to the transport layer, the TCP
Sender side: Network Layer
operating in the transport layer now has to take
IP addresses (sender and receiver) and a
responsibility for ensuring the safe delivery of the
checksum are added to
the header
message to the receiver. To do this it creates sufficient
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
Sender side: Link Layer
Formats the packets into a frame. These protocols
attach a third
header and a footer to “frame” the
packet. The frame header
includes a field that
checks for errors as the frame travels
over the
network media.
Sender side: Physical Layer
Receives the frames and converts the IP addresses
into the
hardware addresses appropriate to the
network media. The
physical network layer then
sends the frame out over the network
media.
OTHER PROTOCOLS:
Server/ Service Provider
Acronym Protocol Purpose
Re-Routes the packets according to the IP address
Receiver side: Physical Layer Handles transmission of
Hyper Text Transfer
Receives the packet in its frame form. It computes HTTP data to and from a
Protocol
the checksum
of the packet, and then sends the website
frame to the data link layer. Handles transmission of
FTP File Transfer Protocol
Receiver side: Link Layer files across a network
Verifies that the checksum for the frame is correct Handles the receiving of
and strips
off the frame header and checksum. POP3 Post Office Protocol 3
emails
Finally, the data link
protocol sends the frame to Simple Mail Transfer Handles the sending of
the Internet layer. SMTP
Protocol emails
Receiver side: Network Layer
Reads information in the header to identify the
SMTP is a push protocol. POP3 is a pull protocol, the recent
transmission and
determine if it is a fragment. If
alternative to POP3 is IMAP(internet message access
the transmission was
fragmented, IP reassembles
protocol) and it offers facilities of POP3 and more. This
the fragments into the original
datagram. It then
approach has been largely superseded by the use of web
strips off the IP header and passes it on to
based mail. A browser is used to access the email application,
transport layer protocols.
so HTTP is now the protocol used(direct and automatic
Receiver side: Transport Layer
emails from a website). However SMTP remains in use for
Reads the header to determine which application
transfer between the mail servers.
layer protocol
must receive the data. Then TCP o
strips off its related header
and sends the
message or stream up to the receiving application. Peer to Peer File Sharing
Receiver side: Application Layer
Receives the message and performs the operation P2P file sharing generates a lot of network traffic in internet
requested by the
sender usage. It is an architecture that has no structure and no
Bit Torrent protocol: A protocol that allows fast sharing of controlling mechanism. Peers act as both client and servers
files via peer-to-peer networks. and each peer is just one end system. The BitTorrent
Torrent file: A file that contains details regarding the protocol is the most used protocol because it allows fast
tracker sharing of files. There are three basic problems to solve if
Tracker: A server that keeps track of the peers end systems are to be confident in using BitTorrent:
Peers: A user who is at the time downloading the
1. How does a peer find others that have the wanted
same file as
the
content? The answer by BitTorrent here is to get every
Swarm: A network of peers that are sharing the
content provider to provide a content description -
torrent –
simultaneously downloading and uploading
torrent, which is a file that contains the name of the
the file.
tracker(a server that leads peers to the content) and a
Seeding: The act of uploading a part of the file or the
list of the chunks that make up the content. The
file
itself as a whole after/while downloading
torrent file is at least 3 orders of magnitude smaller
Leeching: The act of simply downloading a part of the
than the content to so can be transferred quickly. The
file or
the file itself on a whole and not seeding it
tracker is a server that maintains a list of all the other
during or after
the download.
peers/the swarm actively downloading and uploading
Seeders: Users who are currently seeding the file.
the content.
Leechers/Free-raiders: Peers who are currently
2. How do peers replicate content to provide high speed
leeching the
file.
downloads for everyone? This answer involves peers
simultaneously downloading and uploading chunks
but peers have to exchange lists of chunks and aim to
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
download rare chunks for preference. Each time a 6. Client sends an encrypted message to the server
rare chunk is downloaded it automatically becomes using the server’s public key.
less rare. 7. The server can use its private key to decrypt the
3. How do peers encourage other peers to provide message and get data needed for generating
content rather just using the protocol to download for symmetric key .
themselves? This answer requires dealing with the 8. Both server and client compute symmetric key (to be
free riders/leachers who only download. The solution used for encrypting messages) // session key
is for a peer to initially randomly try other peers but established.
then to continue to upload to those peers that 9. The client sends back a digitally signed
provide regular downloads. If a peer is not acknowledgement to start an encrypted session.
downloading or downloading slowly, it will eventually 10. The server sends back a digitally signed
be isolated/choked. acknowledgement to start an encrypted session.
Eg for online banking.
2.2. Circuit switching, packet switching
and routers 2.3. Local Area Networks (LAN)
Circuit switching: A method of data transfer in which the Bus topology: A network topology in which each
message is sent over a dedicated communication workstation is
connected to a main cable (backbone)
channel. through which the network is
established.
Eg: - Landline Phone The Backbone acts as the common medium, any
Packet switching: A method of data transfer in which the signals sent or
received go through the backbone in
intended message is broken down into parts and is sent order to reach the
recipient.
over
whichever route is optimum in order to reach its
destination.
Each packet travels through several other networks –
“switching”
between them in order to reach its
destination.
Eg: - Internet
Router: A device that connects two or more computer
networks.
Directs the incoming packets to their receiver
according to the
data traffic in the network.
Transport Layer Security (TLS) Star topology: A network topology in which each
workstation is
connected to a central node/connection
TLS(transport layer security) protocol: Purpose of TLS is to point through which the
network is established.
provide for secure communication over a network, maintain The central node (hub) re-directs and directs the
data integrity and add an additional layer of security. TLS packets
according to the data traffic and their
provides improved security over SSL(secure sockets layer). recipient.
TLS is composed of two layers: record protocol and Wireless networks: A computer network that uses
handshake protocol. TLS protects this information by using wireless data
connections between its network
encryption. It also allows for authentication of servers and components.
clients. A handshake process has to take place before any Bluetooth: A type of short-range wireless communication
exchange of data using the TLS protocol. The handshake that
uses
process establishes details about how the exchange of data Wi-Fi OR IEEE 802.11x.– A type of wireless communication
will occur. Digital certificates and keys are used. The that
allows the users to communicate within a particular
handshake process starts with:
area/ access
internet.
1. The client sending some communication data to the
Component Purpose in a LAN
server.
Allows different networks to
2. The client asking the server to identify itself. Switch
connect
3. The server sending its digital certificate including the
public key. Directs the incoming packets
Router
4. The client validates (the server’s) TLS Certificate. into
5. The client sends its digital certificate (to the server if
requested).
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
Component Purpose in a LAN for the sender and receiver and is the reason they are
Provides a medium for the called the MAC addresses.
storage, sharing of usage of
Servers
files and applications for its Hardware Connection Device
users
Consists of the electronic An end system on an ethernet LAN needs a network
Network Interface Cards circuitry required to interface card(NIC). Each NIC has a unique physical
(NICs) communicate with other address, MAC address. The end system itself has no
networks/devices. identification on the network. If the NIC is removed and
inserted into a different end system, it takes the address
Ethernet: an array of networking technologies and with it.
The simplest device used for the center of the star
systems used
in local area networks (LAN), where
topology LAN is the hub which ensures that any incoming
computers are connected within a
primary physical
communication is broadcast to all connected end
space.
systems. However, the use of a hub is not restricted to
CSMA/CD:
Standard ethernet was implemented on a LAN configured supporting an isolated network, it can have a hierarchical
configuration with one hub connected to other hubs,
as a bus or a star topology with a hub as the central
which support individual LANs. A hub can also have a
device where the transmission was broadcast in a
built in broadband modem which allows all of the end
connectionless service.
Because of the broadcast
user systems on the LAN to have an internet connection
transmission, there was a need for the access to the
shared medium by end systems to be controlled. If there when this modem is connected to a telephone line.
A switch can function as a hub but it's more intelligent
wasn’t any control, two messages sent at the same time
and can keep track of the addresses of connected
would collide and each message would be corrupted. The
devices, this allows a switch to send an incoming
method adopted was CSMA/CD(carrier sense multiple
transmission to a specific end system as a unicast. This
access with collision detection). If a frame was being
transmitted there was a voltage level on the ethernet reduces the amount of network traffic compared to the
hubs.
cable which could be detected by an end system. If this
A router is the most intelligent of the connecting devices.
was the case, the protocol defined at a time that the end
It can function as a switch and make decisions about
system had to wait before it tried again. However
because two end systems could have waited then both which device it will transmit a received transmission to.
decided to transmit at the same time collisions could still The main use of routers is in the backbone fabric of the
internet. Nearer to the end systems, a router may
happen thus there was also a need to incorporate a
function as a gateway, as a network address translation
means for an end system to detect a collision and to
box or be combined with a firewall.
discontinue transmission if a collision occurred. Before
transmitting a device checks if the channel is busy. If it is
busy the device waits, if channel free data is sent. When
WIreless networks
transmission begins the device listens for other devices
The dominant technology is no longer using cables now, it's
also beginning transmission. If there is a collision,
wireless. The following are discussed in order of increasing
transmission is aborted/ transmitting a jam signal. Both
scale of operation.
devices wait a (different) random time, then try again.
The
modern implementation of ethernet is switched. The star Bluetooth: this has been standardized as IEEE802.15.
configuration has a switch as the central device which Communication is by short range radio transmission in a
controls transmission to specific end systems. Each end confined area. A Bluetooth LAN is an ad hoc network thus
system is connected to the switch by a full duplex link so no defined infrastructure and network connections are
no collision is possible along the link and therefore created spontaneously. eg Wireless keyboard
CSMA/CD is no longer needed as collisions are Wi-Fi: aka WLAN and is a wireless ethernet known as
impossible.
Ethernet is the most likely protocol to be IEEE802.11. This is a wireless LAN protocol which uses
operating in the data link layer when the IP in the radio frequency transmission. Mostly a Wi-Fi LAN is
network layer sends a datagram to the data link layer. centered on a wireless access point in an infrastructure
When the data link layer uses ethernet, the protocol network and not an ad hoc network. The wireless access
defines 2 sub layers. The upper one is the logical link point communicates wirelessly with any end systems that
layer which handles flow control, error control and part of have connected to the device. It also has a wired
the framing process. The lower is the media access connection to the internet. •WiMAX(worldwide
control(MAC) sublayer which completes the framing interoperability for microwave access): an IEEE802.16 is a
process and defines the access method. The MAC layer protocol for a MAN or WAN. It's designed for use by
transmits the frames that contain the physical address PSTNs to provide broadband access to the internet
without having to lay underground cables. Local
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
subscribers connect to the antenna of a local base station
using a microwave signal.
Cellular networks: used in mobile/cell phones. Each cell
has at its center a base station. The system works
because each cell has a defined frequency for
transmission which is different from the frequencies used
in adjacent cells. The technology available in cell phones
has vastly progressed: NOT Gate: A = X
1. 1G was designed for voice communication using A Output
analogue technology 0 1
2. 2G went digital
1 0
3. 3G introduced multimedia and serious internet
connection capability
4. 4G introduced smartphones with high bandwidth
broadband connectivity.
**Wireless access points: • Allowing devices to connect to the
LAN via radio communication instead of using a cable • Easy
to move a device to as different location.
3. Hardware NAND Gate: A.B = X
A B Output
3.1. Logic gates & circuit design 0 0 1
0 1 1
Logic gates: A component of a logical circuit that can perform 1 0 1
a
Boolean operation (logical function).
1 1 0
AND Gate: A.B = X
A B X
0 0 0
0 1 0
1 0 0
1 1 1
NOR Gate: A + B =X
A B Output
0 0 1
0 1 0
1 0 0
1 1 0
OR Gate: A + B =X
A B Output
0 0 0
0 1 1
1 0 1
1 1 1
XOR Gate: A.B + A.B = X
A B Output
0 0 0
0 1 1
1 0 1
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
A B Output Adsorption
1 1 0 A. (A + B ) = A
A + A.B = A
De Morgan’s Law
(A.B ) = A + B
(A + B) = A.B
{S15-P33} Question: 5
a) i. Complete the truth table for this logic circuit:
Logic circuits: A circuit that performs logical operations on
symbols.
Sequential circuit: a circuit whose output depends on the ii. Complete the truth table for this logic circuit:
input
values and the previous output values. Eg: - Flip-
flops (Section
3.3.4)
Combinational circuit: a circuit whose output is
dependent only
on the input values
Half-Adder: A logic circuit that adds two bits together
b) A student decides to write an equation for X to represent
and
outputs their sum.
the
full behaviour of each logic circuit.
i. Write the Boolean expression that will complete the
required equation for X for each circuit:
Circuit 1: X =
Circuit 2: X =
Input Output
ii. Write the De Morgan’s Law which is shown by your
A B S C
answers to
part (a) and part (b)(i).
0 0 0 0
0 1 1 0 c) Write the Boolean algebraic expression corresponding to
the
following logic circuit:
1 0 1 0
1 1 0 1
3.2. Boolean algebra d) Using De Morgan’s laws and Boolean algebra, simplify your
answer to
part (c).
Double Complement: A =A
Identity Law Show all your working.
1.A = A Solution:
0 + A = A Part a):
Null Law
0.A = 0 i. Assume that the letter “C” equates to the first
1 + A = 1 function/logic gate.
Idempotent Law A+B =C
A.A = A
A B C
A+A=A
Inverse Law 0 0 0
A.A = 0 0 1 1
A + A = 1 1 0 1
Commutative Law 1 1 1
A.B = B.A
A + B = B + A 0 = 0
$$
Associative De Morgan's law: the inverse of a Boolean product becomes
(A.B).C = A.(B.C) the sum of the inverses of the individual values in the
(A + B) + C = A + (B + C) product. The inverse of a Boolean sum is the product of the
Distributive Law individual inverses.
A + B.C = (A + B).(A + C) Not (A and B) is the same as Not A or Not B.
A. (B + C ) = A.B + A.C
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
Not (A or B) is the same as Not A and Not B. Karnaugh maps: a method of obtaining a Boolean algebra
expression from a truth table involving the
RISC processors give the opportunity of providing efficient Benefits of using Karnaugh Maps:
pipelining. Pipelining is instruction level parallelism. Its Minimises the number of Boolean expressions.
underlying principle is that the fetch decode execute cycle Minimises the number of Logic Gates used, thus
can be separated into a number of stages. One of the providing a more
efficient circuit.
possibilities include: Methodology
Try to look for trends in the output, thus predict the
1. Instruction fetch (IF)
presence
of a term in the final expression
2. Instruction decode (ID)
Draw out a Karnaugh Map by filling in the truth table
3. Operand fetch (OF)
values
into the table
4. Instruction execute (IE)
Column labelling follows Gray coding sequence
5. Result write back (WB)
Select groups of ‘1’ bits in even quantities (2, 4, 6 etc),
PIPELINING FOR FIVE STAGE INSTRUCTION HANDLING if
not possible then consider a single input as a group
Note: Karnaugh Maps wrap around columns
Within each group only the values that remain
constant are
retained
{S17-P31} Question: 3
Consider the following logic circuit, which contains a
redundant logic
gate.
(a) Write the Boolean algebraic expression corresponding to
this
logic circuit. (3 Marks)
(b) Complete the truth table for this logic circuit. (2 Marks)
A B C Working Space X
For pipelining to be implemented, the construction of the
processor must have five independent units with each 0 0 0
handling one of the five stages identified. This explains the 0
0
1
need for a RISC processor to have many register sets. Each 0
1
0
processor unit must have access to its own set of registers. 0 1 1
The representation 1.1, 1.2 and so on are used to define the 1 0 0
instruction and the stage of the instruction. Initially only the 1 0 1
first stage of the first instruction has entered the pipeline. At 1
1
0
clock cycle 6 the first instruction has left the pipeline, the last 1
1
1
stage of instruction 2 is being handled and instruction 6 has
just entered.
Once under way, the pipeline is handling 5
stages of 5 individual instructions. At each clock cycle the 3.4. Flip-flops
complete processing of one instruction has finished. Without
the pipelining the processing time would've been 5 times SR flip-flop: SR(Set-Reset) flip-flop or “Latch”
longer. Used as a storage device for 1 bit in the RAM, since it’s
One disadvantage is interrupt handling. There will be 5 values
can be altered
instructions in the pipeline when an interrupt occurs. Issue: When the both the input signals are 1 (invalid
state)
the flip-flop sets the value of Q and Q’ to 0.
1. Erase the pipeline contents for the latest 4
instructions to have entered. Then the normal Input signals Initial state Final state
interrupt handling routine can be applied to the S R Q Q’ Q Q’
remaining instruction.
0 0 1 0 1 0
2. Construct the individual units in the processor with
individual program counter registers. This allows 1 0 1 0 1 0
current data to be stored for all of the instructions in 0 1 1 0 0 1
the pipeline while the interrupt Is handled. 0 0 0 1 0 1
1 0 0 1 1 0
3.3. Karnaugh Maps 0 1 0 1 0 1
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
J K Clock Q Contains multiple processors, which have their own
0 0 ↑ Q unchanged memory.
MISD
1 0 ↑ 1
Multiple Instruction Single Data stream
0 1 ↑ 0 Used to sort large quantities of data.
1 1 ↑ Q toggles Contains multiple processors which process the same
data
Flip-flops are used to build: MIMD
Data storage elements Multiple Instruction Multiple Data.
Digital circuits Found in modern personal computers.
Each processor executes a different individual
3.5. RISC processors instruction.
Massively parallel computers
RISC: Reduced Instruction Set Computers. Computers that contain vast amounts of processing
CISC: Complex Instruction Set Computers. power.
Has a bus structure to support multiple processors
RISC CISC and a network
infrastructure to support multiple
Fewer instructions More instructions ‘Host’ computers.
Commonly used to solve highly complex
Simpler instructions Complicated instructions
mathematical problems.
Small number of instruction
Many instruction formats
formats
Single-cycle instructions
Multi-cycle instructions
4. System software
whenever possible
Fixed-length instructions Variable-length instructions 4.1. Purposes of an operating system
Only load and store
instructions to address
May types of instructions to (OS)
address memory
memory
Optimizes use of computer resources
Fewer addressing modes More addressing modes Implements process scheduling to ensure efficient
Multiple register sets Fewer registers CPU use
Microprogrammed control Manages main memory usage
Hard-wired control unit
unit Optimizes I/O
Pipelining easier Pipelining much difficult Dictates whether I/O passes through CPU or not
Hides the complexities of the hardware
Pipelining: Instruction level parallelism UI allows users to interact with application programs
Used extensively in RISC processor based systems to Automatically provides drivers for new devices
reduce the
time taken to run processes Provides file system
Multiple registers are employed Organizes physical storage of files on disk
Interrupt handling in CISC and RISC Processors: Provides programming environment, removing the
As soon the interrupt is detected the current need for
knowledge of processor functions
processes are
paused and moved into registers Provides system calls/APIs
The ISR (Interrupt Service Routine) is loaded on to the Portability
pipeline
and is executed. Multitasking:
When the interrupt has been serviced, the paused More than one program can be stored in memory, but
processes are
resumed by bringing them back from only one can
have CPU access at any given time
the registers to the pipeline Rest of the programs remain ready
Process:
A program being executed which has an associated
3.6. Parallel processing Process Control
Block (PCB) in memory
PCB: a complex data structure containing all data
SISD relevant to the execution of a process
Single Instruction Single Data stream Process states
Found in the early computers
Ready: New process arrived at the memory and
Contains single processor thus no pipelining
the PCB is
created
SIMD
Running: Has CPU access
Single Instruction Multiple Data stream. Blocked: Cannot progress until some event has
Found in array processors occurred
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
Scheduling ensure that the computer system is able to An OS has to be structured in order to provide a platform for
serve all
requests and obtain a certain quality of service. resource management and the provision of facilities for
Interrupt: users. The logical structure provides 2 modes of operation:
Causes OS kernel to invoke ISR
The kernel may have to decide on priority 1. The user mode is the one available for the user or an
Register values stored in PCB application program.
Reasons 2. Privileged/kernel mode has the sole access to parts of
Errors the memory and to certain system functions that the
Waiting for I/O user mode cant access.
Scheduler halts process
Low-level scheduling: Allocation specific processor 4.3. Virtual machine
components
to complete specific tasks.
Low-level scheduling algorithms Virtual machine:
Preemptive: Will stop the process that would have Process interacts with software interface provided by
otherwise have
continued to execute normally. the OS.
This provides exact copy of hardware.
First-come-first-served OS kernel handles interaction with actual host
Non-preemptive hardware
FIFO(First In First Out) queue
Round-robin Pros Cons
Allocates time slice to each process Allows more than one OS to Performance drop from
Preemptive run on a system native OS
Can be FIFO queue Allows multiple copies of the Time and effort needed for
Does not prioritize same OS implementation is high
Priority-based
Most complex Examples and usage:
Priorities re-evaluated on queue change
Priority calc. Requires computation Used by companies wishing to use the legacy software on
Criteria for priority time newer hardware and server consolidation companies
Estimated time of execution Virtualizing machines allows developers to test
Estimated remaining time of execution applications on a multitude of systems without having to
Is the CPU/IO bound? make expensive hardware purchases.
Length of time spent in waiting queue
Paging:
4.4. Translation software
Process split into pages, memory split into frames
Lexical analysis: The process of converting a sequence of
All pages loaded into memory at once
characters to a sequence of tokens.
Virtual memory: Tokens: Strings with an assigned meaning
No need for all pages to be in memory Syntax analysis: The process of double-checking the code
CPU address space thus larger than physical space for
grammar mistakes (syntax errors).
Addresses resolved by memory management unit Code generation: The process by which an intermediate
Benefits code is
generated after syntax analysis.
Not all of the program has to be in memory at Optimization: A process in which the code is edited to
once make
improvements in efficiency.
Large programs can be run with or without large
physical
memory
Process
All pages on disk initially
One/more loaded into memory when process
‘ready’
Pages replaced from disk when needed
Can be done with FIFO queue or usage-
statistics based
algorithm
Disk thrashing: Perpetual loading/unloading of pages due
to a
page from disk immediately requiring the page it
replaced**.**
4.2. OS STRUCTURE For interpreters:
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
Analysis and code generation run for each code line
as above
Each line executed as soon as intermediate code
generated
BNF: Backus Naur Form
Can be used as a basis for an algorithm
Enccryption and Decryption:
Can be defined recursively
1. The process starts with original data, plaintext,
Notation Meaning
whatever form it takes.
::= Defined by
2. This is encrypted by an encryption algorithm which
| OR makes use of a key.
<x> Meta variable 3. The product of the encryption is ciphertext, which is
transmitted to the recipient.
RPN: Reverse Polish Notation 4. When the transmission is received it is decrypted
Used for representing algebraic expressions using a decryption algorithm and a key to produce the
Operator placed after operands original plaintext.
Example:
Security concerns relating to a transmission:
X + Y -> X Y +
Confidentiality: only the intended recipient should be able
to decrypt the ciphertext.
5. Security Authenticity: the receiver must be certain who sent the
ciphertext.
Integrity: the ciphertext must not be modified during
5.1. Asymmetric keys and encryption transmission.
methods Non repudiation: neither sender nor receiver should be
able to deny involvement in the transmission.
Plain text: data before encryption. Availability: nothing should happen to prevent the
Cipher text: the result of applying an encryption receiver from receiving the transmission.
algorithm to
data.
At the sending end the sender has a key which is used to
Encryption: the making of cipher text from plain text.
encrypt some plaintext and the ciphertext produced is
Encryption can be used:
When transmitting data over a network. transmitted to the receiver. Now, the receiver needs to get
the key needed for decryption.
As a routine procedure when storing data within a
computing system. 1. If symmetric key encryption is used, there needs to be
Public key: encryption key which is not secret. a secure method for the sender and receiver to be
Private key: encryption key which is a secret. provided with the secret key.
Symmetric key encryption: when there is just one key 2. Using asymmetric key encryption, the process starts
which is used to encrypt and then to decrypt. The secret with the receiver. The receiver must be in possession
key is shared by the sender and the receiver of a of two keys. One is a public key which is not secret.
message. The other is a private key which is secret and known
Asymmetric encryption: when two different keys are only to the receiver. The receiver can send the public
used, one for encryption and a different one for key to a sender, who uses the public key for
decryption. Only one of these is a secret. encryption and sends the ciphertext to the receiver.
Sending a private message: The receiver is the only person who can decrypt the
message because the private and public keys are a
matched pair. The public key can be provided to any
number of different people allowing the receiver to
receive a private message from any of them.
5.2. Digital signatures and digital
certificates
Sending verified message to public:
Using asymmetric encryption, the decryption works if the
keys are used the other way round. An individual can
encrypt a message with a private key and send this to
many recipients who have the corresponding public key
WWW.ZNOTES.ORG
CAIE A2 LEVEL COMPUTER SCIENCE (9618)
and can therefore decrypt the message. This is not for individuals, the public key must be made available in a way
confidential messages but can be used to verify who the that ensures authentication. The would-be receiver would
sender was. Only the sender has the private key and the need to obtain the digital certificate to allow safe public key
public keys only work with that one specific private key. delivery:
Therefore, used this way, the message has a digital
signature identifying the sender. However the digital 1. An individual(A) who is a would-be receiver and has a
signature is associated with an encryption of the whole public-private key pair contacts a local CA.
message. 2. The CA confirms the identity of A.
Cryptographic one way hash function creates from the 3. A's public key is given to the CA.
message a number, uniquely defined for the particular 4. The CA creates a public-key certificate(a digital
message, a digest. The private key is used as a signature certificate) and writes A's key into this document.
for this digest. This speeds up the process of confirming 5. The CA uses encryption with the CA's private key to
the sender's identity. add a digital signature to this document.
It is assumed that the message is transmitted as plaintext 6. The digital certificate is given to A.
together with the digital signature as a separate file. The 7. A posts the digital certificate on a website.
same public hash key function is used that was used by
