Solution for QID #107979: Assume that n programsare to be storedon two tapes.Let lj be | StudyHelpMe

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?