2.3 Algorithms

Question 1

Algorithm

Answer 1

“A sequence of steps designed to perform a particular task. An algorithm may be constructed to describe the operation of a complete system or to describe a particular part of it.”

Question 2

Big O Notation

Answer 2

“Used in computer science to describe the performance or complexity of an algorithm. Big-O specifically described the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.”

Question 3

Bubble Sort

Answer 3

“A simple algorithm popular with inexperienced programmers. It is inefficient when sorting large amounts of data as the time taken is related to the square of the number of items. If 10 items take 1ms then 100 times will take 100ms (this is 10 times the number of items and so the time will be 102 or 100 times longer).”

Question 4

Insertion Sort

Answer 4

“A simple sorting algorithm that builds the final sorted array (or list) one item at time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.”

Question 5

Merge Sort

Answer 5

“A type of divide and conquer algorithm that was incited by John von Neumann. First the list is divided into the smallest unit (1 element), then each element is compared with the adjacent list to sort and merge the two adjacent lists. Finally all elements are sorted and merged.”

Question 6

Quick Sort

Answer 6

“A type of divide and conquer algorithm which sorts the given sequence in place meaning that it doesn’t require extra storage as would be needed in a merge sort. The basic idea is dividing the sequence into two sub-lists around an element which is called the pivot such that all elements in the lower sub-list are less than the value of the pivot element and all elements in the higher sub-list are greater than the pivot element.”

Question 7

Dijkstra’s Shortest Path

Answer 7

“A graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree. This algorithm is often used in routing and as a subroutine in other graph algorithms. In practice in picks an unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbour, and updates the neighbours distance if smaller. It the marks the visited when done with neighbours.”

Question 8

A* Algorithm

Answer 8

“Widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it follows a path of the lowest expected total cost or distance, keeping a sorted priority queue of alternate path segments along the way.”

Question 9

Binary Search

Answer 9

“A particularly efficient search method. It only works if records in the file are in sequence. A binary search involvers accessing the middle record in the file and determining if the target record has been found or, if not, if it is before or after in the sequence. This process is repeated on the part of the file where the target record is expected, until it is found.”

Question 10

Linear Search

Answer 10

“Involves examining each entry in turn in the file until the time is found or the end of the file is reached. Unless the file is in some useful order a serial search has to be used.”