Use recursion: To move a stack of n disks from some origin peg to some destination peg, we could think of some number k between $1$ and n $($you decide if it should be inclusive or not$),$ and then:

$$ Move n $$ k disks to an intermediate peg using all four pegs.

$$ Move what$$s left on the origin peg to the destination peg, using as many pegs as possible. $($You$$ll need to

decide whether to use $3$ or $4$ pegs here.$)$

$$ Move the n$$k smallest disks from the intermediate peg to the destination peg, using as many pegs as possible.

$($You$$ll need to decide whether to use $3$ or $4$ pegs here.$)$

Your job is to implement the $4-$peg TOH solution with the above strategy, as well as conducting experiments measuring the number of moves taken by the solution and reporting the results. Specifically, complete the following tasks:

$($a$)$ Download and read the starter code A$2$Q$2.$java carefully and understand the requirements and specifications of the methods to be implemented. Read all instructions in the starter code carefully. In particular, make sure to NOT modify the parts of the starter code that says $$DO NOT MODIFY$$ in the comments, e$.$g$.,$ the package declaration $$package A$2$ and the import lines.

$($b$)$ Implement the threePegTOH method, which returns the sequence of moves that solves the $3-$peg TOH problem. The solution to this problem is well$-$known and easily found online. However, you should complete it independently for your own learning benefits.

$($c$)$ Perform experiments to demonstrate that the number of moves taken by the $3-$peg TOH solution is $2$n $1.$ Report your experiments and their results in your PDF submission.

$($d$)$ Implement the fourPegTOH method.

$($e$)$ In the PDF file, describe your strategy on how to choose the value of k$.$ You are NOT required to come up with the optimal strategy. What$$s important is that you come up with something original that is better than the $3-$peg solution, and that you can use experiments to evaluate the strategy you choose.

$($f$)$ Perform experiments to demonstrate the number of steps taken by your $4-$peg TOH solution as a function of n$,$ and show that it is consistently faster than the $3-$peg solution. Compare different ways of choosing k and show how it affects the number of steps taken. Report your experiments and their results in your PDF submiss