Algorithmusingthe ideaof BFSto find a shortest(directed) cycle containinga given vertex v. Prove that your algorithmfinds a shortestcycle.What are the timeand spacerequirementsof your algorithm?     ??? 2.Showthat DFSvisits allverticesin G reachablefrom v. 3.Provethat the boundsof Theorem6.3holdfor DFS. 4.It is easy toseethat for any graph G,both DFS and BFS will take almostthe sameamount of time. However,the spacerequirements may beconsiderablydifferent. (a) Give an exampleof an n-vertexgraphfor which the depth of recursion of DFSstartingfrom a particularvertexv is n \342\200\224 1whereas the queueof BFShas at most onevertexat any given timeif BFS is startedfrom the samevertexv. (b) Give an exampleof an n-vertexgraphfor which the queueof BFS has n \342\200\224 1verticesat one timewhereasthe depth of recursionof DFS is at most one. Both searchesare startedfrom the same vertex.     1.Algorithm NQueenscanbemademoreefficient by redefiningthe function Place(/c,i)sothat it eitherreturnsthe next legitimatecolumnon whichto placethe kth. queenoran illegalvalue.Rewritebothfunctions (Algorithms 7.4and 7.5)so they implementthis alternatestrategy. 2. For the n-queensproblemwe observethat somesolutionsare simply reflectionsor rotationsof others.Forexample,when n = 4, the two solutionsgiven in Figure7.9areequivalent underreflection. Observethat for finding inequivalentsolutionsthe algorithmneedonly setx[l]= 2,3,...,\\n/2]. (a) ModifyNQueenssothat only inequivalentsolutionsarecomputed. (b) Run the n-queensprogramdevisedabove for n = 8,9, and 10. Tabulatethe number of solutionsyour programfinds for each value of n.         5. (a) Obtaina knapsackinstancefor whichmorenodesaregenerated by the backtrackingalgorithmusinga dynamic treethan usinga statictree. (b) Obtaina knapsackinstancefor whichmorenodesaregenerated by the backtrackingalgorithmusinga statictree than usinga dynamic tree. (c) Strengthenthe backtrackingalgorithmswith the following heuristic: Build an array minw[ ] with the property that minw[i] is the indexof the objectthat has leastweight amongobjects i,i+1,..., n. Now any \302\243?-node at whichdecisionsfor x\\,..., x^-\\ have beenmadeand at whichthe unutilizedknapsackcapacity is lessthan i<;[mmi<;[\302\253]] canbeterminatedprovidedthe profit earned up tothis nodeis no morethan the maximumdeterminedsofar. Incorporatethis into your programsof Exercise4(a).Rerunthe new programson the samedata setsand seewhat (if any) improvements result.