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

1. DFS to find cycle.
2. Backtrack all vertices in the cycle.
3. Find the minimum weight edge then set a flag.
4. Repeat until there are no cycles.
5. Output edges which is labeled to remove.

Method 2 : Derive from MST

1. Treat the graph as undirected graph, perform Kruskal to find MST.
2. We got the removed edge list.
3. 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