question archive Algorithmusingthe ideaof BFSto find a shortest(directed) cycle containinga given vertex v
Algorithmusingthe ideaof BFSto find a shortest(directed) cycle containinga given vertex v
Subject:Computer SciencePrice: Bought3
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.
