Cs- Algorithms

define time complexity

a measure of how the running time of an algorithm increases as the size of input increases

define algorithm

a step by step set of instructions used to solve a problem

define a bubble sort

repeatedly compares adjacent elements and swaps them if they are in the wrong order

define insertion sort

builds a sorted section of a list by inserting each value into its correct position

Binary search

repeatedly checks the middle value of a sorted list, halving the search space each time

LIST MUST BE SORTED

O(logn)

ADV and DIS of binary search

DIS = only works on sorted lists

ADV = fast/ reduces search space by half each time

ADV and DIS of linear search

ADV= works on unsorted lists + simple to implement

DIS = slow for large lists as each item has to be checked

ADV + DIS of insertion sort

ADV = efficient for small or nearly sorted lists

DIS = inefficient for large lists due to many comparisons

ADV and DIS of bubble sort

ADV = simple + easy to understand

DIS = requires many passes through the list- inefficient for large data sets

ADV and DIS of merge sort

ADV = more efficient than bubble + insertion sort for large lists

DIS = requires additional memory

ADV and DIS for quick sort

ADV = fast for large lists

DIS = can be slow if poor pivot is chosenD

Describe how merge sort works

uses a divide and conquer approach

list repeatedly split into smaller sublists until each sublist contains one element

these sublists then merged back together in order, comparing elements and placing into their correct position

process continues until entire list is sorted

ADV and DIS of Dijkstra’s algorithm

ADV = guarantees shortest path - no heuristic required

DIS = slower than A* for many graphs (explores many unnecessary nodes)

Does not work with negative edge weights

ADV and DIS of A* algorithm

ADV = faster than Dijkstra’s- heuristic to guide the search

DIS = depends on quality of heuristic

What is Dijkstra’s algorithm?

finds the shortest path between one node and all other nodes on a weighted graph

Describe how Dijkstra’s algorithm works

start node distance = 0

all other nodes = infinity

The unvisited node with the smallest tentative distance is selected

update distance to its neighbours if a shorter path is found

mark the node as visited

repeat until all nodes are visited or destination has been reached

What is A* path finding algorithm used for?

to find the shortest path by using both the distance so far and a heuristic

What is a heuristic?

an estimate of the remaining distance to the destination

How does A* algorithm work?

calculates a value for each node by adding the distance from start node to a heuristic estimate of the distance to the goal

the node with the lowest total value is visited next

this process continues until destination is reached

define recursion

a technique where a function calls itself to solve a problem.

A base case is required to stop the problem and prevent infinite calls

ADV and DIS of recursion

ADV = leads to cleaner, simpler code

DIS = uses more memory than the call stack/ slower than iteration

How does recursion work?

function calls itself with a simpler input each time

this continues until a base case is reached, at which point the function stops calling itself returns

values back up the call stack

recursion + iteration, SIM and DIF

SIM = both are used to repeat a process

DIF = recursion uses function calls, iteration uses loops

what is space complexity?

measures the total memory an algorithm uses as the input size grows

Why does merge sort have O(n) space complexity?

It creates temporary arrays during the merge process

what’s technique for pre order, in-order, and post order?

pre order = root, left, right

in order = left, root, right

post order = left, right, root (kids before parents)