4) Which is a more efficient way to determine the optimal number of multiplications in a matrix-chain multiplication problem: en
umerating all the ways of parenthesizing the product and computing the number of multiplications for each, or running RECURSIVE-MATRIX-CHAIN? Justify your answer
1 answer:
Answer:
Running RECURSIVE-MATRIX-CHAIN is asymptotically more efficient than enumerating all the ways of parenthesizing the product and computing the number of multiplications of each.
the running time complexity of enumerating all the ways of parenthesizing the product is n*P(n) while in case of RECURSIVE-MATRIX-CHAIN, all the internal nodes are run on all the internal nodes of the tree and it will also create overhead.
Explanation:
You might be interested in
Answer:
Check the explanation
Explanation:
//Bugs are highlighted in bold text
class Invoice
Declarations
private num invoiceNumber
private string customer
private num balanceDue
private num tax
public void setInvoiceNUMBER(num number)
Declarations
num LOW_NUM = 1000
num HIGH_NUM = 9999
if number > HIGH_NUM then
invoiceNumber = 0
else
if number < LOW_NUM then
invoiceNumber = 0
else
invoiceNumber = num
endif
return
public void setCustomer(string cust)
customer = cust
return
public void setBalanceDue(num balance)
//Bug balanceDue is Invoice class varible
//but it is assigned to balance .it gives error
balance = balanceDue
setTax()
return
private void setTax()
Declarations
//Bug TAX_RATE is declared as string
//but assigned a double value
string TAX_RATE = 0.07
tax = tax * TAX_RATE
return
public void displayInvoice()
output "Invoice #", invoiceNumber
output "Customer: ", customer
output "Due: ", balanceDue
output "Tax: ", taxDue
//Bug
//Invoice class has no variable called balance .it should be balanceDue
output "Total ", balance + taxDue
return
endClass
start
Declarations
Invoice inv1
Invoice inv2
Invoice inv3
//Warning
//it gives warning object taken but not initilaized
Invoice inv4
inv1.setInvoiceNumber(1244)
inv1.setCustomer("Brown")
inv1.setBalanceDue(1000.00)
inv1.displayInvoice()
inv2.setInvoiceNumber(77777)
inv2.setCustomer("Jenkins")
inv2.setBalanceDue(2000.00)
inv2.displayInvoice()
inv3.setInvoiceNumber(888)
inv3.setCustomer("Russell")
inv3.setBalanceDue(3000.00)
//Bug
//setTax method of Invioce doesnot take any arguments
inv3.setTax(210.00)
inv3.displayInvoice()
stop
//Here is the complete program in c++
//Run the program using Microsoft visual studio 2010 vc++
#include<iostream>
#include<iomanip>
#include<string>
using namespace std;
class Invoice
{
//class varibales
private:
int invoiceNumber;
string customer;
double balanceDue;
double tax;
//class methods
public:
void setCustomer(string cus);
void displayInvoice();
void setBalanceDue(double balance);
void setInvoiceNUMBER(int number);
void setTax();
};
void Invoice::displayInvoice()
{
cout<< setw(10)<<"Invoice #"<<setw(5)<<invoiceNumber<<endl;
cout<<setw(10)<<"Customer: "<<setw(5)<<customer<<endl;
cout<<setw(10)<<"Due: "<<setw(5)<<balanceDue<<endl;
cout<<setw(10)<<"Tax: "<<setw(5)<<tax<<endl;
//Bug
//Invoice class has no variable called balance .it should be balanceDue
cout<< "Total "<< balanceDue + tax<<endl;
}
void Invoice::setCustomer(string cust)
{
customer = cust;
}
void Invoice::setInvoiceNUMBER(int number)
{
const int LOW_NUM = 1000;
const int HIGH_NUM = 9999;
if( number > HIGH_NUM )
invoiceNumber = 0;
else
if (number < LOW_NUM )
invoiceNumber = 0;
else
invoiceNumber = number;
}
void Invoice::setBalanceDue(double balance)
{
balanceDue = balance;
}
void Invoice::setTax()
{
double TAX_RATE = 0.07;
tax = balanceDue * TAX_RATE;
}
int main()
{
Invoice inv1;
Invoice inv2;
Invoice inv3;
inv1.setInvoiceNUMBER(1244);
inv1.setCustomer("Brown");
inv1.setBalanceDue(1000.00);
inv1.setTax();
inv1.displayInvoice();
inv2.setInvoiceNUMBER(77777);
inv2.setCustomer("Jenkins");
inv2.setBalanceDue(2000.00);
inv2.setTax();
inv2.displayInvoice();
inv3.setInvoiceNUMBER(888);
inv3.setCustomer("Russell");
inv3.setBalanceDue(3000.00);
inv3.setTax();
inv3.displayInvoice();
system("pause");
return 0;
}
Kindly check the output image below.
