Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 2: Q1E (page 83)

Question: Use the divide-and-conquer integer multiplication algorithm to multiply the two binary integers 10011011and10111010 and .

Short Answer

Expert verified

Multiplication of 10011011and10111010is: 111000010011110

Step by step solution

01

Introduction

This keep dividing and conquering is different technique tackles an issue by:

1. This keep dividing and conquering is different technique tackles an issue by:

2. Solving these sub-problems in a recursive manner

3. Combining their responses in an appropriate manner.

The main work being composed of three parts: splitting issues into sub-problems, solving sub-problems outright at the very end of the recursion, and gluing together partial answers. The algorithm's basic recursive structure holds them all together and coordinates them.

02

Division of given binary numbers

Divide and conquer multiplication:

Apply and consider X=10011011Y=10111010

P1=multiply(X1,Y1)P2=multiply(Xr,Yr)P3=multiply(X1+Xr,Y1+Yr)X*Y=P1*(2n)+(P3-P2-P1)*(24)+P2

Here, given binary number divided into two ( N / 2 )

X1=1001,Y1=1011,Xr=1011,Yr=1010X1+Xr=1001+1011=10100Y1+Yr=1011+1010=10101X1*Y1=1100011callitisP1

03

Multiplication using Divide-and-Conquer

Find Xr * Yr recursively we get,

Xr * Yr = 1011 * 1010 = 1101110 calling it as P2

Find X1+XrxY1+Yrrecursively we are get,

X1+XrxY1+Yr=110100100

Counting of P3 - P2 - P1

P3 - P2 - P1 = 110100100 - 1101110 - 1100011

=11010011

Finally here we can get last answer:

P1*2n+P3-P2-P1*24+P2=1100011*100000000+11010011*00010000+1101110=110001100000000+110100110000+1101110=011100001001111010011011*10111010=111000010011110

This is the required answer.

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

A binary tree is full if all of its vertices have either zero or two children. Let Bndenote the number of full binary trees with n vertices. (a)By drawing out all full binary trees with 3, 5, or 7 vertices, determine the exact values of B3, B5, and B7. Why have we left out even numbers of vertices, like B4?

(b) For general n, derive a recurrence relation for Bn.

(c) Show by induction that Bnis Ω(2n).

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.

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 ).

Question: On page 66 there is a high-level description of the quicksort algorithm.

(a) Write down the pseudocode for quicksort.

(b) Show that its worst - case running time on an array of size n is Θ(n)2.

(c) Show that its expected running time satisfies the recurrence relation.

T(n)≤O(n)+1n∑i=1n-1(Ti+Tn-i)

Then, show that the solution to this recurrence is O(nlogn).

In this problem we will develop a divide-and-conquer algorithm for the following geometric task.

CLOSEST PAIRInput: A set of points in the plane, {p1=(x1;y1),p2=(x2,y2),...,pn=(xn,yn)}

Output: The closest pair of points: that is, the pair Pi≠Pjfor which the distance between piand pj, that is,

(xi-xi)2+z(yi-yi)2,

is minimized.

For simplicity, assume that n is a power of two, and that all the x-coordinates role="math" localid="1659237354869" xi are distinct, as are the y-coordinates.

Here’s a high-level overview of the algorithm:

.Find a value for which exactly half the points have xi<x, and half have xi>x. On this basis, split the points into two groups, L and R.

• Recursively find the closest pair in L and in R. Say these pairs are pL·qL∈Land pR·qR∈Rwith distances dLand dR respectively. Let d be the smaller of these two distances.

• It remains to be seen whether there is a point in Land a point in R that are less than distance dapart from each other. To this end, discard all points with xi<x-dor xi>x+d and sort the remaining points by y-coordinate.

• Now, go through this sorted list, and for each point, compute its distance to the seven subsequent points in the list. Let pM·qMbe the closest pair found in this way.

• The answer is one of the three pairs role="math" localid="1659237951608" {pL,qL},{pR,qR}{pM,qM}, whichever is closest.

(a) In order to prove the correctness of this algorithm, start by showing the following property: any square of size d×d in the plane contains at most four points of L.

(b) Now show that the algorithm is correct. The only case which needs careful consideration is when the closest pair is split between L and R.

(c) Write down the pseudocode for the algorithm, and show that its running time is given by the recurrence:

T(n)=2T(nl2)+0(nlogn)

Show that the solution to this recurrence is o(nlogzn).

(d) Can you bring the running time down to O(nlogn)?
See all solutions

Recommended explanations on Computer Science Textbooks

Game Design in Computer Science

Read Explanation

Problem Solving Techniques

Read Explanation

Theory of Computation

Read Explanation

Data Structures

Read Explanation

Big Data

Read Explanation

Issues in Computer Science

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