Introduction
：
，，，，，
，，，，
Requirement
Homework 05 (Due: Monday, November 27,2017,11 : 59 : 00PM
(Central Time)
CSCE 310
Instructions
This assignment consists of 5 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 T E X or a word processor with an equation editor. The legibility of your
solutions is of great importance.
Programming Assignment
Your methods will be tested on the cse.unl.edu server, using
4.8.1 20130909 [gcc-4_8-branch revision 202388] (SUSE Linux). To ensure proper execu-
tion, you should test your submission in the webgrader
You will submit OurCSCE310Tree.h and OurCSCE310Tree.cpp, along with your PDF, via web-
handin.
rotateLeft
rotateLeft is a function that will rotate a OurCSCE310Tree to the left.
rotateRight
rotateRight is a function that will rotate a OurCSCE310Tree to the right.
deleteNode (15 Points Extra Credit or Honors Contract)
deleteNode is a function that will receive a number and (if it exists in the OurCSCE310Tree) delete
it.
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 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 pt, but I will only be copying OurCSCE310Tree.h and OurCSCE310Tree.cpp out of your
submission and into separate directories for Part 1 and Part 2. You may assume that only positive
values will be placed into the OurCSCE310Tree.
1
Written Assignment
Question 1 (10 points)
Question 11.2.10, Parts b through e, in The Design and Analysis of Algorithms
Question 2 (10 points)
From Introduction to Algorithms ISBN:978-0-262-03293-3 You are given a a sequence of ele-
ments to sort. The input sequence consists of
n
k
subsequences, each containing k elements. The
elements in a given subsequence are all smaller than the elements in the succeeding subsequence
and larger than the elements in the preceeding subsequences. Thus, all that is needed to sort
the whole sequence of length n is to sort the k elements in each of the
n
k
subsequences. Show
an Ω(nlogk) lower bound on the number of comparisons needed to solve this variant of the
sorting problem. (Hint: It is not rigorous to simply combine the lower bounds for the individual
subsequences.)
Question 3 (10 points)
Question 11.3.2 in The Design and Analysis of Algorithms
Question 4 (10 points)
Question 11.3.6 in The Design and Analysis of Algorithms
Question 5 (10 points)
Question 11.3.11 in The Design and Analysis of Algorithms
Point Allocation
Question Points
Question 1 10
Question 2 10
Question 3 10
Question 4 10
Question 5 10
rotateLeft
Test Cases 1 × 15
Compilation 10
rotateLeft Total 25
rotateRight
Test Cases 1 × 15
Compilation 10
rotateRight Total 25
Total 100
Page 2