Algorithms course programming homeworks
Implement Insersion Sort, Merge Sort, Quick Sort and Heap Sort.
Program for testing test cases
$ python3 test.py <options>
Options:
-IS → Insersion Sort
-MS → Merge Sort
-QS → Quick Sort
-HS → Heap Sort
Run test
$ ./run
Given a graph G= (V, E)
which may containcycles, we want to remove some edges to make the graph acyclic with minimum total cost.
Can be treated as Reversing Deleting MST problem. ← The performance is not good in this implementation.
Using Kruskal's algorithm to find the removed edges not in the Maximum Spanning Tree.
Known as minimum feedback arc set problem Is a NP-hard problem.
Adjacency list
[V0]->V1->V3...
[V1]->
[V2]->
...
[Vn]->
V_i : pair(<vertex index>,<weight>)
Method 1 : Directly perform DFS
- DFS to find cycle.
- Backtrack all vertices in the cycle.
- Find the minimum weight edge then set a flag.
- Repeat until there are no cycles.
- Output edges which is labeled to remove.
Method 2 : Derive from MST
- Treat the graph as undirected graph, perform Kruskal to find MST.
- We got the removed edge list.
- Add the edges from the list edge by edge back to the graph if there is no cycle.
※ Heuristic : only add positive weight edges back to the graph to minimize the cost. (That is, adding negative weight edges to "Removed" edge list.)
For public_cases/public_case_N.in
:
1, 2, 4, 5, 6
: undirected weighted
3, 7, 8
: directed weighted