# Wednesday, December 31, 2014 COMP 251 F2014

## 1Stable Matching¶

With $n$ men and $n$ women, find a pairing with no instabilities

Instability:
Man $m$ prefers woman $w$ over assigned woman $x$
$w$ prefers man $m$ over her assigned partner

Results in a male-optimal and female-pessimal solution

### 1.1Gale-Shapley Algorithm¶

all people are free
while( any man is free & hasn't proposed to all women):
Choose such a man m
w = 1st on m's list who hasn't been proposed to yet
if (w is free):
assign w to m
else:
if (w prefers m over assigned partner, a):
assign w to m
make a free
else
w rejects m


#### 1.1.1Stability Proof¶

• Suppose $A-Z$ is an unstable pair in the GS Matching $S^*$
• $A$ is matched to $B$, $Z$ is matched to $X$
• Case $A$ never proposed to $Z$
• $A$ goes down his list in order of favorites.
• If $A$ never proposed to$Z$, he prefers $B$ over $Z$
• Case $A$ proposed to $Z$
• $A$ and $Z$ were matched for a time.
• They can only become unmatched if $Z$ prefers some other suitor over $A$

#### 1.1.2Male-Optimality Proof¶

• Suppose man $M$ is matched to someone other than his best stable partner in $S$
• Men propose in decreasing order of preference
• If $M$ was rejected by a partner, she would have to have stably preferred someone

### 1.2Bipartiteness¶

only one of the following holds for a graph $G$ and BFS $B$

• No edge joins two nodes inside $B$, $G$ is bipartite
• An edge joins two nodes in the same layer $\to$ $G$ contains an odd length cycle $\to$ $G$ is not bipartite

## 2Divide and Conquer¶

1. Divide problem into several parts
2. Solve parts recursively
3. Combine solutions from sub-problems into final answer

### 2.1Mergesort¶

1. divide array $O(1)$
2. recursively sort $2 \times T(\frac{n}{2})$
3. merge $O(n)$

#### 2.1.1Merging¶

• Two pointers for each (sorted) array
• Compare values, and add lowest to output array
• left shift pointer
• repeat

#### 2.1.2Pseudocode¶

def mergesort( var a as array )
if ( n == 1 )
return a
var l1 as array = a[0] ... a[n/2]
var l2 as array = a[n/2+1] ... a[n]

l1 = mergesort( l1 )
l2 = mergesort( l2 )

return merge( l1, l2 )

def merge( var a as array, var b as array )
var c as array

while ( a and b have elements )
if ( a[0] > b[0] )
add b[0] to the end of c
remove b[0] from b
else
add a[0] to the end of c
remove a[0] from a
while ( a has elements )
add a[0] to the end of c
remove a[0] from a
while ( b has elements )
add b[0] to the end of c
remove b[0] from b
return c


### 2.2Closest Pair of Points¶

#### 2.2.1Algorithm¶

1. Draw vertical line to roughly cut points in half
2. Recursively find closest points in each half
3. Find any potentially closer pairs after merging halves
4. Return closest pair of points

#### 2.2.2Analysis¶

This algorithm takes $O(\log^2(n))$, but can be improved to $O(\log(n)$ via pre-sorting the list of points. Each recursion returns a list, with points sorted by y-coordinate, and we then merge the lists.

### 2.3Integer Multiplication¶

#### 2.3.1Brute Force¶

• brute force requires $O(n^2)$ operations
• an $n$ digit number can be represented by 2 $\frac{n}{2}$ digit numbers
• $x = 2^{\frac{n}{2}}x_1+x_0$, $y = 2^{\frac{n}{2}}y_1+y_0$
• $xy = 2^n(x_1y_1)+2^{\frac{n}{2}}(x_1y_0+x_0y_1)+x_0y_0$

• multiply 4 $\frac{n}{2}$ digit numbers

• add two $\frac{n}{2}$ digit integers and shift
• $T(n) = 4T(\frac{n}{2})+\Theta(n) \to T(n) \in \Theta(n^2)$

#### 2.3.2Karatsuba Multiplication¶

• instead, you can add 2 $\frac{n}{2}$ digit numbers
• multiply three $\frac{n}{2}$
• same as above, but:

$$xy = 2^n(x_1y_1) + 2^{\frac{n}{2}}((x_1+x_0)(y_1+y_0)-x_1y_1-x_0y_0)+x_0y_0$$

Runtime
$T(n)=3T(\frac{n}{2})+\Theta(n)$
$T(n) \in O(n^{\log_2 3}) \approx n^{1.5}$

### 2.4Matrix Multiplication¶

#### 2.4.1Brute Force¶

• $O(n^3)$ time
• $n$ multiplications for $n \times n$ elements

#### 2.4.2Divide and Conquer¶

1. Divide matrix into 4 ${\frac{n}{2}} \times {\frac{n}{2}}$ parts
2. Find product of quarters, with 8 multiplications (of 2x2)
3. Add appropriate products with 4 matrix additions
4. Return appropriate values
$T(n) = 8T(\frac{n}{2}) + \Theta(n^2)\to T(n)\in\Theta(n^3)$

No improvement over naive algorithm
BUT you can multiply two 2x2 matrices with 7 multiplications
leads to $T(n) \in \Theta(n^{\log_2 7})$

### 2.5Master Theorem¶

$T(n) = \alpha T(\frac{n}{\beta}) + f(n), \alpha \ge 1, \beta \gt 1$

• $n$ is size of problem
• $\alpha$ is number of sub problems
• $\frac{n}{\beta}$ is size of sub problems
• $f(n)$ is additional work required
Case 1
$f(n) \in O(n^c),\ st.\ c \lt \log_{\beta}\alpha$
$T(n) \in \Theta(n^{\log_{\beta}\alpha})$
Case 2
$f(n) \in \Theta(n^c \log^k n),\ st.\ c \lt \log_{\beta}\alpha$
$T(n) \in \Theta\left( n^{c} \log^{k+1} n \right)$
Case 3
$f(n) \in \Omega(n^c),\ st.\ c \lt \log_{\beta}\alpha$ and
$a f\left( \frac{n}{b} \right) \le k f(n)$ for some constant $k < 1$ and sufficiently large $n$
$T(n) \in \Theta(f(n))$

## 3Graphs¶

• captures pairwise relationship between objects
• V nodes and E edges
• Size Parameters: $n=V$, $m=E$
• degree is number of neighboring edges

### 3.1Representations¶

• $n\times n$ matrix where $A_{uv}$ is 1 if $(u, v)$ is an edge
• Requires $n^2$ space
• Checking if $(u, v)$ is an edge takes $\Theta(1)$ time
• Identifying all edges takes $\Theta(n^2)$ time

• $n$ length array of nodes, each index is list of connected nodes
• requires $m+n$ space
• Checking if $(u, v)$ is an edge takes $O(deg(u))$ time
• Identifying all edges takes $\Theta(m+n)$ time

### 3.2Paths and Connectivity¶

Path
a sequence of nodes $\{v_1, ..., v_k\}$ st. any pair $(v_i, v_{i+1})$ is connected
Simple Path
all nodes in path are distinct
Connected Path
There is a path between any pair of nodes
Cycle
A path $\{v_1, ..., v_k\}$ where $v_1=v_k$, k > 2, and the first $k-1$ nodes are distinct
Tree
An undirected path which is connected and doesn't contain a cycle
Connected Component
all nodes reachable from s

### 3.3Traversal¶

1. Connectivity: is there a path between nodes $s$ and $t$
2. Shortest Path: the length of the shortest path between nodes $s$ and $t$
##### 3.3.1Breadth First Search¶

Explore outwards from a starting node s, in all directions. Add nodes a layer at a time

Output
$L_0 = {s}$
$L_1 =$ all neighbors of $L_0$
$L_2 =$ all nodes that are not in $L_0, L_1$ which have an edge to a node in $L_1$

There is a path from $s$ to a node $t$ in $L$ if and only if $t$ appears in a BFS with $s$

Graph G
s = some node in G
Discovered[s] = true;
l = 0 //layers
Tree = null
L[0] = s

while(L[l] is not empty):
initialize L[l+1]
for each node u in L[l]:
for each edge e connecting u to v:
if Discovered[v] == false
Discovered[v] = true
add edge e to tree
add v to L[l+1]
l++


runs in $O(m+n)$ time

• for each node, there are deg(u) incident edges
• total time processing edges if $\sum_{u \in G} deg(u) = 2m$, since each edge is counted twice

#### 3.3.2Depth First Search¶

A BFS checks all nodes within a certain distance of the root. Instead, a DFS goes all the way done a branch of the tree, and then goes down any visible branch, until it has explored every node. The DFS requires less memory, since you don't need to store each node's pointers at each level.
You would chose an algorithm based of the use case, for example a search for something far down the tree would be found quicker with a DFS search, while something closer would be easier to find with a BFS.

#### 3.3.3Connected Component¶

Flood Fill
Recolor all neighboring pixels of a color l

Given a pixel of color lime, change the blob of neighboring pixels to blue

Definitions
Node: Pixel
Edge: neighboring lime pixels
Blob: connected component of lime pixels
get_connected_component() {
R = {s}
while (there is an edge (u, v) st. u is in R and v is not in R )
add v to R
}


For flood fill: ensure the edge $(u, v)$ is connecting to like colored edges

#### 3.3.4Bipartite Graphs¶

Bipartite
an undirected graph st. nodes can be colored red and blue such that no neighboring nodes are like colored
graph can't have an odd length cycle

Let G be a connected graph with L layers from a BFS

1. No edge of G joins two nodes of the same layer, and G is bipartite
2. An edge of G joins two nodes of the same layer, and G contains an odd-length cycle (and hence is not bipartite)

#### 3.3.5Connectivity in Directed Graphs¶

An edge $(u, v)$ goes from node $u$ to node $v$

Mutually Reachable
$\exists$ a path between $u$ and $v$ a path between $v$ and $u$
Strong Connectivity
Every pair of nodes is mutually reachable
##### 3.3.5.1Strong Connectivity¶
• pick a node $s$
• run BFS in $G$
• run BFS in $G^{-1}$, where every edge in $G$ has been reversed
• return true if all nodes are reachable in both BFS executions

### 3.4Directed Acyclic Graph¶

DAG
A directed graph with no cycles
Topological Order
Ordering of nodes as $v_1, v_2,...,v_n$ st for every edge $(v_i, v_j), i < j$
• If G has a topological order, G is a DAG.
• If G is a DAG, then there is a node with no incoming edges

To computer topological order:

def topological(G):
Find a node v with no incoming edges
G.delete(v)
return v + topological(G)


<div id="pagebreak"></div>

## 4Greedy Algorithms¶

• make an optimal/plausible choice for current position
• keep making the same decision for the remaining set

### 4.1Strategies¶

Show that greedy algorithm is optimal after each step
Exchange
Show the greedy algorithm's output is equivalent to another solution
Structural
Show every possible solution matches a condition, and the greedy algorithm matches this

### 4.2Interval Scheduling¶

• sort by earliest finish time

#### 4.2.1Proof of Optimality¶

1. Assume greedy algorithm is suboptimal
2. let $\{i_1, i_2, ... , i_k\}$ be the greedy set
3. let $\{j_1, j_2, ..., j_m\}$ be the optimal set with $i_a = j_a$ for the largest possible $a$
4. $a = m$ since the job $j_{a+1}$ must start after $j_a$ finish meaning it can be added to the set

### 4.3Interval Partitioning¶

• assign a grouping of lectures to various lecture halls, such that there is no overlap, with the minimum number of rooms
• A lecture $l_i$ starts and finishes at $s_i, f_i$

#### 4.3.1Algorithm¶

sort lectures by (increasing) starting time
classrooms = {priority_queue}

for lecture j in schedule:
if (j can be added to some room):
else:


#### 4.3.2Runtime¶

It takes $O(n\log n)$ to sort the lectures, and then $O(n)$ time to add them to the schedule

#### 4.3.3Analysis¶

A new classroom is only created if there is a conflict with a current lecture. Since we have sorted by starting time, any conflict starts after $s_j$

### 4.4Minimize Lateness¶

You want to perform a set of jobs with a known processing time and due time. They should be performed such that the maximum overdue time of any job is minimized. Use a sorting of 'earliest deadline first'

### 4.5Djikstra's Shortest Path¶

• Maintain a set of explored nodes $S$, which have a shortest path from $s$ to all nodes $u$
• Initialize $S = \{s\}$
• Repeatedly greedily choose the shortest available path to an unexplored node, until all nodes are explored
• $O(E + V\log|V|)$

#### 4.5.1Implementation¶

• maintain $d(v) = min(d(u) + l_e)$, st $l_e$ is an edge $(u, v)$
• sort new nodes by $d(v)$

### 4.6Minimum Spanning Tree¶

Given a connected graph with real value edge waits, the MST is the subset of edges touching all vertices such that the sum of edge weights is minimized.

• where $n$ is the number of vertices in the
• Any MST has to have $n-1$ edges
• There are $n^{n-2}$ spanning trees

#### 4.6.1Kruskal's Algorithm¶

##### 4.6.1.1Algorithm¶
1. Sort edges by increasing weight, start with MST $T = \{0\}$
2. Try inserting edge $e$ with lowest weight
1. if $e$ creates a cycle, remove
2. repeat until $n-1$ edges in graph
##### 4.6.1.2Runtime¶

$O(E\log E)$
1. Comparison Sort for edges
2. Use Union Find Data Strucutre to create tree, requires $O(v)$ operations

#### 4.6.2Reverse-Delete Algorithm¶

##### 4.6.2.1Algorithm¶
1. Sort edges by decreasing weight, Start with MST $T = \{E\}$ (all edges)
2. Try deleting edge $e$ with highest weight
1. if removing $e$ disconnects graph, add it back
2. repeat until $n-1$ edges in graph
##### 4.6.2.2Runtime¶

$O(E \log V (\log \log V)^3)$
Comparison Sort for edges
E iterations of loop
* delete in $O(1)$
* connectivity takes $O(\log V (\log \log V)^3)$

#### 4.6.3Prim's Algorithm¶

##### 4.6.3.1Algorithm¶
1. Start with $T = \{v\}$ (some random vertex)
2. Add the edge with lowest weight which doesn't have an end point in $T$
##### 4.6.3.2Runtime¶
Minimum edge weight data structure Time complexity (total)
adjacency matrix, searching $O( binary heap and adjacency list$O((

## 11Overview¶

1. 2 Questions about Algorithms
1. Analyze Runtime
2. Presumably Dynamic and Max Flow / Min Cut
2. Divide and Conquer
1. No Matrix Multiplication
2. Effect of Parameters to Runtime
3. Master Method
3. Graphs
1. Breadth First Search
2. No DAG
4. Greedy Algorithms
1. Djikstra's Algorithm
2. Minimum Spanning Tree
5. Dynamic
1. Can't use dynamic for most recursive algorithms
1. Often easier to iteratively solve problem
2. Expect a question
6. Flow
1. Ford Fulkerson
2. Capacity Scaling
3. Runtime and Comparison
7. Randomized Algorithm
1. Randomized Quicksort
2. Hashing and Expected Collisions