Design a dynamic programming algorithm to achieve Degree Anonymization stated as below: Problem (Degree Anonymization). For an input graph G(V,E) with degree sequence d and an integer k, construct a new degree sequence d that is k-anonymous and such that the degree-anonymization cost PiV d(i)d(i) is minimized, where d(i) means the degree of the i-th node. Here, we only consider adding edges to increase the node degrees, i.e., d(i) d(i), i.

Task 1: Follow the below steps to achieve the anonymized degree sequences

Step 1 (3 Points): Generate a random graph G = (V,E) with n nodes and m edges. You can use the

NetworkXs built-in functions to generate random graphs. Try 3 different n = 6, 10, 20 and m = 1.5n.

Step 2 (2 Points): Obtain the degree sequence d from each of the 3 generated random graphs and sort

degrees in a descending order.

Step 3 (15 Points): Obtain the k-anonymous degree sequence d with the minimal cost via dynamic

programming. Try k = 2,3 for the graph with n = 6, and k = 3,4 for the graph with n = 10,20. "explain it in detail steps"

Step 4 (10 Points): Are the degree sequences d reliable? Why or why not? You only need to check n = 6

with k = 2,3.

solve Obtain the k-anonymous degree sequence d with the minimal cost via dynamic programming. Try k = 2,3 for the graph with n = 6, and k = 3,4 for the graph with n = 10,20.