Crowdly

It must have clear and unambiguous instructions

It must produce an output

It must terminate after a finite number of steps

It must always run in polynomial time

Find the asymptotic running time for the recurrence relation T[n]=8T[n/4]+n^1.51 and then select every correct answer below (more than one choice could be selected).

T[n]=Θ(n^1.51)

T[n]=O(n^3/2)

T[n]=Θ(n²)

T[n]=O(n^8/5)

T[n]=O( log₂n )

What does asymptotic analysis focus on?

The performance of an algorithm for very small inputs

The number of times an algorithm accesses memory

The best possible performance of an algorithm in ideal conditions

The execution speed of an algorithm on a specific machine

The growth rate of an algorithm’s running time as input size increases

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

h₁(k) = (2k+3)mod 29

and the secondary hash function is

h₂(k) = 1+(3k mod 23).

Assume that the table size is 29.

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

Consider the following array: [3, 6, 8, 10, 1, 2, 4].

Suppose we perform quicksort on this array using the first element as the pivot. What is the state of the array after the first partitioning step based on our discussion in lectures?

[1, 2, 3, 6, 8, 10, 4]

[1, 2, 3, 6, 8, 4, 10]

[1, 2, 4, 3, 6, 8, 10]

[1, 2, 3, 4, 6, 8, 10]

[2, 1, 3, 6, 8, 10, 4]

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

f ( n ) = O (g ( n )) implies f ( n ) = Ω (g ( n ))

f ( n ) = Θ (g ( n )) implies f ( n ) = O (g ( n )) and f( n ) = Ω (g ( n ))

f ( n ) = Ω (g ( n )) implies f ( n ) = O (g ( n ))

f ( n ) = O (g ( n )) implies f ( n ) = Θ (g ( n ))

f ( n ) = Θ (g ( n )) implies f ( n ) = O (g ( n )) but not f( n ) = Ω (g ( n ))

How many statement(s) shown above is/are correct?

Consider the following undirected graph:

Image failed to load

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

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

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

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

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

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?