Algorithms (Cambridge (CIE) A Level Computer Science): Flashcards

False.

The best case is O(1), where the item is found on the first comparison. O(n) is the worst case.

O(n/2), which after removing coefficients is still O(n).

Linear time dominates constant time. The constant term and coefficients contribute significantly less as the input size n grows larger.

The index of the item if it is found, or -1 if it is not.

If the item is not found, the linear search returns -1.

index to -1, i to 0, and found to FALSE.

WHILE i < LENGTH(list) AND found = FALSE

index ← i saves the current index, and found ← TRUE stops the search.

To stop the search once the item has been found, rather than checking the rest of the list.

A binary search compares the middle item to the target item, halving the search space with each step. It is more efficient than a linear search.

The list must be sorted.

False.

The list must be sorted for a binary search to work correctly.

The index is returned.

The top half is ignored.

The bottom half is ignored.

False.

It does not discard, delete or remove parts of the list. It only adjusts the start, end and mid pointers, which gives the appearance that items have been removed.

A binary search only adjusts the start, end and mid pointers.

When the item is found, or when the item is shown not to be in the list.

O(log n), because it halves the search space with each iteration of the loop.

A binary search is an example of logarithmic time complexity.

An approach where a problem is progressively reduced in size, so that when each problem is at its smallest it is easiest to solve.

n divided by 2 to the power i. The algorithm starts with n items, then n/2, then n/4, then n/8, and so on.

O(1), where the item is found on the first comparison.

O(log n / 2), which after removing coefficients is still O(log n).

Rounding up or down are both valid, provided the same rounding is used consistently throughout the algorithm.

The index of the item if it is found, or -1 if it is not found.

start to 0, and end to LENGTH(list) - 1.

WHILE start <= end AND found = FALSE

mid ← (start + end) DIV 2

start ← mid + 1, which searches the right half.

end ← mid - 1, which searches the left half.

When the item is found, or when the search range becomes invalid.

A bubble sort puts items into order smallest to largest, by comparing pairs of elements and swapping them if they are out of order.

The first to the second, the second to the third, and so on, until the second to last is compared to the last.

A pass is one complete run of comparisons through the list.

The value at the top of the list is now in order, and the sort resets back to the start of the list to sort the next largest value.

Because after each pass the previously sorted final value is in order and does not need to be rechecked.

A final pass checks all elements, and if no swaps are made the sort is complete.

A bubble sort is complete when a final pass makes no swaps.

Sorting an array of names into alphabetical order, or sorting an array of student marks from a test.

O(n squared)

O(n), for an already sorted list, since each item must still be compared to check it is in order.

False.

The best case is O(n) for an already sorted list. O(n squared) is the worst case.

O(n squared / 2) for an almost sorted list, which after removing coefficients is still O(n squared).

O(1), because it operates in-place, requiring only a fixed amount of memory for loop counters and a temporary swap variable.

A bubble sort operates in-place, requiring only a fixed amount of memory.

False.

It has space complexity O(1), because it sorts in-place.

The length of the list.

The number of completed passes.

It is a boolean flag used to check whether any swaps occurred during a pass.

To assume a swap will happen, so that the loop is entered at least once.

WHILE i < (last - 1) AND swap = TRUE

FALSE

From index 0 to last - i - 2, which is the unsorted part of the list.

temp ← list[j], then list[j] ← list[j + 1], then list[j + 1] ← temp

i is incremented, which shortens the range checked on the next pass.

It shortens the range checked on each subsequent pass, because the end of the list is already sorted.

An insertion sort sorts one item at a time by placing it in the correct position of an unsorted list, repeating until all items are in the correct position.

The insertion sort places each item in the correct position of an unsorted list.

Each previous item in the list.

The previous item is moved to the right and the current item takes its place.

It is already in the correct position, and the next item is then sorted.

When all items are in the correct position.

O(n squared)

O(n), for an already sorted list, where each item is checked one at a time.

O(n squared / 2) for a half sorted list, which after removing coefficients is still O(n squared).

O(1), because the insertion sort requires no additional space.

False.

It requires no additional space, so its space complexity is O(1).

Index 1, not 0, because the first item is considered already sorted.

False.

It starts at index 1, because the item at index 0 is considered already sorted.

The current value to be positioned.

Where item should go in the sorted portion of the list.

FOR i ← 1 TO n - 1

WHILE position > 0 AND list[position - 1] > item

It shifts elements in the sorted portion to the right while they are greater than item.

In an insertion sort, elements greater than the item are shifted to the right.

The start of the list is reached (position = 0), or the correct spot is found (list[position - 1] <= item).

list[position] ← item inserts the value in its correct position.

