Question 1

Question 5.3.2 in The Design and Analysis of Algorithms

Question 2

• Draw a binary tree with 10 nodes labeled 0,1,,9 in such a way that the inorder and preorder traversals of the tree yield the following lists: 8,2,3,5,6,4,0,9,1,7 (inorder) and 0,5,8,3,2,6,4,1,9,7 (preorder).
• Give an example of two permutations of the same n labels 0,1,,n 1 that cannot be inorder and postorder traversal lists of the same binary tree.
• Design an algorithm that constructs a binary tree for which two given lists of n labels 0,1,,n 1 are generated by the inorder and postorder traversals of the tree. Your algorithm should also indentify inputs for which the problem has no solution.

Question 3

Estimate how many searches will be needed to justify time spent on presorting an array of 10¹ elements if sorting is done by mergesort and searching is done by binary search. You may assume that all searches are for elements known to be in the array. What about an array of 10⁵ elements?

Question 4

Question 6.1.1 in The Design and Analysis of Algorithms

Question 5

Question 6.1.9 in The Design and Analysis of Algorithms

Question 6

Question 6.5.1 in The Design and Analysis of Algorithms

webgrader Notes

The webgrader should take roughly 60 seconds to complete running. Evidence of successfully running the webgrader consists of producing a PDF successfully in the directory

https://cse.unl.edu/~cse310/reports/02/USER/USER 02.pdf, where USER is your CSE username.

Your submissions success against each test case will be determined by use of diff. Your output must be exact. If you are intending to use debugging output, send that output to stderr, not stdout. Only send output you intend to be matched against the solution output to stdout.