Algorithms Concepts¶
Proof¶
Two steps of correctness proof
feasibility: satisfy the constraints
optimality: better than any other solution
To prove feasibility, we just check whether the constraints are satisfied. To prove optimality, there are many approaches.
\(OPT\) gradually approaches out solution \(S\), e.g. by induction
Say our solution will not overshoot by saying that it is a feasible solution.
Simplification¶
Try to think some reasonable assumptions to transform the original problem setting into a simpler setting. If the optimal solution under the new setting corresponds to an optimal solution under the original setting, then the transformation is valid.
Graph Basics¶
Forest: a graph that is not connected and have no cycles