# Advanced Alogorithm

[TOC]

## Book List(2020/06/21, MT)
- Probability Method
- best of discrete space prob
- Communication Capacity
- Information Theory
- Abstract Algebra
- Advanced LA

## Week 1-1

- Graph Orientation
- flow
- acyclic?

### degeneracy
- tree, $d(T)\le1$
- forest, $d(T)\le1$
- grid, $d(T)\le2$
- planar graph, eular characristic, one point degree <= 5

- acyclic graph orientation
- $d(H)\le d(G) \forall H \in sub(G)$
- $\delta(G) \le d(G)$

- removal of min degree point can be done in $O(m+n)$
- by removal of min and find min, no need heap
- $\sum degree = 2*m$

- k-degenerate ordering


#### bound
- $\frac{m}{n} \le d(G) \le (2*m)^\frac{1}{2}$
- $(\frac{m}{2})^2$ by sort
- and compare degree with $(\frac{m}{2})^2$

- "extremal" graph theory

- listing triangle in $O(m*d(G))$
- for 4-clique? $O(m*d(G)^2)$

- coloring and independent set with d(G)

### k-core

- $O(m+n)\alpha (n)$ find max $\delta (H) * |H|$ of G
- longest single path
- at least m/n, k-core=>k-simple path
- at least have a degenracy(G) >= m/n k-core

- a(G), arboricity
- planar <= 3
- proof planar graph, eular characristic, one point degree <= 5
- by face edge relation of filled with triangle graph

- proof:
- induction on point
- case 3, 4, 5

- a(G) <= d(G) < 2*a(G)

- t(G), thickness
-

- t(G) <= d(G) < 6*a(G), by planar partition to forest

- end of class

### degeneracy's application

## Week 2-1(2020/3/13)

### Color Coding
color the elements in the input with different colors
so that the pattern is highlighted, so it becomes easier to find

#### Useful Inequalities
- $1+x \le e^x \forall x \in \mathbb{R}$
- use log(n) to approximate 1/n in $e^{-x}$
- $(\frac{n}{k})^k \le C^n_k \le (\frac{ne}{k})^k$
- $\frac{k^k}{k!} \le e^k \implies \frac{k!}{k^k} \ge e^{-k}$

#### k-sum tuple

Input: n positive integers a1, a2, ..., an
Output: "Yes" if there exists **distinct** (i, j, k, p, q) such that $a_i+a_j = a_k+a_p+a_q$

#### k-path

- k-cycle
- special, 4-cycle
- $n^2$ table filling
- k-independent triangles
- k color, kelly lu
- 3k color, prof
- tree-iso subgraph
- Remark: trade off between # of color and P

## Week 3 - study group
* minimal enclosing ball
* O(n), 2 times approximation
* one point and its farthest
* minimal enclosing n/k ball
* O(n), P(1/2) correct, 2 times approximation
* 1/k P can find a point in answer ball, 2 time approximaton
* Planar O(n) spanning tree
* Borůvka's Algorithm
* fibonocci heap mentioned
* current MST best = M*alpha(N)
* a decision tree of lowerbound is constructed, but not analyzed
* planar graph ~= cutting circles, no P algorithm is proposed
* circle packing theorem

* planar graph cycle decomposition
* n/10, $4\sqrt n$, n/10


* for i in {001...100}; do blabla $i > done

## Week 3

### Strong Orientation
* Robin's theorem
* has a strong orientation <=> 2-edge connected
* => trivial
* <= dfs tree
* alternative by definitio and check every u, v

### Bipolar Orientation
* main theorem
* $G = (V\cup \{s, t\}, E )$ <=> 2-vertex connected
* => dfn on articulation point
* <=
---
* why stop if have bipolar (acyclic + finite)
* to contruct <= use ear

### Ear decomposition
* an ear
* is a path whose vertices except the endpoints ans edges cannot repeat(property)
* is a simple path or single cycle
* decomposition
* first component is a cycle
* attach
* ear => strong orientation exists
* open ear decomposition
* except first is simple path
* => has a bipolar orientation
* by orienting the added chains

### Conclusion
* ear decomposition <=> 2-edge connected <=> strong orientation
* open ear <=> 2-vertex <=> bipolar orientation
* find bridge and cut vertex
* alternative for tarjan, not hard to code

#### Algorithm for decompositions
* dfs tree
* for all non tree edge add component

