CompSci - Algorithms

Question 1

Recursion

Answer 1

Occurs when a function calls itself (not subroutine; that has no return value)

Question 2

Stack Overflow

Answer 2

While recursion occurs, memory is filled with return addresses and local variables. If these exceed allocated memory capacity, stack overflow occurs, causing the program or device to crash.

For this reason, stopping conditions must be included in recursive algorithms.

Question 3

Stopping Condition

Answer 3

A condition in a recursive algorithm that stops it once some criteria has been reached.

Question 4

Validation

Answer 4

Automatic proccess that is done by an algorithm to ensure that data input by the user is appropriate and follows set rules.

Length, Lookup, Range, Presence, Type, Format

Question 5

Verification

Answer 5

Manual process that is done by the user themselves to check that data input is correct.

Double-Keying, Proofreading

Question 6

Authentication

Answer 6

Automatic process done by an algorithm that compares data input by the user with appropriate previously entered data to check that data is correct.

2FA, Biometrics, Password

Question 7

Trace Tables

Answer 7

IDE tool that helps to keep track of variables’ values as an algorithm runs. Useful for debugging by comparing with expected values.

Question 8

Dry-Running

Answer 8

Manually working through an algorithm without the use of a computer.

Question 9

Dry-Running Benefits

Answer 9

Uses pseudocode, which is more easy to understand and write
Helps the programmer to become familliar with the process
Low stakes

Question 10

Search Algorithms

Answer 10

Linear

Binary

Binary Tree

Shortest Path

Question 11

Sort

Answer 11

Bubble

Insertion

Merge

Quicksort

Question 12

Quicksort Algorithm

Answer 12

quicksort(data, first, last)
if data length > 1:
if first < last:
pivot = data[first]
up = 1
down = last
while up < down:
while up <= down and data[up] <= pivot:
up += 1
while up <= down and data[down] >= pivot:
down -= 1
if up < down:
temp = data[up]
data[up] = data[down]
data[down] = temp
temp = data[first]
data[first] = data[down]
data[down] = temp

quicksort(data, first, down-1)
quicksort(data, down+1, last)

Question 13

Algorithm Definition Methods

Answer 13

Flowcharts, pseudocode

Question 14

Benefits & Drawbacks

Answer 14

ACCESS MDC

Accessibility
Cost
Convenience
Efficiency
Security
Scalability

Maintenance
Depencence
Complexity

Question 15

Bubble Sort

Answer 15

Repeatedly compares two consecutive elements in a list, swapping them if they are in the wrong order.

Requires multiple passes.

Question 16

Insertion Sort

Answer 16

Iterate over elements starting from the second.
For each element, while the current is < previous and previous exists, replace the current index’ element with the previous index’ element and select the index previous to the previous index.
Else replace the next index’ element to the index previous to the previous index with the current element.

Question 17

Quicksort

Answer 17

Select the first value of the list as the pivot.
Select the second and last values as the low and high marks respectively.
While the low mark element is lower than the pivot, move the low mark up the list.
While the high mark element is higher than the pivot, move the high mark down the list.
If low mark is lower than high mark, swap the elements of the two.
If high mark becomes lower than low mark, swap the pivot value and high mark element.
Repeat this process for each partition that the pivot value seperates until the partition only has one element in it.

Recursive.

Question 18

Merge Sort

Answer 18

Select the middle element of the list and separate it into two sublists with the middle element part of the left sublist. Keep separating the sublists until they all contain one element each.
Compare elements left-to-right when merging sublists until an ordered list is formed.