Set: Sorting, Searching and Hashing
Overview:
Questions 1(b) and 2(a) of this assignment require a C++ compiler. As usual, you must submit the actual source code files (ending in .cpp) so that I can compile and run your programs, and your programs must compile. The remaining problems must be written up in a Microsoft Word document. A Power Point file or a scanned handwritten diagram is also fine for Problem 1(a). Remember to include your name and course number within all of the files and documents that you submit.
Sorting
Read the assigned chapter and the notes for Week 7 located in the Learning Activities area, and then do the following problems:
Download the QuickSort.zip file and modify the QuickSort.cpp file by implementing the functions for the Quick Sort Algorithm. When finished your function will sort the list of strings in alphabetical order. The quickSort() function will call the partition() function, and the partition() function will call the swapItem() function. Your program must use these functions.
Searching and Hashing
Read the assigned chapter and notes for Week 8 located in the Learning Activities area, and then do the following problems:
Download the SequentialSearch.zip file, then implement the details for the sequentialSearch() function so that it uses recursion. The following is the non-recursive iterative version of the function. The modified version of the function must implemented using recursion. The function prototype, the function signature, and everything else within the program will remain the same.
int sequentialSearch(string list[], int itemIndex, int lengthOfList,
string item)
{
for (itemIndex=0; itemIndex < lengthOfList; itemIndex++)
{
if (list[itemIndex] == item)
{
return index;
}
}
return -1;
}
Briefly describe what double hashing is and describe what problem double hashing helps to resolve. Also, provide an example of a rule that can be used for a double hashing probe sequence.
Other Notes: Submit your solutions as a single Zip file using the Problem Set 4 link provided in the Assignment area. Again, if you are using Visual C++ or Dev-C++, please do not submit the entire source code project. You only need to submit the individual source code file. As usual, please ask if you have questions in either the Ask the Instructor forums area or via e-mail.