3.3 Algorithms

Question 1

What is a recursive algorithm?

Answer 1

An algorithm that calls upon itself until a base case is met.

Question 2

What is a general and base case?

Answer 2

General case is a smaller instance of the same problem

Base case is what causes the algorithm to stop

Question 3

Benefits and drawbacks to recursion

Answer 3

+ Natural way to process data
+ fewer lines of code, easier to read
- utilises stacks, which have limited size and stack overflows can occur
- takes longer to process due to stacking

Question 4

Quicksort

Answer 4

divide and conquer sorting algorithm. very efficient and fast and often considered better than merge sort due to using less memory but this isn’t really the case as it depends on other factors

Question 5

Quicksort Pseudocode

Answer 5

FUNCTION quick_sort(items, start, end)

IF start >= end THEN 
	RETURN

ELSE
	pivot_value = items[start]
	low_mark = start + 1
	high_end = end
   	finished = False

    WHILE finished = False
    	WHILE low_mark <= high_mark AND items[low_mark] <= pivot_value
            	low_mark = low_mark +1
            ENDWHILE

            WHILE low_mark <= high_mark AND items[high_mark] >= pivot_value
            	high_mark = high_mark - 1
	ENDWHILE

	IF low_mark < high_mark THEN
		temp = items[low_mark]
		items[low_mark] = items[high_mark]
                    items[high_mark] = temp

	ELSE
		finished = TRUE
	ENDIF
ENDWHILE

temp = items[start]
items[start] = items[high_mark]
items[high_mark] = temp

quick_sort(items, start, high_mark - 1)

    quick_sort(items, high_mark + 1, end)

ENDIF

RETURN items

ENDFUNCTION

Question 6

Compare sorting algorithms and their time complexity

Answer 6

bubble sort - simple and easy to implement but only ideal for small data sets

best case (items in order) - O(n)
worst case (reverse order) - O(n^2)
average case - O(n^2)

Insertion sort - efficient for small or nearly sorted datasets

best case (items in order) - O(n)
worst case (reverse order) - O(n^2)

merge sort- very fast and efficient
but uses additional memory for merging
best case/average case/worst case is O(n log n) as always splits array and merges regardless of list size

quick sort - fast efficient and ideal for large data sets but can use memory (varies on factors like pivot placement)

best case (list is partioned into two equal sizes) - O(n log n)
worst case (unbalanced partion) - O(n^2)
average case - varies on factors but generally is O(n log n)

Question 7

space complexities of algorithm

Answer 7

Bubble sort/Insertion sort - O(1) as sorting is done in same space as original data

Quick sort - sorting done in same space however since its a recursive algorithm it has stack processing which at its most efficieint makes it O(log n)

Question 8

Algorithm

Answer 8

An unambigous set of instructions to solve a problem. Example being flowchart or psuedocode

Question 9

Iteration

Answer 9

Repeating a set of instructions until a condtion is met

+easier to look at and debug
+ generally uses less memory than recursive too.