VE477 Lab 7

Description

Unless specified otherwise, all the programs are expected to be completed in Python or O’caml.

In this lab we want to compare three search algorithms. Let A be an array of size n and k be a value to find in A.

1. The first algorithm, RandomSearch, consists in randomly searching A for k. One simply selects a random index i and test if A[i ] = k. If true, then the algorithm returns i and otherwise randomly chooses a new i until either all the indices have been explored or k has been found. In this algorithm a same index can be generated more than once.

1. 1. Implement RandomSearch.

1. 2. Determine the average number of indices that are picked if:

1. 1. 1. There is no index i such that A[i ] = k.

1. 1. 2. There is exactly one index i such that A[i ] = k.

1. 1. 3. There is more than one index i such that A[i ] = k.

2. The second algorithm, LinearSearch, consists in performing a linear search on A, i.e. testing if k is in A[1], · · · , A[n], and either return i , the index where k is stored in A, or exit if k is not found.

1. 1. Implement LinearSearch.

1. 2. Determine the average-case and worst-case running times if:

1. 1. 1. There is no index i such that A[i ] = k.

1. 1. 2. There is exactly one index i such that A[i ] = k.

1. 1. 3. There is more than one index i such that A[i ] = k.

3. The third algorithm, ScrambleSearch, consists in randomly permuting A into A^′ and then run the

LinearSearch algorithm on A^′ .

1. 1. Implement ScrambleSearch.

1. 2. Determine average-case and worst-case running times if:

1. 1. 1. There is no index i such that A[i ] = k.

1. 1. 2. There is exactly one index i such that A[i ] = k.

1. 1. 3. There is more than one index i such that A[i ] = k.

4. From the previous complexities which algorithm seems to be the best.

5. Generate A, a random array of one million elements, and time each of the previous algorithms searching a random k on it. Repeat the process one thousand times, keeping track of the previous runs.

1. 1. Which algorithm performs best in practice?

1. 2. Discuss the result by comparing to your expected result in item 4.