1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
Viktor [21]
3 years ago
8

Greedy Algorithm Design

Computers and Technology
1 answer:
Alik [6]3 years ago
8 0

Answer:

The algorithm is as follows:

1. Start

2. Get the number of items (n)

3. Get the current price of the n items (a1, a2..... an)

4. Get the possible hiked price of the n items (b1, b2..... bn)

5. Calculate the difference between the current and hiked prices for each item i.e. d_i = b_i - a_i

6. Sort the differences in descending order (i.e. from the greatest to the least)

7. Buy items in this order of difference

8. Stop

Explanation:

The algorithm is self-explanatory; however, what it does is that:

It takes a list of the current price of items (say list a)

E.g: a = [100, 150, 160]

Then take a list of the hiked price of the items (say list b)

E.g: b = [110, 180, 165]

Next, it calculates the difference (d) between corresponding prices d_i = b_i - a_i

d = [(110 - 100),(180-150),(165-160)]

d = [10,30,5]

Sort the difference from greatest to lowest (as the difference is sorted, lists a and b are also sorted)

d = [30,10,5]

a = [150, 100, 160]

b = [180, 110, 165]

If there is no hike up to item k, the couple would have saved (i = 1 to d[k-1])

Assume k = 3

The couple would have saved for 2 item

Savings = d[1] + d[2]

Savings = 30 +10

Savings = 40

The saved amount will then be added to the kth item in list a i.e. a[k](in this case k = 3) in order to buy b[k]

Using the assumed value of k

a[k] = a[3]

a[3] = 160

b[3] = 165

Add the saved amount (40) to a[3]

New\ Amount = 40 + 160

New\ Amount = 200

This new amount can then be used to buy b[3] i.e. 165, then they save the change for subsequent items

You might be interested in
A type of touch screen that can be up to four feet by six feet is a(n) _____. plasma screen multitouch interface Electronic Pape
zlopas [31]
<span>a multi touch interface</span><span />
5 0
3 years ago
Read 2 more answers
Your task is to write a C program that measures the latencies of various system calls. In particular, you want to know 1) the co
tensa zangetsu [6.8K]

Answer and Explanation:

#include <stdio.h>

#include<fcntl.h>

#include <sys/time.h>

#include<time.h>

#define MAX 1000

int main()

{

int pid;

int i,fd ;

char c[12];

FILE *fp;

struct timeval start,end;

double time1,time2,time3;

//open file for writing

fp=fopen("output.txt","w");

 

if(!fp)

{

printf("Not able to open the file output.txt\n");

return -1;

}

for(i = 0; i < MAX ; i++)

{

gettimeofday(&start,NULL);

//invoke getpid call

system(pid = getpid());

//printf("%d\n",start.tv_usec);

}

gettimeofday(&end,NULL);

//printf("%d\n",(end.tv_usec - start.tv_usec));

time1 = ((end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec) / 1000000.0)/MAX;

 

//wtite the time taken to execute getpid to

//to get micro second , divide multiply time by 1000000 , to get nano multiply time by 1000000000

printf("getpid(): %.10f %.10f\n",time1*1000000,time1*1000000000);

fprintf(fp,"getpid():%.10f %.10f\n",time1*1000000,time1*1000000000);

//in similar way execute other two commands ,open and read

 

for(i = 0; i < MAX ; i++)

{

gettimeofday(&start,NULL);

//invoke getpid call

system(open("/dev/null", O_RDONLY ));

//printf("%d\n",start.tv_usec);

}

gettimeofday(&end,NULL);

//printf("%d\n",(end.tv_usec - start.tv_usec));

time2 = ((end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec) / 1000000.0)/MAX;

 

//wtite the time taken to execute getpid to

printf("open(): %.10f %.10f\n",time2*1000000,time2*1000000000);

fprintf(fp,"open():%.10f %.10f\n",time2*1000000,time2*1000000000);

//in similar way execute other two commands ,open and read

fd = open("/dev/dev",O_RDONLY );

//printf("fd = %d\n",fd);

for(i = 0; i < MAX ; i++)

{

gettimeofday(&start,NULL);

//invoke getpid call

system( read(fd,c,10));

//printf("%d\n",start.tv_usec);

}

gettimeofday(&end,NULL);

//printf("%d\n",(end.tv_usec - start.tv_usec));

time3 = ((end.tv_sec - start.tv_sec) + (end.tv_usec - start.tv_usec) / 1000000.0)/MAX;

 

//wtite the time taken to execute getpid to

printf("read(): %.10f %.10f\n",time3*1000000,time3*1000000000);

fprintf(fp,"read(): %.10f %.10f\n",time3*1000000,time3*1000000000);

}

