Motivation
Given a list of elements,
we want to calculate cumulative total based on an associative binary operation.
Moreover, efficient modification is desired.
Naive
Concept
Using an array arr to store each element in the original list.
Motivation
Design a data structure that stores a partition of a set.
With the operations of union, find, etc.
Naive
Way-A: Update the Set Each Element Belongs to
Find: $O(1)$
Make Union: $O(N)$
Prim's Algorithm
Sample Code
Kruskal's Algorithm
$\text{Input: } G=(V,E)\text{ and a weight function }w:V\times V\rightarrow\mathbb{R}$
$\text{Output: } T=(V,F) \text{ where }F\subseteq E\text{ and }T\text{ is a spanning tree of }G.$
$1F\leftarrow\varnothing$
$2\textbf{for each }e={u,v}\text{ in }E \text{ ordered by }w(u,v)\text{ do}$
$3~~~~~~~~\textbf{if }\text{there is no cycle in }H=(V,F\cup e)\text{ do}$
$4F\leftarrow F\cup e$
Special case: 2-Dimensional space
Graham's Scan
First choose a trivial point $p_0$ that it must be in convex hull (leftmost and lowest).
sort all the other points in polar angle order, getting ${p_1, \dots,p_n}$.
let $s={p_0,p_1}={s_2,s_1}$(reversed order).
let $i=2$.
while $i<n$ do the following:
If $|s|<2$ or $\angle p_is_1s_2$ is convex, then let $s=s\cup{p_i}$, and $i=i+1$.
If not, $s=s\setminus{s_1}$.
Fractional Knapsack Problem
Input: A sequence of weights and another of values, the capacity of knapsack.
Output: Maximum value. (You can cut item into pieces.)
Greedy
Sorted by $\dfrac{\text{value}}{\text{weight}}$ of each item, always choose the biggest one in that moment.
Since every unit of space in the knapsack contains the most valued item,
Problem
Input: number of cites, number of roads, a sequence of roads
Output: Minimum cost of travelling through all the cities.
Naive: Exhaustive Search
All permutation of cities.
Time complexity: $O(n!)$, where $n$ is the number of cities.
AlfredTing changed 4 years agoView mode Like Bookmark
Problem Description
Given a DAG (directed acyclic graph), find out a sequence ${a_1,\dots,a_n}$
such that if $i<j$, you need to go through $a_i$ before you go to $a_j$.
Kahn's Algorithm
vector<vector<int>> adj;
vector<int> topological_sort() {
int n = adj.size();