Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 2: Q14E (page 85)

You are given an array of nelements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(nlogn) .

Short Answer

Expert verified

All duplicates are removed from the array in time: O(nlogn)

Step by step solution

01

Method-I

We may use pre-processing to eliminate duplicates by sorting the array. Its arrays sort consumes Onlogn time, and then we can verify if the last value is like the present value inside one pass; if it is, we don't display that number; otherwise, we do. We'll be able to get rid of the duplicates this way.

So the total amount of time is nLogn+1=OnLogn

02

Method-II

We need to perform nested loops if we haven't done the pre-processing yet. We execute one loop over the whole array (assuming index i and for each index i we check to see if the identical element is in the remaining set; if so, we do not print the element; otherwise, we do. Without pre-processing, the complexity will be ON2.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Section 2.2 describes a method for solving recurrence relations which is based on analyzing the recursion tree and deriving a formula for the work done at each level. Another (closely related) method is to expand out the recurrence a few times, until a pattern emerges. For instance, let’s start with the familiar T(n)=2T(n/2)+o(n). Think of o(n) as being role="math" localid="1658920245976" <cnfor some constant , so: T(n)<2T(n/2)+cn. By repeatedly applying this rule, we can bound T(n) in terms of T(n/2), then T(n/4), then T(n/8), and so on, at each step getting closer to the value of T(.) we do know, namely .

T(1)=0(1).

T(n)≤2T(n/2)+cn≤2[2Tn/4+cn/2]+cn=4T(n/4)+2cn≤4[2Tn/8+cn/4]+2cn=8T(n/8)+3cn≤8[2Tn/16+cn/8]+3cn=16T(n/16)+4cn

.

.

.

A pattern is emerging... the general term is

T(n)≤2kT(n/2k)+kcn

Plugging in k=log2n, we get T(n)≤nT(1)+cnlog2n=0(nlogn).

(a)Do the same thing for the recurrence T(n)=3T(n/2)+0(n). What is the general kth term in this case? And what value of should be plugged in to get the answer?(b) Now try the recurrence T(n)=T(n-1)+0(1), a case which is not covered by the master theorem. Can you solve this too?

A k−way merge operation. Suppose you have ksorted arrays, each with nelements, and you want to combine them into a single sorted array ofkn elements.

(a)Here’s one strategy: Using the merge procedure from Section 2.3, merge the first two arrays, then merge in the third, then merge in the fourth, and so on. What is the time complexity of this algorithm, in terms of kand n?

(b) Give a more efficient solution to this problem, using divide-and-conquer.

Given a sorted array of distinct integersA[1,...,n] , you want to find out whether there is an indexi for which A[i]=i. Give a divide-and-conquer algorithm that runs in time O(logn).

Thesquare of a matrix A is its product with itself, AA.

(a) Show that five multiplications are sufficient to compute the square of a 2 x 2 matrix.

(b) What is wrong with the following algorithm for computing the square of an n x n matrix?

“Use a divide-and-conquer approach as in Strassen’s algorithm, except that instead of getting 7 subproblems of size n2, we now get 5 subproblems of size n2 thanks to part (a). Using the same analysis as in Strassen’s algorithm, we can conclude that the algorithm runs in time O (nc) .”

(c) In fact, squaring matrices is no easier than matrix multiplication. In this part, you will show that if n x n matrices can be squared in time S(n) = O(nc), then any two n x n matrices can be multiplied in time O(nc) .

  1. Given two n x n matrices A and B, show that the matrix AB + BA can be computed in time 3S(n) + O(n2 ) .
  2. Given two n x n matrices X and Y, define the 2n x 2n matrices A and B,L as follows:
    A=X000andB=0Y00
    What is AB + BA, in terms of X and Y?
  3. Using (i) and (ii), argue that the product XY can be computed in time 3S(2n) + O(n2 ). Conclude that matrix multiplication takes time O(nc ).

The Hadamard matricesH0,H1,H2,… are defined as follows:

  • • H0 is the 1×1matrix[1]
  • For k>0,Hkisthe2k×2k matrix

localid="1658916810283" Hk=[Hk-1|Hk-1Hk-1|-Hk-1]

Show that if υ is a column vector of lengthlocalid="1658916598888" n=2k, then the matrix-vector product localid="1658916618774" Hkvcan be calculated using localid="1658916637767" O(nlogn) operations. Assume that all the numbers involved are small enough that basic arithmetic operations like addition and multiplication take unit time.
See all solutions

Recommended explanations on Computer Science Textbooks

Data Structures

Read Explanation

Computer Organisation and Architecture

Read Explanation

Theory of Computation

Read Explanation

Functional Programming

Read Explanation

Game Design in Computer Science

Read Explanation

Databases

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free