CSCE4110 Final Flashcards Preview

Programming > CSCE4110 Final > Flashcards

Flashcards in CSCE4110 Final Deck (42):
1

Advantages of adjacency list

works well for sparse graphs

space is theta(V + E)

2

disadvantage of adjacency list

searching for edges slower than adjacency matrix

3

advantages of adjacency matrix

works well for dense graph

edge lookup is theta(1)

4

disadvantage of adjacency matrix

requires more space than adjacency list

5

Examples of a BFS algorithm

Prims and dijkstras

6

Goal for a BFS algorithm

find smallest number of edges to each reachable vertex

7

time complexity for BFS

O(V+E)

8

Explain BFS briefly

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

9

Explain DFS briefly

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

10

Time complexity of DFS

O(V+E)

11

Are MST always unique

NO

12

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

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

13

Time complexity of Kruskals and Prims algorithm

O(E lg V)

14

How is single-source shortest paths exhibit optimal substructure?

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

15

Can shortest paths be computed with negative weight edges?

Yes

16

Can shortest paths be computed with negative edge cycle?

No

17

Can a shortest path have a cycle?

No

18

Initialize single source
3 steps

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

19

Running time of initializing single source

theta(V)

20

Running time for bellman ford

theta(VE)

21

Running time for Dijkstras

O(E lg V)

22

All pair shortest path input and output

a matrix

23

Max Flow equilibrium

inflow = outflow at every vertex

24

Max flow termination

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

25

applications for maxflow

data mining and baseball elimination

26

Rounding errors can increase over series of computations

numerical stability

27

What is a hamiltonian cycle

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

28

Hamiltonian cycles are generally not solvable in

polynomial time

29

You can check hamiltonian cycles in

polynomial time

30

what are P problems

problems that are solvable in polynomial time

31

what are NP problems

problems that are verifiable in polynomial time

32

if there exists a polynomial-time computable function

the problem is polynomial time reducible

33

what is an approximation ratio

δ 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

34

δ is always at least

1

35

Why do we use approximation algorithms

used to find approximate solutions to optimization problems

36

traverse traveling sales man graph in

preorder (dot to the left)

37

applications for linear programming

data mining, and supply-chain management

38

what is a slack variable

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

39

Feasible solution properties

Set n – m nonbasic variables to 0, solve for remaining m variables.

Solve m equations in m unknowns.

40

Where are feasible solutions located on the graph

On the line

41

Decision problems are simply

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

42

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

True