### Sparsification Techniques

#### K-EC, k-VC certificate
* if S, $|S| = k$ disconnect $\cup_{k+1} F$
* when each of edge/vertex in S is removed, can cause at least 1 $F_i$ lose connectivity
* if the former k is originally connected and now disconnect by S, if $F_{k+1}$ is not connected, then G is not connected, because if not, F can be connected originally

#### k-VC
* bfs forest definition
* G/Bi => removal of edges used in Bi, not vertex
* each time removal at least cost a vertex with connectivity

### Problem k-threading on DAG
* 2 => greedy
* k => NP-hard
* my though bipartite matching DAG path cover?

### Vote for class changes

## Quiz 1

### Pictures of my solutions
:::spoiler
:::

## Week 4

### t-multiplicative Spanner

- other ref
- http://theory.stanford.edu/~virgi/cs267/lecture7.pdf
- https://www.mpi-inf.mpg.de/fileadmin/inf/d1/teaching/summer19/algorithms/lecture_notes_spanners.pdf

#### Definition

#### Erdős Even Circuit Theorem
- $C_{2k-free}$

#### the algorithm
- add edge in non decreasing order
- discard if neew e has alternative t
- i.e. form a t+1 cycle

### additive-2 Spanner proof
- key:
- use Q + Cauchy to bound $\sum degree$ to bound $|E|$
- $\Theta(\Delta Q) = O (\Delta P) \forall added~path$
- $O(P) = O(n^2)$
- key:
- for each neighbor of p
- at most 3 contact point on p
- the contact points zs contibute to $\Delta P$

### additive-6 spanner
- key u', v'
- $d^{1/3}$

### Mixed spanner
- mentioned, ax+b

## Week 5 - Holiday

## Week 6

### Low-Diameter Decompositions

#### logn-logn decomposition - existence
- concept of $membrance$
- $|inner| > |surface|$
- round and R noth $O(log n)$
- Observe that Vi contains at least half the nodes contained in V \ V \ (V1 ∪ V2 ∪ ... ∪ Vi-1).

#### Application - Distibuted Alogorithm(ex: MIS)
- modeling
- how to distribute information

#### logn-logn decomposition - build effciently
![](https://i.imgur.com/s72tToz.png
)
- truncated geometric distribution
Q: is the complexity discussed be "on average"(my original thought is not aoubt average)
A: sure is with P

### Tree Packing Conjecture

## Week 7 - Hash-1

### Quiz 1 Score + distribution
::: spoiler

:::

### Ref
"Pairwise Independence and Derandomization," Luby and
Wigderson (2005)

### Bins and Ball

#### if bins is O(balls^2)

### Hashing n Keys Into cn2 Slots
w/o Collisions

#### fuction by direct mapping is too long
- info.(bit) = $log_2(|S|)$
- $O(|U|logn)$
- Q: why cant save f but can save hash table(O(n^2))
- A: table is imaginary

#### Linearity of Variance if Pairwise Independent
- https://mathcs.clarku.edu/~djoyce/ma217/covar.pdf
- $Cov(X, Y) = E(XY) - \nu_x\nu_y$

#### Concentration bound with Chebyshev Inequality
- https://en.wikipedia.org/wiki/Chebyshev%27s_inequality
- 


#### the function
- $f:x \to U \to [0,cn^2)$
- $f(x) = ((ax+b) \mod |U|) \mod cn^2, a,b \in[0, n)$

#### Proof
- use Chebyshev Inequality with $k = \frac{1}{var(X)}$

### Review

### Advanced Q
#### hint

## Week 8 - Hash2 (seigel hash function)

### Local Concentrator

#### proof of existence by P>0

#### Proof of L.I.
- by assuming minimal but exist even smaller => no minimal

#### exam discussion
- probrabalistic methods alan and spxxx

---

## Week 10 - Monge
- http://web.cs.unlv.edu/larmore/Courses/CSC477/monge.pdf
- http://www.cs.tau.ac.il/~haimk/adv-alg-2012/smawk-and-applications5.3.2012.pdf

---

## Week 11 - Review Range of Quiz 3

## Office Hour 2020/5/14
- about Mail
- not asked, teacher had lunch meeting with prof.
- about Research
- Minimal Tree Domination is DP hard
- about lecture
- Hash Physical meanning
- About details
- on site note pictures
:::spoiler

