Test 3

Question 1

Attributes of greedy algorithms?

Answer 1

Always chooses best option at time, not always correct, proof by contradiction and disprove by counterexample

Question 2

Similarities between greedy algorithms and dynamic programming?

Answer 2

Makes a choice at each step

Question 3

Differences between greedy and dynamic programming?

Answer 3

Dynamic finds optimal solutions to subproblems solves bottom up, greedy makes choice before solving some problems. Solves top down

Question 4

What is the complexity to add an edge, remove an edge, is adjacent, for an adjacency matrix?

Answer 4

O(1)

Question 5

What is the complexity to add an edge, remove an edge, and isadjacent for an adjacency list?

Answer 5

O(1)

Question 6

What is the complexity difference between an adjacency list and an adjacency matrix to make?

Answer 6

An adjacency matrix takes O (n^2) vs adjacency list takes O(n)

Question 7

What is the complexity difference between an adjacency list and an adjacency matrix to GetNeighbors(v)?

Answer 7

For adjacency matrix it is O(n), and for an adjacency list it is O(deg(v)) which equates to? O(m). (M is the number of edges).

Question 8

What is the space difference between an adjacency list and an adjacency matrix?

Answer 8

O(n^2) for the adjacency matrix and O(m+n) for the adjacency list.

Question 9

Main difference in structure between BFS and DFS?

Answer 9

BFS is queue-based and DFS is recursively stack based

Question 10

Explain a BFS traversal tree

Answer 10

All non-tree edges are cross edges, they’re the same level or next level down

Question 11

Explain a DFS traversal tree

Answer 11

All non-tree edges are back edges, they connect to ancestors

Question 12

What are the characteristics of Dijkstra’s algorithm?

Answer 12

Weighted graph distance.

1. Choose vertex with minimum distance
2. Update Distance of neighbors with distance plus weight(u,v) if shorter.
3. Repeat until destination or all vertices explored

Question 13

Characteristics of prim’s algorithm?

Answer 13

Its a Minimum spanning tree

1. Choose closest vertex.
2. Update distance of neighbors with w(u,v) If shorter.
3. Repeat until all vertices explored.

Question 14

Describe Kruskal’s algorithm

Answer 14

1. Sort edges
2. Choose minimum edge
3. Add to MST if inpoints are not already joined

Question 15

What is the time complexity for Dijkstra’s algorithm?

Answer 15

O(|V|+|E|log|V|)

Question 16

Time complexity of BFS, DFS and topological sorting?

Answer 16

O(|V|+|E|)

Question 17

What is the time complexity of prim’s MST?

Answer 17

O(|V|+|E|log|V|)

Question 18

What is the time complexity of Kruskal’s MST?

Answer 18

O(|V|+|E|log|E|)

Question 19

What is the complexity of a graph? (How does m relate to n)

Answer 19

M= O(n^2)

Where m equals number of edges and n equals number of vertices

Question 20

What is adjacent mean in reference to a graph?

Answer 20

Two vertices with an edge between them

Question 21

What does degree mean in reference to a graph?

Answer 21

The number of vertices adjacent to a given vertex

Question 22

Describe an adjacency matrix

Answer 22

It’s an n by n matrix where:

A of IJ is one if v of I and v of j are adjacent otherwise it is zero.

Question 23

What is a walk in reference to a graph?

Answer 23

A sequence of vertices joined by edges

Question 24

What is a path in reference to a graph?

Answer 24

A walk with no repeated vertices or edges

Question 25

What is a circuit in reference to a graph?

Answer 25

A walk that begins and ends at the same vertex

Question 26

What is a cycle in reference to a graph?

Answer 26

A non-trivial path that begins and ends the same vertex, ie does not repeat edges or vertices

Question 27

What is connected mean in reference to a graph?

Answer 27

Two vertices that have a path between them

Question 28

Explain the process of BFS

Answer 28

1. Mark all vertices as undiscovered 2. Add v(0) to queue 3. Mark v(0) as discovered 4. While q is not empty: Dequeue vertex v Enqueue children of v that are undiscovered Mark v as explored Mark children as discovered 5. If any vertex still undiscovered choose one and restart process

Question 29

Explain DFS process

Answer 29

``` DFS recursive: 1. Mark v as discovered 2. For c in N(v): If C is undiscovered call DFS recursive on C 3. Mark v as explored ```

Question 30

What are the similarities of BFS and DFS?

Answer 30

1. Both traverse one component at a time 2. Both take O(n+m) time 3. Both traversal trees have special properties

Question 31

What are the differences between DFS and BFS?

Answer 31

1. DFS is somewhat easier to implement | 2. The usage depends on the application

Question 32

What can BFS and DFS both be used for?

Answer 32

Component detection and cycle detection

Question 33

What applications are better for BFS?

Answer 33

On way to distance, radius and center of unweighted graph, and between this centrality

Question 34

What applications are best for DFS?

Answer 34

Cut edge or cut vertex detection, sorting (on a BST), topological sorting and backtracing

Question 35

What does a traditional algorithm for topological sorting use?

Answer 35

DFS

Question 36

What is a spanning tree?

Answer 36

Given an undirected and connected graph, a spanning tree spans the entirety of the graph

Question 37

What is a minimum spanning tree?

Answer 37

Given an undirected weighted graph, a minimum spanning tree cost the least to span the whole tree

Question 38

Main difference between Prim's algorithm and Kruskal's algorithm?

Answer 38

Prim's runs faster and dense graphs with more edges and vertices, where? K is found to run faster and sparse graphs (Think about it, K is reliant on log (M) so less edges = better)