[4, 5, 9, 2, ...]. The value 4 is shifted in front of both 9 and 5.

isEmpty(), isFull(), push(value), pop(), peek() and size().

items, top and capacity.

In pseudocode, a stack is assumed to be record-based, with items, top and capacity fields.

-1

False.

It is -1 when empty, which is why size is calculated as top + 1.

RETURN s.top = -1

RETURN s.top = s.capacity - 1

Increment top, then assign the value to s.items[s.top].

A push must check the stack is not full before adding a value.

It outputs "Stack is full".

Read s.items[s.top] into a value, then decrement top, then return the value.

-1

It returns s.items[s.top] without removing it, provided the stack is not empty.

False.

peek() returns the top value without removing it. It is pop() that removes.

RETURN s.top + 1

Because top is a zero-based index, and it is -1 when the stack is empty.

30, the value at the top of the stack.

1. The pops return 30 then 20, leaving only 10.

Whether the stack is full, using IF AnimalTopPointer = 20.

FALSE

Inserts the value at Animal[AnimalTopPointer], increments the pointer, and returns TRUE.

A queue is a linear ADT that follows the First In, First Out (FIFO) principle.

A queue is a linear ADT that follows the First In, First Out principle.

False.

A queue is First In, First Out (FIFO). It is a stack that is Last In, First Out.

Enqueue, dequeue, peek or front, isEmpty and isFull.

Adds an item to the back of the queue.

Removes an item from the front of the queue.

Looks at the front item without removing it.

items, front, rear, size and capacity.

q.rear ← (q.rear + 1) MOD q.capacity

So the pointer wraps around to the start of the array, which is what makes the queue circular.

The MOD operator makes the pointer wrap around to the start of the array.

Advances rear, stores the item at q.items[q.rear], and increments size.

"Queue is full"

Reads q.items[q.front] into a value, advances front using MOD, decrements size, and returns the value.

False.

It only advances the front pointer, using MOD to wrap around the array.

"Queue is empty"

RETURN q.size = 0

RETURN q.size = q.capacity

It performs a linear search, starting at q.front and stepping forward with pos ← (pos + 1) MOD q.capacity for q.size items.

TRUE if the target is found, otherwise FALSE.

Because only size items are actually in the queue, even though the array has capacity slots.

Create a linked list, traverse it, add data to it, and remove data from it.

A data field, for example fruit, and a next field storing a reference to the next node in the list.

In a linked list, the next field stores a reference to the next node.

By setting the next field of each node to the appropriate next node.

NULL

Start at the head, output the current node's value, then set current to current.next, repeating until current is NULL.

WHILE current != NULL

Traversal of a linked list stops when current becomes NULL.

Create a new node with the new data, and set its next field to NULL.

Whether the list is empty, that is IF node1 = NULL.

The new node becomes the head of the list.

Traverse with WHILE current.next != NULL, then set current.next to the new node.

current and previous.

previous is NULL, so the head is updated to current.next.

False.

If the node being removed is at the head, the head is updated to current.next.

previous.next is set to current.next, which bypasses the node.

False.

It only updates the previous node's pointer to bypass the removed node.

The loop breaks, so no further nodes are checked.

previous ← current, then current ← current.next.

Check for a free node.

Search for the correct insertion point.

To the first node in the free list, that is the node pointed to by the free list's start pointer.

The pointer from A is changed to point to B instead of C, and the pointer from B points to C.

Its start pointer moves to point to the next free node.

A binary tree is a rooted tree where every node has a maximum of 2 nodes.

False.

Every node in a binary tree has a maximum of 2.

A graph, and it can therefore be implemented in the same way.

By storing each node with a left and right pointer.

Traverse the tree data structure, add new data to a tree, and remove data from a tree.

An item in a tree.

An edge connects two nodes together, and is also known as a branch or pointer.

A single node which does not have any incoming nodes.

A root is a single node which does not have any incoming nodes.

A node with incoming edges.

A node with outgoing edges.

A parent has outgoing edges. A child has incoming edges.

A node with no children.

False.

A leaf is a node with no children, so it has no outgoing edges.

A subsection of a tree, consisting of a parent and all the children of that parent.

The process of visiting each node in a tree data structure, exactly once.

Traversing is the process of visiting each node in a tree exactly once.

The value of the current node, before visiting any of its children.

IF node = NULL THEN RETURN

It searches the parent's children for a matching value, removes the first match, and then returns.

It only removes the first matching child from the direct children of a node. Removing nodes anywhere in the tree would need a recursive version.

Being able to explain or demonstrate how one abstract data type can be built on top of another.

A stack from a linked list, a queue from two stacks, and a dictionary from a binary search tree.

