# Algorithm Analysis

## Gale-Shapley Algorithm(Stable Marriage Problem)

Correctness:
- Termination: algo terminates after at most n2 iterations.
- Perfection: Everyone get married
- Stability: The marriages are stable

Algorithm:
```
initialize each person to be free
while (some man m is free and hasn't proposed to every woman) do
  w = highest ranked woman in m's list to whom m has not yet proposed
  if (w is free) then
    (m, w) become engaged
  else if (w prefers m to her fiancÈ m') then
    (m, w) become engaged
    m' become free
  return the set S of engaged pairs
```
Even with the same procedure, we might implement the algorthm with different time complexity due to many reasons(e.g. different data structures)

# Graph

~~~~~~~~~~~~~~~~~~~~
The core of graph is to discuss the relationship of nodes(objects), which represent the edges
~~~~~~~~~~~~~~~~~~~~

## How to solve problems? → Car Theorem
- C → Criticality: Identify the core of problems, and remove extraneous details
- A → Abstraction: First think at high level(design the algorithm), then go down to low-level(implementation)
- R → Restriction: List the limitations, and think how to extend the algorithm to simplify the limitations

## Graph concepts
- Directed edge: ()
- Undirected edge: {}
- Neighbor nodes: Adjancency

An undirected graph G with n vertices is a tree if it satisfied two of the following statements:
- Graph G does not contains cycle
- Graph G is connected(all vertices are reachable)
- Graph G has n-1 edges

A rooted tree encodes the notion of hierarchy (parent, child, sibling, uncle, nephew, root)

### BFS vs DFS

~~~~~~~~~~~~~~~~~~~~
Find all reachable nodes and paths of certain node
~~~~~~~~~~~~~~~~~~~~

BFS:
- Able to find the shortest path of two vertices by using 'Layer'. Other visited & labeled nodes will be skipped.
- The distance between two node will be the difference of their layer in BFS tree. (note: the difference of layer each edge got in BFS tree will no greater than 1, which means that the edge in BFS tree will not cross 2 layers or above)
Application using BFS: The color fill-in feature of painter(If two pixels hold the same color, then we build a edge between them and give them the new color)

Non-tree edges in BFS: They are ancestor-decendent relationship
Non-tree edges in DFS: They are sibling or uncle relationship

Traverse time of a graph -> O(m+n) m=number of edges & n= number of nodes

How to store graph?
Adjacency matrix -> Inefficient when encounter sparse graph
Time: neighbor nodes lookup adjacency : O(n)
Space: O(n2)

Adjacency list (Best suited for BFS since it can lower the complexity)
Time: O(deg(u)))
Space: O(n+2m) = O(n+m) (undirected)

#### Implementation of BFS & DFS

Queue(FIFO) a double-opened structure with front(pop) & rear(push) pointer
Note that the push pop in Javascript array is not queue but stack since it is LIFO

Stack(LIFO) a single-opened structure with top pointer

Implement Stack & Queue with linked list:
- variable size
- insert/delete in O(1)

For the implementation of BFS, both queue and stack are fine because the order does not matter.
Adjacency list is preferable for storing Graph in BFS, since the step of neighbor searching in BFS is important.
And the complexity of neighbor searching in adjacency list O(n+m) is lower than adjacency matrix, which is O(n2)

The implementation of DFS uses stack
- Recursive ver: We don't need to maintain stack since we are using a system stack
- Iteration ver: we need to maintain a stack data structure by ourselves