2.3 - Algorithms

Page 1

2.3.1 - Algorithms

Suitability of Different Algorithms:

The goal is to design algorithms which will run quickly whil taking up the minimal amount of resources such as memory.

Time Complexity:

How much time an algorithm needs to solve a particular problem.

Space Complexity:

How much working storage an algorithm needs.

Permutations:

The number of ways of arranging a set of objects.

Big-O Notation:

Used to express time complexity (and space complexity).

Constant Time:

O(1) - describes an algorithm that takes a constant timeto execute regardless of the size of the data.

Linear Time:

O(n) - describes an algorithm in which its time complexity increases in direct proportion to the size of the data.

Polynomial Time:

O(n^2) - describes an algorithm in which its time complexity increases in direct proportion to the square of the size of the data.

Exponential Time:

O(2^n) - describes an algorithm in which its time complexity will double with every additional item in the data.

Logarithmic Time:

O(log n) - describes an algorithm in which its time complexity will grow very slowly in comparison to the size of the data.

Factorial Time:

O(n!) - describes an algorithm in which its time complexity will grow very quickly.

Ordered from Slowest to Fastest:

O(1)

O(log n)

O(n)

O(n^2)

O(2^n)

O(n!)

Standard Algorithms:

Searching Algorithms:

Linear Search:

Items are searched through one by one until the required item is found, or the end of the list is reached.

Items can be unordered.

Has time complexity of O(n).

Binary Search:

Items MUST be ordered.

Repeatedly divides the data set in half, comparing the middle value to the required value:

If the middle value is bigger, the middle value and all values above are discarded.

If the middle value is smaller, the middle value and all values below are discarded.

Has time complexity of O(log n).

Sorting Algorithms:

Bubble Sort:

Go through the array, comparing each item with the one next to it:

If it is greater, swap them.

If not, compare the next item with the next item after that.

The last element in the array will be in the correct place after the first pass.

Repeat n-2 times, reducing by on on each pass the number of elements can be examined.

Has time complexity of O(n^2).

Insertion Sort:

Sorts one data item at a time.

The current data item is compared against all other items before it, and then placed into its correct position.

Has time complexity of O(n^2).

Merge Sort:

Uses divide and conquer.

A list of n items is cut in half repeatedly until there are n sublists, each containing one element.

These sublists are then combined together again, in opposite to the first step, only this time they are sorted together.

Has time complexity O(log n).

Requires additional memory space of the merging process.

Quick Sort:

Uses divide and conquer, but does not require extra stprage required by the merge sort.

Steps:

A pivot is selected, normally chosen as the first item in the list.

All remaining items are divided into two groups: values that are bigger and values that are smaller.

Depending on the whether the list is to be sorted in descending or ascending, the values are placed on either side of the pivot (this is not sorted, they are placed in the order they are presented).

The process is then repeated for each partition until the list is sorted.

Has time complexity of O(log n).

Advantages:

Very fast.

Does not require additional memory space.

Disadvantages:

Can result in a time complexity of O(n^2) if the divisions are uneven - i.e. the split point is the first item in the list.

If the list is very large, and recursion is repeated too many times, it may cause stack overflow and the program will crash.

Dijkstra's Shortest Path Algorithm:

Designed to find the shortest path between one particular start node and all other nodes in a weighted graph.

A* Algorithm:

Has two cost functions:

g(x) - the real cost from the source node to a given node.

h(x) - the approximate cost from node x to the goal node:

It is a heuristic function.

Focuses on only reaching the goal node.

IT SHOULD BE NOTED THAT YOU NEED TO KNOW HOW TO IMPLEMENT ALL OF THESE ALGORITHMS USING PSEUDOCODE.

THIS ALSO INCLUDE ALL OF THE DATA STRUCTURES - STACKS, QUEUES, TREES, LINKED LISTS, DEPTH-FIRST (POST-ORDER) TRAVERSALS AND BREADTH FIRST TRAVERSALS.