xxsang

# Union-Find -- 30 May 2019

1. Used to solve dynamic connectivity problem
	1. Process
		1. Model the problem
		2. Find an algorithm to solve it
		3. Fast enough?Fits in memory?
		4. If not, figure out why
		5. Find a way to address the problem
		6. Iterate until satisfied

xxsang

# Sorting -- 3 Jun 2019

1. Callbacks
	1. To sort any type of data
	2. client passes array of objects to sort() function
	3. The sort() function calls back object’s compareTo() method as needed.
2. Selection Sort
	1. Find the smallest remaining entry and swap a[i] and a[min]
	2. N^2/2 compares and N exchanges
	3. Quadratic time even if input is sorted

xxsang

	1. Priority Queue: remove the largest/smallest item
2. Implementations
	1. Sort: NlgN time, N space
	2. elementary PQ: MN time, M space
	3. Binary heap: NlogM time, M space (best in practice)
	4. unordered array: insert 1, del max N, max N
	5. ordered array: insert N, del max 1, max 1
3. Binary Heap
	1. Based on complete binary tree (perfectly balanced except for bottom level)
	2. Heap order

xxsang

1. Symbol table
	1. key-value pair abstraction
	2. Associate one value with each key
	3. values are not null, get() returns null is key not present
	4. use hashCode() to scramble key
	5. equals(): reflexive, symmetric, transitive, non-null
2. Elementary implementations
	1. unordered linked list of key-value pairs
	2. Search scan through all keys until find a match; insert scan through all keys until find a match, if no match add tofront
	3. Search N, Insert N

xxsang

1. 2-3 Search Trees
	1. Allows 1 or 2 keys per node
		1. 2-node: one key two children
		2. 3-node: two keys three children
		3. when search target is between 2 keys in 3-node go middle
		4. Insert into a 3-node at bottom, add new key to 3-node temporarily and move middle key in 4-node into parent, repeat up as necessary
	2. Maintain symmetric order and perfect balance
	3. Worst case lgN, best case ~0.631lgN
	4. search insert deletion O(clgN)
	5. Difficult to implement the original version

xxsang

1. Faster but doesn’t support order
2. Save in a key-indexed table
	1. Hash function
	2. equality test
	3. Collision resolution
	4. space-time limitation tradeoff -hashing
3. Hash function
	1. Idea: scramble the key uniformly to create a table index
	2. designed differently for practice
	3. if x==y then x.hashCode() == y.hashCode(); highly desirable if x!=y, x.hashCode()!=y.hashCode()

xxsang

1. Sets
	1. A collection of distinct keys, no associated value
	2. Symbol table without values
	3. in or not in the list (whitelist blacklist)
		1. spell checker, browser, parental controls, chess, spam filter, credit cards
2. Dictionary clients
3. Indexing clients
	1. strings as sets
4. Sparse vector matrices
	1. standard matrix(vector of vector) manipulation takes quadratic running time

xxsang

1. Graphs
	1. Set of vertices connected pairwise by edges
	2. Complex and huge
	3. Terminology
		1. Path: sequence of vertices connected by edges
		2. Cycle: path whose first and last vertices are the same
		3. Euler tour: a cycle that uses each edge exactly once
		4. Hamilton tour: cycle that uses each vertex exactly once
		5. MST: best way to connect all of the vertices
		6. biconnectivity: is there a vertex whose removal disconnects the graph

xxsang

1. DiGraph:
	1. Set of vertices connected pairwise by directed edges
		1. Problems
			1. Shortest Path
			2. Topological sort (all edges point upwards)
			3. Strong connectivities
			4. Transitive closure
			5. PageRank
		2. adjacency-list representation
2. Digraph search

xxsang

1. MST
	1. Given a connected graph, MST is a subgraph with no cycles, that is both a tree and including all vertices (V-1 edges)
	2. Brute-force: try all possible MSTs to find minimum weighted tree
2. Greedy Algorithms
	1. Assumption: distinct edge weights and connected, MST exists and unique
	2. Cut: a partition of vertices into two nonempty sets
	3. Crossing edge: connect a vertex in one set with a vertex in the other
	4. Given any cut, the crossing edges of min weights is in the MST
	5. Algorithm
		1. Start with all edges colored grey