19-21 Flashcards
What is a depth first search?
Depth first search goes deeper whenever possible, backtracking up once it can go no deeper.
Why would we use an iterative search method instead of a recursive?
We might choose to use an iterative search method rather than a recursive. This could be done to get around the maximum recursion limit or increase efficency.
What is a directed acrylic graph? How can we find a path?
A directed acyclic graph (DAG) has no cycles, these can be used to model a project’s dependencies. By topologically sorting this we can get a list of what order to do things.
If we want to find the path between two locations we can use a DFS, this will not typically be optimum though.
What can make basic graphs more useful? What is Dijkstra’s algorithm?
Graphs become more useful once their edges have been weighted, this can allow us to model many different situations. A good application for these is finding the shortest path between two nodes.
Dijkstra’s algorithm uses a breadth-first search and a priority queue which keeps track of the shortest distance so far.
What is the complexity of Dijkstra’s algorithm?
Dijkstra’s algorithm has O(n^2) time complexity if the queue is badly implemented, this implementation is better if there are lots of edges, but a low amount of nodes. With a better priority queue the complexity is instead (n). Where n is the number of vertices.
How does a minimum spanning tree apply to graphs?
A minimum spanning tree is good for if a path needs to be made between every node, giving the minimum total cost. A shortest path algorithm does not give the best answer here as the shortest path may be quicker but does not reutilise already made paths to save costs.
What is Prim’s algorithm?
Prim’s algorithm is a minimum spanning tree algorithm that works similar to dijkstra’s algorithm. We use a priority queue and add edges greedily. The shortest edges are added to the current tree (replacing already in place paths if the edge is shorter than the current edge to the same location).
What is a greedy algorithm?
A greedy algorithm solves an optimisation problem by taking the option that seems best at that moment. This is typically done using a priority queue. Because these are simple to implement they are typically tried first.
What is the knapsack problem? Which is the greedy algorithm good for and why?
The knapsack problem involves items with a given benefit and a cost(weight), you have a bag which can carry a maximum weight. The 0-1 knapsack problem means we cannot take fractions of items. The fractional knapsack problem does let us take fractions of items. A greedy algorithm is optimal for a fractional knapsack problem, but not for the 0-1 knapsack problem as the greedy algorithm may not fill the knapsack. The greedy algorithm tends to be the worst when the most valuable item relative to its weight takes up some amount of space and the rest of the items are larger than the remainder.
How can we solve the 0-1 knapsack problem?
To solve the 0-1 knapsacke problem we let V be a 2D array storing the maximum possible value using the first k items in S(Sk) and maximum total weight w (So there will be optimum solutions for different weights, for different sets of items). The array is calculated starting with only 1 item in S, increasing by one with each column.
