Cpe 349 Final

Front 1

4 steps of algorithm analysis

Back 1

1) define the parameters and input size

2) define the basic operation

3) determine how the number of operations varies with different inputs

4) express as a closed form solution in terms of input size

Front 2

Graph

Back 2

data structure composed of vertices and edges. G = (V, E)

Front 3

Directed Graph

Back 3

graph whose edges have a direction

Front 4

in-degree

Back 4

number of edges going into a vertex

Front 5

out-degree

Back 5

number of edges going out of a vertex

Front 6

weighted graph

Back 6

graph whose edges have a weight value

Front 7

graph path

Back 7

a sequence of vertices and edges that go from a starting vertex to an ending vertex

Front 8

acyclic graph

Back 8

graph with no cyclical paths

Front 9

path length

Back 9

the number of edges in a path

Front 10

depth

Back 10

the number of edges separating one vertex from another

Front 11

Euler Path

Back 11

a path in a graph that uses all edges exactly once

Front 12

Hamilton Path

Back 12

a path in a graph that uses all vertices exactly once

Front 13

source

Back 13

a vertex with in-degree 0

Front 14

sink

Back 14

a vertex with out-degree 0

Front 15

flow network

Back 15

graph with 1 source, 1 sink, and where the total flow into any other vertex equals the total flow out of the vertex.

Front 16

flow value

Back 16

the sum of the flow leaving a source, or entering a sink

Front 17

cut

Back 17

given a flow network graph G = (V, E), separate V into two subsets X and Xbar where X contains the source and Xbar contains the sink. Then the cut is the set of all edges whose tails are in X and whose heads are in Xbar.

Front 18

cut capacity

Back 18

The sum of all capacities of the edges in the cut

Front 19

Depth First Search (DFS)

Back 19

searching a tree or graph from a starting vertex and searching "deep". Often implemented recursively

Front 20

Breadth First Search (BFS)

Back 20

searching a tree or graph from a starting vertex and searching all children of a node before continuing. Often implemented with a Queue.

Front 21

Tree edge

Back 21

an edge used in traversal during a BFS or DFS

Front 22

Back Edge

Back 22

an edge that goes to an ancestor vertex in the DFS tree

Front 23

Forward edge

Back 23

an edge that goes to a previously visited, but non-ancestor vertex in a DFS tree

Front 24

cross edge

Back 24

an edge that goes to a previously visited vertex in a BFS tree

Front 25

Tree

Back 25

data structure composed of nodes that have none or more children

Front 26

tree leaf

Back 26

a node with no children

Front 27

tree height

Back 27

the number of levels in a tree (starting with 0)

Front 28

spanning tree

Back 28

a tree that is inside a graph that visits all vertices

Front 29

minimal spanning tree

Back 29

a spanning tree of a weighted graph with the smallest total weight of the summed edges

Front 30

min heap

Back 30

data structure that allows easy access to small values

Front 31

max heap

Back 31

data structure that allows easy access to large values

Front 32

heap: sift down

Back 32

moving a node of a heap down the tree to its correct position

Front 33

heap: sift up

Back 33

moving a node of a heap up the tree to its correct position

Front 34

optimal substructure

Back 34

the relation that defines how to 'build' a dynamic programming solution

Front 35

Class P

Back 35

the set of problems that can be solved by a polynomial time algorithm

Front 36

Class NP

Back 36

the set of problems that, given a potential solution, can be verified in polynomial time

Front 37

NP Complete

Back 37

a problem D is NP complete if it is in NP and all other problems in NP can be polynomially reduced to D.

Front 38

polynomial reduction

Back 38

problem D1 is polynomially reducible to problem D2 if there exists transformation T from D1 -> D2 that maps all 'yes' instances of D1 to a 'yes' instance of D2 and all 'no' instances of D1 to a 'no' instance of D2 in polynomial time.

Front 39

big O definition

Back 39

if f(n) and g(n) are functions, then f(n) is in O(g(n)) if there exist c, n_0 such that f(n) < c * g(n) for all n > n_0.

