Lab Overview
Scenario Summary
The purpose of the Lab exercises is to help the student acquire skills in developing programs that involve search algorithms and techniques.
Deliverables
There are four exercises in this Lab, although not all of them will be required for submission. Be sure to read the following instructions carefully.
• For Exercise 1, no submission is required.
• Exercise 2 requires not only software development but also explanations about the results of the experiments that are conducted. Create a separate Word document to provide the details required in the exercise.
• Exercise 2 requires sections of code to be timed. To review how to time a section of your source code, please refer to the explanations provided in the Lab last week.
• Create a folder and name it “Week 5 Lab.” Inside this folder, create the subfolders Ex2, Ex3, and Ex4. Place the solution to each of the three exercises required for submission in the corresponding subfolder. Compress the Week 5 Lab folder and submit the resulting zipped folder.
• Note that Exercises 2, 3, and 4 require software development. For each of them, place in the corresponding folder the source code files (i.e., .h and .cpp files) you created, and a screenshot of the execution window. Do not submit other files or folders, including those automatically generated by the IDE.
Required Software
Visual Studio
Use a personal copy or access the software at https://lab.devry.edu (Links to an external site.)Links to an external site..
All steps
Microsoft Office: Word
Use a personal copy or access the software at https://lab.devry.edu (Links to an external site.)Links to an external site..
Step 2
Lab Steps
Exercise 1: Lesson Review
Create a project, Search Algorithms, using the program in Search Algorithms (Links to an external site.)Links to an external site..
Compile the project, run it, and carefully review the given code. This program tests the code discussed in the lesson.
Exercise 2: Study of Search Algorithms
Expand the project developed in the previous exercise to perform the following experiment: Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment.
Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? In addition to the source code and a screenshot of the execution window, please submit a separate document with the table and your conclusions about the experiment.
Exercise 3: Searching Applications
Design and implement an algorithm that determines whether or not a given array of integers, list1, is completely contained within another given array of integers, list2. Consider two different scenarios: (1) Both arrays are unsorted and (2) both arrays are sorted and write functions unsortedSearch and sortedSearch for (1) and (2), respectively. Your algorithm for (2) is expected to be more efficient than the one for (1).
Exercise 4: Hash Functions
Design and implement a hash function that converts a string to a hash value. Test your function by computing the hash values for the C++ keywords.
Note: You can use Sections 9.2.2–9.2.4 of our textbook as a reference to implement your own hash function; these sections discuss hash function design.