Studied by 2 people
What is recursion?
When a function calls itself
What are the 3 rules of a recursive function?
1) Base case (stopping condition)
2) It can reach the base case
3) The subroutine must call itself
What is Big-O notation?
A measure of the time complexity of an algorithm
What is time complexity?
The amount of time needed to solve a problem
What is space complexity?
The amount of resources needed to solve a problem (e.g. memory)
How does a linear search work?
Iterate through a list of items. Stop if you find what you are searching for. Otherwise keep going to the end
What is the time complexity of a linear search?
O(n)
How does a binary search work?
Check the middle value of the list. Compare your value to this value and if it is higher discard the bottom half of the list or vice versa. Keeps halving the list until you find your item or until there are no items left
What is required for a binary search to be able to take place on a list?
The list needs to be sorted
What is the time complexity of a binary search?
O(logn)
How does a bubble sort algorithm work?
Compare the first two elements and swap them if they aren't in the correct order. Keep going through the list comparing pairs of values and swapping if necessary. Repeat this process the number of times as the length of the list
What is the time complexity of a bubble sort?
O(n²)
How does a merge sort algorithm work?
Divide the unsorted list into sublists of each containing one element. Repeatedly merge two sublists at a time to produce new sorted sublists until there is only one sublist remaining
What is the time complexity of a merge sort?
O(nlogn)
What are the two types of graph-traversal algorithms?
Depth-first and breadth-first
How does a depth-first graph traversal algorithm work?
Go as far as you can down a path before backtracking and searching other paths
What data structure does a depth-first algorithm use?
A stack
How does a breadth-first graph traversal algorithm work?
Explore all neighbours of the current vertex, then the neighbours of each of those vertices and so on
What are possible applications of depth-first traversal?
Navigating a maze, Job scheduling where some jobs have to be completed before others begin
What are possible applications of breadth-first traversal?
Finding the shortest path between two points, A web crawler that analyses sites by following links randomly
What is the time complexity of depth-first and breadth-first searches?
In a sparse graph O(n) but if every vertex has the maximum number of edges it is O(n²) as every vertex must be searched and n number of edges from each vertex
What are the 3 different tree traversal algorithms?
Pre-order, in-order, post-order
Which order do you traverse a tree using the 3 (binary) tree traversal algorithms?
Pre-order) Root, Left, Right
In-order) Left, Root, Right
Post-order) Left, Right, Root
What is a use of pre-order?
Copying a tree
What is a use of in-order?
Outputting contents of a binary tree in ascending order
What is a use of post-order?
Emptying a tree
What algorithm can be used to find the shortest path between nodes on a graph?
Dijkstra's shortest path algorithm
What must be true about a graph for Dijkstra's algorithm to work?
It must be weighted
What supporting data structure does Dikjstra's algorithm use?
A priority queue
How does Dijkstra's algorithm work?
1) Set distance to starting node to 0 and all other nodes to infinity
2) Search all connected nodes to starting node and note their value down in priority queue
3) Remove starting node from queue and search all adjacent nodes to the next node in the queue
4) Update any values in the queue if there is a shorter path
5) Dequeue item
6) Repeat until no nodes left in queue
When is a problem defined as being computable?
If there is an algorithm that can solve every instance of it in a finite number of steps
What is a tractable problem?
A problem with a polynomial-time solution (or less)
What is an intractable problem?
A problem that does not have a polynomial-time solution e.g. time complexity O(2^n) and O(n!)
How do we attempt to solve intractable problems with computers?
Come up with heuristic approaches (an imperfect solution but does a good enough job)
Note
Flashcard