Block 3: Graph Algorithms Flashcards
how would you write th edge connecting vertices u and v?
uv
What does “u and v are adjacent” mean?
that u and v are neighbours on the graph
what does it mean for a graph to be eulerian?
every edge can be visited in a single tour.
what is hamiltonicity?
whether on not you can visit every vertex of a graph in a single tour
what are 2 popular ways to stare edges?
adjacency lists and adjacency matrix
what is the time complexity for finding whether or not an edge exists?
Θ(1) for the first, Θ(dG(v)) for the second
what is the time to iterate through all edges of a graph?
Θ(n^2) for the first, Θ(n + m) for the second
What is the sum of degrees theorem?
the sum of degrees of vertices in a graph G = (V, E) equals twice the number of edges in G.
what is a graph traversal?
an algorithm for visiting every vertex of a graph
what are the 2 main orders of graph traversal?
DFS and BFS
what is the DFS process?
- mark vertex v
- visit v
- for every neighbour u of v, if u unmarked, call DFS on u recursively
What is the BFS process?
- before calling, initialise with all vertices unmarked
- create an empty queue
- mark a vertex v, add v to queue
- until queue is empty
i. dequeue a vertex u from the queue
ii. for every neighbour w of u, if w is unmarked, mark w and add to queue
what is memoization?
remember all computed subproblems to avoid recomputation in a big table
what is dynamic programming?
replace “recursive scaffolding” to work directly on the table
What is the knapsack problem definition?
Given n items [I1, I2, .. In], each with a size I.size and a value I.value, and a total capacity c, find the most valuable way to pack items of total size at most c.
what are the common traits between all subproblems in a bigger problem?
> capacity is between 0 and original
> item list is [I1, I2, … , Ii]: first i items
what is the worst case time complexity of a naïve search?
O(nm)
what is the average performance time of Rabin Karp
O(n)
what are the steps for BFS on a graph?
- Before calling, initialise with all vertices unmarked
- create empty queue
- mark a vertex v, add v to queue
- until queue is empty:
i. dequeue a vertex u from the queue
ii. for every neighbour w of u:
> if w is unmarked, mark w and add to queue
what is Pₙ ?
a path on n vertices, a graph with verticies v1, v2, … , vn and edges v1v2, v2v3, … , vn-1vn
what is Cₙ ?
a cycle on n vertices. Obtained if we add edge vnv1 to Pₙ
what is a tree in terms of graphs?
a connected graph with no cycles and n - 1 edges
what is a complete graph on n vertices, Kₙ?
a graph on n vertices in which every 2 vertices are joined by an edge (are adjacent)
what is the DFS pattern on a graph?
- Mark vertex v
- visit v
- for every neighbour u of v; if u in unmarked: call DFS(u) recursively
what makes a graph connected?
a graph is connected if it contains a path from any vertex to any other vertex
what are the maximal connected subgraphs of a disconnected graph?
the connected components of the graph
when do we draw an arc?
whenever the DFS visits a vertex coming from another vertex
what is an arc?
a directed edge
What is the BFS shortest path claim?
A BFS tree with root r always contains the shortest path from r to every vertex
what is a spanning tree?
A tree T = (V, F) with edges from E that connects every vertex of G
what is a minimum spanning tree?
a spanning tree T of minimal total cost
what are the 2 properties of spanning trees?
cycle property and cut property
what is cycle property?
- adding any edge uv to T creates a cycle C
2. removing any edge u’v’ from C creates a new spanning tree
what is the cut property?
- removing any edge uv from T disconnects T into 2 parts
2. Adding any edge u’v’ between these parts creates a new spanning tree
what is the cycle rule of min-cost spanning trees?
Let G = (V, E), be a graph with edge weights, T a spanning tree in G. Then T is min-cost if and only if:
> let uv be an element of E be any edge not used in T
> let C be the cycle created by adding uv to T
> then uv is the most expensive edge of C (can be tied)
what is the cut rule for min-cost spanning trees?
Let G = (V, E) be a graph with edge weights and T be a minimum spanning tree in G. then T is min cost if and only if for any split of V into two parts V = A ∪ B, T contains a cheapest edge between A and B.
What is prims algorithm?
- begin with tree T of single vertex v, no edges
- repeat until T is a spanning tree:
Extend T by the cheapest edge uv where u in T, v not in T
What is Kruskal’s algorithm?
- begin with T = ∅
- sort all edges of E by weight
- for every edge e in this order:
if adding e to T does not create a cycle, add e to T
What is a greedy algorithm?
a greedy-type solution to an optimisation problem that always finds the true (global) optimum in the end
What is a greedy heuristic?
rule of thumb optimisation: usually works, sometimes fails
Shortest paths tree statement:
For any graph, with a source vertex and non-negative edge lengths, shortest paths from s to all other vertices can be captured via a rooted spanning out-tree (branching)
what are the 3 vertex types in Dijkstra’s shortest path algorithm?
marked, queued, unseen
What length is every sensible path?
at most n
What is dynamic programming?
an advanced algorithm design principle
What is the time of Floyd-Warshall?
O(n^3)
What makes a graph bipartite?
if its vertices can be partitioned into sets (V1 and V2) such that every edge has one end vertex in V1 and the other in V2
Bipartite Graph Theorem
A graph G is bipartite iff it has no cycles of odd length
Are trees bipartite?
Every tree is a bipartite graph because it has no cycles, so no odd length cycles
What is the time complexity of propagation?
O(n + m)
What is a vertex colouring?
an assignment that assigns a colour to every vertex of a graph
What makes vertex colouring proper?
it assigns different colours to end-vertices of all edges.
When is a graph k-colourable?
if it has a proper vertex colouring with at most k colours
What is the chromatic number of a graph?
x(G), the minimum k such that G is k-colourable
Is there an efficient algorithm to decide whether a graph is 3-colourable?
unlikely
Is there an efficient algorithm to compute the chromatic number of a graph?
unlikely
What is primality testing?
is a d-digit number prime or not?
What is submodular minimisation?
an important difficult problem in combinatorial optimisation.
What is P-Hard?
if we could solve every problem X in polynomial time, then we could solve every problem in P in polynomial time
What is the NP class?
a class of puzzle-like problems with answer yes or no. yes = there is a “witness” solution, no = no universal proof
What does it mean if a problem is NP-complete?
it has no efficient solution
What is the NP fact?
If any NP problem can be solved by an efficient algorithm, then every problem in NP can be solved efficiently.
What is a lower bound on the problem complexity?
showing that a problem cannot be solved in a certain time/space
3 kinds of lower bound:
1) problems that can’t be solved at all (halting problem)
2) lower bounds against very restricted algorithms (comparison sorting)
3) conditional lower bounds
What is the Comparison Sorting lower bound?
any sorting algorithm that only uses comparisons to decide the item order must take running time Ω(n log n) for most inputs
2 ways to show that a problem is NP-complete?
- is a known NP-complete problem
2. use reduction algorithm to show
What is reduction?
a translation from one problem to another
What is the Hamilton Path Problem?
given G, check whether G has a Hamilton path. suppose we know the path is NP-complete.
What is the Hamilton Cycle Problem?
given G, check whether G has a Hamilton cycle. Prove it is NP-complete.
What is the heap property?
every node in the tree contains smaller value than both its children.
What does the internal node of a comparisons decision tree represent?
a comparison question
What does the leaf of a comparisons decision tree represent?
a final answer
What does a comparison tree do?
represents the sequence of comparisons performed by an algorithm
How many leaves does a binary tree of height h have
2^h
What time complexity is called “asymptotically optimal”?
O(n log n)
What is the time complexity of counting sort?
O(n)
Is counting sort stable?
yes
What is Radix sort?
for sorting fixed-length “column based” data
What is the time complexity of Radix sort?
O(n)
What is a proposition?
a statement that can be True or False
What is CNF?
Conjunctive Normal form
What is DNF?
Disjunctive Normal Form
What is a clause?
A disjunction of literals
What is a complete graph?
(Kvn) a graph on n vertices in which every 2 vertices are joined by an edge
