Consider the following undirected graph:

If we perform Breadth-First Search (BFS) traversal starting from node 3, how many of the following traversal(s) is/are possible? 

3 → 2 → 4 → 6 → 7 → 1 → 8 → 5

Consider the following partially sorted array after a few steps of insertion sort: [2, 5, 9, 4, 15, 3].

How many comparisons will insertion sort perform when inserting the element 4 into its correct position in the array during the next step of the algorithm?

Which of the following statements about quicksort is TRUE?

Suppose you inserted the keys 1, 3, 4, 7, 12, 14, 16, 17, 30, 39 (exactly in this order) into a hash table of size 13 using the hash function:

h(x)=(3x+5) mod  13 also insert key 27 and 43 after that

using chaining for collision resolution.

What is the running time of the above pseudocode in Θ notation?

Consider a double hashing scheme in which the primary hash function is:

h₁(k) = k mod  13  

and the secondary hash function is:

h₂(k) = 1+(k mod  5)

Assume that the table size is 13.

Find the address returned by probe 2 in the probe sequence for the key value k=20. Assume that the probe sequence begins at probe 0.

Implement the Boolean function

For the circuit shown below (implemented using a 2-to-4 line decoder with enable and an OR gate), find the expression for the output function and implement it using 2-input NOR gates and choose the right answer.

Perform the following binary subtraction:

11001 - 10111