Instructions
This request 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 request
Your methods will be tested on the cse.unl.edu server, using1
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 request
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