2.3.1 Algorithms

Question 1

What are the sorting algorithms we’ve learned? (4)

Answer 1

Bubble sort (1) insertion sort (1) merge sort (1) Quick sort (1)

Question 2

What are the searching algorithms we’ve learned? (2)

Answer 2

Binary search (1) Linear search (1)

Question 3

What is the precondition for a binary search? (1)

Answer 3

Data must be in order (1)

Question 4

Which sorting algorithm uses divide and conquer? (1)

Answer 4

Merge sort (1)

Question 5

What are the different Big O notation categories? (5)

Answer 5

Constant - O(1) (1) linear O(n) (1) polynomial - O(n^2) (1) Exponential - O(2^n) (1) Logarithmic - O(log n) (1)

Question 6

What is the time complexity of bubble and insertion sort? (1)

Answer 6

Polynomial - O(n^2)

Question 7

What is the time complexity of merge sort? (1)

Answer 7

Loglinear - O(n log n)

Question 8

What is the time complexity of quick sort? (1)

Answer 8

Polynomial - O(n^2)

Question 9

What is the time complexity of a linear search? (1)

Answer 9

Linear - O(n)

Question 10

What is the time complexity of a binary search? (1)

Answer 10

Logarithmic - O(log n)

Question 11

What are the key features of a stack data structure? (4)

Answer 11

Last in first out (LIFO) (1) It has an array to store data (1) with a pointer to show the top of the stack (1) items are added to the top using the pointer (1) items are removed from the top using the pointer (1)

Question 12

What are the key features of a queue data structure? (4)

Answer 12

First in first out (FIFO) (1) It has an array to store data (1) with a pointer for the head and tail (1) items are removed from the front using head (1) items are added to the rear using tail (1)

Question 13

What are the key features of a tree data structure? (4)

Answer 13

1 directional data structure (1) Has a root node with no incoming edges (1) branch nodes with incoming and outgoing edges (1) leaf nodes with incoming edges only (1) unweighted (1) dynamic (1)

Question 14

What are the key features of a binary tree data structure? (4)

Answer 14

Each node has maximum 2 outgoing edges (1) data lower in the sequence goes left (1) data higher in the sequence goes right (1) has a root branches and leaves (1)

Question 15

What are the pointers in a linked list? (2)

Answer 15

head or headpointer points to the start of the list (1) next free or freelistpointer points to the first free space (1)

Question 16

What is a linked list? (3)

Answer 16

A dynamic data structure (1) each node consists of data and pointer (1) pointer gives location of next node (1)

Question 17

What is depth first traversal? (4)

Answer 17

Depth first goes to left child node when it can (1) if there is no left child node it goes to right child node (1) if there are no child nodes to visit it backtracks to the parent node (1) uses a stack to order nodes (1)

Question 18

What is breadth first traversal? (3)

Answer 18

Breadth first visits all nodes directly connected to start node (1) then visits all nodes directly connected to each of those nodes (1) uses a queue to order nodes. (1)

Question 19

How do you traverse a binary tree in order? (3)

Answer 19

Visit the left node (1) then read the data (1) then visit the right node (1)

Question 20

How do you traverse a binary tree in pre-order? (3)

Answer 20

Read the data (1) then visit the left node (1) then visit the right node (1)

Question 21

How do you traverse a binary tree in post-order? (3)

Answer 21

Visit the left node (1) then visit the right node (1) then read the data (1)

Question 22

Describe a Merge Sort (5)

Answer 22

Splits the list in half repeatedly until it is in independent arrays(1) Compare the first two items and combine to create a new array (1) Repeat for the other indexes (1) and then compare the first elements in the first two new arrays choose the largest (decesing order) or smallest (ascending order) writing them into the new array first and reapeat till no elements are left.(1) Combine 2 remaining lists into one list.(5)

Question 23

Describe a Bubble Sort (5)

Answer 23

Compare each adjacent pair elements(1) If they are not in the correct order then swap the elements(1) If in correct order do not swap(1) When you read the array return to start and repeat for n elements times(1) Set a Flag to false whenever swap is made and repeat loop if flag is not false.(1)

Question 24

Describe Insertion sort (3)

Answer 24

One item at a time(1) Moved into correct position(1) Until all items in list are checked (1)

Question 25

Describe Quick Sort (5)

Answer 25

Choose a pivot OR identify start and end pointers (1) Compare each element to the pivot OR compares start and end pointers (1) Put item < pivot in left sublist and items > pivot in the right sublist (1) Choose a pivot in each sublist(1) If start pointer is larger than end pointer then swap them around(1) Repeat the process until each item becomes a pivot(1)

Question 26

State Purpose Of Big O Notation(1)

Answer 26

Either One: Evaluate the complexity of the algorithms (1) Show how the time / memory / resources increase as the data size increases (1) Evaluate worst case scenario for the algorithms

Question 27

The time complexity of a binary search is Logarithmic - O(log n). What is its space complexity?

Answer 27

Iterative: Constant - O(1)
Recursive: Logarithmic - O(log n)

Question 28

The time complexity of a linear search is Linear - O(n).
What is its space complexity?

Answer 28

Constant - O(1)

Question 29

The time complexity of bubble and insertion sort is Polynomial - O(n^2)
What is their space complexity?

Answer 29

Constant - O(1)

Question 30

The time complexity of merge sort is O(n log n).
What is its space complexity?

Answer 30

Linear - O(n)