Question

Given a collection of n nuts, and a collection of n bolts, each arranged in an increasing order of size, give an O(n) time algorithm to check if there is a nut and a bolt that have the same size. You can assume that the sizes of the nuts and bolts are stored in the arraysNUTS[1..n] and BOLTS[1..n], respectively, where NUTS[1] < ··· < NUTS[n] and BOLTS[1] < ··· < BOLTS[n]. Note that you only need to report whether or not a match exists; you do not need to report all matches.

(When asked to give an algorithm that meets a certain time upper bound, you need to give the algorithm (pseudocode/description) and analyze its running time to show that it meets the required bound)

Answer #1

Following is the pseudocode algorithm:

matching_size(nuts[],bolts[],n) //nuts and bolts are arrays containing size of nuts and bolts in increasing order. n is the size of both

{

i=0,j=0; //we initialize two indexes to 0 to iterate through the array

while(i<n and j<n)

{

if(nuts[i]<bolts[j])

i=i+1;

else if(bolts[i]<nuts[j])

j=j+1;

else //if sizes are equal

return true;

}

return false; //if program reaches this point, no match was found

}

Time complexity analysis:

In the best-case scenario, the first elements of both arrays will be equal and only 1 comparison will take place. So best-case is O(1).

In the worst-case scenario, the arrays will have alternating increasing elements and will take 2n comparisons. So worst-case is O(n).

So, overall time complexity is O(n).

Given a set of n distinct bolts and n
corresponding nuts, (a one-to-one correspondence exists between
bolts and nuts), we want to find the correspondence between them.
We are not allowed to directly compare two bolts or two nuts, but
we can compare a bolt with a nut to see which one is bigger. Design
an algorithm to find the matching pairs of bolts and nuts in time
O(n2) for the worst-case scenario. Your algorithm should
have an expected running...

1. Given an
n-element array A, Algorithm X executes an
O(n)-time computation for each even
number in A and an O(log n)-time computation for
each odd number in A.
What is the best-case running time of Algorithm X?
What is the worst-case running time of Algorithm X?
2. Given an array,
A, of n integers, give an O(n)-time algorithm that finds
the longest subarray of A such that all the numbers in that
subarray are in sorted order. Your algorithm...

Design a recursive divide-and-conquer algorithm A(n) that takes
an integer input n ≥ 0, and returns the total number of 1’s in n’s
binary representation. Note that the input is n, not its binary
representation. For example, A(9) should return 2 as 9’s binary
representation is 1001, while A(7) should return 3 since 7 is 111
in binary. Note that your algorithm should have a running time of
O(log n). Justify your answer. You need to do the following: (1)...

We are given an array A of size n containing n positive and
negative integers (the array is indexed starting from 0).
Our goal is to find two indices i and j such that 0 ≤ i ≤ j ≤ n
and Pk=j k=i A[k] is maximized.
Input sequence: [2, -4, 1, 9, -6, 7, -3]
Output: [1, 9, -6, 7] or i = 2 and j = 5
Input sequence: [1, 2, 3, 4, 5, 6, -3]
Output: [1,...

you are given a list of n bits {x1,x2,...,xn} with each xi
being an element in {0,1}. you have to output either: a) a natural
number k such that xk =1 or b) 0 if all bits are equal to zero. the
only operation you are allowed to access the inputs is a function
I(i,j) defined as:
I(i,j) = { 1 (if some bit in xi, xi+1,...,xj has vaue 1), or
0, (if all bits xi,xi+1,...,xj have value 0}.
the...

You're are working on n different projects, but in m hours you
are going on vacation. Imagine that for each project i, you had a
function fi that told you how happy the people paying for project i
would be if out your m available hours you devoted 0 ≤ x ≤ m to
project i. Imagine further that each such function has maximum
value at most s, corresponding to the project being fully finished
(and thus the clients being...

You are an algorithm designer and you came up with four
different divide-and-conquer algorithms for some problem Q. Those
four algorithms are described below in parts (1), (2), (3), and
(4). You wrote those descriptions a long time ago so now you want
to remind yourself, for each one of them, what was the
corresponding recurrence relation and provide an upper bound on the
running time. So first give the recurrence then solve it using any
method of your choice...

For this lab assignment you will need to write some code and
create some graphs. You may use excel to create your graphs, or
other language of your choice. Your data needs to demonstrate the
experimental running time for Selection Sort (code in book), Merge
Sort (code in book), and the Arrays.sort() method.
Here is a basic outline of how you need to code this
assignment.
1) Create several arrays of size 100, 1000, 10000, 100000,
1000000, … (you need...

For this assignment you need to write a parallel program in C++
using OpenMP for vector addition. Assume A, B, C are three vectors
of equal length. The program will add the corresponding elements of
vectors A and B and will store the sum in the corresponding
elements in vector C (in other words C[i] = A[i] + B[i]). Every
thread should execute approximately equal number of loop
iterations. The only OpenMP directive you are allowed to use
is:
#pragma...

For this assignment, you need to write a parallel program in C++
using OpenMP for vector addition. Assume A, B, C are three vectors
of equal length. The program will add the corresponding elements of
vectors A and B and will store the sum in the corresponding
elements in vector C (in other words C[i] = A[i] + B[i]). Every
thread should execute an approximately equal number of loop
iterations. The only OpenMP directive you are allowed to use
is:...

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 16 minutes ago

asked 32 minutes ago

asked 32 minutes ago

asked 39 minutes ago

asked 45 minutes ago

asked 51 minutes ago

asked 51 minutes ago

asked 52 minutes ago

asked 58 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago