Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

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
Q

what makes a graph connected?

A

a graph is connected if it contains a path from any vertex to any other vertex

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

what are the maximal connected subgraphs of a disconnected graph?

A

the connected components of the graph

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

when do we draw an arc?

A

whenever the DFS visits a vertex coming from another vertex

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

what is an arc?

A

a directed edge

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

What is the BFS shortest path claim?

A

A BFS tree with root r always contains the shortest path from r to every vertex

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

what is a spanning tree?

A

A tree T = (V, F) with edges from E that connects every vertex of G

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

what is a minimum spanning tree?

A

a spanning tree T of minimal total cost

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

what are the 2 properties of spanning trees?

A

cycle property and cut property

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

what is cycle property?

A
  1. adding any edge uv to T creates a cycle C

2. removing any edge u’v’ from C creates a new spanning tree

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

what is the cut property?

A
  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
Q

what is the cycle rule of min-cost spanning trees?

A

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
Q

what is the cut rule for min-cost spanning trees?

A

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
Q

What is prims algorithm?

A
  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
Q

What is Kruskal’s algorithm?

A
  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
Q

What is a greedy algorithm?

A

a greedy-type solution to an optimisation problem that always finds the true (global) optimum in the end

40
Q

What is a greedy heuristic?

A

rule of thumb optimisation: usually works, sometimes fails

41
Q

Shortest paths tree statement:

A

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
Q

what are the 3 vertex types in Dijkstra’s shortest path algorithm?

A

marked, queued, unseen

43
Q

What length is every sensible path?

A

at most n

44
Q

What is dynamic programming?

A

an advanced algorithm design principle

45
Q

What is the time of Floyd-Warshall?

A

O(n^3)

46
Q

What makes a graph bipartite?

A

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
Q

Bipartite Graph Theorem

A

A graph G is bipartite iff it has no cycles of odd length

48
Q

Are trees bipartite?

A

Every tree is a bipartite graph because it has no cycles, so no odd length cycles

49
Q

What is the time complexity of propagation?

A

O(n + m)

50
Q

What is a vertex colouring?

A

an assignment that assigns a colour to every vertex of a graph

51
Q

What makes vertex colouring proper?

A

it assigns different colours to end-vertices of all edges.

52
Q

When is a graph k-colourable?

A

if it has a proper vertex colouring with at most k colours

53
Q

What is the chromatic number of a graph?

A

x(G), the minimum k such that G is k-colourable

54
Q

Is there an efficient algorithm to decide whether a graph is 3-colourable?

A

unlikely

55
Q

Is there an efficient algorithm to compute the chromatic number of a graph?

A

unlikely

56
Q

What is primality testing?

A

is a d-digit number prime or not?

57
Q

What is submodular minimisation?

A

an important difficult problem in combinatorial optimisation.

58
Q

What is P-Hard?

A

if we could solve every problem X in polynomial time, then we could solve every problem in P in polynomial time

59
Q

What is the NP class?

A

a class of puzzle-like problems with answer yes or no. yes = there is a “witness” solution, no = no universal proof

60
Q

What does it mean if a problem is NP-complete?

A

it has no efficient solution

61
Q

What is the NP fact?

A

If any NP problem can be solved by an efficient algorithm, then every problem in NP can be solved efficiently.

62
Q

What is a lower bound on the problem complexity?

A

showing that a problem cannot be solved in a certain time/space

63
Q

3 kinds of lower bound:

A

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
Q

What is the Comparison Sorting lower bound?

A

any sorting algorithm that only uses comparisons to decide the item order must take running time Ω(n log n) for most inputs

65
Q

2 ways to show that a problem is NP-complete?

A
  1. is a known NP-complete problem

2. use reduction algorithm to show

66
Q

What is reduction?

A

a translation from one problem to another

67
Q

What is the Hamilton Path Problem?

A

given G, check whether G has a Hamilton path. suppose we know the path is NP-complete.

68
Q

What is the Hamilton Cycle Problem?

A

given G, check whether G has a Hamilton cycle. Prove it is NP-complete.

69
Q

What is the heap property?

A

every node in the tree contains smaller value than both its children.

70
Q

What does the internal node of a comparisons decision tree represent?

A

a comparison question

71
Q

What does the leaf of a comparisons decision tree represent?

A

a final answer

72
Q

What does a comparison tree do?

A

represents the sequence of comparisons performed by an algorithm

73
Q

How many leaves does a binary tree of height h have

A

2^h

74
Q

What time complexity is called “asymptotically optimal”?

A

O(n log n)

75
Q

What is the time complexity of counting sort?

A

O(n)

76
Q

Is counting sort stable?

A

yes

77
Q

What is Radix sort?

A

for sorting fixed-length “column based” data

78
Q

What is the time complexity of Radix sort?

A

O(n)

79
Q

What is a proposition?

A

a statement that can be True or False

80
Q

What is CNF?

A

Conjunctive Normal form

81
Q

What is DNF?

A

Disjunctive Normal Form

82
Q

What is a clause?

A

A disjunction of literals

83
Q

What is a complete graph?

A

(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.
© 2024 Bold Learning Solutions. Terms and Conditions