.
 Vyom World.com  . Let's Touch the Sky Together!  
.
. . . . . . .
 Home
VyomWorld.com Home
Free Magazines!
VyomLinks.com Home
JobsAssist.com Home
Vyom Network
Contact Us
 Jobs & Careers
Resume Submitter
Placement Papers
IT Companies Directory
Computer Jobs
Interview Questions
Online Exams
Vyom Career eMag.
 Fun
Screensavers New!
Send FREE SMS!
SMS Jokes
 Source Codes Library
Source Codes Home
ASP Source Codes
C Source Codes
C++ Source Codes
COBOL Source Codes
Java Source Codes
Pascal Source Codes
Submit Source Codes
 GATE
GATE an Overview
GATE Preparation
Study Materal
 GRE
GRE an Overview
GRE Questions
GRE Preparation
GRE Universities
 TOEFL Preparation
TOEFL Resources
 GMAT Preparation
GMAT Resources
 MBA Preparation
MBA Resources
 Networking Concepts
Networking Concepts
 Testing Preparation
Testing Resources
 Webmasters
Free Traffic Builder
Webmaster Articles
Web Hosting
 Tutorials
Hardware Tutorial
1500 Free eBooks New!
 FREE Publications
Vyom Career eMag.
 
.
Get 9,000+ Interview Questions & Answers in an eBook.


  • 9,000+ Interview Questions
  • All Questions Answered
  • 5 FREE Bonuses
  • Free Upgrades

    Get it now!


    Post your Resume to 5800+ Companies

    Reliable Web Hosting

  •  
     
     
    Get 9,000+ Interview Questions with Answers in an eBook


     Home

    Analysis and Design of Algorithms


    Advertisements
    Advertisements

    5.1 Greedy Method

    Greedy method is a method of choosing a subset of the dataset as the solution set that results in some profit. Consider a problem having n inputs, we are required to obtain the solution which is a series of subsets that satisfy some constraints or conditions. Any subset, which satisfies these constraints, is called a feasible solution. It is required to obtain the feasible solution that maximizes or minimizes the objective function. This feasible solution finally obtained is called optimal solution.

    If one can devise an algorithm that works in stages, considering one input at a time and at each stage, a decision is taken on whether the data chosen results with an optimal solution or not. If the inclusion of a particular data results with an optimal solution, then the data is added into the partial solution set. On the other hand, if the inclusion of that data results with infeasible solution then the data is eliminated from the solution set.

    The general algorithm for the greedy method is

    1. Choose an element e belonging to dataset D.
    2. Check whether e can be included into the solution set S if Yes solution set is s ¬ s U e.
    3. Continue until s is filled up or D is exhausted whichever is earlier.





    5.1 Cassette Filling

    Consider n programs that are to be stored on a tape of length L. Each program I is of length li where i lies between 1 and n. All programs can be stored on the tape iff the sum of the lengths of the programs is at most L. It is assumed that, whenever a program is to be retrieved the tape is initially positioned at the start end.

    Let tj be the time required retrieving program ij where programs are stored in the order

    I = i1, i2, i3, ,in.

    The time taken to access a program on the tape is called the mean retrieval time (MRT)

    i.e., tj =S lik k=1,2,,j

    Now the problem is to store the programs on the tape so that MRT is minimized. From the above discussion one can observe that the MRT can be minimized if the programs are stored in an increasing order i.e., l1 £ l2 £ l3, £ ln.

    Hence the ordering defined minimizes the retrieval time. The solution set obtained need not be a subset of data but may be the data set itself in a different sequence.

     

    Illustration

    Assume that 3 sorted files are given. Let the length of files A, B and C be 7, 3 and 5 units respectively. All these three files are to be stored on to a tape S in some sequence that reduces the average retrieval time. The table shows the retrieval time for all possible orders.

    Order of recording Retrieval time MRT
    ABC 7+(7+3)+(7+3+5)=32 32/3
    ACB 7+(7+5)+(7+5+3)=34 34/3
    BAC 3+(3+7)+(3+7+5)=28 28/3
    BCA 3+(3+5)+(3+5+7)=26 26/3
    CAB 5+(5+7)+(5+7+3)=32 32/3
    CBA 5+(5+3)+(5+3+7)=28 28/3

    Study Notes Home | Next Section>>




     

    Discussion Center

    Discuss

    Query

    Feedback/ Suggestion

    Yahoo Groups

    Sirfdosti Groups

    Contact Us


    .

    Recently Updated: New Placement Papers added.
    Vyom Network : Web Hosting | Dedicated Server | Free SMS, GRE, GMAT, MBA | Online Exams | Freshers Jobs | Software Downloads | Programming & Source Codes | GRE Preparation | Jobs, Discussions | Software Listing | Free eBooks | Free eBooks | Free Business Info | Interview Questions | Free Tutorials | International Business Information | IAS Preparation | Jokes, Songs, Fun | Free Classifieds | Free Recipes | FAQs | Free Downloads | Bangalore Info | Tech Solutions | Project Outsourcing, Web Hosting | GATE Preparation | MBA Preparation | SAP Info | Excellent Mobiles | Software Testing | Interview Questions | Freshers Jobs | Server Insiders | File Extension Directory

    Copyright ©2003-2017 Vyom Technosoft Pvt. Ltd., All Rights Reserved. Read our Privacy Policy