2.3.1 - algorithms

Question 1

algorithm

Answer 1

A set of rules or a sequence of steps specifying how to solve a problem.

Question 2

2 searching algorithms

Answer 2

• linear search
• binary search

Question 3

linear search pseudocode

Answer 3

function LinearSearch(alist,itemSought}
index = -1
i = 0
found = False
while i < length(alist) and found = False
if alist[iI = itemSought then
index = i
found = True
endif
i = i + 1
endwhile
return index
endfunction

Question 4

linear search

Answer 4

If the items are not in any particular sequence, the data items have to be searched one by one until the required one is found or the end of the list is reached.

Question 5

binary search

Answer 5

The algorithm works by repeatedly dividing in half the portion of the SORTED data list that could contain the required data item. This is continued until there is only one item in the list.

Question 6

binary search pseudocode

Answer 6

function binarySearch(aList, itemSought}
found = False
index = -1
first = C
last = len (aList)-1
while first <= last and found = False
midpoint = Integer part of ((first + last)/2)
if aList[midpoint) = itemSought then
found = True
index = midpoint
else
if aList(midpoint) < itemSought then
first = midpoint + l
else
last = midpoint - i
endif
endif
endwhile
return index
endfunction

Question 7

bubble sort

Answer 7

• Go through the array, comparing each item with the one next to it. If it is greater, swap them.
• The last element of the array will be in the correct place after the first pass
• Repeat n-2 times, reducing by one on each pass the number of elements to be examined

Question 8

bubble sort pseudocode

Answer 8

numItems = len(numbers)
for i = 0 to numItems - 2
for j = 0 to(numItems - i - 2)
if numbers [j] > numbers [j + 1]
temp = numbers[j]
numbers [ j ] = numbers[ j + 1]
numbers [j+1] = temp
endif
next j
print (numbers)
next i

Question 9

insertion sort

Answer 9

The algorithm takes one data item
from the list and places It in the correct location in the list. This process is
repeated until there are no more unsorted data items in the list.

Question 10

insertion sort pseudocode

Answer 10

procedure inaertionSort(alist)
n = len(alist)
for index = 1 to n - 1
currentvalue = alist[index]
position = index
while position > 0 and alist[position - l| >
currentvalue
alist(position] = alist[position - 1]
position = position - l
endwhile
alist(position) = currentvalue
next index
endprocedure

Question 11

average time complexity of a binary search

Answer 11

O(log n)

Question 12

average time complexity of a bubble sort

Answer 12

O(n²)

Question 13

average time complexity of an insertion sort

Answer 13

O(n²)

Question 14

average time complexity of a merge sort

Answer 14

O(n log n)

Question 15

best case for bubble sort

Answer 15

O(n): Items are already in order, only one pass is needed. There would be n-1 comparisons for the inner for loop.

Question 16

worst case for bubble sort

Answer 16

O(n²): Values in list are in reverse order. There will be n-1 passes with n-1 comparisons made in each pass.

Question 17

best case for insertion sort

Answer 17

O(n): Items are already in order. Outer loop will iterate n-1 times. Condition of the inner while loop will evaluate to false so loop won’t be executed.

Question 18

worst case for insertion sort

Answer 18

O(n²): Reverse order.

Question 19

Why is the best, average and worst case time complexity for a merge sort always O(n log n)?

Answer 19

The full split and merge process is always executed.

Question 20

best case for quick sort

Answer 20

O(n log n)

Question 21

worst case for quick sort

Answer 21

O(n²): When the pivot value is in the first or last position of the current partition. This will result in one partition with 0 elements and one with all the remaining.

Question 22

worst case for binary sort

Answer 22

O(log n): If the item to be found is found in the last comparison or not at all.

Question 23

best case for binary sort

Answer 23

O(1): Item to be found is found in the first comparison.

Question 24

worst case for linear search

Answer 24

O(n): Item is found at end of list. Operation is carried out n times.

Question 25

best case for linear search

Answer 25

O(1): Item to found is first item in list.

Question 26

code to implement a static array

Answer 26

public const int MaxSize = 100; // Use a constant string[] stack = new string[MaxSize]; int top = -1;

Question 27

code to push an element onto a stack

Answer 27

public static bool IsFull(int top) { if (top == MaxSize - 1) return true; else return false; } public static int Push(string[] stack, int top, string data) { if (IsFull(top) == true) Console.WriteLine($"\nStack is full - {data} not added"); else { top = top + 1; stack[top] = data; } return top; }

Question 28

code to pop item from stack

Answer 28

FUNCTION is_empty(top) IF top == -1 THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION pop(stack, top) IF is_empty(top) == True THEN PRINT ("Stack is empty - nothing to pop") popped_item = Null ELSE popped_item = stack[top] top = top - 1 ENDIF RETURN (popped_item, top) ENDFUNCTION

Question 29

code to peek stack

Answer 29

FUNCTION peek(stack, top) IF is_empty(top) == True THEN PRINT("Stack is empty - nothing to peek") peeked_item = Null ELSE peeked_item = stack[top] ENDIF RETURN peeked_item ENDFUNCTION

Question 30

code to implement a linear queue

Answer 30

public const int MaxSize = 100; // Use a constant string[] queue = new string[MaxSize]; int front = 0; int rear = -1;

Question 31

code to enqueue to a linear queue

Answer 31

FUNCTION is_full(rear) IF (rear + 1) == MAX_SIZE THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION enqueue(queue, rear, data) IF is_full(rear) == True THEN PRINT ("Queue is full") ELSE rear = rear + 1 queue[rear] = data ENDIF RETURN rear ENDFUNCTION

Question 32

code to dequeue from a linear queue

Answer 32

FUNCTION is_empty(front, rear) IF front > rear THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION dequeue(queue, front, rear) IF is_empty(front, rear) == True THEN PRINT("Queue is empty - nothing to dequeue") dequeued_item = Null ELSE dequeued_item = queue[front] front = front + 1 ENDIF RETURN (dequeued_item, front) ENDFUNCTION

Question 33

code to initialise a circular queue

Answer 33

public const int MaxSize = 100; // Use a constant string[] circular_queue = new string[MaxSize]; int front = -1; int rear = -1;

Question 34

code to enqueue to a circular queue

Answer 34

FUNCTION is_full(front, rear) IF (rear + 1) MOD MAX_SIZE == front THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION enqueue(queue, front, rear, data) IF is_full(front, rear) == True THEN PRINT("Queue is full") ELSE rear = (rear + 1) MOD MAX_SIZE queue[rear] = data IF front = -1 THEN // First item to be queued front = 0 ENDIF ENDIF RETURN (front, rear) ENDFUNCTION

Question 35

code to dequeue from a circular queue

Answer 35

FUNCTION is_empty(front) IF front == -1 THEN RETURN True ELSE RETURN False ENDIF ENDFUNCTION FUNCTION dequeue(queue, front, rear) IF is_empty(rear) == True THEN PRINT("Queue is empty - nothing to dequeue") dequeued_item = Null ELSE dequeued_item = queue[front] // Check if the queue is empty IF front == rear THEN front = -1 rear = -1 ELSE front = (front + 1) MOD maxsize ENDIF ENDIF RETURN (dequeued_item, front, rear) ENDFUNCTION

Question 36

code to implement a linked list

Answer 36

class NodeRecord { public string data; public NodeRecord next; } // Do not intialise yet as the linked list is empty NodeRecord head;

Question 37

code to traverse a linked list

Answer 37

PROCEDURE traverse(my_list) // Set the current node as the head current = my_list.head // Repeat until there are no more linked nodes WHILE current != Null PRINT(current.data) current = current.next ENDWHILE ENDPROCEDURE

Question 38

code to add a new node to a linked list

Answer 38

PROCEDURE insert_at_front(my_list, data) // Create a new node new_node = NodeRecord new_node.data = data // Check if the head node exists IF my_list.head == Null THEN my_list.head = new_node ELSE // Update the pointers so the new node is the head new_node.next = my_list.head my_list.head = new_node ENDIF ENDPROCEDURE

Question 39

code to delete a node from a linked list

Answer 39

PROCEDURE delete(my_list, data) // Start at the head of the list current = my_list.head // Check if the head node is to be deleted IF current.data == data THEN // Update the head pointer my_list.head = current.next ELSE // Repeat until the node has been found WHILE current.next.data != data // Change the current node to be the next node current = current.next ENDWHILE // Set the pointer to be the next node's pointer current.next = current.next.next ENDIF ENDPROCEDURE

Question 40

code for depth-first traversal (post order)

Answer 40

PROCEDURE post_order_traversal(node) // Check any nodes to the left of the current node IF node.left != Null THEN post_order_traversal(node.left) ENDIF // Check any nodes to the right of the current node IF node.right != Null THEN post_order_traversal(node.right) ENDIF // Output the data of the current node PRINT(node.data) ENDPROCEDURE