CompSci - Algorithms

Question 1

Recursion

Answer 1

Occurs when a function calls itself (not subroutine; 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

Question 11

Sort Algorithms

Answer 11

Bubble

Insertion

Merge

Quicksort

Variety in recursion needed for more memory control and speed

Question 12

Algorithm Definition Methods

Answer 12

Flowcharts, pseudocode

Question 13

General Benefits & Drawbacks

Answer 13

ACCESS MDC

Accessibility
Cost
Convenience
Efficiency
Security
Scalability

Maintenance
Depencence
Complexity

Question 14

Bubble Sort

Answer 14

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

Requires multiple passes.

Pseudocode
Two flags
Reset swap at start of each pass, if no swaps all pass, sorted

Question 15

Insertion Sort

Answer 15

Separates the unsorted array into a “sorted” left side and “unsorted” right side. It iteratively compares values left to right and orders them appropriately.

Pseudocode
Starts from second element
Define current element and previous index
While current < prev & prev exists
Replace current with prev
Define previous previous index
OUTSIDE FOR replace prev with current
[i] only used in initial for, then in terms of [prev]

Question 16

Quicksort

Answer 16

Select an arbitrary value as a pivot, then separate the list into two sublists of elements lesser and greater than the pivot. These sublists are then sorted and ordered correctly.

Recursive.

Pseudocode
a,start,end parameters, if start>=end else,def pivot, low,high,sorted while while obv go closer, if obv swap low high. outside swap start high. quicksort start high -1 and high+1 start

Question 17

Merge Sort

Answer 17

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.

Recursive

Pseudocode
Two functions, merge & sort
merge: def i_l/r=0 and merged, compare from left to right and append if true. return merged
sort: if len <= 1, def mid,l,r, sort each and merge both. return merged

Question 18

Algorithm Definition

Answer 18

A defined set of sequential operations to apply to data in order to achieve a useful output.

Question 19

Sorting Algorithm Efficiency Factors

Answer 19

Extra memory needed in addition to the input data
How many comparisons the CPU makes between data
How often two elements are swapped
How many times the algorithm scans the entire dataset

Question 20

Data Compression

Answer 20

Representing the same information using fewer bits for more efficiency

Question 21

Data Compression Algorithms

Answer 21

Run-Length Encoding - Replace repeated values with an instance and a count. Lossless

Huffman Encoding - Binary tree created based on character frequency, where traversal is optimised for most frequent characters. Lossless

Truncation - Redundant data is removed. Lossy

Dictionary Encoding - Dictionary created, containing frequently repeating patterns and their keys. Lossless

Question 22

Lossy and Lossless Algorithms

Answer 22

Lossy - JPEG, MP3

Lossless - PNG, ZIP

Question 23

Shortest Path Algorithms

Answer 23

Djikstra’s Algorithm - Find smallest weighing of adjacent nodes from the start until the end node is reached.

A* Algorithm - Estimates the smallest weighing heuristically until the shortest path is found.

Question 24

Binary Search

Answer 24

Compare searched value with midpoint of sorted list. If greater of smaller than it, compare it with the midpoint of the respective sublist. Repeat until a midpoint is equal or not found.

Pseudocode
Def left,right, while left<right compare value with array[mid]

Question 25

Big O Notation In Order of Efficiency

Answer 25

E(k) E(logn) E(n) E(n^2) E(k^n)

Question 26

Determining Time Efficiency of Algorithm

Answer 26

Count the basic operations and consider how they grow with n. No of operations within loops become coefficients and outside constants. To represent using big O notation, only use the largest order term. O(1+n) = O(n) (if loop is to n-1, assume n)

Question 27

Determining Space Efficiency of Algorithm

Answer 27

Consider how each variable grows in memory with respect to n.