$30$ points total$]$ Collaborative Problem: Programming Assignment $2($PA$2)$ explores the Traveling Salesperson

Problem $($TSP$)$ in the form of the The Maryland Lighthouse Challenge$1,$ a biennial event where people

race around the state of Maryland attempting to visit all $10$ historic lighthouses and one lightship spread out

among the most beautiful parts of the state. The winner is the first team that visits all of the lighthouses during

the challenge weekend. One of your professors and his wife$2$ have competed very favorably$3$ in this ;$-)$

The lighthouse challenge can be modeled as a variation of the traveling salesperson problem $($TSP$)$ that recurs

frequently in networking, semiconductor layouts,and efficient routing. This problem asks you for a strategy of

finding the shortest Hamiltonian path, the path and starting point that leads contestants to visit all lighthouses

finishing at the earliest possible time. $($Unlike traditional TSP$,$ you do not return to the starting lighthouse$$this

is a straight up race from a start point to a separate finish point.$)$

Special note$$despite the algorithm taking a starting lighthouse, you are expected to choose the best lighthouse

to start at$.$ Assume some caller function, a kickoff function, will try all combinations of starting light. See

the mention of the phantom below, which is an easy way to find the best starting light automatically.

If you need a template for writing algorithms, check this out at Overleaf.com, an online LATEX editor$\mathrm{.}4($Even if

you$$re using Word, you can format at Overleaf and then paste a screenshot.$)$

$($a$)[15$ points$]$ Construct a recursive, brute$-$force algorithm for finding the optimal path among a small set of

lighthouses, starting at a given light, and analyze its running time.

Write a recursive brute$-$force algorithm in good pseudocode that follows this signature. Note, it must use

recursion to operate $($that is part of this assignment$)$: