Computer Science Searching and Sorting and modelling (complex computer science)

Recursion

The repeated application of a recurring procedure

Linear search steps

1. Algorithm iterates through each element of the list one by one.

2. It compares each element to the key (the value being searched for).

3. If the current element matches the key, the search is successful, and the index of the element is returned.

4. This process continues until either the key is found or the end of the list is reached.

Worst and best case for Linear search

Worst: O(N)

Best: O(1)

Binary search steps

1. Start with the entire sorted list

2. Calculate the midpoint of the list

3. Compare the midpoint value with the target value (the key)

4. If the midpoint value is equal to the target value, the search is successful and ends.

5. If the midpoint value is greater than the target value, search the left half of the list.

6. If the midpoint value is less than the target value, search the right half of the list.

7. Repeat This process until the target value is found or the search interval is empty.

Best and worst case for binary search

Best: O(1)

Worst: O(log2(N))

Selection Sort

1. Find the smallest element in the unsorted portion of the array.

2. Swap it with the first element of the unsorted portion.

3. Move the boundary of the unsorted portion of the list one element to the right.

4. Repeat steps 1-3 until the entire array is sorted.

Best and worst case for selection sort

Worst Case: O(N²)

Best Case: O(N²)

This is because every value in the list has to compare itself with every other value.

Insertion Sort

1. Starting with the second element, each element of the array is compared with the elements before it (to its left).

2. For each element, we compare it with the elements to its left (which are already sorted at that point).

3. If the element to the left is larger than the current element, we shift the larger element to the right, making space for the current element to be inserted in its correct position.

4. This process continues for each element in the array until the entire array is sorted.

Worst and Best case for Insertion sort

Both is O(N²) as every value is compared.

Bubble sort.

Iterates through a list by comparing pairs at a time. At each step of the bubble sort process, the pairs of items are compared and fixed with the higher number in front.

Worst and best case for bubble sort

Worst: O(N²)

Best: O(N)

Quicksort

A recursive sorting algorithm that selects a pivot element from the list and partitions the list into two sublists: One with elements smaller than the pivot and the other with elements larger than the pivot. It then recursively applies the same process to each sublist until the entire list is sorted.

Best and Worst case for quicksort

Worst: List is sorted in descending order O(N²)

Best: When the pivot at each step splits the list in half O(N x log(N))

Big-O notation

A simplified analysis of an algorithms efficiency.

Heuristics

Problem solving strategies or rules of thumb that simplify complex decision-making processes into an algorithm which may not always give the exact answer.

Equation Based Modelling

An approach where you define the behaviour of a system using mathematical equations.

Agent based modelling

A computational approach used to simulate complex systems by modelling individual “Agents” and their interactions. In agent based modelling, each agent follows simple rules, and emergent behaviours may be seen.

Emergent behaviour

Collective patterns or phenomena that arise from the interactions of individual agents within a system that are not explicitly programmed.

Examples of where Agent based Modelling may be used

1. Economic processes

2. Ecological systems, e.g. a school of fish.

3. Traffic

Computer Modelling

Simulation