----------------------------------------------------------

//output

//I have written output to standard output also , you can remove that

getpid(): 0.1690000000 169.0000000000    

open(): 0.1890000000 189.0000000000    

read(): 3.1300000000 3130.0000000000

------------------------------------------------------

//Makefile content

prob2.o : prob2.c    

         gcc -c  prob2.c                                                                                                                                      

prob2 : prob2.o                                                                                                                                                

       gcc -o prob2 prob2.o                                                                                                                                    

all   :                                                                                                                                                        

       gcc -o prob2 prob2.c                                                                                                                                    

clean:                                                                                                                                                          

       rm -rf prob2.o  

---------------------------------------

use

$make all

then execute as below

$./prob2

3 0
3 years ago
What is one of the differences between Random Access Memory (RAM) and Read Only Memory (ROM)? RAM is where files are stored, and
Dmitry [639]

Answer:

Characteristics of RAM or ROM memory

Explanation:

RAM (Random Access Memory).  

• It is a read (R) and write (W) memory (R/W)

• Types of RAM - SDR SDRAM, RDRAM, DDR SDRAM. The difference is the speed in sending data.

• It is used for the operating system, programs and most of the software.

• Recommendations of at least 8 GB of RAM for PC and   At least 2 GB of RAM for a mobile.

ROM (Read Only Memory)

• Store instructions and data permanently

• it's read only

•  Type of non-volatile memory

• Save data and system information, settings and programs

• Types of ROM - Mask ROM, PROM, EPROM and EEPROM.

  • A PC must have at least 256 GB.

4 0
3 years ago
Read 2 more answers
In this exercise, you will get some practice with the __add__ method by implementing it for a class called ContactBook. This cla
Wittaler [7]

Answer:

class ContactBook():

   def __init__(self):

       self.contacts ={}

   def __repr__(self):

       return str(self.contacts)

   def add_contact(self,name,number):

       self.contacts[name] = number

   def __add__(self, other):

       new_contact = ContactBook()

       other_contact = other.contacts.keys()

       for name,num in self.contacts.items():

           if name in other_contact:

               new_contact.add_contact(name,num or other_contact[name])

           else:

               new_contact.add_contact(name,num)

       for name,num in other.contacts.items():

           if name not in self.contacts:

               new_contact.add_contact(name, num)

       return new_contact-

cb1 = ContactBook()

cb2 = ContactBook()

cb1.add_contact('Jonathan','444-555-6666')

cb1.add_contact('Puneet','333-555-7777')

cb2.add_contact('Jonathan','222-555-8888')

cb2.add_contact('Lisa','111-555-9999')

print(cb1)

print(cb2)

cb3 = cb1+cb2

print(cb3)

Explanation:

The ContactBook class holds the contact details of an instance of the class. The class has three magic methods the '__repr__', '__init__', and the '__add__' which is the focus of the code. The add magic method in the class adds the contact book (dictionary) of two added object instance and returns a new class with the contact details of both operand instances which is denoted as self and other.

8 0
3 years ago
What are the design concepts and assumptions behind a class, an object and the relationship between them? What are the roles met
Triss [41]

Answer:

Object-oriented programming (OOP) is a procedural language and based on classes associated with an object. Without classes and object relationship OOP is not possible. According to program's design concept classes provide abstraction and encapsulation with the help of object. Object have states and behaviors like cat has states like name, color and  cat has also behaviors like  wagging the tail, eating, jumping etc. A class forms template or blueprints for these states and behaviors because different cats have different behaviors and states.

Methods provide a way for encapsulation and accessing private class members with public methods and static fields are sometimes best alternative for global variable. We can use static field when it same for all and shared by all objects of that class and it can save memory because we do not have to initialize it for each object

8 0
3 years ago
Other questions:
  • In the two-level directory, if a user refers to a particular file then__________________ Select one: a. only his/her own UFD (us
    7·1 answer
  • The ________ of the operating system enables users to communicate with the computer system. modem window network adapter card us
    14·1 answer
  • End user needs assessment is a formal procedure to analyze a user's computer needs; it involves a specific set of steps that are
    8·1 answer
  • What does the history feature in a web browser do
    10·1 answer
  • What can a scientist do if he repeats and experiment and gets diffrent results?
    5·1 answer
  • Which of the following is false about arrays? Group of answer choices
    15·1 answer
  • Your dad just gave you his old computer running Windows 7. You want to see how many volumes are contained within it. Which tool
    10·1 answer
  • Which of the following is not a data visualization technique?
    6·1 answer
  • Explain different types of networking-based attacks
    5·1 answer
  • Why can it be helpful to perform mathematical calculations using programming? Choose the best answer.
    11·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!