代写两个算法程序以及六个算法分析题，代码题简单，但是分析题比较繁琐。
Instructions
This assignment consists of 6 analytical problems and 2 programming problems.
Your solutions to the analytical problems must be submitted, as one PDF, via
webhandin. While handwritten (then scanned) solutions to the analytical
problems are acceptable, you are strongly encouraged to typeset your solutions
in L A TEX or a word processor with an equation editor. The legibility of your
solutions is of great importance. It is required that your PDF’s filename not
include spaces, percent signs, pound symbols, or parentheses.
Programming Assignment
Your methods will be tested on the cse.unl.edu server, using
gcc version 4.8.1 20130909 [gcc-4_8-branch revision 202388] (SUSE Linux).
To ensure proper execution, you should test your submission in the webgrader
You will submit csce310hw002pt01.h, csce310hw002pt02.h, csce310hw002pt01.cpp,
csce310hw002pt02.cpp (and maybe csce310hw002pt03.h and csce310hw002pt03.cpp),
along with your PDF, via web handin.
ourQuickSelect
ourQuickSelect is a function that should take an integer value i and a vector
of n integer values. ourQuickSelect should return the number of comparisions
needed to find the i th smallest value in the vector using the quickselect
algorithm. The first element in the vector should be used as the pivot. You
may assume that each number in the vector is unique.
sumToN
sumToN is an adaptation of Exercise 6.1.7 on page 206. sumToN will take two
arguments: a vector of integer values and another integer value. The function
will return true if two unique values in the array sum to the quantitiy of the
second input value. It may be assumed that the vector will be in ascending
order.
averageComparisions (10 Points Extra Credit or Honors Contract)
Given an array of n integers, return the average number of comparisons that
would be required to successfully find an element in the array using binary
search. You may assume that the values in the array will be provided in
ascending order. When more than one element can be chosen in the search,
choose the element with a smaller value.
General Guidelines
Sample header, source, and testing files have been provided. You may modify
the .h and .cpp files as needed, but you will only be turning in the four/six
files mentioned above. The webgrader will be compiling the code with the
command g++ -o /path/to/executable.out /path/to/source/files/*.cpp for
each part, but I will only be copying the files I asked for out of your
submission and into separate directories for Part 1, Part 2, and Part 3.
Written Assignment
Question 1 (10 points)
Question 5.3.2 in The Design and Analysis of Algorithms
Question 2 (10 points)
(a) 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: 3,
1, 7, 9, 5, 8, 2, 0, 6, 4 (Preorder) and 9, 7, 1, 5, 3, 8, 0, 6, 4, 2
(Inorder)
(b) 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.
(c) 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 (10 points)
Estimate how many searches will be needed to justify time spent on presorting
an array of 10^6 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^9 elements?
Question 4 (10 points)
Question 6.1.1 in The Design and Analysis of Algorithms
Question 5 (10 points)
Question 6.1.9 in The Design and Analysis of Algorithms
Question 6 (10 points)
Question 6.5.1 in The Design and Analysis of Algorithms
