/*! This file is auto-generated */ .wp-block-button__link{color:#fff;background-color:#32373c;border-radius:9999px;box-shadow:none;text-decoration:none;padding:calc(.667em + 2px) calc(1.333em + 2px);font-size:1.125em}.wp-block-file__button{background:#32373c;color:#fff;text-decoration:none} Q4E Suppose you are choosing between... [FREE SOLUTION] | 91影视

91影视

Log out

Learning Materials

Features

Discover

Chapter 2: Q4E (page 83)

Suppose you are choosing between the following three algorithms: 鈥� Algorithm A solves problems by dividing them into five sub-problems of half the size, recursively solving each sub-problem, and then combining the solutions in linear time. 鈥�

Algorithm B solves problems of size n by recursively solving two sub-problems of size n-1and then combining the solutions in constant time. 鈥� Algorithm C solves problems of size n by dividing them into nine sub-problems of size n/3, recursively solving each sub-problem, and then combining the solutions in O(n2)time.

What are the running times of each of these algorithms (in big- O notation), and which would you choose?

Short Answer

Expert verified

Running time for each algorithm are:

  • Tn=Onlg5
  • Tn=O2n

Tn=On2logn

Step by step solution

01

Basic information about each algorithm

Algorithmic A solves issues by breaking these onto five half-size sub-problems and systematically answering each one.

Algorithm B repeatedly tackles two sub-problems in size n to solve these issues of size n .

Algorithm C divides issues of size n over nine sub-problems with size n/3 and solves every sub-problem iteratively.

02

Running time calculation

  1. Algorithm A will also be expressed as
    Tn=5Tn/2+n
    by use of the Master's theorem
    b=5a=2
    Thus, Tn=Onlg5
    1. Algorithm B will be expression as
    2. Tn=2Tn-1+c
      We're having multiple sub issues for every stage, like as 2,3,8,....
      So run time will be of order:

    localid="1659070651841" Tn=O2n

    1. For Algorithm C, calculation is based on question is given as above.
      Tn=9Tn/3+n2
      So,

    b=9a=3log39=2
    Which is equal to power of constant term
    so run time will be: Tn=On2logn

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.

Over 30 million students worldwide already upgrade their learning with 91影视!

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

This problem illustrates how to do the Fourier Transform (FT) in modular arithmetic, for example, modulo .(a) There is a number such that all the powers 蝇,蝇2,...,蝇6 are distinct (modulo ). Find this role="math" localid="1659339882657" 蝇, and show that 蝇+蝇2+...+蝇6=0. (Interestingly, for any prime modulus there is such a number.)

(b) Using the matrix form of the FT, produce the transform of the sequence (0,1,1,1,5,2) modulo 7; that is, multiply this vector by the matrix M6(蝇), for the value of 蝇you found earlier. In the matrix multiplication, all calculations should be performed modulo 7.

(c) Write down the matrix necessary to perform the inverse FT. Show that multiplying by this matrix returns the original sequence. (Again all arithmetic should be performed modulo 7.)

(d) Now show how to multiply the polynomials and using the FT modulo 7.

An array A [1...n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element. The elements of the array are not necessarily from some ordered domain like the integers, a A2 nd so there can be no comparisons of the form 鈥渋s A[i]>A[j]?鈥�. (Think of the array elements as GIF files, say.) However you can answer questions of the form: 鈥渋s ..?鈥� in constant time.

(a) Show how to solve this problem in O(nlog n) time. (Hint: Split the array A into two arrays A1 and of half the size. Does knowing the majority elements of A1 and A2 help you figure out the majority element of A? If so, you can use a divide-and-conquer approach.)

(b) Can you give a linear-time algorithm? (Hint: Here鈥檚 another divide-and-conquer approach:

  • Pair up the elements of A arbitrarily, to get n/2 pairs
  • Look at each pair: if the two elements are different, discard both of them; if they are the same, keep just one of them
    Show that after this procedure there are at most n/2 elements left, and that they have a majority element if A does.)

Show that for any positive integers n and any base b , there must some power of b lying in the range [b,bn].

Practice with the fast Fourier transform.

(a) What is the FFT of (1,0,0,0)? What is the appropriate value of 蝇in this case? And of which sequence is (1,0,0,0)the FFT?

(b)Repeat for (1,0,1,-1).
See all solutions

Recommended explanations on Computer Science Textbooks

Theory of Computation

Read Explanation

Data Representation in Computer Science

Read Explanation

Cybersecurity in Computer Science

Read Explanation

Game Design in Computer Science

Read Explanation

Computer Systems

Read Explanation

Cloud Services

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.