Algorithms

Question 1

Stacks

Answer 1

• first in, last out
• uses a pointer that points to the element at the top of the list
  PEEK - to look at the top item without popping it off
  POP - removing the top item of the stack
  PUSH - to add an item to the top of the stack

Question 2

Queues

Answer 2

• first in, first out
• uses two pointers for the front and back. The front holds the first element, and the back stores the next available space
  ENQUEUE - adds to the end of the queue
  DEQUEUE - removes the first item

Question 3

Algorithm definition

Answer 3

A series of steps that completes a task

Question 4

Linked list

Answer 4

A dynamic/ data structure
Each node item consists of data and a pointer
the pointer gives the location of the next node

Question 5

Trees

Answer 5

Formed from nodes and edges that can be traversed.

Question 6

Breadth first search

Answer 6

(row by row)

Question 7

Depth first search

Answer 7

(column by column)
v

Question 8

Pre-order Traversal

Answer 8

Marker is on the left

root, left leaf, right leaf

Question 9

In-order traversal

Answer 9

the marker is below the node

left leaf, root, right leaf

Question 10

Post-order traversal

Answer 10

the marker is on the right

left node, root, right node

Question 11

Graphs

Answer 11

Set of vertices/ nodes, connected by edges/arcs
Directed graph: edges can be traversed in both directions
Weighted graph: each arc has a cost/ value attached to it.

Question 12

Binary Search

Answer 12

A O(log(n)) algorithm to search a sorted list for a particular item by repeatedly halving the sublist which contains the item

Question 13

Bubble sort

Answer 13

A O(n^2) sorting algorithm that iterates through a list comparing each element to its successor and swapping elements if the successor is greater than the current element. This is repeated until no more swaps can be made.

Question 14

Linear search

Answer 14

A O(n) algorithm to search a list for a particular item by iterating through the list and checking each element until the required item is located, or the end of the list is reached.

Question 15

Merge sort

Answer 15

A O(n log(n)) divide and conquer sorting algorithm that recursively halves the list into sublists until all sublists are length of 1 item. The sublists are then merged back together and sorted.

Question 16

Quick sort

Answer 16

A O(n log(n)) sorting algorithm similar to merge sort, but relies on choosing a pivot element whenever the list is split. Elements greater than the pivot go into one sublist.