Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Algorithms and Complexity > Block 3: Graph Algorithms > Flashcards

Block 3: Graph Algorithms Flashcards

1
Q

how would you write th edge connecting vertices u and v?

A

uv

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What does “u and v are adjacent” mean?

A

that u and v are neighbours on the graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what does it mean for a graph to be eulerian?

A

every edge can be visited in a single tour.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

what is hamiltonicity?

A

whether on not you can visit every vertex of a graph in a single tour

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

what are 2 popular ways to stare edges?

A

adjacency lists and adjacency matrix

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

what is the time complexity for finding whether or not an edge exists?

A

Θ(1) for the first, Θ(dG(v)) for the second

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what is the time to iterate through all edges of a graph?

A

Θ(n^2) for the first, Θ(n + m) for the second

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the sum of degrees theorem?

A

the sum of degrees of vertices in a graph G = (V, E) equals twice the number of edges in G.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

what is a graph traversal?

A

an algorithm for visiting every vertex of a graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

what are the 2 main orders of graph traversal?

A

DFS and BFS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

what is the DFS process?

A
  1. mark vertex v
  2. visit v
  3. for every neighbour u of v, if u unmarked, call DFS on u recursively
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the BFS process?

A
  1. before calling, initialise with all vertices unmarked
  2. create an empty queue
  3. mark a vertex v, add v to queue
  4. 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

what is memoization?

A

remember all computed subproblems to avoid recomputation in a big table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

what is dynamic programming?

A

replace “recursive scaffolding” to work directly on the table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the knapsack problem definition?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what are the common traits between all subproblems in a bigger problem?

A

> capacity is between 0 and original

> item list is [I1, I2, … , Ii]: first i items

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

what is the worst case time complexity of a naïve search?

A

O(nm)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

what is the average performance time of Rabin Karp

A

O(n)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

what are the steps for BFS on a graph?

A
  1. Before calling, initialise with all vertices unmarked
  2. create empty queue
  3. mark a vertex v, add v to queue
  4. 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

what is Pₙ ?

A

a path on n vertices, a graph with verticies v1, v2, … , vn and edges v1v2, v2v3, … , vn-1vn

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

what is Cₙ ?

A

a cycle on n vertices. Obtained if we add edge vnv1 to Pₙ

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

what is a tree in terms of graphs?

A

a connected graph with no cycles and n - 1 edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

what is a complete graph on n vertices, Kₙ?

A

a graph on n vertices in which every 2 vertices are joined by an edge (are adjacent)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

what is the DFS pattern on a graph?

A
  1. Mark vertex v
  2. visit v
  3. for every neighbour u of v; if u in unmarked: call DFS(u) recursively
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
what makes a graph connected?
a graph is connected if it contains a path from any vertex to any other vertex
26
what are the maximal connected subgraphs of a disconnected graph?
the connected components of the graph
27
when do we draw an arc?
whenever the DFS visits a vertex coming from another vertex
28
what is an arc?
a directed edge
29
What is the BFS shortest path claim?
A BFS tree with root r always contains the shortest path from r to every vertex
30
what is a spanning tree?
A tree T = (V, F) with edges from E that connects every vertex of G
31
what is a minimum spanning tree?
a spanning tree T of minimal total cost
32
what are the 2 properties of spanning trees?
cycle property and cut property
33
what is cycle property?
1. adding any edge uv to T creates a cycle C | 2. removing any edge u'v' from C creates a new spanning tree
34
what is the cut property?
1. 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
35
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)
36
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.
37
What is prims algorithm?
1. begin with tree T of single vertex v, no edges 2. repeat until T is a spanning tree: Extend T by the cheapest edge uv where u in T, v not in T
38
What is Kruskal's algorithm?
1. begin with T = ∅ 2. sort all edges of E by weight 3. for every edge e in this order: if adding e to T does not create a cycle, add e to T
39
What is a greedy algorithm?
a greedy-type solution to an optimisation problem that always finds the true (global) optimum in the end
40
What is a greedy heuristic?
rule of thumb optimisation: usually works, sometimes fails
41
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)
42
what are the 3 vertex types in Dijkstra's shortest path algorithm?
marked, queued, unseen
43
What length is every sensible path?
at most n
44
What is dynamic programming?
an advanced algorithm design principle
45
What is the time of Floyd-Warshall?
O(n^3)
46
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
47
Bipartite Graph Theorem
A graph G is bipartite iff it has no cycles of odd length
48
Are trees bipartite?
Every tree is a bipartite graph because it has no cycles, so no odd length cycles
49
What is the time complexity of propagation?
O(n + m)
50
What is a vertex colouring?
an assignment that assigns a colour to every vertex of a graph
51
What makes vertex colouring proper?
it assigns different colours to end-vertices of all edges.
52
When is a graph k-colourable?
if it has a proper vertex colouring with at most k colours
53
What is the chromatic number of a graph?
x(G), the minimum k such that G is k-colourable
54
Is there an efficient algorithm to decide whether a graph is 3-colourable?
unlikely
55
Is there an efficient algorithm to compute the chromatic number of a graph?
unlikely
56
What is primality testing?
is a d-digit number prime or not?
57
What is submodular minimisation?
an important difficult problem in combinatorial optimisation.
58
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
59
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
60
What does it mean if a problem is NP-complete?
it has no efficient solution
61
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.
62
What is a lower bound on the problem complexity?
showing that a problem cannot be solved in a certain time/space
63
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
64
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
65
2 ways to show that a problem is NP-complete?
1. is a known NP-complete problem | 2. use reduction algorithm to show
66
What is reduction?
a translation from one problem to another
67
What is the Hamilton Path Problem?
given G, check whether G has a Hamilton path. suppose we know the path is NP-complete.
68
What is the Hamilton Cycle Problem?
given G, check whether G has a Hamilton cycle. Prove it is NP-complete.
69
What is the heap property?
every node in the tree contains smaller value than both its children.
70
What does the internal node of a comparisons decision tree represent?
a comparison question
71
What does the leaf of a comparisons decision tree represent?
a final answer
72
What does a comparison tree do?
represents the sequence of comparisons performed by an algorithm
73
How many leaves does a binary tree of height h have
2^h
74
What time complexity is called "asymptotically optimal"?
O(n log n)
75
What is the time complexity of counting sort?
O(n)
76
Is counting sort stable?
yes
77
What is Radix sort?
for sorting fixed-length "column based" data
78
What is the time complexity of Radix sort?
O(n)
79
What is a proposition?
a statement that can be True or False
80
What is CNF?
Conjunctive Normal form
81
What is DNF?
Disjunctive Normal Form
82
What is a clause?
A disjunction of literals
83
What is a complete graph?
(Kvn) a graph on n vertices in which every 2 vertices are joined by an edge

Algorithms and Complexity (3 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions