Summary
A Level 9618 Computer Science Programming Summary
- Institution
- CIE
A Level 9618 Computer Science Programming Summary for Paper 4 A* guaranteed
[Show more]
Connected book
Book Title:
Author(s):
- Edition:
- ISBN:
- Edition:
4 reviews
By: hank0 • 6 months ago
By: drahmed1 • 1 year ago
By: roro2552005 • 1 year ago
By: ashnacmr • 1 year ago
Content preview
CAIE A LEVEL COMPUTER SCIENCE PAPER 4 (9618)Abstraction: Iterative Binary Search:
• Process of modelling/filtering a complex system in an easy-to-
understand way by only including essential details, using:
o Functions and procedures with suitable
parameters → Imperative Programming
o Classes → Object Orientated Programming
o Facts and rules → Declarative programming
o ADTs (Abstract Data Types)
Insertion Sort:
Algorithms: • Items from the input array are copied one at a time to the
output array
Serial/Sequential/Linear Search: • Each new item is inserted into the right place so that the
output array is always in order
• All the values are considered in sequence
• Considerably faster than the bubble sort for a smaller number
• Even if an item is not found, all the values will have been
of data items
considered
• Best-case scenario: item to be found is at the start of the list
→ O(1) Iterative process:
• Worst-case scenario → max number of comparisons, when
item to be found is at the end of the list → O(N) where N is
the number of elements in the list
• Average number of comparisons → N/2
Binary Search:
• Used to search an ordered array
• Much faster than a linear search for arrays of more than a
few items
Bubble Sort:
1. Ordered array divided into 3 parts: middle, lower and upper
• The list is divided into two sublists: sorted and unsorted.
2. Middle item is examined to see if it is equal to the sought
• The largest element is bubbled from the unsorted list and
item
moved to the sorted sublist.
3. If not, and the middle value is greater than the sought item,
• After that, the wall moves one element back, increasing the
the upper part of the array is disregarded
number of sorted elements and decreasing the number of
4. The process is repeated for the bottom part
unsorted ones.
▪ Worst-case → log2 N + 1 → O(log2 N)
• Each time an element moves from the unsorted part to the
▪ When compared to linear search, whose worstcase
sorted part one sort pass is completed.
behaviour is N iterations, we see that binary search is
• Given a list of n elements, bubble sort requires up to n-1
substantially faster as N grows large. For example, to
passes (maximum passes) to sort the data.
search a list of one million items takes as many as one
million iterations with linear search, but never more
than twenty iterations with binary search
Recursive Binary Search:
• The performance of either sort routine is the best when the
data is already in order and there are a small number of data
items.
1
, CAIE A LEVEL COMPUTER SCIENCE PAPER 4 (9618)
Linked Lists: Searching a Linked List
• Can be represented as two 1-D arrays -string array for data
values and integer array for pointer values
• Creating a Linked list →Setting values of pointers in free list
and empty data linked list
• A user-defined record type should first be created to
represent a node’s data and pointer:
Deleting an Item from a Linked List
1. Use a Boolean value to know when an item has been found
and deleted (initially false)
2. Use a pointer (CurrentPointer) to go through each node’s
address
3. If new item is found at the header:
i. Set head pointer to pointer of node at
CurrentPointer
ii. Set pointer od node at CurrentPointer to free
pointer
iii. Free pointer points to CurrentPointer
Inserting into a Linked List
iv. Set Boolean value to True
4. Otherwise:
Search for Item while end of linked list not reached and
Boolean value is false
a) Use a Previous Pointer to keep track of
the node located just before the one
deleted
b) CurrentPointer point’s to next node’s
address
c) If data in node at CurrentPointer
matches SearchItem
• Set pointer of node at
PreviousPointer to pointer of
node at CurrentPointer
• Set pointer of node at
CurrentPointer to FreePointer
• Set FreePointer to
CurrentPointer
• Boolean value becomes true
5. If Boolean value is false
i. Inform user that item to be deleted has not been
found
2
, CAIE A LEVEL COMPUTER SCIENCE PAPER 4 (9618)
Stacks: • To add an Element to the Queue:
• Stack – an ADT where items can be popped or pushed from
the top of the stack only
• LIFO – Last In First Out data structure
Popping:
o The front of the queue is accessed through the pointer
Pushing:
Front.
o To add an element to the queue, the pointers have to be
followed until the node containing the pointer of 0 is
reached → the end of the queue, and this pointer is then
changed to point to the new node.
o In some implementations, 2 pointers are kept: 1 to the
front, and 1 to the rear. These saves having to traverse
the whole queue when a new element is to be added.
• To Remove an Item from the Queue
Use of Stacks:
• Interrupt Handling
o The contents of the register and the PC are saved
and put on the stack when the interrupt is detected
o The return addresses are saved onto the stack as
well
o Retrieve the return addresses and restore the
register contents from the stack once the interrupt
has been serviced
• Evaluating mathematical expressions held in Reverse Polish
Notation
• Procedure Calling
o Every time a new call is made, the return address o Items may only be removed from the front of the
must be stored list and added to the end of the list
o Return addresses are recalled in the order ‘last one
stored will be the first to be recalled’
o If too many nested calls then stack overflow
Queues:
• Queue – an ADT where new elements are added at the end of
the queue, and elements leave from the start of the queue
• FIFO – First In First Out Data structure
o Creating a Circular Queue:
3
, CAIE A LEVEL COMPUTER SCIENCE PAPER 4 (9618)
• Binary Trees: • Hash Tables:
o Dynamic Data structure → can match the size of o A hash table is a collection of items which are
data requirement. stored in such a way as to make it easy to find
o Takes memory from the heap as required and them later.
returns memory as required, following a node o Each position of the hash table, often called a
deletion slot, can hold an item and is named by an
o An ADT consisting of nodes arranged in a integer value starting at 0.
hierarchical fashion, starting with a root node o Given some key, we can apply a hash function
o Usually implemented using three 1-D arrays to it to find an index or position that we want
o In a binary tree, a node can have no more than two to access.
descendants. o To find data from the hash table, we need a
key to search for. From this key, we can
calculate the hash code. This tells us where in
the data array we need to start searching.
o Because of the collision resolution of the add
operation, the target data might reside at a
location other than the element referred to by
the hash code.
o A binary tree node is like a linked list node but with o Therefore, it is necessary to probe the hash
two pointers, LeftChild and RightChild. table until an empty hash element is found,
o Binary trees can be used in many ways. One use is and for an exact match between each data
to hold an ordered set of data. In an ordered binary item and the given key. (The probing stops at
tree all items to the left of the root will have a an empty element, since it signals the end of
smaller key than those on the right of the root. This where potential data might have been stored.)
applies equally to all the sub-trees.
o Tree algorithms are invariably recursive.
o To insert data into an ordered tree the following
recursive algorithm can be used:
o Consider a situation where 'G' maps to the
same hash code as 'B', and a search is
undertaken. The retrieval algorithm will start
looking at data items starting at that hash
code, and continue comparing each hash
item's contents for a match with 'G', until
o Another common use of a binary tree is to hold an either the blank element is found, or (if the
algebraic expression, for example: X + Y * 2 could be array is full) the probing loops back and ends
stored as: up where the traversal started.
• Algorithm to search a Binary Tree:
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 SKH392. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £4.26. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
60434 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