3.3 Algorithms

Question 1

What is a recursive algorithm?

Answer 1

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

An elegant method as it is a** divide and conquer algorithm** that breaks down tth problem into sub problems and **combining them to form a final solution **

Simpler and more compact than iteration

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
- harder to debug

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 space and time complexity

Answer 6

Linear search, goes thorugh each item until item is found
Time: O(n)
Space O(1)

Binary search: divides list into two, compare and discards side if the item isnt in it, repeats.* Data must be sorted*

Time: O(log(n))
Space: O(1) uses a constant amount of memory regardless of input size

Bubble sort: contirunously compares items and does passes until item is found:

Time: O(n^2)
Space: O(1)

Insertion Sort: creates a seperate sorted sub list

Time: O(n^2)
Space: O(1)

Merge sort: seperate to individual elemetns, pair up in sorted order, repeat. Its O(n log n) complexity grows much slower than Bubble Sort’s O(n²) as n increases. Although Merge Sort is more complex to implement and requires extra space, its performance gains on large or unsorted data sets are significant.

Time: O(nlog(n))
Space: O(n)

Quick sort: divide and conquer algorithm, first element becomes pivot point, move item left or right dependign on size, do not sort sub list and repeat for all sub lists until sorted

Time: O(nlog(n))
SpaceL O(log(n))

Question 7

Algorithm

Answer 7

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

Question 8

Iteration

Answer 8

Repeating a set of instructions until a condtion is met

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

Question 9

Linear search pseudocode

Answer 9

declare myArray[0-999] is integer

searchValue is integer
found is boolean

set found = False

for i = 0 to len(myArray)
    if searchValue == myArray[i]
		   set found = True
		   output "searchValue found at position" i
		end if

next i 

if found = False
   output "searchValue not found"
end if

Question 10

Binary search pseudocode

Answer 10

declare myArray[0 to 999] is integer
start is integer
end is integer
found is boolean
mid is integer

set start = 0
set end = len(myArray)
set found = False

input searchValue

repeat
  set mid =(start +end) DIV 2
	
	if searchValue = myArray[mid] then
	  set found =  TRUE
		output "searchValue found at position" mid
		
  if searchValue > my array[mid] then
	   set start = mid + 1
	end if
	
	if searchValue < myArray[mid] then
	  set end = mid - 1
	end if
	
	until (found= True) OR (end < start)

Question 11

Bubble Sort pseudocode

Answer 11

declare myArray[0-999] is integer
temp is integer
swapped is boolean

repeat
  set swapped = False
	for i = 0 to (len(myArray)- 1)
	  if  myArray[i] <= myArray[i+1]
		   temp = myArray[i]
			myArray[i+1] = myArray[i]
			myArray[i+1] = temp
			set swapped True
		end if
	end for
until swapped = False

Question 12

Purpose of data validation and verification

Answer 12

Validation aims to ensrue that data is sensible,reasoonable, complete and within acceptable boundaries

Only proves the data entred has a reasonable value, cant prove its what the user intended to enter.

An example of such would be a presence checks, range checks etc

Verfication is used to ensure data entered by user is consistent, like double entry of passwords upon setting

Both are used to minmises human error

Question 13

Structured English

Answer 13

Structured English is a method of writing algorithms using plain English but in a more formal, rule-based style (such as IF…THEN, WHILE, and REPEAT UNTIL).

+easy to understand by non-technical people
+clear logic
+ no syntax errors as its not actual code
+ ideal fro planning before implmentation

• not executable
• can be lengthy

Question 14

Big O

Answer 14

Big O notation is used to describe how efficient an algorithm is by showing how its time or space requirements grow as the size of the input increases.

Time complexity refers to how many operations an algorithm performs in relation to the input size ‘n’

Space complexity refers to how much extra memory the algorithm uses, beyond the input itself.