I will provide below the original problem and the code I've written. What is my code doing wrong?

Traveling Salesperson Problem $--$ Held$-$Karp Algorithm

This exercise is about the Traveling Salesperson Problem I mentioned in the lecture on NP$-$hard problems $--$ given a set of cities, determine the length of the shortest tour that visits all of them. We can get from any city to any other city, i$.$e$.$ the graph of cities is completely connected. We consider the version of the Traveling Salesperson Problem that finds the shortest tour to visit $\backslash ($ n $\backslash )$ cities, starting at a city and ending at the $\backslash ($ n $\backslash )$th city; it does not go back to the start. The start city may be any of the cities. Remember that the graph for a TSP is undirected, i$.$e$.$ the cost is the same in either direction.

The Held$-$Karp algorithm for solving the Traveling Salesperson Problem is a recursive algorithm that considers every subset of cities and finds shortest tours within them. It takes advantage of the fact that every subroute of a route of minimum length is of minimum length itself. The main idea is that to solve the problem of finding the shortest route for $\backslash ($ n $\backslash )$ cities, we first solve the problem of finding the shortest route for $\backslash ($ n$-1\backslash )$ cities, and then find the shortest route from the $\backslash (\backslash$$ n$-1\backslash$$ $\backslash )$ st city to the $\backslash (\backslash$$ n $\backslash$$ $\backslash )$ th city. The pseudocode for the algorithm is as follows:

$```$

$//$ cities is the set of cities not visited so far, including start

heldKarp$($cities$,$ start$)$

if $|$cities$|==2$

return length of tour that starts at start, goes directly to other city in cities

else

return the minimum of

for each city in cities, unless the city is start

$//$ reduce the set of cities that are unvisited by one $($the old start$),$ set the new start, ac

heldKarp$($cities $-$ start, city$)+$ distance from start to city

$```$

Implement a dynamic programming version $($which could use memoization$)$ of the Held$-$Karp algorithm. If you use memoization, make sure that the cache is reset every time the function is called such that multiple calls do not end up using old and incorrect values. Start with the template I provided in

The function takes a distance matrix $($the adjacency matrix for the graph where the values in the cells are the distances between the corresponding cities$)$ and returns the length of the shortest tour $($not the tour itself$).$

Test your new function; l've provided some basic testing code in

Runtime Analysis

What is the worst$-$case asymptotic time complexity of your implementation? What is the worst$-$case asymptotic memory complexity? Add your answer, including your reasoning, to this markdown file.

$```$

Js code.js $>...$

$//$ helper function that takes a list of cities, a start city, our distance matrix, and a set used for memoization, to recursively find the shortest path

function hk$($cities$,$ start, distance$\_$matrix, memoization$)\{$

$```$

$```$

if $($cities$.$length $==2)\{$

let end;

if $($cities$[0]==$ start$)\{$

end $=$ cities$[1]$;

$\}$

else $\{$

end $=$ cities$[0]$;

$\}$

return distance$\_$matrix$[$start$][$end$]$;

$\}$

$//$ create a unique key for our current call of cities and start. got the idea for generating a unique key for each subproblem using this line from chatGPT

let memoizationKey $=$ cities.sort$().$join$(",")+"-"+$ start;

$//$ if we've already checked this subproblem, ie there already exists a value stored at this key, return that value

if $($memoization$[$memoizationKey$]!=$ undefined$)\{$

return memoization$[$memoizationKey$]$;

$\}$

$//$ initialize our shortest path to infinity

let shortestPath $=$ Infinity;

$//$ initialize a nel set of cities to be used in recursive call that excludes our current city using a higher order filter function $($learned in functional$)$

let unmarkedCities $=$ cities.filter$($city $=>$ city $!=$ start$)$;

$//$ loop through all cities in our list excluding our start city, as detailed in psuedocode

for $($let i $=0$; i $$ unmarkedCities.length; i$++)\{$

$//$ set our current city to be city at index i

let currentCity $=$ unmarkedCities$[$i$]$;

$```$

$```$

let pathDistance $=$ hk$($unmarkedCities$,$ currentCity, distance$\_$matrix, memoization$)+$ distance$\_$matrix$[$start$][$currentCity$]$;

$//$ check if our path is shorter than what is currently the shortest path

if $($pathDistance $$ shortestPath$)\{$

$//$ if so$,$ set shortest path to be this path

shortestPath $=$ pathDistance;

$\}$

$\}$

$//$ memoize this shortest path by adding it to memoization at its unique key

memoization$[$memoizationKey$]=$ shortestPath;

$//$return shortest path

return shortestPath;

$\}$

function tsp$\_$hk$($distance$\_$matrix$)\{$

$//$ initialize a list of cities using the keys along the length of the distance matrix

let cities $=[...$Array$($distance$\_$matrix.length$).$keys$()]$;

$//$ initialize start to city $0$

let start $=0$;

$//$ initialize our memoization object as an empty set

let memoization $=\{\}$;

$//$ call our helper function with our initial variabl