Algorithms and programming Flashcards
What is a recursive algorithm?
A recursive algorithm is one that repeatably calls itself until a base case is met.
What are the advantages of recursion?
More natural to read.
Suited to certain problems, for example those using trees.
Quicker to write as some functions are naturally recursive.
Can reduce the size of the problem with each call
What are the disadvantages of recursion?
Can run out of stack space / memory (due to too many calls) causing it to crash. This can be avoided with tail recursion.
More difficult to trace / follow as each frame on the stack has its own set of variables
Requires more memory than the equivalent iterative algorithm.
Usually slower than iterative methods due to maintenance of the stack
What is iteration?
Iteration is when the same procedure is repeated using a count controlled ‘for’ loop or a condition controlled ‘while’ loop.
Identify where the recursion is taking place.
01 def factorial(n) 02 if n == 0: 03 return 1 04 else: 05 return n * factorial(n-1)
Line 05
Identify the base case/terminating condition.
01 def factorial(n) 02 if n == 0: 03 return 1 04 else: 05 return n * factorial(n-1)
Line 02
What is the worst case number of searches for binary search?
O(log2(n)) when the search reaches the deepest level of the tree.
What is the best case number of searches for binary search?
O(1) when the target value is the middle element.
What is the average case number of searches for binary search?
O(log2(n) -1)
What is the worst case number of searches for linear search?
O(n) when the value at the end of the list or not in the list so that n comparisons are needed.
What is the best case number of searches for linear search?
O(1) when the value is equal to the first element of the list so only one comparison is needed
What is the average case number of searches for linear search?
O(n/2)
What is logarithmic complexity O(log n)?
The inverse of exponential growth. (Halving a dataset)
What is linear complexity O(n)?
An algorithm who’s complexity will grow in direct proportion to the size of the input data. (For/While loop)
What is constant complexity O(1)?
Algorithm that will always execute in the same time regardless of the size of the input data set. (No loops)
What is polynomial complexity O(n^2)?
An algorithm whose performance is directly proportional to the squared size of the input data set. (Nested loops)
What is exponential complexity O(2^n)?
An algorithm whose growth doubles with each addition to the input data set (Recursion)
Write a binary search algorithm in pseudocode.
def binary
In what situation would you use a linear search?
Unsorted array as it does not need to be sorted, useful if often inserting/removing
Array is very small
Item being searched for is very close to start of the array
In what situation would you use a binary search?
Sorted array
Large amount of data
What are the key steps of quicksort
Quicksort is a divide and conquer algorithm
1) Pick an element in the array as the “pivot”
2) In the partition phase it “partitions” the array into two divisions: Items to the left of the pivot are less than the “pivot”, and items to the right of the pivot are greater than the “pivot”
3) It does this recursively on smaller and smaller subarrays until the entire array is sorted.
What is the worst case complexity of quicksort?
O(n^2)
What is the best and average case complexity of quicksort?
O(n log n)
What are the advantages of quicksort?
On average it runs very fast.
It requires no additional memory.
What are the disadvantages of quicksort?
Quicksort’s running time degrades if given an array that is almost sorted (or almost reverse sorted).
Write pseudocode for a bubble sort
SET counter = 0
SET swapped = True
SET swaps = 0
SET length TO LENGTH(list)
WHILE swapped == True DO
WHILE counter < length – 1 DO
IF list[counter] > list[counter + 1] THEN
SET temp TO list[counter]
SET list[counter] TO list[counter + 1]
SET list[counter + 1] TO temp
SET swaps TO swaps + 1
END IF
SET counter TO counter + 1
SET length TO length - 1
END WHILE
IF swaps = 0 THEN
SET swapped TO False
ELSE
SET swaps TO 0
SET counter TO 0
END IF
END WHILEWhat are the advantages of bubble sort
Simple to write and understand
