Reference no: EM132915609

Question 1

Given an array of n unsorted items, the following function Fun finds the frequency of the median of the values of A. The median is the element in the middle of the ordered (smallest to largest) array. Select ONE or MORE of the following statement/s that is/are correct.

Algorithm 1 Fun(A[0..n-1])
1: sort(A)
2: medianIndex = floor(n/2)
3: medianValue = A[medianIndex]
4: medianFreq = 1
5: i = medianIndex - 1
6: while i > 0 and A[i] == medianValue do
7: medianFreq += 1
8: i -= 1
9: end while
10: i = medianIndex + 1
11: while i < n and A[i] == medianValue do
12: medianFreq += 1
13: i += 1
14: end while
15: return medianFreq

if using QuickSort to sort the array in line 1, the overall worst case time complexity of Fun is 0(n²) .

if using InsertionSort to sort the array in line 1, the overall worst case time complexity of Fun is 0(n²).

if using QuickSort to sort the array in line 1, the overall best case time complexity of Fun is (9(log n).

if using MergeSort to sort the array in line 1, the overall worst case time complexity of Fun is 0(n²).

if using Selection Sort to sort the array in line 1, the overall worst case time complexity of Fun is (9(n² log n) .

Question 2

Select ONE or MORE of the following statement's that is/are correct.

Top down dynamic programming is always faster than bottom up dynamic programming.

BFS is typically ran on graphs but can be applied to binary trees.

The Insertion Sort algorithm uses a Transform-and-Conquer approach as it transforms the problem to a different representation of the same problem instance.
To find the minimum spanning tree of a given weighted connected graph, Prim's algorithm guarantees to be faster than Krushal's algorithm in all cases.
To find the minimum spanning tree of a given weighted connected graph, Prim's algorithm guarantees to return the optimal solution, regardless of which node it starts with.
The primary criteria for priority queues is First-In-First-Out (FIFO).

Question 3

Which of the following statements are true? Select ONE or MORE that is/are true.

Note: [x] denote the ceiling of x, and [x] denote the floor of x.
\/0.01 n⁸ + 100n⁷ - 1200n³ - 0.45n ∈ Ω(n⁴)

10n log n] ∈ Ω(n²)
12x⁵ + 6x⁶ - 5x³ ∈ Θ(x⁶)
(n² + n)² ∈ Θ(n⁴)

[10n log n] ∈ 0(n)

5n log n E 0(n)

Question 4

To sort the array [5, 9, 13, 6, 8, 10] in ascending order (from smallest to largest), Insertion Sort takes [ans1] key comparisons.

Question 5
Consider the following graph:

Compute single source shortest path distance from Node B to all the other nodes.
Starting from the initial estimate of non-infinity distances, using Dijkstra's algorithm list out the sequence of estimates (previous node in path, estimate of shortest path distance) for each of the following nodes (the final estimate should be its shortest path distance from the source node):
a) The sequence of estimates for Node A is
b) The sequence of estimates for Node H is
c) The sequence of estimates for Node D is
d) The sequence of estimates for Node F is Resolve ties by using the alphabetical order, i.e., prioritise A, then B, then C, etc.
For formatting, using a made up example (note the nodes in this example doesn't exist in in the question, only used here to illustrate how to format the answer), say we are estimating the shortest path distance for the fictitious node X from source node U. If the Dijkstra's algorithm estimates were first the path U->X (distance of 15).

Question 6
Given the input of integers in the following order 21,51,32,20,44,11 and the hash function h(K) = K mod 9

1) if we use separate chaining hashing to construct the hash table, and always adding the new key to the HEAD of any linked list chains, the number of comparisons required to search for key 51 in this table is ; the_____ number of comparisons required to search for key 68 in this table is _.

2) if we use open address hashing with linear probing to construct the hash table, the number of comparisons required to search for key 20 in this table is the number of comparisons required to search for key 22 in _____ this table is Formatting note: in each of the above blanks, fill in a single integer value, with NO space before or after.

Question 7
Starting with an empty tree, insert the following keys into an AVL tree in the given order: 15,5,2,22,16,8,18. Answer the following questions for the constructed AVL tree:

The key of the root of the tree is _______. The key of the right child of the root of the tree is ______. The sequence of rotations that were applied in the construction of the tree is _____

Formatting note: for the first two subquestions where you are specifying keys for the blanks, fill in a single integer value, with NO space before or after.
For the last subquestion, write down the sequence using comma delimiter (NO space between rotations, or before or after first and last rotation in sequence). Rotations are one of L (left), R (right), LR (left-right) and RL (right-left). E.g., if sequence is a R followed by RL, then answer should be R,RL