False.

You are not limited to built-in types. ADTs can be composed out of each other.

A list or array, using push and pop operations.

A list or array, or a circular buffer.

As a class with next fields, implementing the nodes manually.

A hash table, giving key-value mapping.

As a class with left and right fields, where each node links to its children.

Push and pop from the head of the list.

Store the keys and values in the BST, which gives ordered lookup.

From a linked list or array, where the nodes link to each other like a graph.

A queue can be implemented using two stacks.

inStack and outStack.

Push the item onto inStack.

If outStack is empty, pop all items from inStack and push them onto outStack, then pop from outStack.

False.

If outStack is empty, all items are first moved from inStack to outStack, and the pop then happens from outStack.

That you can simulate FIFO behaviour using LIFO operations.

Two stacks can simulate FIFO behaviour using LIFO operations.

To determine how suitable they are for solving a specific problem or working with a particular set of data.

Time complexity and space complexity.

It solves the problem in the shortest time and using the least memory.

The number of operations or steps an algorithm takes to complete, not the actual time in seconds or minutes.

False.

It measures the number of operations or steps, not the actual time.

A faster CPU executes instructions more quickly, but the number of instructions the algorithm performs stays the same.

The marathon distance is the algorithm and the runners are different CPUs. Each runner finishes at a different time, but the distance is the same.

The amount of memory an algorithm needs to complete its task.

Space for input data, temporary variables, and any additional data structures such as arrays, stacks or queues.

Because of the call stack.

A mathematical way to describe the time and space complexity of an algorithm, showing how well it scales as the size of the input increases.

The order of growth, or efficiency, of an algorithm.

Big O is hardware-independent, measuring steps rather than seconds.

False.

Big O is hardware-independent. It measures steps or operations, not seconds.

Keep only the dominant term, and ignore constants.

Only the dominant factor is used when determining an algorithm's Big O.

They become insignificant as the input size grows.

Constant time. The algorithm always takes the same number of steps, regardless of input size.

Linear time. The number of steps increases proportionally with the input size.

Polynomial time. Performance is proportional to the square of the input size, caused by nested loops.

Logarithmic time. The number of steps grows slowly even as the input size grows rapidly. Common in binary search.

Exponential time. The number of steps doubles for every additional input value, so it grows extremely fast.

Linear logarithmic time, for algorithms that divide data and process each part. Merge sort is an example.

Exponential, then polynomial, then linear, then logarithmic, then constant.

It performs worse than exponential time.

Between polynomial and linear time.

O(n squared), because n squared is the dominant factor and coefficients are removed.

As the input grows arbitrarily large, multiplying by 3 contributes very little to the overall time complexity.

1 loop is O(n), 2 nested loops are O(n squared), and no loops is O(1).

10, because 2 to the power 10 is 1,024.

The worst case, in order to guarantee a minimum standard of performance.

Best O(1) when the item is first, average O(n) when it is in the middle, and worst O(n) when it is not found.

A binary tree is a rooted data structure where each node can have a maximum of two child nodes, one on the left and one on the right.

Each node in a binary tree can have a maximum of two child nodes.

Storing data in a way that allows fast searching, insertion and deletion.

Using pointers that reference the left and right child nodes.

A data value, plus Left and Right pointers, which may be NULL if no child exists.

The topmost node, which has no parent.

A node with no children.

A connection between two nodes, also called a branch or pointer.

A smaller tree that is part of a larger one.

The process of visiting every node exactly once.

A parent links to one or more children. A child is a node linked from a parent.

A type of binary tree that stores data in sorted order.

All values in the left subtree are less than the node's value. All values in the right subtree are greater than or equal to the node's value.

False.

Values greater than or equal to the node go in the right subtree.

They use comparison to decide which branch to follow, which makes searching and insertion efficient.

A Value, a Left pointer and a Right pointer.

It creates a new node, sets its Value to the data passed in, and sets both Left and Right to NULL.

Compare it with the current node. If smaller, move left; if greater or equal, move right. Insert the new node when an empty pointer is found.

Pre-order, in-order and post-order.

Visit the current node, then left, then right.

Visit left, then the current node, then right.

Visit left, then right, then the current node.

10 5 15 12 20

5 10 12 15 20

5 12 20 15 10

False.

The base case is IF Node = NULL THEN RETURN, that is reaching a NULL pointer, not a leaf.

The node has no children, one child, or two children.

Simply remove the node.

Replace the node with its single child.

Replace the node's value with its in-order successor, the smallest value in the right subtree, then delete that successor node.

To delete a node with two children, replace it with its in-order successor.

It walks left from a node until Left is NULL, returning the smallest value in that subtree.