Algorithm Self-Learning Notes

Reference: J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2006

Algorithm CH1 Friday, January 8, 2021

1. Stable Matching
2. Termination:G-S terminates after at ost n² iteration

Algorithm Sunday, January 10, 2021

Stable Matching

Correctness:

1.Termination: at most n² iteration

2.Perfection: Everyone gets married => prove by contradiction

3.Stability: The marriages are stable

Male Optimality

prove by contradiction

Proposed Definition

Polynomial running time:

cN^d primitive computational steps

Intrinsic computational tractability

Asymptotic upper bound: Of(n)

Asymptotic lower bound: Ωf(n)

Asymptotic tight bound: θf(n)

cf(n) find c and n0

Algorithm Monday, January 11, 2021

第三週 Stable Matching

1. While loop → O(n²)
2. Use Pref[ ] needs O(n) total O(n³)
3. Use Ranking[ ] needs O(n) total O(n³)

4. Keys to Success: CAR Theorem

5. Euler-七橋問題

6. BFS tree

Algorithm Tuesday, January 12, 2021

1. Use BFS and DFS to find connected component
2. Adjacency Matrix and Adjacency List compared
3. Queue: FIFO order , Stack: LIFO
4. Implementing BFS, use adjacency list O(n+m)
5. Implementing DFS, use stack, adjacency list O(n+m)
6. Testing Bipartiteness use BFS (drawing colors)
7. Testing Strong connectivity use BFS

Algorithm Thursday, January 14, 2021

第五週

1/2

1. Directed Acyclic Graphs (DAG)
2. Topological Ordering

Lemma: If G is a DAG, then G has a topological ordering

proof by induction

- base case

- Introduction steps

3.Time: From O(n2) to O(m+n)

2/2

Greedy Algorithm

Application : The Interval Scheduling Problem

1. Greedy rule

2. Stays Ahead : by induction

3. Optimal: proof by contradiction

Implementation: The Greedy Algorithm

Running time: From O(n2) to O(n log n)

Algorithm Friday, January 15, 2021

第七週

1/2

1. Interval Partitioning

Application: Use the least source

find depth d lower bound

proof

2. Scheduling to minimise lateness

An exchange argument → common proof method

3. Summary: Greedy Analysis Strategies

extra — internal graph (intersection graph)

- 輕重緩急分類

2/2

1. Shortest Path

Dijkstraís Algorithm

implementation: use binary heap

Algorithm Saturday, January 16, 2021

第九週

1/2 Reap Heaps: priority Queues

Binary Tree Application

Heap:

Max Heapify

Build Max Heap: O(nlogn)

2/2 Minimum Spanning Tree Sunday, January 17, 2021

Greedy Algorithm

1.Kruskal ’s

2.Prim’s

3.Reverse-delete

Cut Property

pf: Exchange argument

Cycle property

pf: Exchange argument

Prim => Cut Property (Similar to Dijkstra’s)

Kruskalís Algorithm

1. Sorting — mlogn

2. Use Union Find data structure

Greedy Algorithm

• Pf: Exchange argument
• Application: Shortest path, Minimum Spanning Tree

Algorithm Monday, January 25, 2021

第10週

Divide and Conquer

1. Weak(Strong) induction

Example: A Defective Chessboard

1. Merge sort, heap sort: nlogn
2. Binary Search:logn
3. Merge sort: O(nlogn)
4. 5.Counting Inversions: O(nlogn)
5. closet pair of points: O(nlogn)

Algorithm Monday, May 24, 2021

第13週

Dynamic Programming

Get Michael Chang’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Problem1: Weighted Interval Scheduling

Solve: Memorisation :Top-Down

M-Compute-Opt(j)
1. if (j = 0) then return 0
2. else if (M[j] is not empty) then return M[j]
3. else return M[j] = max{{vj+M-Compute-Opt(p(j))}, M-Compute-Opt(j-1)}

Running Time: O(n)

Solve: Iteration: Bottom-Up

