question archive Assume that n programsare to be storedon two tapes
Assume that n programsare to be storedon two tapes
Subject:Computer SciencePrice: Bought3
Assume that n programsare to be storedon two tapes.Let lj be
the length of tape neededto storethe ith program. Assume that
J2h < 302243, whereL is the length of eachtape. A programcan be
storedon eitherof the two tapes.If S\ is the set of programson tape 1,then the worst-caseaccesstimefor a programis proportionalto
?
max{Eies1hi JligSih}- An optimalassignmentof programsto tapes
minimizesthe worst-caseaccesstimes.Formulatea dynamic
programming approachto determinethe worst-caseaccesstimeof an optimal
assignment.Write an algorithmtodeterminethis time. What is the
complexityof your algorithm?
6.RedoExercise5 makingthe assumptionthat programswill be stored
on tape 2 usinga different tape density than that usedon tape 1.If
li is the tapelengthneededby programi when storedon tape1,then
ah is the tapelengthneededon tape2.
7. Let L bean array of n distinctintegers.Give an efficient algorithmto
find the lengthof a longestincreasingsubsequenceof entriesin L.For
example,if the entriesare11,17, 58,6,4,7,12,3, a longestincreasing
subsequenceis 5,6,7,12.What is the run timeof your algorithm?
3.Useone of the three traversalmethodsdiscussedin Section6.1to
obtain an algorithmEquiv(i,u)that determineswhetherthe binary
treest and u areequivalent.Two binary treest and u areequivalent
if and only if they are structurallyequivalent and if the data in the
correspondingnodesof t and u arethe same.
4. Showthe following:
(a) Inorderand postordersequencesof a binary treeuniquely define
the binary tree.
(b) Inorderand preordersequencesof a binary treeuniquely define
the binary tree.
(c) Preorderand postordersequencesof a binary treedo not uniquely
define the binary tree.
5. In the proofof Theorem6.1,show,usinginduction,that T(n) < C2n+
c\ (whereC2 is a constant>2c\).
6.Write a function to constructthe binary tree with a given inorder
sequence/ and a given postordersequenceP.What is the complexity
of your function?
7. DoExercise6 for a given inorderand preordersequence.
8.Write a nonrecursivealgorithmfor the preordertraversalof a binary
treet. Your algorithmmay usea stack.What arethe timeand space
requirementsof your algorithm?
9. Do Exercise8 for postorderas well as inordertraversals.
10.[Triple-ordertraversal] A triple-ordertraversalof a binary tree t is
definedrecursivelyby Algorithm6.3.A very simplenonrecursive
algorithm for sucha traversalis given in Algorithm 6.4.In this algorithm
p, q, and r point respectivelyto the presentnode,previously visited
node,and next nodeto visit. Thealgorithmassumesthat t ^ 0 and
that an empty subtreeof nodep is representedby a link to p rather
than a zero.Provethat Algorithm 6.4is correct.(Hint: Threelinks,
Ichild,rchild,and onefrom itsparent,areassociatedwith eachnode
s. Eachtimes is visited,the links are rotatedcounterclockwise, and
soafter threevisits they arerestoredto the originalconfigurationand
the algorithmbacksup the tree.)
11.[Level-ordertraversal] In a level-ordertaversalof a binary treet all
nodeson level i are visited beforeany nodeon level i' + 1is visited.
Within a level,nodesarevisited left to right. In level-orderthe nodes
of the treeof Figure6.1arevisited in the orderABCDEFGHI. Write
an algorithmLevel(t) to traversethe binary treet in level order.How
much timeand spaceareneededby your algorithm?
