Unit 4 Quiz

Question 1

Graph

Answer 1

set of vertices and set of edges that relate to the vertices

Question 2

Path

Answer 2

how to get from one point to another

Question 3

Weighted Graph

Answer 3

Graph with “cost” associated with the travel from one vertex to another

Question 4

Directed Graph

Answer 4

Also called Digraph; a graph where each vertex has a one-way relationship represented with arrows

Question 5

Cyclic Graph

Answer 5

a graph that contains at least one cycle in it, meaning you can travel back to a vertex.
“All roads lead home”

Question 6

Acyclic Graph

Answer 6

no cycles allowed

Question 7

Biconnected Graph

Answer 7

Graph with no articulation points ( vertices whose removal disconnects the graph )

Question 8

Topological Sort

Answer 8

Printing of vertices ( nodes ) from graph so that if there is a path from Vi to Vj, then Vj appears after Vi. In other words, no prerequisites are violated.

Question 9

Topological sort has __________ and does not need to be _________

Answer 9

multiple answers ; truly sorted

Question 10

Trees are always ________

Answer 10

Acyclic

Question 11

All trees are _______

Answer 11

graphs

Question 12

Multilist

Answer 12

linked list of linked lists

Question 13

adjacency list

Answer 13

1d array of pointers to whoever we connect to

Question 14

Min spanning tree

Answer 14

Tree with minimum number of paths to connect

Question 15

When does dijkstras fail?

Answer 15

when there is a negative weight

Question 16

Dijkstras is a ______

Answer 16

connected graph

Question 17

dijkstras runtime

Answer 17

O ( E log V ) B, A, W
E = # edges
V = # vertices

Question 18

Topological Sort runtime

Answer 18

O ( E + V )
E = # edges
V = # vertices

Question 19

Depth and breadth first search runtime

Answer 19

O ( E + V )
E = # edges
V = # vertices

Question 20

Breadth first search

Answer 20

setup identical to DFS, but use a queue
Prints row by row left to right

Question 21

Depth first search

Answer 21

basically a preorder traversal in disguise
1) push start vertex onto stack
2) pop stack, output top vertex, mark it, push all adj non marked vertices.

Question 22

Euler circuit

Answer 22

Identical to Hamiltonian circuit, except we want to visit every edge once
- if every vertex has an even degree => euler circuit

Question 23

Circuit

Answer 23

special type of cycle on a connected, undirected graph

Question 24

Hamiltonian Circuit

Answer 24

circuit with a path that visits every vertex exactly once and returns to the starting point

Question 25

Upper bound

Answer 25

the best weve been able to do so far

Question 26

Lower bound

Answer 26

The best we can hope to do that is theoretically possible

Question 27

Is there a solution to the Euler bridge problem? why?

Answer 27

No because you have to get off the island.

Question 28

example of NP complete problem

Answer 28

travelling salesman problem , four color problem

Question 29

tractable problems

Answer 29

upper and lower bounds are polynomials

Question 30

NP complete problems

Answer 30

upper bound suggests intractable, but lower bound suggests tractable

Question 31

Intractable problems

Answer 31

upper and lower bounds are non-polynomial

Question 32

Undecidable problems

Answer 32

"impossible" to solve

Question 33

What is the halting problem?

Answer 33

trying to figure out if the program is going to run forever or not