CSCE4110 Final

Question 1

Advantages of adjacency list

Answer 1

works well for sparse graphs

space is theta(V + E)

Question 2

disadvantage of adjacency list

Answer 2

searching for edges slower than adjacency matrix

Question 3

advantages of adjacency matrix

Answer 3

works well for dense graph

edge lookup is theta(1)

Question 4

disadvantage of adjacency matrix

Answer 4

requires more space than adjacency list

Question 5

Examples of a BFS algorithm

Answer 5

Prims and dijkstras

Question 6

Goal for a BFS algorithm

Answer 6

find smallest number of edges to each reachable vertex

Question 7

time complexity for BFS

Answer 7

O(V+E)

Question 8

Explain BFS briefly

Answer 8

Pick a starting vertex
Visit all nodes connected to starting vertex (start alphabetically)
Mark visited node
Add visited node to Queue

Question 9

Explain DFS briefly

Answer 9

Pick a starting vertex
Visit next connected node (alphabetically)
Mark visited node
Add node to top of stack

Question 10

Time complexity of DFS

Answer 10

O(V+E)

Question 11

Are MST always unique

Answer 11

NO

Question 12

How are Prim’s and Kruskal’s algorithms greedy?

Answer 12

Adds smallest weighted edge each step as long as it maintains tree property

Question 13

Time complexity of Kruskals and Prims algorithm

Answer 13

O(E lg V)

Question 14

How is single-source shortest paths exhibit optimal substructure?

Answer 14

If we have a path p(xy) and patch a new path in between it would be impossible

Question 15

Can shortest paths be computed with negative weight edges?

Answer 15

Yes

Question 16

Can shortest paths be computed with negative edge cycle?

Answer 16

No

Question 17

Can a shortest path have a cycle?

Answer 17

No

Question 18

Initialize single source

3 steps

Answer 18

Set distance: infinity
Set predecessors: NULL
Set s.d: 0

Question 19

Running time of initializing single source

Answer 19

theta(V)

Question 20

Running time for bellman ford

Answer 20

theta(VE)

Question 21

Running time for Dijkstras

Answer 21

O(E lg V)

Question 22

All pair shortest path input and output

Answer 22

a matrix

Question 23

Max Flow equilibrium

Answer 23

inflow = outflow at every vertex

Question 24

Max flow termination

Answer 24

all paths from s to t are blocked by either full forward edge or empty backward edge

Question 25

applications for maxflow

Answer 25

data mining and baseball elimination

Question 26

Rounding errors can increase over series of computations

Answer 26

numerical stability

Question 27

What is a hamiltonian cycle

Answer 27

a simple cycle in a graph G=(V,E) that contains each vertex in V

Question 28

Hamiltonian cycles are generally not solvable in

Answer 28

polynomial time

Question 29

You can check hamiltonian cycles in

Answer 29

polynomial time

Question 30

what are P problems

Answer 30

problems that are solvable in polynomial time

Question 31

what are NP problems

Answer 31

problems that are verifiable in polynomial time

Question 32

if there exists a polynomial-time computable function

Answer 32

the problem is polynomial time reducible

Question 33

what is an approximation ratio

Answer 33

δ if and only if for every instance of the problem, A, gives a solution which is at most δ times the optimal value for that instance

Question 34

δ is always at least

Answer 34

1

Question 35

Why do we use approximation algorithms

Answer 35

used to find approximate solutions to optimization problems

Question 36

traverse traveling sales man graph in

Answer 36

preorder (dot to the left)

Question 37

applications for linear programming

Answer 37

data mining, and supply-chain management

Question 38

what is a slack variable

Answer 38

variable that is added to an inequality constraint to transform it to an equality

Question 39

Feasible solution properties

Answer 39

Set n – m nonbasic variables to 0, solve for remaining m variables. Solve m equations in m unknowns.

Question 40

Where are feasible solutions located on the graph

Answer 40

On the line

Question 41

Decision problems are simply

Answer 41

any problem | whose answer is one bit: “yes” or “no”

Question 42

T/F: The superscripts in an output matrix for an all-pairs shortest paths algorithm refer to the dimensions of the matrix.

Answer 42

True