Question 8

Consider the unsorted array of 9,4,12,8,5,24,6,7,11,3,23
Using Quicksort to sort the array and assuming we are using the first element as the pivot:
• the pivot(s) used at the start of the 2nd iteration is/are _____.
• the pivot(s) used at the start of the 3rd iteration is/are ______.
• the pivot(s) used at the start of the 4th iteration is/are ______.
• the total number of swaps to sort the array is . Include in the count the swaps to put the pivot inplace as well.

The 1st iteration is to use 9 as the pivot to divide the whole array into two partitions.

List the pivots in the format of pivot1, pivot2, ...,pivotn, if there are n pivots. E.g., if the pivots are 1, 2 and 3, then put the answer as 1,2,3 (comma separated, no space inbetween). Order the pivots from left to right.

Question 9

Consider two teams, Red and Blue.
We need to match one member from each teach with each other, i.e., one member of Red to one member of Blue.

Each member of Red has a ranking of preferred partners with the members of Blue.

B1	B2	B3	B4
R2	R3	R1	R3
R3	R2	R4	R4
R1	R1	R3	R2
R4	R4	R2	R1

Using the Gale-Shapely algorithm, find the stable matchings.

The stable partners that R2 can be matched with is/are . If there is only one possible partner, then type that single answer, e.g., B1. If there are two possible partners, then type both in, in the format, e.g., B1,B2 (comma separated, no space). Hint: Perform both Red team proposing and Blue team proposing to obtain this.

The number of proposals that R4 gave before finding their final match (INCLUDING the last proposal made to the final match), when the Red team is proposing, is The number of proposals that B1 gave before finding their final match (INCLUDING the last proposal made to the final match), when the Blue team is proposing, is

Question 12

Consider the following problem.

In the future, you are presented with two alien words W1 and W2, both of length m. Both of these words are formed from the alien alphabet/symbols (assume the number of unique symbols is greater than m). Each word is stored in an array. Part of our understanding of this alien language is a) each word can, at most, have one of each alien symbol/alphabet letter; and b) that two words have the same meaning if one word is a permutation of another, or if after rearranging the order of one word, it is the same as the other word. E.g., assuming alien alphabet is A,B,C, then the two alien Words ABC and CBA are the same. You have many words to check, hence you been tasked to design an algorithm to find that has worst case complexity of (9(m log m) for comparing two alien words of the same length.

Which of the following are possible algorithms to achieve this worst case complexity? Select ONE or MORE answers.
1. Concatenate W1 and W2, end to end, to form W1W2 of length 2m.
2. Sort the concatenated word W1W2 by the alien alphabet order.
3. For p = 0 to m-1, compare W1W2[2p] with W1W2[2p+1]
4. If all the comparisons have the same characters, then the two words are considered the same word in the alien language, otherwise they are different words.
1. Initialise an array A that indicates which positions are matched in W2, to all false values.
2. For each position in W1, using array A, compare each unmatched position in W2 to see if characters match. If so, set corresponding position in A to True (matched) and continue with next position in W1.
3. If after step 2, all positions in array A are True (matched), then they are considered the same word in the alien language, otherwise they are different words.
1. Sort both each word (W1 and W2) by its alien alphabet order.
2. For each position p in sorted W1, compare sortedW1 [p] with sortedW2[p]
3. If all positions have the same characters, then the words are considered the same word in the alien language, otherwise they are different words.
1. Recursively divide W1 into halves, then each half into 2 etc, until we all partitions are singletons (i.e., contain one element).
2. Recursively divide W2 into halves, then each half into 2 etc, until we all partitions are singletons (i.e., contain one element).
3. Merge one singleton partition of W1 with one singleton partition of W2 if they have the same character. Recursively do this across all singleton partitions.
4. Recursively merge the partitions until we have an array that is combined of W1 and W2.
5. If we have matches at every stage, then the two words are considered the same word in the alien language, otherwise they are different words.

Question 13

Using backward substitution, simplify the recurrence relationship of C(n)=3C(n-1)+2, C(1)=2 into a function of n. Which of the following are possible steps and answer to this simplification? Select ONE or MORE answers.
C (n) = 3^n-1C (1) + 6n - 10

C(n), 3 x3^n-1 +3 x 2(n- 2)+2
C (n) = 2 x 3^n-1 + 6n - 10

C (n) = 3ⁿ + 6n - 10
C (n) = 3⁵C (n - 5) +5 x 2

C (n) = 3²C (n -2)+4 x 2 C (n) = 3^n-1
C (n) = 3ⁿ - 1

Attachment:- DAT.rar