3.1 Fundamentals of algorithms

Contains: 3.1.1 Representing algorithms 3.1.2 Efficiency of algorithms 3.1.3 Searching algorithms 3.1.4 Sorting algorithms

Explain the term algorithm.

An algorithm is a sequence of steps that can be followed to complete a task.

(be aware that a computer program is an implementation of an algorithm and that an algorithm is not a computer program)

Explain the term decomposition.

Decomposition means breaking a problem into a number of sub-problems, so that each subproblem accomplishes an identifiable task, which might itself be further subdivided.

Explain the term abstraction.

Abstraction is the process of removing unnecessary detail from a problem.

Understand that more than one algorithm can be used to solve the same problem.

-

Compare the efficiency of algorithms.

Some algorithms are more efficient than others in solving the same problem because they are faster (time efficiency).

e.g code being shorter/variables are already declared in the code ← the simpler the algorithm, the less efficient the search/sort will be on very large numbers of records

Space efficiency looks at how much storage a code needs.

Understand and explain how the linear search algorithm works.

A linear search searches a list or other collection of data one item at a time until the desired search object is located.

Understand and explain how the binary search algorithm works.

Binary search uses DIVIDE AND CONQUER - a method for searching data that splits datasets into 2 components repeatedly until the search term is located.

Compare and contrast linear and binary search algorithms.

• Binary search is more efficient than linear search, especially for large data sets

• A binary search only works with an ordered list (whereas a linear search works with an unordered list)

• A binary search also needs to know the size of the list to identify the middle of it.

• A linear search has an algorithm that is easier to understand, whereas the binary search algorithm is more complex

Understand and explain how the merge sort algorithm works.

Merge sort is a sorting algorithm based on DIVIDE AND CONQUER

• it divides a list into half repeatedly until each data item is seperate

• the data items are combined in the same way they were divided, but in the correct order

• multiple individual lists are eventually all merged into one list and the algorithm ends.

Understand and explain how the bubble sort algorithm works.

• Bubble sort compares adjacent data elements (starting from the first value).

• Data elements are swapped if they are not in the correct order.

Compare and contrast merge sort and bubble sort algorithms.

• Merge sort is faster and therefore more efficient (1) for large lists (1) because it uses divide and conquer

• Has a consistent running time (1) so doesn’t depend on how ordered original list is (1)