Please enable JavaScript.
Coggle requires JavaScript to display documents.
COMP26120 Algorithms and Data Structures (26 marks for a 1st, 15 marks for…
COMP26120 Algorithms and Data Structures (26 marks for a 1st, 15 marks for 2:1)
Graph Algorithms (9 marks)
Introduction
We have directed and undirected graphs, where edge pairs are not ordered
A path is a sequence of nodes between two specific nodes. If not noted otherwise: paths are cycle-free ie no repeated nodes
A cycle is a path with the same start and end node
Simple graph
No parallel edges and no self loops
Spanning subgraph
A subgraph that contains all nodes
Operations for graphs are empty, addEdge, removeEdge, isEdge and succs
Adjacency Lists
These map each node to a list of successors
Memory O(|V| + |E|)
Adjacency Matrix
Implementation: m(u,v) = TRUE iff edge from u to v
Memory O(|V|^2), bad for sparse graphs
Generic Graph Traversal Algorithm
Explore edges to new nodes untill all nodes discovered
Creating sets as we go: D for discovered, F for finished
Algorithm explore(s) returns exactly the nodes reachable from s
DFS vs BFS
Stack is DFS as last in is first out; this has a nice recurseive implementation
Queue is BFS as first in is first out
Topological Sorting
A set of tasks with dependencies between them can be modelled as a directed graph if we find a build sequence
We arrange node sequentially, such that all edges point forwards (so prerequisits come earlier in sequence) and have topologial sorting iff the graph has no cycles (Directed Acyclic Graph)
We use a DFS based algorithm for topological sorting and cycle detection (when encountering a node, it is marked as open until we've explored all its children. If we encounter it as open, then there is a cycle)
(You have to prepend nodes to the list when marked as done)
Shortest Paths
The shortest path from s to some node is the path with the minimal edges, found using BFS. We obtain the path via predecessor map and backtracking. We also do this with weigths
Multiple Shortest paths
Shortest path is not always unique, but distance is
We compute this using the Bellman Ford Algorithm; start with an overestimate, and improve it until it is precise
Loop invariant
justfication to prove a claim about a loop that holds initially, is preserved by loop iteration and implies correctness when loop terminates
For Bellman Ford, we claim that the shortest paths upto length I are precise, so we assume that at the end of round i, D is prcise uo to length i, so we show that at the end of round i + 1, D is precise up to length i + 1
The prefix of a shortest path is also a shortest path
Negative weight cycles
These mean there are no shortest paths reachable from the cycle
This is detected with Bellman Ford, as we iterate until D does not change, but if it still changes in the |V|th round, there must be a negative cycle
Complexity
Worst |V| rounds
Each round inspects |E| edges
Time for relaxing an edge is O(1)
Hence complexity sis O(|V||E|)
Search
Dijkstra's Algorithm
Using a priority queue, we relax nodes that we have looked at meaning, the value may decrease, so we need a decrease key function and use a minHeap to restore heap-property after pop, insertion and relaxation operations
By adding nodes as they are discovered we won't explore any unreachable nodes
We use predecessors to backtrack and find shortest path
Complexity
Every edge is relaxed at most once, every node is added and removed at most once
Cost of relaxing, addition and extraction within the min heap is O(log|V|)
O((|E|+|V|)log(|V|))
This will not produce correct results if there are edges with negative weights
A* Algorithm
Very similar to Dijkstra's but uses a heuristic
Heuristic Admissibility and Monotonicity
To use an heuristic it must be admissable (not overestimate true cost) and monotone (fir the trangle inequality)
Complexity wise it is the same as Dijkstra, but will be faster, terminate earlier as it stops when it finds the targetand use less memory
Minimum Spanning Trees
An MST will connect all nodes with the sum weight of the edges minimised
Generic Greedy Algorithm
Grow the MST one edge at the time (not always optimal)
Correctness
If A is our growing MST, then we must determine that a new edge is not in A yet, but will be in the whole MST then it will be safe (this is also the loop invariant as we add only safe edges)
Cuts and Light edges
A cut is a partition of V and respresents a set of edges if no edge in A crosses the cut
An edge is a light edge if its weight is the minimum of any edge ctossing the cut (more than one may exist)
We use Kruskal's algorithm, using disjoint sets to add to the MST, starting with the lowest weight. meaning it uses multiple MST to create the one
We also use Prim's algorthms, starting with arbitrary node r, adding a light edge that connects A to an isolated vertex, creating a single tree from a priority queue
Linear Programming (8 marks)
Number-Theoretic Algorithms (5 marks)
Tractability and NP-completeness (4 marks)
Intractability
Classes of Problems
P: problems that are solvable in polynomial time
NP: problems that are verifiable in polynomial time or solvable in polynomial time by a non-deterministic machine
NP-Hard: problems that are at least as hard as all problems in NP
NP-Complete: problems that are in both NP and NP-Hard
Reductions, given problems A and B where B is within A, and we know how to solve A, then we can solve B
Decision Problems, a function from some input to 0 or 1, answering if something exists
Optimisation Problem, has a decision problem within it, making the best decision
Abstract and Concrete Inputs
Abstract includes element, list, graph and circuit
Algorithms need these to be concrete ie represented in a way the computer understands ie binary representation
Synoptic Questions (14 marks)
