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