:::
- def
- U - key universe
- n - how many keys
- p - O(n^2) prime
- Hash 1(the |U| to n^2 step)
- why can replace domain from |U| to O(n^2) when having a perfect hash(n-wise i.d.)
- how to use pair-wise(2th moment) to hash from |U| to O(n^2)
- this is h(x) = (ax+b) mod |U| mod p
- Hash 2(the n^2 to n step)
- intuition to have a (c,k)-universal hash with reasonable time and memory use
- Seigel's hash
- local concentrater
- the bound
- important
- $d = 2 + k/\delta$
- $h = \frac{n^{\frac{\delta^2}{k}}}{2e^2}$
- self reduction
- to proof h-wise i.d. => h l.i. hyper planes
- proof by contracdiction with minimal setting
- Hash 3(dymamically deal with collision)
- what can a logn-wise i.d. hash do(proof logn-wise enough)
- Cuckoo Hash
- case study
- rehash does not happen often
- Monge Optimization
- view function as n by m matrix
- monotone, total monotone, monge
- mlogn
- m+n reduction + SMAUK
- example

---

## Quiz 3

---

## Week 11 - Matroid

### Graph matroid linear representation
- proof l.i. => not l.d. => assume minimal l.d. set => smaller l.d. set

### PRAN judge cycle in O(logn2)

### Weighted Matroid Problem
- EQ to MST

### Recommended
- Thirty-Three Miniatures: Mathematical and Algoirithmic Applications of Linear Algebra

---

## Week 12 - Discussion Meeting with Friends at 2020/5/21(1900-2200)
- chat
- 宗達, Kelly, 達仁, steven
- 宗達's Qs
- 01-string encoding(same legth)/partition to be palindrome s.t. num of parts is maximized
- encoding
- use rolling to do O(n/d) for all divisor(factor) d
- $O(\sum n/d) = o(\sum n/i) = O(nlogn)$
- conclusions about complexity related to prime and factors
- $prime~factorization$ can statisfy for all k > 0, $O((logn)^k)$ factors for n
- my guess was right about ans(prime factor)
- ${a_i}$ XOR parition to be same(no same size restriction)
- discussion on the case of all xor is 0 or k
- if is 0, discuss on the resultting partition count is even or odd
- is odd => all partition seg => 0
- is even => all same to some value, enum value(can only be prefix)
- this is O(n) by prefix Xor sum
- if is k, the result for each partition seg is k, greedy construction
- is odd, no even case or all xor should be 0
- Matroid problem(吳仲昇路過) on CP?
- No discussion on Matroid LOL

### Other
- 精神受到高微+晚睡+AI logic agent摧殘感覺今天很遲鈍
- 宗達接IOI Camp 講師在想要講什麼有趣的資料結構
- 宗達有提到 資料流相關的東西
- 想到是否可以在因數上做二分蒐的手法
- 看到c++ tie(a,b) = ab寫法 tie is lvalue reference
- Kelly 今天怪怪的=_=

## Week 12 - Submodularity

### Definition
- deminished return(in eco)
- define on $f : 2^I \to \mathbb{R}$
- $\forall x \in I \backslash S,~T\subseteq S \subseteq I, f(T\cup {x}) - f(T) \ge f(S\cup {x}) - f(S)$

### NP-hardness

### Greedy Algorithm(1-1/e + O(1)-approx)

### MIS has no submodurality

### Q: FPT
- poly(n)*f(params)

### Refetence found in break
- https://theory.stanford.edu/~jvondrak/data/submod-tutorial-1.pdf

### Combinatorial Opproximation

### Proof of 1-1/e approximation
- rearrangement +

### Knapsack Scheme

### Proof

#### LP(did Not understand)

#### |I|3 for analysis!

---

## Week 17 - sublinear
- book
- communication complexity Rao
- https://www.cambridge.org/core/books/communication-complexity/5F44993E3B2597174B71D3F21E748443
- alteration tech techniq

---

## Week 18 - (on Week 17 Saturday) mother model(last class)
- Distributed
- Dynamic
- Think of a new problem in my id project
- change root dp?? seems not
- force to dominated 1/k point?
- 1=> root choose opt(0,1) or opt(1,1)
- if broken, need to be dominate opt(0, 0)
- applications can be added
- dp state can be limited!!!!
- 2020:6:20 11:27 End of class
- Q: Text book recommendation