Front 40

big Omega definition

Back 40

if f(n) and g(n) are functions, then f(n) is in Omega(g(n)) if there exist c, n_0 such that f(n) > c * g(n) for all n > n_0.

Front 41

big Theta definition

Back 41

if f(n) and g(n) are function, then f(n) is in Theta(g(n)) if there exist c_1, c_2, n_0 such that c_1 * g(n) < f(n) < c_2 * g(n) for all n > n_0.

Front 42

sum from i=k to n of (1)

Back 42

= n - k + 1

Front 43

sum from i = 1 to n of (i)

Back 43

= [n(n+1)]/2

Front 44

sum from i = 1 to n of (i^2)

Back 44

= [n(n+1)(2n+1)]/6

Front 45

sum from i = 1 to n of (i^k)

Back 45

~= [n^(k+1)]/(k+1)

Front 46

sum from i=0 to n of (a^i)

Back 46

= [a^(n+1)-1]/(a-1)

Front 47

Master Theorm

Back 47

Given time function T(n) = a T(n/b) + n^d)

log_b(a) < d ==> T(n) in Theta(n^d)

log_b(a) = d ==> T(n) in Theta(n^d * log(n))

log_b(a) > d ==> T(n) in Theta(n ^ log_b(a))

Front 48

Traveling Salesperson

Back 48

Given a weighted graph G = (V, E), what is the shortest Hamilton Path?

Front 49

Knapsack Problem

Back 49

Given a set of items I, each with a value and weight and a knapsack with a capacity, what is the most valuable subset of items that fit into the knapsack?

Front 50

Brute force Traveling Salesman

Back 50

pick starting vertex. generate all permutations for the other (n - 1) vertices, for each permutation, check if it makes a circuit and is a new smaller distance

Front 51

Brute Force Knapsack

Back 51

generate all subsets of items, for each subset, check if it can fit in the knapsack and is a new highest value.

Front 52

Topological Sort

Back 52

a linear ordering of vertices of a directed graph so that there are no paths from any given vertex to any other vertex previously in the listing

Front 53

Topological Sort DFS implementation

Back 53

using a DFS of the graph, add vertices as they are "left" in reverse order.

Front 54

Topological Sort Source Removal implementation

Back 54

make a list of all vertices and their in-degrees. add one with 0 in-degree, and decrament the in-degrees of all adjacent vertices. repeat until all are added.

Front 55

Lomuto's partitioning algorithm

Back 55

two counters, each move left -> right. If Lead counter is larger than p, increase, if it is smaller, increase lower counter, swap, increase lead counter.

Front 56

quicksort partition

Back 56

two counters move in from each end. while left is smaller than p, increase. While right is larger than p, decrease. swap left and right. repeat until left and right cross.

Front 57

Heap sort

Back 57

build heap in array. continuously remove from heap and place at the position after the last element in heap.

Front 58

Cut Property

Back 58

For a weighted graph G = (V, E), if V is 'cut' into X and V - X, then the smallest edge between X and V-X must be part of the MST for G.

Front 59

Sequence Alignment Algorithm

Back 59

table is m x n with sequences along sides. initialize table T. Then, each cell at i, j is max of:

- T[i, j - 1] + 2

- T[i -1, j] + 2

- T[i - 1, j - 1] + C[i,j]

where C[i,j] is 0 if letters at i and j are same, 1 otherwise.

Front 60

Max Flow, Min Cut theorem

Back 60

The maximum flow for a flow network is equal to the min cut of that same network

Front 61

Stable Marriage

Back 61

Start with everyone free, as long as there are free men:

a free man proposes to his highest preferred single lady

if she is free, she accepts

if she is taken, but the new man is better, the old man is now free

if she is taken, but the new man is worse, he remains free

continue until all men are taken

Front 62

State Space Tree

Back 62

A tree that represents all possible configurations of a problem

Front 63

backtracking

Back 63

walking backwards through a state space tree to construct a solution