Algorithms Flashcards
(39 cards)
What is an algorithm?
A set of instructions that when followed can solve a specific problem
What are the two ways of traversing a graph?
Breadth first and depth first
How does breadth first traversal work?
A method for traversing a graph that explores nodes closest to the starting node first before progressively exploring nodes that are further away
What is depth first traversal?
A method for traversing a graph that starts at a chosen node and explores as far as possible along each branch away from the starting node before backtracking
Why do we traverse a tree?
To extract data in a particular order ; pre-order, in-order, post-order
What does it mean to visit a node?
Extracting the data at that node
What is a pre-order traversal?
A method of traversing a tree by visiting the root, traversing the left subtree and then traversing the right subtree
What is in-order traversal?
A method of traversing a tree by traversing the left subtree, visiting the root and traversing the right subtree
What is post-order traversal?
A method of traversing a tree by traversing the left subtree, traversing the right subtree and then visiting the root
What is traversal?
The process of reading data
What is a recursion?
When the function calls itself
How does recursion work?
After the procedure has been called for the first time the program will check if theres a node to the left. If there is then it goes left and the procedure calls itself.
Keeps repeating the process until there are no more nodes to visit on the left ; reaches terminating case
What is a terminating case?
The point at which the recursive function will stop calling itself
(AKA base case)
What is Dijkstra’s algorithm?
An algorithm that calculates the shortest path between two vertices/nodes on a graph
[can only be used in weighted graphs]
What type of queue do you use in Dijkstra’s algorithm?
A priority queue
Steps to do dijkstra’s algorithm
set a to 0 and evrything to infinity
What do you use to keep a note of the path travelled of the nodes?
A trace table
What are some uses of Dijkstra’s algorithm?
- Satnav
- Logistics and scheduling: where there is a large network of vehicles eg planes and buses, the algorithm can be used to calculate the optimum routes
- Telephone and computer network planning ; where the vertices are network devices and the edges are the connections between them? Algorithm is used to find the shortest route to send data packets
What is a linear search?
A search technique that looks through every single item of data until the search item is found; one at a time
[best for small datasets]
[Big O notation is O(n)]