I-Compute-Opt
1. M[0] = 0
2. for j = 1, 2, .., n do
3. M[j] = max{vj+M[p(j)], M[j-1]}

Running Time: O(n)

Keys for Dynamic Programming

Problem2: Fibonacci Sequence

Solve: Dynamic Programming — Memoization

Store the values in a table

fib(n)

1. Initialize f[0..n] with -1 // -1: unfilled

2. f[0] = 0; f[1] = 1

3. fibonacci(n, f)

1.If f[n] == -1

2.then
f[n] = fibonacci(n -1, f) + fibonacci(n — 2, f)

3. return f[n] // if f[n] already exists, directly return

Dynamic Programming — Bottom-up

fib(n)

1. initialize f[1..n] with -1 // -1: unfilled

2. f[0]=0;f[1]=1

3. for i=2 to n do

4. f[i] = f[i-1]+ f[i-2]

5. returnf[n]

Problem3: Maze Routing

Leeís Algorithm

Running time
§ O(MN)forM*N grid

Algorithm Tuesday, May 25, 2021

第14週

Subset Sum

背包裝東西問題

Solve: DP: Iteration, Bottom-Up

Running Time: O(nw)

W很大效果不好

Pseudo-Polynomial Running Time

W is not polynomial in input size
Karp’s 21 NP-complete problems

The Knapsack Problem

Optimization problem formulation

max SiŒS vi => Use Value diffrent than Subset Sum
s.t. SiŒS wi < W, SÕ{1, Ö, n}

this problem type:

0–1 Knapsack

another type:

fractional Knapsack

Shortest Path — Bellman-Ford Algorithm

Modifying Dijkstraís Algorithm

compensates with subsequent edges of negative cost

Record “successor” for each entry to find shortest path

It can use to Detect Negative Cycles

Application: Currency Conversion

— convert to log and do Bellman-Ford Algorithm

Application: Travelling Salesman Problem

NP problem

§ Space: O(2nn2)
§ Running time: O(2nn3)

Summary: Dynamic Programming

Dynamic programming is NOT about filling in tables; itís about smart recursion.

Algorithm Thursday, May 27, 2021

第15週

The Maximum Flow Problem

UpperBounds: Find cuts of minimum capacity = find maximum flow

Ford-Fulkerson: Residual Graph

- Augmenting Paths

The Max-Flow Min-Cut Theorem

Bipartite Matching via Network Flow

Add s and t and do Ford-Fulkerson Algorithm

Ford-Fulkerson Algorithm

Running time: O(mC)

- while loop: C iterations

• Augmentation:O(m)

Algorithm Thursday, June 3, 2021

第 16 週

Content:
§ Polynomial-timereduction

§ NP-completeness

Decision & Optimization Problems

Class NP is associated with decision problems

Complexity Classes

Developed by S. Cook and R. Karp

Class P, NP, NPC

Verification Algorithm and Class NP

1. check a solution in polynomial time

2. can be done in O(n) time,

so TSP(Traveling Salesman Problem)ΠNP

The First Proved NPC: Circuit Satisfiability

Polynomial-Time Reduction

1. Design algorithms

2. Establish intractability

3. Establish equivalence

Polynomial Reduction: HC <=p TSP

Algorithm Tuesday, May 25, 2021

第 16 週

Linear Programming

consists of three parts:

- A set of decision variables

• An objective function

- A set of constraints

Example: Profit Maximization

最佳解：

The Simplex method: hill climbing

作法：

利用Upper Bound組合 constraints

- 找尋合適的multipliers

- Duality =>Max-flow min-cut

Any feasible value of dual LP is an upper bound on primal LP

The Simplex Algorithm

• 使用座標轉換, 使要找的頂點為原點, 係數均為負為optimal solution
• On each iteration, simplex has two tasks:
  § Task1:Check whether the current vertex is optimal § Task2:Determine where to move next

Standard Form

1. Object Function : minimization

2. Constraints:equations
3. Variables:nonnegative