Problem $5$: $(15$ points$)$ Given a list of integers, design an algorithm to form the largest

possible number. Example: given array $\{12,4,6,89,15\},$ the largest integer that can be

formed is $89641512.$

$1.(5$ points$)$ Describe a greedy algorithm.

$2.(5$ points$)$ State and prove the greedy choice property of your greedy algorithm. $(2$

points for the statement, and $3$ points for a proof$)$

$3.(5$ points$)$ State and prove the optimal substructure property of your greedy algorithm.

$(2$ points for the statement, and $3$ points for a proof$)$