How does interpolation search algorithm estimate the position of the key in a sorted array?

Which of the following statements about Insertion Sort is correct?

In the Floyd-Warshall all shortest path algorithm, what is the purpose of introducing an intermediate vertex k during iteration?

Which of the following scenarios would cause the greedy approach (rational knapsack algorithm, choosing items by highest value-to-weight ratio) to fail in solving the 0/1 (or binary) knapsack optimally?

Based on the discussion from our lectures, what is the running time of the preprocessing step of the string matching algorithm with finite automata (i.e., of the step where we compute the transition function)? Recall that n, and m are the sizes of the text and pattern, respectively, and Σ is the alphabet. (Choose the tightest bound.)

Consider the following graph. 

Which of the following sets represents a minimum vertex cover?

Assume we apply the 2-approximation algorithm for the vertex cover problem as discussed in lectures. Suppose we select the edges in this order:

1. (A-B)
2. (C-D)

Which of the following sets represents the vertex cover formed by this algorithm?

Consider inserting the keys 21, 22, 31, 4,15, 28, 17, 88, 59 (in this order) into a hash table of length m=11 using linear probing with the auxiliary hash function h'(k)=k. Based on our lecture discussion, which of the choices below represents the resulting hash table?

1. n² * log n + n² = O(n²) 

    False

     True
    

2. n² + 1000 = Ω (n³)

     True

    False
    

3. n² + 5000 = Ω(n²)

   False

   True

4. n² + 9000 = Ω (n)

   True

   False

5. n² + 1000 = Θ (n³)

    False

     True
    

6. n² + n + 9000 = Θ (n²)

   True

   False

7. n² + n + 7000 = Θ (n)

     True

    False
    

8. n² * log n + n² + n = Θ (n²) 

     True

    False
    

9. n² * log n + n² + n  + 600 = O (log n²)

     True

    False
    

10. n * log n + 1000 = Θ (n log n)  

    False

    True

You are given the following array:

You are applying Merge Sort to sort the array in increasing order.