CPSC 331 DSA

divide and conquer

divide conquer combine (ie merge sort and quick sort)

master theorem definitions for a,b, d, T(n)

a - # of recursions

b - shrinkage factor

d- exponent in runtime combine

T(n) <= a * (T/b) + O(n^d)

master theorem cases

if a = b^d : O(n^d log n)

a < b^d: O( n ^d )

a> b^d : O( n ^ log b a)

heap

complete binary tree

priority queue

min-heap, max - heap. property - parent vs child

heap sort

build heap, extract max, max-heapify repeat - LHS max-heap, RHS sorted O(n log n)

stack

last in first out, operations: pop push top

all O(1)

queue

first in first out

operations: enqueue, dequeue,

head and tail

all O(1)

linked list

operations: search O(n),insert O(1)- unsorted, delete O(1)

head

pointers to pre (singly), succ. (doubly)

need pre for delete

binary search tree property

smaller on x.left, larger on x.right

binary search tree querying operations

min, max, pre, succ,

in-order tree walk - left root right

pre - root left right

post -left right root

(where ever root is - print)

search

O(log n) if balanced

binary search tree modifying operations

insert (compare with trailing pointer), delete (case 1 - remove, case 2- move subtree case 3 - find successor, switch with removing)

all O(log n) if balanced

hash table

Operations:

insert, search

O(n) space but O(1) time

probability analysis

indicator variable, 1 occur, 0 if doesnt occur

linearity of expectation E[X] =Σ E[Xi]

quicksort

pivot, at the end randomized

partition- recurse left, recurse right

avg O(n log n) worst O(n²)

BFS definition

breadth first search, uses queue

BFS applications

shortest path between u,v. bipartite, level by level

BFS process and run time

1. color all white

2. enqueue u - color grey

3. remove, color black AND enqueue adjacent

Keep repeating til queue empty

keep track of parent, and distance for to return path

O(V + E)

DFS defintion

depth first search, uses stack creates a forest

DFS applications

topological sort, maze, cycle testing

DFS process and run time

1. color everything white, and discovery time of zero

2. add u to stack - color grey

3. pop from stack - color black AND push adjacent

Keep repeating til stack is empty

Keep track of finishing time.

O(V + E)

parenthesis theorem

three posibilites for u and v

1. disjoint

2. u finishes in v

3. v finishes in u

white path theorem

if v is a descendant u, then when u was discovered there was a nodes of white paths reaching u to v

edge classification

1. tree - discovery

2. forward - descendant

3. back - point to ancestor

4. cross - all others, disjoint d and f times

acylic

no back edges

topological sort (input, ouput, process)

input : Directed Acyclic Graph

output : linear ordered sorting

process: DFS as nodes are finished add to a linked list

dijkstra algorithm definition/purpose

finding single source shortest path in a directed weighted graph

dijkstra process and runtime

1. set all distances to zero

2. start at source

3. add adjacent of source to priority queue Q

4. extract min, add to path AND relax edges if applicable

5. relaxing is - redefining distance, and setting parent

Repeat til Q is empty

return path

O( (V+E) lg V)