Write an algorithm for combining two skip lists in O(a + b) time, where a is...

Write an algorithm for combining two skip lists in O(a + b) time, where a is the number of keys in the first list, and b is the number of keys in the second list.

Solutions

Expert Solution

Solution:

Let the two lists to be combined be skip_list1[a],skip_list2[b].

The number of elements are a and b respectively in each list.

The algorithm that combines the two lists is as shown below.

The list 'res' has the combined elements from the lists skip_list1 and skip_list2.

Algorithm:

1. Start
2. Declare 'res' list of size a+b;
3. Declare j <- 0
4. for i = 0 to a
   BEGIN
       res[j] <- skip_list1[i]
       j <- j+1
   END
5. for i = 0 to b
   BEGIN
       res[j] <- skip_list2[i]
       j <- j+1
   END

6. Stop

venereology answered 4 months ago

Next > < Previous

Related Solutions

Write an algorithm to check equality of two link lists.(java)

How to write Prim's Algorithm with min-Heap and adjacency Lists?

(15 pts) Describe an O(n)-time algorithm that partitions a doubly linked list L into two doubly...

(15 pts) Describe an O(n)-time algorithm that partitions a doubly linked list L into two doubly linked lists L1 and L2, where L1 contains the odd-number-th elements in L and L2 contains the even-number-th elements in L. Elements in both L1 and L2 should appear in the same order as they appear in L. For example, if L contains the numbers 4, 7, 9, 1, and -3, in that order, then the output L1 should contain 4, 9, and -3,...

Pseudocode and algorithm of merging k sorted list with running time O(Nlogk).

a) Write Quick Sort and its function algorithm b) Derive the computation time for each statement...

a) Write Quick Sort and its function algorithm b) Derive the computation time for each statement in the algorithm. (You must explain your reason for each statement about how you get the answer of each computation time in at one or two sentences each.)

Given two lists, write python code to print “True” if the two lists have at least...

Given two lists, write python code to print “True” if the two lists have at least one common element. For example, x = [1,2,3], y=[3,4,5], then the program should print “True” since there is a common element 3.

Write a pseudocode function that interchanges two adjacent items of: (a) singly linked lists (b) doubly...

Write a pseudocode function that interchanges two adjacent items of: (a) singly linked lists (b) doubly linked lists if you can make it clean and short that be nice

Describe an O(n)-time algorithm that checks if brackets in a given arithmetic expression is properly placed,...

Describe an O(n)-time algorithm that checks if brackets in a given arithmetic expression is properly placed, i.e., all left brackets are matched with their right counterparts and there are no unmatched brackets between any pair of matched brackets. Note that there are generally more than one types of brackets and only those of the same type can match against each other. For simplicity, you can assume that all operands are represented as ‘a’ and addition, +, is the only available...

Suppose that we performed the algorithm SELECT whose running time is O(n) on 133 elements, and...

Suppose that we performed the algorithm SELECT whose running time is O(n) on 133 elements, and found the median of medians x by making groups of 5 elements. What is the maximum number of elements which are guaranteed to be greater than equals to x (without counting x, itself)?

Describe an optimal algorithm for finding the integers common to two lists of n integers each....

Describe an optimal algorithm for finding the integers common to two lists of n integers each. Evaluate how long each step in your algorithm takes using Θ-notation.

Subjects